**Infinity:
The Story So Far**

(Revised: 2015-11-18)

**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 toreturn to your starting point. Going anywhere else at that point would be going there more than once. (As you might imagine, in aninfinitevillage, 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

Sbe 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 x

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

For every house in

Son your path, you will go next to exactly one house inS.Therefore,fis a function onS.

Figure 1: Relationfis a function onS.You cannot go to the same house more than once, i.e. function

fis injective.

Figure 2: Functionfis injective.

Figure 3: Example of a walk starting and finishing at housex_{0}. Housex_{n}

is the last house visited before returning to housex_{0}.How do we specify that you must return to your starting point x

_{0}? Simply by requiring that there must exist a house x_{n}in the village such thatf(x_{n}) = x_{0}. (See figure 3, dashed line.)Thus, we can define set S to be finite if and only if for all x

_{0}and f, if x_{0 }e_{ }S and f is an injective function mapping S to itself, then there must exist x_{n}e S such that f(x_{n}) = x_{0}.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 s => f(b) e n]

& Injection(f,s,n)]]

A countable set

Smay be finite or infinite. IfSis countable and infinite, there exists a bijection mappingStoN(see Cantor-Bernstein-Schroeder Theorem).It is trivial to show that the set of natural numbers

Nmust itself be countable.

Cantor's Theorem

Let

Pbe the power set ofS. (Smay be finite or infinite.) Then there exists no surjective function mappingSontoP.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

Pwith images ofSunderanyfunction mappingStoP. This suggests that the power set of a setSis always somehowlargerthanSitself, even ifSis infinite. This, in turn, suggests that some infinities are larger than others.It is easy to prove that the set of natural numbers

Nand its power set are both, by definition, infinite. Cantor's Theorem suggests that the power set ofN, in particular is somehow larger thanNitself.

The power set of

Nis uncountableLet

PNbe the power set of the set of natural numbersN:ALL(a):[a e pn <=> Set(a) & ALL(b):[b e a => b e n]]

Then

PNis 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 1Here 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...We can represent each of these decimal numbers in turn by an infinite string of digits – simply drop the leading decimal point.

.100000...

.099999....

.333333...

.121212...

.01001000100001....Assumption 2Note 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 setT'of infinite stringsd_{1}d_{2}d_{3}.... such that ifd_{i}= 9 then there exisits anotherd≠ 9 such that_{j}j>i.Assumption 3We also assume that different elements ofT'correspond to different real numbers in the interval [0, 1).The ProofWe can formally prove thatT'is uncountable [1]. We begin by assuming the existence of an arbitrary functiongmappingNtoT'and prove by using Cantor's so-calledanti-diagonal argumentthat g cannot ever be a surjection. We can construct the anti-diagonal stringhsuch that thekposition of^{th}his 1 if thekposition of^{th}g(k) is 0; 1 otherwise. Thushwill be an infinite string of 0's and 1's. Clearlyhis an element ofT', and it isnotin the range ofg. ThusT'would have to be uncountable.See formal proof in DC Proof 2.0 format (798 lines).

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

Footnotes1. 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.