Injective and surjective functions

[Ciaran]

Hello,

I've been reading about injectivity from Z to N and surjectivity from N to Z and was wondering whether there was some kind of algorithm that could generate these specific types of functions?

 

[I like Serena]

Hello,

I've been reading about injectivity from Z to N and surjectivity from N to Z and was wondering whether there was some kind of algorithm that could generate these specific types of functions?

Sure.

How about $\mathbb Z \to \mathbb N$ given by $n \mapsto \begin{cases}
-2n-1 & \text{if $n < 0$} \\
2n & \text{if $n \ge 0$}
\end{cases}$
Is it injective?
How about surjective?

 

[Ciaran]

Hello!

Thanks for the reply- the function is injective but not surjective. What about surjective from N to Z and is there some algorithm for generating a function satisfying such conditions?

 

[I like Serena]

Hello!

Thanks for the reply- the function is injective but not surjective. What about surjective from N to Z and is there some algorithm for generating a function satisfying such conditions?

Yes, it is injective... but isn't it also surjective? Doesn't every element in $\mathbb N$ have an original in $\mathbb Z$?

 

[Ciaran]

Oh I see, I was asking for 2 separate functions- I was asked by my instructor to find a solely injective function from Z to N and a solely surjective function from N to Z. I was struggling so wondered if there was some way of generating one such that I didn't just have to think of a function then see if it fits either category?

 

[I like Serena]

Oh I see, I was asking for 2 separate functions- I was asked by my instructor to find a solely injective function from Z to N and a solely surjective function from N to Z. I was struggling so wondered if there was some way of generating one such that I didn't just have to think of a function then see if it fits either category?

Ah. I suspect the intention is to make you familiar with what injectivity and surjectivity actually mean.
When you grasp the concept, there should be no need for any generating algorithm.
I suggest to draw what it means and then come up with a matching function.
Or otherwise try a couple of functions, see what they do, categorize them, and think up what you need to cover any missing category.

 

[Ciaran]

It's the conditions that are proving to be tricky to me- for the surjective function, does it mean my function can only generate integer values ?

 

[Ciaran]

I'm pretty sure g(x)= x! and f(x)=x^2 are injective and surjective, respectively

 

[I like Serena]

It's the conditions that are proving to be tricky to me- for the surjective function, does it mean my function can only generate integer values ?

Not precisely.
The fact that we're limiting ourselves to functions from Z to N, respectively N to Z, implies that the function can only generate integer values.
As yet that is unrelated to whether it is surjective or not.

I'm pretty sure g(x)= x! and f(x)=x^2 are injective and surjective, respectively

Sorry, but no.
For starters, I assume you are talking about functions from Z to N.
If so, then g is then undefined for negative values, meaning it is not a function from Z to N (depending on the definition of function you're using).

Another problem with g is the g(x)=1 has 2 originals, and is therefore not injective (see below).

And the problem with f is that f(x)=3 has no originals, and is therefore not surjective.

To be clear, injective means that every element in the codomain has at most 1 original.
And surjective means that every element in the codomain has at least 1 original.

 

[Ciaran]

Ahhh, what about f(x) = x/2 if x is even, (1-x)/2 if x is odd. And g(x)=2x+1 for positive x, -2x for negative x?

 

[I like Serena]

Ahhh, what about f(x) = x/2 if x is even, (1-x)/2 if x is odd. And g(x)=2x+1 for positive x, -2x for negative x?

Are we talking about functions from Z to N?
Because if so, then f is not a function, since an even negative x is not mapped to N.

As for g, did you mean it to be injective or surjective?
Or put otherwise, what do you think about it being either injective or surjective?

 

[Ciaran]

My apologies, I have only now just noticed you replied! f(x) was meant to be surjective from N to Z and g(x) was meant to be injective from Z to N

 

[I like Serena]

Ahhh, what about f(x) = x/2 if x is even, (1-x)/2 if x is odd. And g(x)=2x+1 for positive x, -2x for negative x?

My apologies, I have only now just noticed you replied! f(x) was meant to be surjective from N to Z and g(x) was meant to be injective from Z to N

What is N exactly? Does it include 0 or not?

Assuming that N is { 1, 2, 3, ... }, f is indeed surjective. Is f also injective?

As for g, what is the image of 0? You didn't specify.
It has consequences for whether g is injective or not.