Prove that the set $A = \{(x, y) \mid x$ is an odd integer and $y$ is an even integer$\}$ is enumerable

Question

Prove that the set $A = \{(x, y) \mid x \text{ is an odd integer and } y \text{ is an even integer}\}$ is enumerable.

I created a matrix with $0, 1, 2, 3, \ldots$ as rows and $0, 1, 2, 3, \ldots$ as columns. Then for the element at row $1$ column $0$, for example, the correspondent value is $(1, 0)$, for the element at row $0$ column $0$ there is no value associated because $0$ is even. Then I created the sets $S_z$ where $z=x+y$, so $S_1=\{(1,0)\}$, $S_3=\{(1,2),(3,0)\}$, $S_5=\{(1,4),(3,2),(5,0)\}, \ldots$ So, I created a list of elements, but the problem is that the set of integers contains also negative numbers. How can I solve this?

Answer 1

One way to get countability is to create an injective function (not necessarily surjective) from your set $A$ to $\Bbb{N}$. Because then the image $f(A)$ of your set is a subset of $\Bbb{N}$, hence $f(A)$ is countable and by injectivity $A$ is countable.

A simple way to achieve this with negative integers etc. is as follows: Let $$f(x,y)=\begin{cases} 2^x \cdot 3^y & \text{ if } x \geq 0, y \geq 0 \\ 5^x \cdot 7^{|y|} & \text{ if } x \geq 0, y < 0\\ 11^{|x|} \cdot 13^{|y|} & \text{ if } x < 0, y < 0\\ 17^{|x|} \cdot 19^y & \text{ if } x < 0, y \geq 0\end{cases}$$ From the uniqueness of prime factorization, injectivity can be concluded fairly quickly.

Answer 2

Figure out how to map $\{1,2,3,4,5,6,7....\}=\mathbb N \leftrightarrow \mathbb Z=\{0,1,-1,2,-2,3,-3,.....\}$

Then figure out how to map $\{.....-3,-2,-2,-1,0,-,2,-3....\}=\mathbb Z\leftrightarrow 2\mathbb Z = \{....... -6,-4,-2,0,2,4,6 ......\}$

Now combine those two to figure out how to map $\{1,2,3,4,5,6,7....\}=\mathbb N \leftrightarrow \mathbb Z=\{0,1,-1,2,-2,3,-3,.....\}\leftrightarrow \{0,2,-2,4,-4,6,-6,...\}=2\mathbb Z$.

And figure out how to map $\{.....-3,-2,-2,-1,0,-,2,-3....\}=\mathbb Z\leftrightarrow 2\mathbb Z+1 = \{....... -5,-3,-1,1,3,5,7 ......\}$ and combine what you have to

figure out how to map $\{1,2,3,4,5,6,7....\}=\mathbb N \leftrightarrow \mathbb Z=\{0,1,-1,2,-2,3,-3,.....\}\leftrightarrow \{1,3,-1,5,-3,7,-5,...\}=2\mathbb Z+1$.

And figure out how to map $\{1,2,3,4,5,6,7....\}=\mathbb N\leftrightarrow \{(1,1),(1,2),(2,1),(1,3),(2,2),(3,1).....\} = \mathbb N\times \mathbb N$.

And then combine them all into one ....

$\{1,2,3,4,5,6,7....\}=\mathbb N\leftrightarrow \{(1,0),(1,2),(-1,0),(1,-2),(-1,2),(3,1).....\} $

......

In other words: Let the following be bijections.

$f:\mathbb N \to \mathbb Z$ (you have to figure out this bijection once in your life and then you never need to do it again; it's enough to remember it exists)

$g: \mathbb Z \to ODDS$ (ditto)

THen $g\circ f$ is a bijection $g\circ f:\mathbb N \to ODDS$ (Note: you DON"T have to figure out what this actually is. It's enough to know the compositions of bijections is a bijections)

$h: \mathbb Z\to EVENS$ (you have to figure out this bijection once in your life and.... etc. )

So $h\circ f: \mathbb N \to EVENS$ is bijection.

and $j:\mathbb N \to \mathbb N\times \mathbb N$ (you have to figure out this bijection once in your life and.... etc. ).

Let's define some notation. If $k: A\to B$ and $m: C\to D$ lets define the function that maps $(a,c)\in A\times C$ to $(k(a),m(c)) \in B\times D$ as the function $[m,k]:A\times C \to B\times D$.

Then $j\circ [g\circ f| h\circ f]: \mathbb N \to ODDS\times EVEN$.

That's enough to show that $ODDS \times EVEN$ is enumerable. You don't have to find the functions. It's enough to know they exist.

Answer 3

If you say you know that $\mathbb{N}\times\mathbb{N}$ is enumerable. Then you should be able to conclude that $\mathbb{Z}\times\mathbb{Z}$ is enumerable.

For example send $(x,y)$ to:

1. $(2x,2y)$ if $x,y\geq 0$
2. $(2x,-2y-1)$ if $x\geq 0$ and $y<0$
3. $(-2x-1,2y)$ if $x<0$ and $y\geq 0$
4. $(-2x-1,-2y-1)$ if $x,y<0$

Now your set is a subset of $\mathbb{Z}\times\mathbb{Z}$ so it's enumerable.