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.

The set $S$ of all pairs of integers can be represented as $\{i \ | \ i \in \mathbb{Z} \} \times \{j\ | \ j \in \mathbb{Z}\}$. In other words, all coordinates on the cartesian plane where $x, y$ are integers.

I also know that a set is countable when $|S|\leq |\mathbb{N}^+|$. I attempted to map out a bijective function, $f : \mathbb{N}^+ \rightarrow S$.

$1 \rightarrow (1,1) \\ 2 \rightarrow (1,2)\\ 3 \rightarrow (1,3) \\ \quad \vdots $

I determined from this that the natural numbers can only keep up with $(1,*)$. But there is the ordered pairs where $x=2,3,4,\cdots$ not to mention the negative integers. In other words, $|S|\geq |\mathbb{N}^+|$ and therefore $S$ is not countably infinite.

Is this correct? (I don't think it is... Something to do with my understanding of infinite sets)

share|improve this question
    
As Brian mentions "Cantor's pairing function" will do the job directly. However, it may be easier to understand: First prove that the union of countably many countable sets is countable (See Cantor's first diagonal argument). Then we can write $\mathbb{N}\times\mathbb{N} = \bigcup(\mathbb{N}\times\{n\})$ and hence the product is countable –  Deven Ware Aug 28 '12 at 4:24
    
Perhaps you mean natural numbers, rather than integers ($\mathbb N$ usually denotes natural numbers while $\mathbb Z$ denotes integers)? Either way, the set of pairs of natural numbers/integers is countably infinite; just because the function you found is not a bijection does not mean no bijection exists. –  Alex Becker Aug 28 '12 at 4:26
    
yes, i meant integers. sorry about that –  James Aug 28 '12 at 4:29

3 Answers 3

up vote 3 down vote accepted

Natural Numbers: There are many pairing functions that map $\mathbb{N}\times \mathbb{N}$ bijectively to $\mathbb{N}$. A simple example is the mapping $f$ such that $f(a,b)=2^{a-1}(2b-1)$. For every positive integer $y$ can be uniquely expressed as a power of $2$ times an odd integer.

Integers: If you want a mapping $g(x,y)$ that maps $\mathbb{Z}\times \mathbb{Z}$ bijectively to $\mathbb{N}$, it is simplest to split the work into two parts.

Let $\phi$ be any mapping that maps $\mathbb{Z}$ bijectively to $\mathbb{N}$. For a concrete example of such a mapping, let $\phi(t)=2t+2$ if $t \ge 0$, and let $\phi(t)=-(2t+1)$ if $t \lt 0$. The non-negative integers are sent to the even integers $\ge 2$, and the negative integers are sent to the positive odd integers.

Then the mapping $g(x,y)=f(\phi(x),\phi(y))$ works, where $f$ is any bijective map from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$. For example, we can use the mapping $f$ of the first paragraph, or the Cantor pairing function.

Remark: For most purposes, there is no particular virtue in having an explicit bijection, as long as we can prove that a bijection exists.

share|improve this answer

You simply haven’t yet found a function that works. One that does is the Cantor pairing function, which is described quite well in the Wikipedia article to which I linked.

share|improve this answer

A more general result is a mapping between the set of integers to the set of sets of integers.

If we order all positive sets of integers by their sum, we get the following:

$1\\ 2\\ 1, 1\\ 3\\ 2, 1\\ 1, 2\\ 1, 1, 1\\ 4\\ 3, 1\\ 2, 2\\ 2, 1, 1\\ 1, 3\\ 1, 2, 1\\ 1, 1, 2\\ 1, 1, 1, 1\\ etc.$

Clearly this set contains all possible finite sets of integers.

Next, we can define a mapping from the positive integers to these values as follows:

$0001 \rightarrow1 \\ 0010 \rightarrow 2\\ 0011 \rightarrow 1, 1\\ 0100 \rightarrow 3\\ 0101 \rightarrow 2, 1\\ 0110 \rightarrow 1, 2\\ 0111 \rightarrow 1, 1, 1\\ 1000 \rightarrow 4\\ 1001 \rightarrow 3, 1\\ 1010 \rightarrow 2, 2\\ 1011 \rightarrow 2, 1, 1\\ 1100 \rightarrow 1, 3\\ 1101 \rightarrow 1, 2, 1\\ 1110 \rightarrow 1, 1, 2\\ 1111 \rightarrow 1, 1, 1, 1\\ etc.$

And note that this mapping can be performed easily by adding one to every "1" for every zero after it, and then removing those zeros. This can be more formally described in terms of logarithms or dividing by/modulo 2, but that seems sufficient to get the point across. The interesting part is this has the result of proving that the cardinality of the set of integers is the same as the cardinality of the set of sets of integers, the set of sets of sets of integers, the set of sets of sets of sets of integers, etc. - a very counterintuitive result. I don't think it carries over to an infinite amount of set of sets of sets of sets of sets of ... of integers, however.

Back to your question, a similar mapping to can be made between integers and all pairs of numbers (ordered by the length of the pairs' sums) using a piece of pascal's triangle, specifically the 2nd "row". Indeed, the triangle itself describes all mappings from the set of integers to the set of sets of integers of size $k$ for all $k>0$, but I'll leave that as an exercise to the reader :) Finally you apply a mapping from $\mathbb{Z}$ to $\mathbb{N}$, using something like the one suggested by André.

A corollary to this proof is that the cardinality of all rational numbers/fractions (a pair of two integers) is equal to the cardinality of integers, and a corollary to the more general proof is that a "circuit" taking a set of input integers that sum to n and returning a set of output integers that sum to m is the equivalent of a circuit that takes an n-bit input and returns an m-bit output.

share|improve this answer
    
(1) Please observe the distinction between sets (unordered and no repeats) and ordered tuples. (2) "... the cardinality of the set of integers is the same as the cardinality of the set of sets of integers, the set of sets of sets of integers, the set of sets of sets of sets of integers, etc." is missing a lot of instances of the word "finite". (3) I feel the writing here isn't very clear in general. I still don't know what you're trying to do with the Pascal's triangle, for example. –  epimorphic Jun 4 at 4:56

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.