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

[Aion]

Problem.

Suppose [imath]f:\mathbb{Z}\rightarrow\mathbb{Z}[/imath] given by

[math]f(n)=\begin{cases} \frac{n}{2}&\text{if}~n~\text{is even}\\ \frac{n+1}{2}&\text{if}~n~\text{is odd}\end{cases}[/math]
Determine if the function is injective or surjective.

My attempt: By evaluating the function we see that each output repeats twice. Hence to show that the function is not injective is simple, since [imath]f(0)=0[/imath] and [imath]f(-1)=0[/imath] but [imath]0\neq-1[/imath]. However, I find it difficult to prove that the function is surjective. The goal is to show that [imath]f(\mathbb{Z})=\mathbb{Z}[/imath].

My first thought was to suppose we partitioned [imath]\mathbb{Z}=\mathbb{Z_1}\cup\mathbb{Z_2}[/imath]. Where [imath]\mathbb{Z_1}[/imath] is the odd integers and [imath]\mathbb{Z_2}[/imath] the even integers. And so [imath]\mathbb{Z_1}=2t+1[/imath] and [imath]\mathbb{Z_2}=2t[/imath] for some integer [imath]t[/imath]. Then for each case, we have

[math]f(\mathbb{Z_1})=f(2t+1)=t+1[/math] And
[math]f(\mathbb{Z_2})=f(2t)=t[/math]
Now if [imath]t[/imath] is even, then [imath]t+1[/imath] is odd. And if [imath]t[/imath] is odd, then [imath]t+1[/imath] is even. Then clearly as [imath]t[/imath] varies over all integers, so will the [imath]f(n)[/imath] vary over all integers as well. Hence it must be true that [imath]f(\mathbb{Z})=\mathbb{Z}[/imath].

I know this is not a correct proof, but it was my attempt anyway.

 

[lev888]

Problem.

Suppose [imath]f:\mathbb{Z}\rightarrow\mathbb{Z}[/imath] given by

[math]f(n)=\begin{cases} \frac{n}{2}&\text{if}~n~\text{is even}\\ \frac{n+1}{2}&\text{if}~n~\text{is odd}\end{cases}[/math]
Determine if the function is injective or surjective.

My attempt: By evaluating the function we see that each output repeats twice. Hence to show that the function is not injective is simple, since [imath]f(0)=0[/imath] and [imath]f(-1)=0[/imath] but [imath]0\neq-1[/imath]. However, I find it difficult to prove that the function is surjective. The goal is to show that [imath]f(\mathbb{Z})=\mathbb{Z}[/imath].

My first thought was to suppose we partitioned [imath]\mathbb{Z}=\mathbb{Z_1}\cup\mathbb{Z_2}[/imath]. Where [imath]\mathbb{Z_1}[/imath] is the odd integers and [imath]\mathbb{Z_2}[/imath] the even integers. And so [imath]\mathbb{Z_1}=2t+1[/imath] and [imath]\mathbb{Z_2}=2t[/imath] for some integer [imath]t[/imath]. Then for each case, we have

[math]f(\mathbb{Z_1})=f(2t+1)=t+1[/math] And
[math]f(\mathbb{Z_2})=f(2t)=t[/math]
Now if [imath]t[/imath] is even, then [imath]t+1[/imath] is odd. And if [imath]t[/imath] is odd, then [imath]t+1[/imath] is even. Then clearly as [imath]t[/imath] varies over all integers, so will the [imath]f(n)[/imath] vary over all integers as well. Hence it must be true that [imath]f(\mathbb{Z})=\mathbb{Z}[/imath].

I know this is not a correct proof, but it was my attempt anyway.

I would use proof by contradiction.

 

[Aion]

I've read that the formal definition of a subjective function is the following: [imath]f:A\rightarrow B,[/imath] is subjective if [imath]\forall b\in B \exist a\in A:f(a)=b.[/imath] Applying this definition in conjunction with your idea to use proof by contradiction, I need to suppose

[math]\exist b\in \mathbb{Z}\forall a\in\mathbb{Z} : f(a)\neq b[/math]
And somehow derive a contradiction from this.

 

[lev888]

I've read that the formal definition of a subjective function is the following: [imath]f:A\rightarrow B,[/imath] is subjective if [imath]\forall b\in B \exist a\in A:f(a)=b.[/imath] Applying this definition in conjunction with your idea to use proof by contradiction, I need to suppose

[math]\exist b\in \mathbb{Z}\forall a\in\mathbb{Z} : f(a)\neq b[/math]
And somehow derive a contradiction from this.

Given this b you need to prove that such a exists. One way to do it is to provide an expression for it.

 

[Aion]

Given this b you need to prove that such a exists. One way to do it is to provide an expression for it.

Let [imath]b[/imath] be an arbitrary integer, and suppose [imath]f(a)=b.[/imath]

Case(1) If [imath]a[/imath] is even. Then [imath]b=f(a)=a/2.[/imath] Hence [imath]a=2b \in \mathbb{Z}[/imath]
Case (2) If [imath]a[/imath] is odd. Then [imath]b=f(a)=(a+1)/2[/imath]. Hence [imath]a=2b-1 \in \mathbb{Z}[/imath]

Thus [imath]\exist a \in \mathbb{Z} : f(a)=b[/imath]. Since [imath]b[/imath] was an arbitrary integer we conclude that

[imath]\forall b \in \mathbb{Z} \exist a \in \mathbb{Z} : f(a)=b[/imath]

 

[Aion]

Let [imath]b[/imath] be an arbitrary integer, and suppose [imath]f(a)=b.[/imath]

Case(1) If [imath]a[/imath] is even. Then [imath]b=f(a)=a/2.[/imath] Hence [imath]a=2b \in \mathbb{Z}[/imath]
Case (2) If [imath]a[/imath] is odd. Then [imath]b=f(a)=(a+1)/2[/imath]. Hence [imath]a=2b-1 \in \mathbb{Z}[/imath]

Thus [imath]\exist a \in \mathbb{Z} : f(a)=b[/imath]. Since [imath]b[/imath] was an arbitrary integer we conclude that

[imath]\forall b \in \mathbb{Z} \exist a \in \mathbb{Z} : f(a)=b[/imath]

Maybe it's wrong to suppose [imath]f(a)=b[/imath] above. I've tried to remedy this below.

Let [imath]b[/imath] be an arbitrary integer, and suppose for contradiction that [imath]f(a)\neq b.[/imath]

Case (1) Suppose [imath]a[/imath] is even. Let [imath]a =2b[/imath]. Then [imath]f(a)=f(2b)=b [/imath]

Case (2) Suppose [imath]a[/imath] is odd. Let [imath]a=2b-1[/imath]. Then [imath]f(a)=f(2b-1)=b[/imath]

Hence by contradiction [imath]f(a)=b[/imath], therefore [imath]\forall b \in \mathbb{Z} \exist a \in \mathbb{Z} : f(a)=b[/imath]

 

[lev888]

Maybe it's wrong to suppose [imath]f(a)=b[/imath] above. I've tried to remedy this below.

Let [imath]b[/imath] be an arbitrary integer, and suppose for contradiction that [imath]f(a)\neq b.[/imath]

Case (1) Suppose [imath]a[/imath] is even. Let [imath]a =2b[/imath]. Then [imath]f(a)=f(2b)=b [/imath]

Case (2) Suppose [imath]a[/imath] is odd. Let [imath]a=2b-1[/imath]. Then [imath]f(a)=f(2b-1)=b[/imath]

Hence by contradiction [imath]f(a)=b[/imath], therefore [imath]\forall b \in \mathbb{Z} \exist a \in \mathbb{Z} : f(a)=b[/imath]

This is not quite right. You are given this special b for which supposedly there is no a, such that f(a)=b. Your task is to come up with an expression for a (based on b), such that f(expression)=b, which contradicts the assumption that a does not exist.

 

[Steven G]

This seems trivial. n/2 will generate ALL integers when n is even. Done.
Now write it up nicely and post back with your completed proof.

 

[blamocur]

Hence \(a=2b\in \mathbb{Z}\)

Is not this enough for surjectivity?

 

[Aion]

This seems trivial. n/2 will generate ALL integers when n is even. Done.
Now write it up nicely and post back with your completed proof.

That was my first thought. Suppose [imath]n[/imath] is even, then by definition, there exists some [imath]k\in \mathbb{Z}[/imath] such that [imath]n=2k[/imath]. Then [imath]f(n)=k[/imath] for some integer [imath]k[/imath]. And so [imath]f(n)[/imath] will generate all integers [imath]k[/imath] when [imath]n[/imath] is even.

 

[Aion]

Is not this enough for surjectivity?

Suppose [imath]b[/imath] be an arbitrary integer. Let [imath]a =2b[/imath], then [imath]a[/imath] is even by definition, hence [imath]f(a)=f(2b)=b[/imath]. Therefore [imath]\exist a \in \mathbb{Z} \, f(a)=b[/imath]. And since [imath]b[/imath] was arbitrary we conclude that [imath]\forall b\in\mathbb{Z} \,\exist a \in \mathbb{Z} \,f(a)=b.[/imath]

 

[Aion]

This is not quite right. You are given this special b for which supposedly there is no a, such that f(a)=b. Your task is to come up with an expression for a (based on b), such that f(expression)=b, which contradicts the assumption that a does not exist.

Not quite sure how to apply a proof by contradiction on this problem.

 

[Aion]

I found it interesting that all the points that satisfy the function lie on the two parallel straight lines [imath]f(t)=t[/imath] and [imath]f(t)=t+1[/imath].

 

[lev888]

Not quite sure how to apply a proof by contradiction on this problem.

The expression in question is in your previous post.

 

[Aion]

The expression in question is in your previous post.

Givens	Goal
	[imath]\forall b\in \mathbb{Z} \,\exists a \in \mathbb{Z}\, f(a)=b[/imath]
Givens [imath]b\in \mathbb{Z}[/imath]	Goal [imath]\exists a \in \mathbb{Z}\,: f(a)=b[/imath]
Givens [imath]b\in \mathbb{Z}[/imath] [imath]\neg \exists a \in \mathbb{Z}\, f(a)=b[/imath]	Goal Contradiction
Givens [imath]b\in \mathbb{Z}[/imath] [imath]\forall a \in \mathbb{Z}\, f(a)\neq b [/imath]	Goal Contradiction

Is this the correct proof structure? So I need to suppose [imath]b[/imath] and [imath]a[/imath] are arbitrary integers and suppose [imath]f(a)\neq b[/imath]. But if [imath]a=2b[/imath], then [imath]a[/imath] is even so [imath]f(a)=f(2b)=b[/imath], which contradicts the assumption that [imath]f(a)\neq b[/imath] for all [imath]a\in \mathbb{Z}[/imath]. Hence [imath]\exists a \in \mathbb{Z}\,: f(a)=b[/imath].

 

[Steven G]

That was my first thought. Suppose [imath]n[/imath] is even, then by definition, there exists some [imath]k\in \mathbb{Z}[/imath] such that [imath]n=2k[/imath]. Then [imath]f(n)=k[/imath] for some integer [imath]k[/imath]. And so [imath]f(n)[/imath] will generate all integers [imath]k[/imath] when [imath]n[/imath] is even.

Now you need to show that if n is odd, you also get only integers. If n is even you get all the integers. If n is odd you only get integers (it doesn't matter if you get all the integers or not!). Now the union of Z with a subset of Z is Z. The proof is done.

 

[Aion]

Now you need to show that if n is odd, you also get only integers. If n is even you get all the integers. If n is odd you only get integers (it doesn't matter if you get all the integers or not!). Now the union of Z with a subset of Z is Z. The proof is done.

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

 

[blamocur]

f(n) will generate all integers k when n is even.

Isn't this enough for surjectivity?

 

[Aion]

Isn't this enough for surjectivity?

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

 

[Aion]

I did a similar problem today.

Consider the function [imath]f:\mathbb{Z}\rightarrow \mathbb{Z}[/imath] given by

[math]f(n)=\begin{cases} {n+1}&\text{if}~n~\text{is even}\\ {n-3}&\text{if}~n~\text{is odd}\end{cases}[/math]
Proof of that it's injective:

Suppose [imath]a\in \mathbb{Z}[/imath] and [imath]b\in \mathbb{Z}[/imath] are elements in the domain.

Case 1. Suppose [imath]a[/imath] is even and [imath]b[/imath] is even. Then [imath]f(a)=f(b)[/imath] iff. [imath]a+1=b+1[/imath] iff. [imath]a=b[/imath].

Case 2. Suppose [imath]a[/imath] is odd and [imath]b[/imath] is odd. Then [imath]f(a)=f(b)[/imath] iff. [imath]a-3=b-3[/imath] iff. [imath]a=b[/imath].

Case 3. Suppose [imath]a[/imath] is odd and [imath]b[/imath] even (or vice versa). Then [imath]f(a)=a-3[/imath] and [imath]f(b)=b+1[/imath], clearly in this case [imath]a\neq b[/imath]

Hence if [imath]f(a)=f(b) \rightarrow a=b[/imath], which proves that it's injective.

Proof that [imath]f[/imath] is surjective.

Suppose [imath]b\in \mathbb{Z}[/imath] and suppose for contradiction that [imath]\forall a \in \mathbb{Z} \, : f(a) \neq b[/imath].

Case 1. Suppose [imath]b[/imath] is even. Then consider [imath]a=b+3[/imath]. Since [imath]a[/imath] is odd, [imath]f(a)=f(b+3)=b.[/imath]

Case 2. Suppose [imath]b[/imath] is odd. Then consider [imath]a=b-1[/imath]. Since [imath]a[/imath] is even, [imath]f(a)=f(b-1)=b[/imath].

Hence for each possible case, [imath]\exists a \in \mathbb{Z}: \, f(a)=b[/imath], which proves that it's surjective.