Proving a function is surjective. f(n) = n/2 for even n, (n+1)/2 for odd n, n an integer

[blamocur]

I'm not as experienced at writing proofs as you. It seems it would be enough since the domain and codomain are both [imath]\mathbb{Z}[/imath]?

What I meant is that just for even [imath]n[/imath]'s the image of [imath]f[/imath] is all of [imath]\mathbb Z[/imath] (i.e. the image is the same as codomain), which makes [imath]f[/imath] surjective before we even consider its values for odd [imath]n[/imath]'s.

 

[Aion]

What I meant is that just for even [imath]n[/imath]'s the image of [imath]f[/imath] is all of [imath]\mathbb Z[/imath] (i.e. the image is the same as codomain), which makes [imath]f[/imath] surjective before we even consider its values for odd [imath]n[/imath]'s.

In other words, the range of the function is equal to the codomain. Yes, I think I understand this. I have a book at home that presents this as a theorem, although I haven't read that far yet.

 

[blamocur]

I have a book at home that presents this as a theorem,

I thought of this as a definition of surjectivity. Which definition does your book use?

 

[Aion]

I thought of this as a definition of surjectivity. Which definition does your book use?

The book I'm currently reading gives the following definition.

A function is surjective (a surjection or onto) if every element of the codomain is the output for at most one element from the domain.

 

[Aion]

[imath]A[/imath]The book I'm currently reading gives the following definition.

A function is surjective (a surjection or onto) if every element of the codomain is the output for at most one element from the domain.

The other book I'm referring to is more formal.

[imath]F[/imath] is a relation from [imath]A[/imath] to [imath]B[/imath]. Then [imath]F[/imath] is called a function from [imath]A[/imath] to [imath]B[/imath] if for every [imath]a\in A[/imath] there is exactly one [imath]b \in B[/imath] such that [imath](a,b)\in F.[/imath] In other words

[math]\forall a \in A \exist !b\in B((a,b)\in F)[/math]
Suppose [imath]f:A\rightarrow B[/imath]. We say that [imath]f[/imath] is onto if

[math]\forall b\in B \exists a\in A (f(a)=b)[/math]
The range of [imath]f[/imath] is the set

[math]Ran(f)=\lbrace b\in B:\exist a\in A (a,b)\in f\rbrace[/math]
We can relate the definition of onto to the definition of range.

[math]\begin{aligned} f \,\text{is onto iff} \quad & \forall b\in B \exist a\in A (f(a)=b) \end{aligned}[/math][math]\begin{aligned} f \,\text{is onto iff} \quad & \forall b\in B \exist a\in A ((a,b)\in f) \end{aligned}[/math][math]\begin{aligned} f \,\text{is onto iff} \quad & \forall b\in B (b\in Ran(f))\end{aligned}[/math][math]B \subseteq Ran(f)[/math]
Suppose [imath]f[/imath] is onto. By equivalence just derived we have [imath]B\subseteq Ran(f)[/imath], and by the definition of range we have [imath]Ran(f) \subseteq B[/imath]. Thus it follows that [imath]Ran(f)=B[/imath].

 

[Aion]

The book I'm currently reading gives the following definition.

A function is surjective (a surjection or onto) if every element of the codomain is the output for at most one element from the domain.

Whops, I accidentally wrote that incorrectly without thinking. The definition given is:

A function is surjective if every element of the codomain is the output for at least one element of the domain.

By this definition it is quite obvious that the range must equal the codomain, however, the author never mentions this fact.

 

[blamocur]

Whops, I accidentally wrote that incorrectly without thinking. The definition given is:

A function is surjective if every element of the codomain is the output for at least one element of the domain.

By this definition it is quite obvious that the range must equal the codomain, however, the author never mentions this fact.

Sounds like you got it figured out by now. A minor note: this Wikipedia article says that term range is more ambiguous than image.

 

[Steven G]

Isn't this enough for surjectivity?

No, in theory if n is odd you can get non-integers.

 

[Steven G]

The book I'm currently reading gives the following definition.

A function is surjective (a surjection or onto) if every element of the codomain is the output for at most one element from the domain.

Why at most. I'd like to see an image of that definition. I suspect that it says at least.
Consider the following mapping/function.
Suppose f: Z-> {7,8} where if n is even, f(n)=8 and if f is odd, f(n)=7.
This function is surjective because you hit every element in {7,8}. That is, for each element in y in {7,8} there is an (at least!) element z in Z such that f(z) = y.
What you described is a function which is both 1-1 and onto!

Edit: I'll leave this post but I now see that you updated your definition of surjective.

 

[Steven G]

Thank you, Steven, that was an oversight on my part.

Suppose [imath]n[/imath] is even. By definition, there exists some [imath]k\in\mathbb{Z }[/imath] such that [imath]n=2k[/imath]. Therefore, [imath]f(n)=k[/imath] for some integer [imath]k[/imath]. Hence, [imath]f(n)[/imath] will generate all integers [imath]k [/imath] when [imath]n[/imath] is even.

Now suppose [imath]n[/imath] is odd. By definition, there exists some [imath]m\in\mathbb{Z }[/imath] such that [imath]n=2m+1[/imath]. Thus, [imath]f(n)=m+1[/imath]. Since the integers are closed under addition, [imath]f(n)[/imath] will generate a subset of the integers when [imath]n[/imath] is odd.

In either case [imath]f(n)[/imath] will generate the union of [imath]\mathbb{Z }[/imath] with a subset of the integers. But the union of [imath]\mathbb{Z }[/imath] with a subset of [imath]\mathbb{Z }[/imath] is equal to [imath]\mathbb{Z }[/imath]. Therefore [imath]f(\mathbb{Z })=\mathbb{Z }[/imath].

Looks fine to me.
disclaimer: I have a huge headache so don't trust my opinion at this time.

 

[blamocur]

No, in theory if n is odd you can get non-integers.

[imath]f(n)[/imath] is defined differently for odd [imath]n[/imath]. But the image of even [imath]n[/imath]'s alone covers all of [imath]\mathbb Z[/imath], which by itself makes [imath]f[/imath] surjective.

 

[Steven G]

[imath]f(n)[/imath] is defined differently for odd [imath]n[/imath]. But the image of even [imath]n[/imath]'s alone covers all of [imath]\mathbb Z[/imath], which by itself makes [imath]f[/imath] surjective.

As always, you are correct as f maps from Z to Z.
To OP: Since the range is Z and we already showed that if n is even we cover all of Z then in fact, as blamocur pointed out, the proof is done.