# Surjections (for different functions)

Watch
Announcements

Page 1 of 1

Go to first unread

Skip to page:

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:

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..):

Is this correct?

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

reply

Report

#2

(Original post by

So, let's assume we had: , ( ).

Well, in this case: To show the function is surjective, we have to simply show for every , there exists an such that g(x) = y. Taking x = 3 - y, we have g(x) = g(3-y) = 3 - (3 - y) = y. Hence, it is surjective.

**Chittesh14**)So, let's assume we had: , ( ).

Well, in this case: To show the function is surjective, we have to simply show for every , there exists an such that g(x) = y. Taking x = 3 - y, we have g(x) = g(3-y) = 3 - (3 - y) = y. Hence, it is surjective.

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

reply

(Original post by

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.

**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.

Yes, I understand that part, thank you.

0

reply

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?:

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

Report

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

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

(Original post by

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.

**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.

Yes, sorry, I think I got mixed up with some other question, this one doesn't alternate odd/even. Thank you

0

reply

Report

#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

(Original post by

Try and find a small value of Z(n) that produces a cycle. This shows the function isn't injective or surjective.

**B_9710**)Try and find a small value of Z(n) that produces a cycle. This shows the function isn't injective or surjective.

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top