Year 12s: what will be the first way you research your future options? >>

Surjections (for different functions)

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.

Screen Shot 2019-04-12 at 16.41.09.png

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?

(edited 5 years ago)

Reply 1

RDKGames

Study Forum Helper

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.

Reply 2

Chittesh14

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.

Reply 3

Chittesh14

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?

(edited 5 years ago)

Reply 4

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.

Reply 5

Chittesh14

Original post by DFranklin

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