Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do I prove that the following sets have equal cardinality?

  1. $|\Bbb N \times\Bbb N \times\Bbb N| = |\Bbb N|$ ($|\Bbb N \times\Bbb N| = |\Bbb N|$ also for that matter)
  2. $|\Bbb Z \times\Bbb Z| = |\Bbb Z|$
  3. $|\Bbb R \times\Bbb R| = |\Bbb R|$

Thank you!

share|improve this question
2  
What did you try? Did you try searching the site? –  Asaf Karagila Jan 5 '13 at 18:19
    
yes I tried searching the site –  Yechiel Labunskiy Jan 5 '13 at 18:26
2  
Look here, here, here, here, and here; among them they answer all of your questions. –  Brian M. Scott Jan 5 '13 at 18:41
    
Thank you Brian! Guess I didn't know what to search for. –  Yechiel Labunskiy Jan 5 '13 at 18:54
    
Wie ought to have something like an abstract duplicate "When is $|X\times X|=|X|$?" –  Hagen von Eitzen Jan 6 '13 at 10:34

3 Answers 3

It is easy to produce a sequence that includes all the elements in $\Bbb N\times\Bbb N\times\Bbb N$.

E.g. $(0,0,0)$, $(1,0,0)$, $(0,1,0)$, $(0,0,1)$, $(2,0,0)$, $(1,1,0)$, $(1,0,1)$, $(0,2,0)$, $(0,1,1)$, $(0,0,2)$, $(3,0,0)$, $(2,1,0)$, $(2,0,1)$,...

This can be adjusted to the case of $\Bbb Z\times\Bbb Z\times\Bbb Z$ and/or any finite number of copies of $\Bbb N$ or $\Bbb Z$, or even $\Bbb Q$.

To show that $|\Bbb R|=|\Bbb R\times\Bbb R|$ requires, of course, a different argument.

share|improve this answer
    
How do I map that sequence to |N| with a one-to-one and an unto function? –  Yechiel Labunskiy Jan 5 '13 at 18:55
    
Well, you map $1$ to the first element, $2$ to the second element, $3$ to the third element and so on. Recall that a sequence in a set $X$ is just a function $\Bbb N\rightarrow X$. If a sequence contains exactly once all the elements of $X$, then the sequence, thought as a function, is bijective. –  Andrea Mori Jan 5 '13 at 19:12

Note that having size $|N|$ means something is infinite but enumerable; meaning, roughly, that you can come up with a way of listing all the elements in a single row.

Note: I am abiding by $N = \{0, 1, 2, 3, \ldots\}$.

To show $|N \times N| = |N|$, you could start by listing all the elements $(m, n)$ with $m,n \in N$ such that $m + n \leq 0$. Next, list all the elements with $m+n \leq 1$, and so forth. In this way, you produce a list of the elements; a list of the form:

$a_0, a_1, a_2, a_3 \ldots$ which can be matched up with elements of $N$ using $a_n \rightarrow n$.

The case for $N \times N \times N$ is similar, as is the case for anything $Z$ related.

Your third problem is a bit more involved, but one place to start is by thinking about decimal expansions. I won't say anything more unless you post what you have tried thus far.

share|improve this answer
    
Pairs like (2,2) and (3,1) will both map to 4 which means it's not one-to-one, am I missing something? Don't really know where to start on R x R. Thanks –  Yechiel Labunskiy Jan 5 '13 at 18:29
    
The key is to come up with an organized way of listing all of them. One way to avoid the sort of problem you have described is to always list $(a,b)$ before $(c,d)$ when $a + b = c + d$ and $a < c$. So the list would begin: $(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (0, 3), (1, 2), (2, 1), (3, 0), (0, 4), (1, 3), (2, 2), (3, 1)$ Of course, a similar approach can be used to demonstrate that $\mathbb{Q}$ is countable. –  Benjamin Dickman Jan 6 '13 at 10:22

The function:$$f:\mathbb{Z}^+\times\mathbb{Z}^+\times\mathbb{Z}^+\rightarrow \mathbb{Z}^+$$ that sends $(i,j,k)$ to $(2(2j-1)2^{i-1}-1)2^{k-1}$ is a bijection.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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