# Surjections (for different functions)

Watch
Announcements
#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. 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
11 months ago
#2
Don't have time to read and answer the whole post, but this bit is obviously not true.

I think you mean to define and hence talk about ... not .

So this function is not surjective because there exists many elements in for which we do not have a corresponding .

I.e. if I say that then that's fine, , but if I say that then .

However, if you instead define then this is surjective.
0
#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 and hence talk about ... not .

So this function is not surjective because there exists many elements in for which we do not have a corresponding .

I.e. if I say that then that's fine, , but if I say that then .

However, if you instead define 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
#4
Can someone help on the recursive part please, if it is the correct way to think ? Thank you

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
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
#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
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
#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
X

new posts Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

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

### Poll

Join the discussion

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