Issues relating formulas to functions for use in proving bijectives.

Question

I've realized that I have a lot of trouble with actually finding a working formula to use for once I figure out the function to use. Here's an example of one problem that stumped me:

Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set.

e) The set $A × Z^+$ where A = {2, 3}

I know that I essentially need to (in order)...

• Make a function to use, which I think should be $ f:Z^+→(A×Z^+)$ to start.
• *** Figure out a formula to use with the function that stays true to the problem (This is what I'm having a lot of trouble with).
• Use said formula to either prove or disprove the function f is one-to-one or onto.
• Then flip the function to make $g:(A×Z^+)→Z^+$
• *** Figure out the formula for that function.
• Use this formula to either prove or disprove the function g is one-to-one or onto.

What I've starred are my trouble areas. I honestly don't know where to begin when it comes to finding a formula for this problem. I know that this is countably infinite and I know that the list would go something like this: { (2,1) , (3,1) , (2,2), (3,2) , (2,3) , (3,3) , (2,4) , (3,4) , ... }.

However, I do really want to practice the proof of this, but I can't seem to wrap my head around how I can relate a formula to the function $f$ or $g$. Any feedback is appreciated!

Answer 1

If you want a formula for $2,3,2,3,2,3,\dots$, you can use $2.5+(0.5)(-1)^n$.

If you want a formula for $1,1,2,2,3,3,4,4,\dots$, if you multiply by two you get $2,2,4,4,6,6,8,8,\dots$, which is the sum of $1,2,3,4,5,6,7,8,\dots$ and $1,0,1,0,1,0,1,0,\dots$. The first of those is just $n$, the second can be handled the same way we did $2,3,2,3,2,3,\dots$.

Answer 2

LEMMA: The union of two countably infinite sets $X$ and $Y$ is countably infinite:
$X=\{x_1,x_2\dotsc\}$ and $Y=\{y_1,y_2,\dotsc\}$. Then list $X\cup Y$ as $\{x_1,y_1,x_2,y_2,\dotsc\}$. Explicitly, we have a bijection $f:\mathbb{Z}^+\to X\cup Y$ defined by $f(n)=\begin{cases} x_{(n+1)/2}\ \text{if } n\ \text{is odd,}\\ y_{n/2}\ \text{if } n\ \text{is even.} \end{cases}$

$A\times\mathbb{Z}^+$ is countably infinite:
$A\times\mathbb{Z}^+=(\{2\}\times\mathbb{Z}^+)\cup(\{3\}\times\mathbb{Z}^+)$. Then $\mathbb{Z}^+\approx\{(2,n):n\in\mathbb{Z}^+\}$ by the map $n\to(2,n)$, and similarly, $\mathbb{Z}^+\approx\{(3,m):m\in\mathbb{Z}^+\}$. So $A\times\mathbb{Z}^+$ is the union of two countably infinite sets and hence countably infinite.

This proof lists $A\times\mathbb{Z}^+$ as $\{(2,1),(3,1),(2,2),(3,2),\dotsc\}$, which is how you listed it.

Explicitly, the function $g:\mathbb{Z}^+\to A\times\mathbb{Z}^+$ defined by $g(n)=\begin{cases} \left(2,\frac{n+1}{2}\right)\ \text{if } n\ \text{is odd,}\\ \left(3,\frac{n}{2}\right)\ \text{if } n\ \text{is even} \end{cases}$ describes this listing and is bijective by the lemma.