The set of natural numbers N = { 1, 2, 3, ... }

Definition 2: Set of integers Z

The set of integers Z = { .., -2, -1, 0, 1, 2, ... }

Definition 3: Set of rational numbers Q

The set of rational numbers Q = { a/b : where a,b ∈ Z }

Definition 4: ~

A~B if and only if there is a one-to-one correspondence between the elements of A and the elements of B.

Definition 5: Infinitely countable

A set S is said to be infinitely countable if there is a one-to-one correspondence between that set and the set N. That is, S~N.

Theorem 1: The union of two infinitely countable sets is infinitely countable

Proof:

(1) Let A be an infinitely countable set so that A~N

(2) Let B be an infinitely countable set so that B~N

(3) Let O be the set of odd positive integers = {1, 3, 5, ... }

(4) Let E be the set of even positive integers = {2, 4, 6, ... }

(5) N~O since we can map x to 2x-1 such that:

1 --> 1

2 --> 3

3 --> 5

...

(6) N~E since we can x to 2x such that:

1 --> 2

2 --> 4

3 -- > 6

...

(7) O + E = N ~ N

This is true since N consists of all the positive odd integers and all the positive even integers.

(8) A ~ O since A~N and O~N

(9) B ~ E since B~N and E~N

(10) A + B ~ A + B ~ O + E ~ N

QED

Corollary 1.1: The set of integers Z is countable

Proof:

(1) Let W = the set of positive integers = {0, 1, 2, 3, ... }

(2) W ~ N

In this case, x maps to x-1 so that we have:

1 --> 0

2 --> 1

3 --> 2

...

(3) Let Z-= the set of negative integers = {-1, -2, -3, ... }

(4) Z- ~ N

In this case, x maps -x so that we have:

1 --> -1

2 --> -2

3 --> -3

...

(5) Z = Z- + W so Z is countable because it is the union of two countable sets. [Using Theorem 1 above]

QED

Theorem 2: The set of ordered pairs WxW is infinitely countable

The set WxW is infinitely count where W={0, 1, 2, ... } and WxW = { (0,0), (0,1), ..., (1,0), (1,1), ..., (2,0), ... }

Proof:

(1) The trick here is to find a way of ordering WxW so that we can visit each ordered pair one-at-a-time and still be on track to visit all of them.

(2) Here's the ordering:

(3) We can see that all possible ordered pairs can be listed in this grid and the zig-zag traversal will eventually visit each one.

QED

Corollary 2.1: If two sets A,B are infinitely countable, then AxB is infinitely countable.

Proof:

(1) Since W ~ N, we can see that A ~W, B~W

(2) This means that AxB ~ WxW

(3) Since WxW ~ N [By Theorem 2 above], we have AxB ~ N.

QED

Theorem 3: All infinite subsets of an infinitely countable set are infinitely countable

Proof:

(1) Let A be an infinite set that is infinitely countable.

(2) Let B be an infinite subset of A.

(3) Now, by definition, we know that we can order the elements in A such that A = {a

_{1}, a

_{2}, ..., a

_{n}}

(4) Now, it follows that B can be listed in the same way with deletions so that you have:

{a

_{a}, a

_{b}, a

_{c}, ... } where a is less than b is less than c etc.

(5) The mapping consists of traversing B in the same order as A so that you have:

1 --> a

_{a}[The first element in A not deleted]

2 --> a

_{b}[The second element in A not deleted]

3 --> a

_{c}[The third element in A not deleted]

...

QED

Theorem 3: The set of rational numbers is infinitely countable

Proof:

(1) The trick here is that we can allow repeats. We come up with an algorithm that will sequentially generate all the rational numbers that exist with repeats.

(2) We can use repeats since by Lemma 2 above, if Q + repeats is infinitely countable then its subset Q (deleting all the repeats) is infinitely countable.

(3) We can map rational numbers to Z x N where Z is the set of integers = { ..., -1, 0, 1, ... } and N is the set of natural numbers = {1,2,3,4, ... } since:

(a) Each rational number q = a/b where a,b ∈ Z. [Definition of rational numbers]

(b) We can assume b is a positive integer since:

b ≠ 0 [Since division by zero is not allowed] and if b ≤ -1, then a/b = (-a)/b where b ≥ 1.

(c) So, every q=a/b maps to (a,b) where a ∈ Z and b ∈ N.

(4) Since Z is infinitely countable (See Corollary 1.1 above) and N is infinitely countable (by definition), we know that ZxN is infinitely countable (By Corollary 2.1 above)

QED

Theorem 4: The number of real numbers between 0 and 1 is not infinitely countable

Proof:

(1) Assume that the real numbers between 0 and 1 is infinitely countable so that there is a mapping between these numbers and N.

(2) Then there should be a complete list. All real numbers would have to be included in this mapping.

(3) But it is possible to construct a number that is not one the list.

(4) All numbers in this list are of the form. 0.xxxxxxxxx....

(5) Let x

_{1}= the first number in the list and x

_{1,1}= the first digit of the first number in the list so that 0 ≤ x

_{1,1}≤ 9.

(6) Let n

_{1}= any other digit. For example, if x

_{1,1}= 9 then we could have n

_{1}= 8.

(7) We can see that all numbers that we create from n will not equal x

_{1}

(8) Let x

_{2,2}= the second digit of the second number on the list.

(9) We can now set n

_{2}= any other digit so that n is now distinct from x

_{1}and x

_{2}.

(10) We can continue doing this for as long as i and in each case n is different from all the real numbers that came up to i.

(11) In this way, it is possible to set n = a real number which is not on the list.

(12) But this is impossible since we assumed that there was a complete mapping. Therefore, we have a contradiction and we reject our assumption at step #1.

QED

Corollary 4.1: There are an uncountable number of real numbers.

Proof:

This follows directly from the theorem above since (0,1) is a subset of all real numbers so that if (0,1) is uncountable, it follows that the R, the superset of (0,1) is also uncountable.

QED

Corollary 4.2: The number of irrational numbers is uncountable

Proof:

(1) The set of real numbers = the set of rational numbers + the set of irrational numbers.

(2) The set of rational numbers is infinitely countable. [See Theorem 3 above]

(3) Assume that the set of irrational numbers is infinitely countable.

(4) Then the set of real numbers is infinitely countable since it is the union of the rational and the irrational numbers [See Theorem 1 above]

(5) But this contradicts Theorem 4 that the real numbers are not infinitely countable.

(6) Therefore, we have a contradiction and we reject our assumption in step #3.

QED

References

- Countable Set, Wikipedia
- Countability of the Rational Numbers, Cut-The-Knot