Infinity: The Story So Far
(Revised: 2015-11-18)


Javier Regueira-Serrano

Introduction

Here we turn Hilbert's Hotel on its head. Instead of frantically shuffling infinitely many guests for one room to the next in Hilbert's mythical infinite hotel, we start with a leisurely walk through an ordinary and quite finite village.

A Walk Through a Finite Village

Starting at any house in this finite village, you set out to visit some or all of the houses there. You keep walking non-stop until you return to your starting point, visiting no house more than once.

Intuitively, it seems obvious that you could not avoid returning to your starting point under these conditions. You could, of course, return to your starting point without first going to every other house in the village. If you kept going, however, you would eventually run out of different places to go, and you would have to return to your starting point. Going anywhere else at that point would be going there more than once. (As you might imagine, in an infinite village, it might be possible to keep walking from house to house, never stopping and never returning to your starting point.)

How can we describe such paths mathematically? We can begin by letting S be the set of houses in the village. Each path that you can take through the village can be specified by:

1. Your starting pointing at house x0

2. A relation f on S that specifies the order in which you will visit the houses in S.

For every house in S on your path, you will go next to exactly one house in S. Therefore,  f is a function on S.


Figure 1:  Relation f is a function on S.

You cannot go to the same house more than once, i.e. function f is injective.


Figure 2:  Function f is injective.
 


Figure 3:  Example of a walk starting and finishing at house x0. House xn
is the last house visited before returning to house x0.

How do we specify that you must return to your starting point x0? Simply by requiring that there must exist a house xn in the village such that f(xn) = x0. (See figure 3, dashed line.)

Thus, we can define set S to be finite if and only if for all x0 and f, if x0 e S and f is an injective  function mapping S to itself, then there must exist xn e S such that f(xn) = x0.

In DC Proof format:

ALL(s):[Set(s) => [FiniteA(s)
<=> ALL(x0):ALL(f):[x0
e s
& ALL(a):[a
e s => f(a) e s]
& ALL(a):ALL(b):[a
e s & b e s => [f(a)=f(b) => a=b]]
=> EXIST(xn):[xn
e s & f(xn)=x0]]]]
 

An Equivalent Definition of Finite (Dedekind)

First introduced by Richard Dedekind, here is an equivalent and somewhat easier definition to work with:

ALL(s):[Set(s) => [Finite(s)
<=>
ALL(f):[ALL(a):[a e s => f(a) e s]
& ALL(a):ALL(b):[a
e s & b e s => [f(a)=f(b) => a=b]]
=> ALL(a):[a
e s => EXIST(xn):[xn e
s & f(xn)=a]]]    Formal Proof (55 lines)

In words, a set S is finite if and only if for all functions f mapping S to itself, if f is injective (1-to-1) , then f is surjective (onto).
 

The Infinite as the Negation of the Finite

In walking through an infinite village, there would be no guarantee, as above, that you would ever return to your starting point. Not surprisingly then, a set is infinite if and only it is not finite. Thus, we define Infinite as follows:

ALL(s):[Set(s) => [Infinite(s)
<=> EXIST(f):[ALL(a):[a
e s => f(a) e s]
& [Injection(f,s,s)
& ~Surjection(f,s,s)]]]]

where

Infinte(x) means x is infinite
Injection(f,x,y) means f is an injection (1-to-1) mapping set x to set y
Surjection(f,x,y) means f is an surjection (onto) mapping set x to set y

In words, a set S is infinite if and only if there exists a function f mapping S to itself that is injective (1-to-1) and not surjective (not onto).

An Equivalent, Numerically-based Definition of Infinite

Suppose we are given the set N, 0 e N and a successor function next that satisfy the Peano axioms. Then we can then develop the following equivalent definition of infinite:

ALL(s):[Set(s) => [Infinite(s)
<=> EXIST(f):[ALL(a):[a
e n => f(a) e s]
& ALL(a):ALL(b):[a
e n & b e n => [f(a)=f(b) => a=b]]]]]  Formal Proof (515 lines)

Or equivalently:

ALL(s):[Set(s) => [Infinite(s)
<=> EXIST(f):[ALL(a):[a
e n => f(a) e s]
& Injection(f,n,s)]]]

In words, a set S is infinite if and only if there exists an injective function (1-to-1) mapping N into S.
 

Countable Sets

A set S is said to countable if and only there exists an injective function mapping S into N. (Note similarities to previous definition.)

ALL(s):[Countable(s)
<=> EXIST(f):[ALL(b):[b
e a => f(b) e n]
& Injection(f,s,
n
)]]

A countable set S may be finite or infinite. If S is countable and infinite, there exists a bijection mapping S to N (see Cantor-Bernstein-Schroeder Theorem).

It is trivial to show that the set of natural numbers N must itself be countable.
 

Cantor's Theorem

Let P be the power set of S. (S may be finite or infinite.) Then there exists no surjective function mapping S onto P.

ALL(s):ALL(p):[Set(s)
& Set(p)
& ALL(c):[c
e p <=> Set(c) & ALL(d):[d e c => d e s]]
=> ALL(f):[ALL(a):[a
e s => f(a) e
p] => ~Surjection(f,s,p]]]  Formal Proof (53 lines)

Thus, we can never cover the entire power set P with images of S under any function mapping S to P. This suggests that the power set of a set S is always somehow larger than S itself, even if S is infinite. This, in turn, suggests that some infinities are larger than others.

It is easy to prove that the set of natural numbers N and its power set are both, by definition, infinite. Cantor's Theorem suggests that the power set of N, in particular is somehow larger than N itself.
 

The power set of N is uncountable

Let PN be the power set of the set of natural numbers N:

ALL(a):[a e pn <=> Set(a) & ALL(b):[b e a => b e n]]

Then PN is not countable:

~Countable(pn)  Formal Proof (25 lines)


Uncountable real numbers in the interval [0, 1)

A formal definition of the set of real numbers is beyond the scope of this article, but we can make use of certain well-accepted properties of the real numbers and decimal expansions to argue that there must be uncountable real numbers in the interval [0, 1).
Assumption 1
Here we assume that a decimal point followed by any infinite string of digits (except the string of all 9's) represents a unique real number in the interval [0, 1). Here is a finite list of examples:
.000000...
.100000...
.099999....
.333333...
.121212...
.01001000100001....
We can represent each of these decimal numbers in turn by an infinite string of digits – simply drop the leading decimal point.
Assumption 2
Note that, from this list, we have .1000000... = .0999999.... but 1000000... and 0999999... are quite different strings. We don't want to count the same number (with two different representations) more than once. So, we will further assume that we need not consider strings of digits that end in an infinite string of 9's, e.g. we can exclude from consideration strings like 0999999... or 459999999...
Thus, we will consider only the set T' of infinite strings d1 d2 d3 .... such that if di = 9 then there exisits another dj 9 such that j > i.
Assumption 3
We also assume that different elements of T' correspond to different real numbers in the interval [0, 1).
The Proof
We can formally prove that T' is uncountable [1]. We begin by assuming the existence of an arbitrary function g mapping N to T' and prove by using Cantor's so-called anti-diagonal argument that g cannot ever be a surjection. We can construct the anti-diagonal string h such that the kth position of h is 1 if the kth position of g(k) is 0; 1 otherwise. Thus h will be an infinite string of 0's and 1's. Clearly h is an element of T', and it is not in the range of g. Thus T' would have to be uncountable.

See formal proof in DC Proof 2.0 format (798 lines).

Conclusion
Based on the above three assumptions then, we can reasonably argue informally that, since there uncountable strings in T' (formally proven), there must be uncountable real numbers in [0, 1), with one real number for each string in T' and different strings going to different real numbers.

Footnotes
1. In the interests of brevity, the above proof uses digits in base-3 instead of the usual base-10 . With sufficient time and space, the argument should be extendable to any base greater than two. Using base-10 digits, the proof could easily be more than twice as long since, at several points in the proof, separate cases must be considered for each possible value of digit. For base-10, we would have to consider 10 different possibilities. For base-3, we need only consider three possibilities.

 

Home