Is $\{1, 2, 3\}\times \Bbb Z$ uncountable?

Question

$\Bbb Z$ being the set of integers.
My understanding is that a set is uncountable if it's greater than the set of $\Bbb N$.
Might it be that I'm misunderstanding the question, and misinterpreting the '$\times$' which I'm currently interpreting as 'intersection'.

The $\times$ means the Cartesian product, so it's the set of ordered pairs with first component in ${1,2,3}$ and second component in $\mathbb{Z}$. That set is countable. — Daniel Fischer, Sep 18 '13 at 20:17
The "x" probably stands for Cartesian Product. This is not the same as intersection. $\mathbb{R}\times\mathbb{R} = \mathbb{R}^2$, for instance.
A set is countable if it is denumerable. The original definition due to Cantor comes from a technique of putting the natural numbers into a complete one-to-one correspondence with the natural numbers. This is accomplished by specifying a rule that can be followed as far as one would care to go. — Urðr, Sep 18 '13 at 20:23

Alexander · Accepted Answer · 2013-09-18T20:29:38.107

6

That set is not uncountable. In fact $(a, b) \mapsto 3b+a-1$ is a bijection from your set to $\mathbb{Z}$!

Explanation: Two sets $A, B$ have the same cardinality if there exists a bijection between them. That is, if there is a function $f: A \to B$ so that each $b \in B$ corresponds with exactly one $a \in A$. Now, the function I have given maps from $\{1, 2, 3\} \times \mathbb{Z} \to \mathbb{Z}$. It takes some element of the first set like $(2,7)$ and maps it to $3 \cdot 7+2-1=22$. You can check that each integer corresponds with exactly one ordered pair in $\{1, 2, 3\} \times \mathbb{Z}$. Thus this is a bijection! Thus, your set has the same cardinality as the integers. But the integers are in bijection with the naturals (see if you can find such a function) thus, all these sets have the same cardinality as the natural numbers. We refer to such sets as "countable".

edited Sep 18 '13 at 20:29

answered Sep 18 '13 at 20:14

Alexander

4,292

I'm really new to Discrete Mathematics (first week) so I'm having a bit of trouble understanding what you mean by (a, b) -> 3b + a - 1, could you possibly give me a brief explanation? – Ceelos Sep 18 '13 at 20:20
1

Does that make more sense? Let me know if I can clarify further! – Alexander Sep 18 '13 at 20:32
That was perfect, thank you! – Ceelos Sep 18 '13 at 20:40
1

You're welcome! – Alexander Sep 18 '13 at 20:42
any reason why you subtracted 1? It is a bijection without -1 ;) – N. S. Sep 19 '13 at 01:23
Yeah, that does look pretty strange in hindsight. In my mind I was thinking of ${1,2,3} \times \mathbb{Z}$ as encoding "division by 3 with remainder" so that we can write $x=3b+(a-1)$ where the remainder of $x$ divided by $3$ is $a-1$ and $ 0 \leq a-1<3$. – Alexander Sep 19 '13 at 02:00

score 1 · Answer 2 · edited Jul 23 '17 at 09:14

The symbol $\times$ is not an intersection. Intersection is almost always represented by $\cap$. The $\times$ is a Cartesian product, so the set $$A\times B = \{(a,b) ~~| ~~a\in A, b\in B\}$$

Which means that $\{1,2,3\}\times\Bbb{Z}$ is basically $3$ "copies" of $\Bbb{Z}$, or equivalently a countably infinite number of copies of $\{1,2,3\}$. This can be put into bijection with the integers explicitly, as Alexander pointed out, or simply by thinking of a picture similar to the diagonalization argument proving that $\Bbb{Q}$ is countable, but going horizontally and in both directions. Therefore it is countable.

Is $\{1, 2, 3\}\times \Bbb Z$ uncountable?

2 Answers2