Surjections (for different functions)

Watch
Chittesh14
Badges: 19
Rep:
?
#1
Report Thread starter 11 months ago
#1
Hello, I was just wondering on comparing methods of checking the surjectivity of a function.

If a function f : X → Y is surjective, then for all y in Y, there exists an x in X such that f(x) = y.

So, this is a simple function, in general: I usually let f(x) = y and make x the subject, then check if for all y in (the codomain), does this formula give a corresponding value of x such that x is in the (domain). If it does, then for every y in Y, there is a corresponding x in X such that f(x) = y.

But, in the case of this other function below (a recursive function), I cannot use this.

Name:  Screen Shot 2019-04-12 at 16.41.09.png
Views: 19
Size:  53.5 KB

Firstly, the recursive formula has two parts, one for if z(n) is even and one for if it is odd. I can see the formula for if z(n) is odd, gives an even output, and the formula for if z(n) is even gives an odd output. So the function is constantly giving even, odd outputs one after the other.

So I cannot use my other approach because e.g. if I'm showing that if y (output) is even, there always exist an n such 1/2((z(n) + 3). But, this is if z(n) is odd, so I have to show that there exists a corresponding z(k) such that z(k) + 5 = z(n) etc... and it goes on indefinitely.

Hence, in general: Can I say for recursive sequences (which are defined in two or more ways like one for even outputs, one for odd outputs etc..): Best approach to show it is surjective is simply to list the elements of the sequence. If it ever repeats an input before all outputs cover the codomain, then the function is not surjective i.e. that cycle of output will now repeat indefinitely once an output occurs twice in the function. If an output repeats itself at e.g. n = N, where for all n <= N, f has outputs which cover the entire codomain, then though the sequence repeats itself, the range = codomain, so it is still surjective.

Is this correct?
Last edited by Chittesh14; 11 months ago
0
reply
RDKGames
Badges: 20
Rep:
?
#2
Report 11 months ago
#2
(Original post by Chittesh14)
So, let's assume we had: f : \mathbb{Z} \rightarrow \mathbb{Z}, g(x) = 3 − x(  x \in\mathbb{Z} ).

Well, in this case: To show the function is surjective, we have to simply show for every y \in \mathbb{Z}, there exists an x \in\mathbb{Z} such that g(x) = y. Taking x = 3 - y, we have g(x) = g(3-y) = 3 - (3 - y) = y. Hence, it is surjective.
Don't have time to read and answer the whole post, but this bit is obviously not true.

I think you mean to define f : \mathbb{Z} \to \mathbb{Z}, \quad f(x) = 3x and hence talk about f ... not g.

So this function is not surjective because there exists many elements in \mathbb{Z} for which we do not have a corresponding x \in \mathbb{Z}.

I.e. if I say that y = f(x) = 3 then that's fine, x = 1 \in \mathbb{Z}, but if I say that y = 4 then x = \dfrac{4}{3} \not\in \mathbb{Z}.



However, if you instead define f : \mathbb{Z} \to 3\mathbb{Z}, \quad f(x) = 3x then this is surjective.
0
reply
Chittesh14
Badges: 19
Rep:
?
#3
Report Thread starter 11 months ago
#3
(Original post by RDKGames)
Don't have time to read and answer the whole post, but this bit is obviously not true.

I think you mean to define f : \mathbb{Z} \to \mathbb{Z}, \quad f(x) = 3x and hence talk about f ... not g.

So this function is not surjective because there exists many elements in \mathbb{Z} for which we do not have a corresponding x \in \mathbb{Z}.

I.e. if I say that y = f(x) = 3 then that's fine, x = 1 \in \mathbb{Z}, but if I say that y = 4 then x = \dfrac{4}{3} \not\in \mathbb{Z}.



However, if you instead define f : \mathbb{Z} \to 3\mathbb{Z}, \quad f(x) = 3x then this is surjective.
Thank you, sorry error must've came after last edit. I was meant to write f(x) = 3 - x.
Yes, I understand that part, thank you.
0
reply
Chittesh14
Badges: 19
Rep:
?
#4
Report Thread starter 11 months ago
#4
Can someone help on the recursive part please, if it is the correct way to think ? Thank you

Alternatively, can someone answer this question please?:

For recursive functions, to check for surjectivity: is it better to list out the outputs of the functions and see if the set equals to the codomain, rather than trying to rearrange formulae - since this often won't help?
Last edited by Chittesh14; 11 months ago
0
reply
DFranklin
Badges: 18
Rep:
?
#5
Report 11 months ago
#5
For recursive functions there's no general method that will always work.

That said, if you find there's a repeating cycle, obviously that limits the possible outputs and therefore probably rules out surjectivity.

You might also want to calculate the first few values of your function; I don't think you're right in saying it alternates odd/even.
0
reply
Chittesh14
Badges: 19
Rep:
?
#6
Report Thread starter 11 months ago
#6
(Original post by DFranklin)
For recursive functions there's no general method that will always work.

That said, if you find there's a repeating cycle, obviously that limits the possible outputs and therefore probably rules out surjectivity.

You might also want to calculate the first few values of your function; I don't think you're right in saying it alternates odd/even.
Thank you, I appreciate your reply. Yes, I thought that I couldn't use the method I normally use for functions, so I had to list them out and try to find a pattern.
Yes, sorry, I think I got mixed up with some other question, this one doesn't alternate odd/even. Thank you
0
reply
B_9710
Badges: 17
Rep:
?
#7
Report 11 months ago
#7
Try and find a small value of Z(n) that produces a cycle. This shows the function isn't injective or surjective.
0
reply
Chittesh14
Badges: 19
Rep:
?
#8
Report Thread starter 11 months ago
#8
(Original post by B_9710)
Try and find a small value of Z(n) that produces a cycle. This shows the function isn't injective or surjective.
Yes, got it, thanks
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Are you worried that a cap in student numbers would affect your place at uni?

Yes (196)
59.94%
No (72)
22.02%
Not sure (59)
18.04%

Watched Threads

View All