0
$\begingroup$

The question asks to show that the set $A$ and the set of natural numbers have the same cardinality. Where $$A=(1,2,3)\times\mathbb{N}$$

So I know I have to prove a bijection, but I am having difficulty coming up with the formula to use. Any tips would be greatly appreciated!

$\endgroup$

closed as off-topic by user21820, ℋolo, Alex Provost, Cesareo, mrtaurho Feb 26 at 8:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, ℋolo, Alex Provost, Cesareo, mrtaurho
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I suppose you mean $A = \{1,2,3\}\times\Bbb{N}$. You may try $f:\Bbb{N} \to A$ defined by "division": $f(1) = (1,1), f(2) = (1,2), f(3) = (1,3), f(4) = (2,1), \dots$ $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 24 at 23:45
  • $\begingroup$ I'm not quite sure what you mean by "division". What in particular are you dividing? $\endgroup$ – Morgan Kube Feb 24 at 23:50
  • $\begingroup$ Divide $\Bbb{N}$ into three equal parts. Each of them should have the same cardinality. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 24 at 23:51
1
$\begingroup$

Well, how would we count them?

We've got this set:

$(1,1), (1,2), (1,3), (1,4)........ $

$(2,1), (2,2), (2,3), (2,4)........ $

$(3,1), (3,2), (3,3), (3,4)........ $

How would I count them. Well I imagine I'd point to the first one in the first row and say "Okay, $(1,1)$ you are No. 1" and then I'd point to the first one in the second row and say "Okay, $(2,1)$ you are No. 2", and then I'd point to the first one in the third row and say "Okay, $(3,1)$, you are No. 3". Then I'd point to the second in the first row and say "Okay, $(1,2)$ you are No. 4$.

Then I'd ask myself: "Okay, when I get the the $k$th one in the $b$th row, what number will I have reached?".

And then I'd answer myself: "Well I've gone through $k-1$ terms to get to this $k$th term. And for each of those $k-1$ terms I picked one from each row so that's $3(k-1)$ I've gone through to get to this point. And now I'm on the $b$th row so that's $b$ more terms. So I'm at the $3(k-1) + b$ item I counted."

"So you, $(b, k)$, you are number $3(k-1) + b$".

And that's my bijection: $f:\{1,2,3\}\times \mathbb N\to \mathbb N$ via $f(b, k) = 3(k-1) + b$.

$\endgroup$
  • $\begingroup$ Okay awesome. So if I wanted to write this as a modular equation I could say b=k (mod 3) iff 3|(k-1)+b? $\endgroup$ – Morgan Kube Feb 25 at 17:42
  • $\begingroup$ uh.... maybe? I dont know why you want to write it as a modular equation. Modular equations aren't injective and there are only 3 equivalence classes so I'm not seeing how modularity will help you determine cardinality in any way... But you could say $g(n=3k+r) = (r+1, k+1)$ to get a bijection from $g:\mathbb N\to \{1,2,3\}\times \mathbb N$. It's a different bijection than the inverse of the one I gave but it doesn't matter. It's still good. $\endgroup$ – fleablood Feb 25 at 17:52
  • $\begingroup$ Um... "$b \equiv k \pmod 3 \iff 3|(k-1)+b$" is not true. $b\equiv k\pmod 3 \iff 3|k-b$. $b= 1,2$ or $3$ is "remainder bit". The $k$ and $(k-1)$ is what you multiply $3$ by. $\endgroup$ – fleablood Feb 25 at 17:55
1
$\begingroup$

Hint: You can list all the elements of $\mathbb{N}$ in something like an infinite matrix where its entries come from $A=\{1,2,3\}\times \mathbb{N}=\{(x,n): x=1,2,3 \,\text{ and }\, n\in\mathbb{N}\}$ in the following way

$$\begin{bmatrix}1 & 4 & 7 & \cdots \\2 & 5 & 8 & \cdots \\ 3 & 6 & 9 &\cdots\end{bmatrix}$$

So, you're sweeping natural numbers column-wise, i.e. you associate to each entry $(i,j)$, a natural number defined by $3(j-1)+i$ for $i=1,2,3$ and $j \in \mathbb{N}$. For example, we have $(1,2) \mapsto 4$, $(2,1) \mapsto 2$, $(3,3) \mapsto 9$, so on so forth.


Addendum: If you are interested in a closed form solution, define $f: A \to \mathbb{N}$ by

$$f(x,n) = 3(n-1)+x$$

Then, since $x=1,2,3$, we have that $f(x,n)=m$ if and only if

$$3(n-1)+1 \leqslant m \leqslant 3(n-1)+3$$ $$n-1<(n-1)+\frac{1}{3} \leqslant \frac{m}{3} \leqslant (n-1)+1 = n$$ $$n-1 < \frac{m}{3} \leqslant n$$

which implies that $n = \big\lceil \frac{m}{3}\big\rceil$ and hence, $x = m - 3\big(\big\lceil \frac{m}{3}\big\rceil -1\big)$.

So, $f^{-1}: \mathbb{N} \to A$, is defined by

$$f^{-1}(m) = \bigg(m - 3\big(\lceil \frac{m}{3}\rceil -1\big), \lceil \frac{m}{3}\rceil\bigg)$$

where $\big\lceil x \big\rceil$ denotes the ceiling function, i.e. the smallest integer $n$ such that $x \leqslant n$.

So, $f: A \to \mathbb{N}$ has an inverse and therefore, it's a bijection between $A$ and $\mathbb{N}$, proving that they have the same cardinality.

$\endgroup$
0
$\begingroup$

Consider the map $$ f(j)=\begin{cases} (1,j)&\quad \text{if }\, j=3k+1\\ (2,j)&\quad \text{if }\, j=3k+2\\ (3,j)&\quad \text{if }\, j=3k\\ \end{cases} $$ (for some $k$) and prove that it is a bijection.

$\endgroup$
0
$\begingroup$

The techniques listed above are great, though I would encourage you to think about the problem starting from the simplest case. Namely, if you had all the values in ur set A, and just started counting in the simplest manner what would it look like?

It would be likely: (1,1) -> 1 , (1,2) -> 2 , (1,3) -> 3, (1,4)->4, ...

Unfortunately that set as you know goes on forever, so though that set is clearly countable, it is also infinite which leaves with an inability to ever start counting (2,1) and onward... So you run into the problem of how can I include the other values in my set that do not have the first coordinate equal to 1? Thats where an idea of “sweeping through” each of the 3 sets comes in handy. You avoid the problem of never finishing counting the first set, allowing you a chance to describe a bijection.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.