Discrete Math Show that the set of all nonnegative integers

Discrete Math

Show that the set of all nonnegative integers is countable by exhibiting a one-to-one correspondence between Z⁺ and Z^nonneg.

Solution

Define the map, F from Znonneg to Z+

f(x)=x+1

Let, m,n so that:

f(m)=f(n)

m+1=n+1

m=n

Hence, f is one-to-one

Let, y be in Z+ hence, y>=1 or y-1>=0

So,

f(y-1)=y

Hence, f is onto.

So we have a bijection between Z+ and Znonneg

Hence, Znonneg is countable.