Discrete maths questions

1. Suppose a function h: R → R satisfies the condition
h(x)h(y) = h(x + y) ∀x, y ∈ R.
(a) Show that h is not surjective.
(b) Show that h is injective if and only if (iff) h(0) = 1 and h(x) ̸= 1 for all x ̸= 0.
2. Find a number a ∈ R, a set A ⊆ R with |A| = 5, and a function f : A → A such that
a − x ∈ A ∀ x ∈ A and
f(x) + f(a − x) = x ∀ x ∈ A.
3. Prove that there is no surjective function f : N → 2^N (powerset of N), where N is the set of natural numbers.
Your argument should be “from first principles”, i.e., it should rely on the definitions only
Help anyone?

(edited 10 months ago)

Reply 1

mqb2766

21

Any thoughts? So starting with the first one, what is surjective, have you plugged any "values" in for x and y?

Reply 2

Snigdha02

OP

13

Original post by mqb2766

Any thoughts? So starting with the first one, what is surjective, have you plugged any "values" in for x and y?

Here's what I've got

1.

I know for a function to be subjective every element in the codomain must have a pre-image under the function. Hence to prove a function is not subjective I just need to find an element or a set of elements that have no values in the domain map to them. However, since it's just an arbitrary funciton I'm stuck as to how to form a proof or even come up with a counterexample.

2.

I was thinking if a could be 6 and the set A = {1,2,3,4,5} so that the first condition would be satisfied but i cannot for the life of me figure out a function that would satisfy the other condition of f(x) + f(a-x) = x

3.

I can see how there is no function that can map N to the powerset of N because then it would be a one to many relationship meaning that it's not a function. However, how do I go about proving this? + where does the surjectivity come into this.

Reply 3

mqb2766

21

Original post by Snigdha02

Here's what I've got

1.

I know for a function to be subjective every element in the codomain must have a pre-image under the function. Hence to prove a function is not subjective I just need to find an element or a set of elements that have no values in the domain map to them. However, since it's just an arbitrary funciton I'm stuck as to how to form a proof or even come up with a counterexample.

2.

I was thinking if a could be 6 and the set A = {1,2,3,4,5} so that the first condition would be satisfied but i cannot for the life of me figure out a function that would satisfy the other condition of f(x) + f(a-x) = x

3.

I can see how there is no function that can map N to the powerset of N because then it would be a one to many relationship meaning that it's not a function. However, how do I go about proving this? + where does the surjectivity come into this.

With a definition like this, can you show something by choosing values/... for x and y? Theres a bit about this/functional equations at
https://www.drfrostmaths.com/uploads/users/1/r165/RZC-Chp7-FunctionalEquations.pptx
(for instance). Here, the left hand side is the product of h(x) and h(y) so what might that signify in terms of the function h(x+y) if you choose x and/or y as ...

Reply 4

DFranklin

18

Original post by mqb2766

With a definition like this, can you show something by choosing values/... for x and y? Theres a bit about this/functional equations at
https://www.drfrostmaths.com/uploads/users/1/r165/RZC-Chp7-FunctionalEquations.pptx
(for instance). Here, the left hand side is the product of h(x) and h(y) so what might that signify in terms of the function h(x+y) if you choose x and/or y as ...

I don't like that the Dr Frost presentation seems to assume f is differentiable - there are everywhere discontinuous solutions to many functional equations. (If you assume the axiom of choice, at any rate).

The advice about choosing suitable values for x and y still works, of course.

Reply 5

mqb2766

21

Original post by DFranklin

I don't like that the Dr Frost presentation seems to assume f is differentiable - there are everywhere discontinuous solutions to many functional equations. (If you assume the axiom of choice, at any rate).

The advice about choosing suitable values for x and y still works, of course.

Agreed, it was just something that came to mind that had several examples of choosing x and y, to give an idea about how to go. The rest wasnt really applicable. The drfrost stuff is aimed ~y12/13 where its pretty much just assumed things are continuous/differentiable.

(edited 10 months ago)

Reply 6

Snigdha02

OP

13

Original post by mqb2766

With a definition like this, can you show something by choosing values/... for x and y? Theres a bit about this/functional equations at
https://www.drfrostmaths.com/uploads/users/1/r165/RZC-Chp7-FunctionalEquations.pptx
(for instance). Here, the left hand side is the product of h(x) and h(y) so what might that signify in terms of the function h(x+y) if you choose x and/or y as ...

Thank you for the resource, it's really helpful!
So I took x to be 0 which would make h(y) = 0 for all values of y (the same applies vice versa)
Hence it's not surjective for all values of x and y in the reals as when x \ y are 0 there are values in the codomain (every number but 0) which do not map to anything in the domain.
I don't know if that makes sense?

(edited 10 months ago)

Reply 7

DFranklin

18

Original post by Snigdha02

Thank you for the resource, it's really helpful!
So I took x to be 0 which would make h(y) = 0 for all values of y (the same applies vice versa)
Hence it's not surjective because there are values in the codomain (every number but 0) which do not map to anything in the domain.
However, this wouldn't consider the cases where x or y are not 0 right?

Post exactly what your argument is. (From what you've said, it's pretty certain that it's wrong, but hard to say exactly what the problem is without seeing the actual mathematics you're claiming).

Reply 8

mqb2766

21

Original post by Snigdha02

Thank you for the resource, it's really helpful!
So I took x to be 0 which would make h(y) = 0 for all values of y (the same applies vice versa)
Hence it's not surjective because there are values in the codomain (every number but 0) which do not map to anything in the domain.
However, this wouldn't consider the cases where x or y are not 0 right?

Not sure about that. The trivial function h(x)=0 obviously satisfies the property, but it doesnt show that the range is such for all possible functions. If youre looking for intuition, you should be able to easily spot an elementary function which satsifies the property (so along the lines of frost) and get the range of that, but as dfranklin notes, its not necessarily the only function and it would make extra assumptions which are not given. So which elementary function, when you add terms in the argument, so x+y, corresponds to the product of the functions and what would its range be?

Then if youve an idea of what you want to prove can you choose x and y (hint is to make use of the product of the functions on the left hand side) so you can say something about the range (of the function on the right hand side).

The proof is pretty much a one liner with the right argument, so dont overcomplicate it.

(edited 10 months ago)

Discrete maths questions

Quick Reply

Related discussions

Articles for you