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

[Aion]

Problem.

Suppose $f:\mathbb{Z}\rightarrow\mathbb{Z}$ given by

$$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}$$
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 $f(0)=0$ and $f(-1)=0$ but $0\neq-1$. However, I find it difficult to prove that the function is surjective. The goal is to show that $f(\mathbb{Z})=\mathbb{Z}$.

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

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

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

 

[lev888]

Problem.

Suppose $f:\mathbb{Z}\rightarrow\mathbb{Z}$ given by

$$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}$$
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 $f(0)=0$ and $f(-1)=0$ but $0\neq-1$. However, I find it difficult to prove that the function is surjective. The goal is to show that $f(\mathbb{Z})=\mathbb{Z}$.

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

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

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: $f:A\rightarrow B,$ is subjective if $\forall b\in B \exist a\in A:f(a)=b.$ Applying this definition in conjunction with your idea to use proof by contradiction, I need to suppose

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

 

[lev888]

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

$$\exist b\in \mathbb{Z}\forall a\in\mathbb{Z} : f(a)\neq b$$
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 $b$ be an arbitrary integer, and suppose $f(a)=b.$

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

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

$\forall b \in \mathbb{Z} \exist a \in \mathbb{Z} : f(a)=b$

 

[Aion]

Let $b$ be an arbitrary integer, and suppose $f(a)=b.$

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

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

$\forall b \in \mathbb{Z} \exist a \in \mathbb{Z} : f(a)=b$

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

Let $b$ be an arbitrary integer, and suppose for contradiction that $f(a)\neq b.$

Case (1) Suppose $a$ is even. Let $a =2b$. Then $f(a)=f(2b)=b$

Case (2) Suppose $a$ is odd. Let $a=2b-1$. Then $f(a)=f(2b-1)=b$

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

 

[lev888]

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

Let $b$ be an arbitrary integer, and suppose for contradiction that $f(a)\neq b.$

Case (1) Suppose $a$ is even. Let $a =2b$. Then $f(a)=f(2b)=b$

Case (2) Suppose $a$ is odd. Let $a=2b-1$. Then $f(a)=f(2b-1)=b$

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

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 $n$ is even, then by definition, there exists some $k\in \mathbb{Z}$ such that $n=2k$. Then $f(n)=k$ for some integer $k$. And so $f(n)$ will generate all integers $k$ when $n$ is even.

 

[Aion]

Is not this enough for surjectivity?

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

 

[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 $f(t)=t$ and $f(t)=t+1$.

 

[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
	$\forall b\in \mathbb{Z} \,\exists a \in \mathbb{Z}\, f(a)=b$
Givens $b\in \mathbb{Z}$	Goal $\exists a \in \mathbb{Z}\,: f(a)=b$
Givens $b\in \mathbb{Z}$ $\neg \exists a \in \mathbb{Z}\, f(a)=b$	Goal Contradiction
Givens $b\in \mathbb{Z}$ $\forall a \in \mathbb{Z}\, f(a)\neq b$	Goal Contradiction

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

 

[Steven G]

That was my first thought. Suppose $n$ is even, then by definition, there exists some $k\in \mathbb{Z}$ such that $n=2k$. Then $f(n)=k$ for some integer $k$. And so $f(n)$ will generate all integers $k$ when $n$ 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 $n$ is even. By definition, there exists some $k\in\mathbb{Z }$ such that $n=2k$. Therefore, $f(n)=k$ for some integer $k$. Hence, $f(n)$ will generate all integers $k$ when $n$ is even.

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

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

 

[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 $\mathbb{Z}$?

 

[Aion]

I did a similar problem today.

Consider the function $f:\mathbb{Z}\rightarrow \mathbb{Z}$ given by

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

Suppose $a\in \mathbb{Z}$ and $b\in \mathbb{Z}$ are elements in the domain.

Case 1. Suppose $a$ is even and $b$ is even. Then $f(a)=f(b)$ iff. $a+1=b+1$ iff. $a=b$.

Case 2. Suppose $a$ is odd and $b$ is odd. Then $f(a)=f(b)$ iff. $a-3=b-3$ iff. $a=b$.

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

Hence if $f(a)=f(b) \rightarrow a=b$, which proves that it's injective.

Proof that $f$ is surjective.

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

Case 1. Suppose $b$ is even. Then consider $a=b+3$. Since $a$ is odd, $f(a)=f(b+3)=b.$

Case 2. Suppose $b$ is odd. Then consider $a=b-1$. Since $a$ is even, $f(a)=f(b-1)=b$.

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