Are there really as many rational numbers as natural numbers? You might answer “Yes” but a better answer would be “It depends on the underlying order relation you use for comparing infinite sets”. In my opinion there really is no reason why we should consider Cantors characterization of cardinality as the only possible one and there is also a total order relation for countable sets where proper subsets are also strictly smaller than their supersets. In this article I want to present you one of them.

Introduction to Cantors concept of cardinality

The main problem Georg Cantor solved with his concept of cardinality was to provide a way for comparing infinite sets. If one just considers finite sets it is easy to compare them: One just has to count their elements and afterwards has to compare the counted number of elements. But it is not possible to count the elements of infinite sets (or better to say: there is no obvious way for doing it). So the problem was unsolved until Greorg Cantor and others established an order relation on arbitrary sets, even infinite ones, in the late nineteenth century.

Here is a possible way, how Cantor might have found his ideas: First he could have collected properties for comparing finite sets \( A \) and \( B \):

1. \( A \) is strictly smaller than \( B \), if and only if the number of elements of \( A \) is less than the number of elements of \( B \).
2. If \( A \) is a proper subset of \( B \), then \( A \) is also strictly smaller than \( B \)
3. If there is an injective function from \( A \) to \( B \), than the cardinality of \( A \) is less or equal than the cardinality of \( B \).
4. ...

The first property would be the standard definition for comparing finite sets. Unfortunately it cannot be extended to infinite sets because there is no obvious way to count their elements.

But lets have a look on property three “If there is an injective function from \( A \) to \( B \), than the cardinality of \( A \) is less or equal than the cardinality of \( B \)”. On the on hand it provides a proper definition for cardinality of finite sets and on the other hand is also extendable to infinite sets because the concept of “injective functions“ is well defined on functions between infinite sets too. Cantor could have seen this and therefore stated for all (finite and infinite) sets \( A \) and \( B \):

If there is an injective function from \( A \) to \( B \), than the cardinality of \( A \) is less or equal than the cardinality of \( B \).

This is Cantors famous definition for the cardinality of infinite sets and also the starting point of his work. Now he could find famous theorems like that there are as many rational as natural numbers.

The statement that \( \Q \) and \( \N \) have the same cardinality shows also that by extending the concept of cardinality to infinite sets not all properties we know from comparing finite sets can be preserved. If one wants to have the above property three (Cantors definition of cardinality) he has to drop the second property (“proper subsets are strictly smaller”) because the third property imply the existence of proper subsets which have the same cardinality like their subsets (for example \( \N \) and \( \Q \)).

But is Cantors way to extend cardinality the only one? No, as you already might expect from the articles title. But how might another extension look like?

Lets have a look again on the standard definition for comparing finite sets. In the time of Cantor the main problem was, that there were nothing like infinite natural numbers. But meanwhile non-standard analysis was invented, a theory where infinitesimal small and big numbers are defined. There are also hypernatural numbers which provide a extension of \( \N \) to infinite natural numbers.

But before I want to show you my idea of a new order relation based on hypernatural numbers I want to give you a short introduction to those numbers. You might skip it, if you are already familiar with them.

Introduction to hypernatural numbers

Hypernatural numbers are hyperreal numbers and are constructed by extending the set of natural numbers \( \N \) to the set of hypernatural numbers \( \N^* \). This construction is somehow similar to the extension of the set of rational numbers \( \Q \) to the set of real numbers \( \R \) with Cauchy sequences.

Construction of hypernatural numbers

First we consider the set of natural numbers \( \N \) and create the set \( S \) of all sequences \( (x_n)_{n\in\N} \) of natural numbers from it:

Step 1: \( S := \{ (x_n)_{n\in\N}\,|\, \forall n\in\N: x_n \in \N \} \)

We want to represent hypernatural numbers by sequences of natural numbers. At the end the constant sequence \( (1, 1, 1, \ldots) \) shall represent the number 1 and the sequence \( (1, 2, 3, 4, \ldots ) \) will represent an infinite hypernatural.

But we have some problems. For example, which number shall be represented by the sequence \( (1, 2, 1, 2, 1, \ldots ) \)? Because the sequence is bounded we might want it to represent a finite number. But shall it be 1 or 2?

The solution is to define an equivalent relation on \( S \). We will say that two sequences \( (x_n)_{n\in\N} \) and \( (y_n)_{n\in\N} \) are equivalent, if and only if \( x_n = y_n \) for almost all \( n \in \N \). But we have to extend the fragment “for almost all \( n \in \N \)”, you might already know from calculus, to a concept which fulfills the following properties:

1. If \( A(n) \) implies \( B(n) \) and \( A(n) \) is true for almost all \( n \in \N \) than also \( B(n) \) is true for almost all \( n \in \N \).
2. If \( A(n) \) and \( B(n) \) are two propositional formulas which are true for almost all \( n \in \N \), then also the conjunction \( A(n) \land B(n) \) is true for almost all \( n \in \N \).
3. If \( A(n) \) is true for a cofinite set of natural numbers (for a set \( \{ n \ge k \,|\, n\in\N \} \) with a given \( k \in \N \)), then \( A(n) \) is true for almost all \( n \in \N \).
4. For all statements \( A(n) \) either \( A(n) \) or \( \neg A(n) \) is true for almost all \( n \in \N \).

From the above properties we can conclude that the sequence \( (x_n)_{n\in\N} = (1, 2, 1, 2, 1, \ldots ) \) will either represent 1 or 2. From the fourth property follows that either \( x_n = 1 \) or \( x_n \neq 1 \) is true for almost all \( n \in \N \). In the second case we have \( x_n = 2 \) for almost all \( n \in \N \) because \( x \neq 1 \Rightarrow x_n = 2\) (property 3).

I do not want to go deep in the theory but there is a possibility to establish such a concept “for almost all \( n \in \N \)” by using ultrafilters. Unfortunately there is just a proof which uses Zorn's lemma now and therefore the axiom of choice. As a consequence we now know that there exists a concept “for almost all \( n \in \N \)” with the above properties but we cannot say for every propositional formulas \( A(n) \) whether it's true or false for almost all \( n \in \N \). For example we can derive that \( (1, 2, 1, 2, 1, \ldots ) \) will represent 1 or 2 but we cannot say which number. Okay I have to be more precise: You can find a concept “for almost all \( n \in \N \)” where the sequence will represent 1, but nobody has found a concept yet where you can decide for all pairs of sequences whether they are equivalent or not. And there are also many of them: I am not sure but I think the set of all such concepts is uncountable.

Lets come back to our construction of hypernaturals. In non-standard analysis it is not necessary to know how the concept “for almost all \( n \in \N \)” really looks like. It is just necessary that it fulfills the above listed properties. We get the set of hypernaturals by creating the partition of \( S \) in the equivalence classes of the relation “\( (x_n)_{n\in\N} \) and \( (y_n)_{n\in\N} \) are equivalent, if and only if \( x_n = y_n \) for almost all \( n \in \N \)”:

Step 2: \( \N^* = {S/{\sim}} \) with \( (x_n)_{n\in\N} \sim (y_n)_{n\in\N} \Leftrightarrow x_n = y_n \text{ for almost all } n \in \N \)

So hypernatural numbers are equivalence classes \( \left[(x_n)_{n\in\N}\right] \) of sequences.

Properties of hypernatural numbers

A statement \( A(x) \) of the hypernatural number \( x=\left[(x_n)_{n\in\N}\right] \) is defined to be true, if the statement \( A(x_n) \) is true for almost all \( n \in \N \). So we have \( \left[(n)_{n\in\N}\right] < \left[(2n)_{n\in\N}\right] \) because the statement \( n < 2n \) is true for almost all \( n \in \N \). So properties of natural numbers transfers to hypernaturals.

An order relation on \( \Pot(\N) \) based on hypernatural numbers

As I mentioned already there is an order relation on the power set of \( \N \) where proper subsets are also strictly smaller than their supersets. Because there is always an bijective function from \( \N \) to an infinite countable set, this relation can be easily defined on any arbitrary power set of an infinite countable set. As I also mentioned above I will somehow count the elements of a set, even infinite ones, by using hypernatural numbers.

Definition of the order relation

Let be \( M \) an arbitrary set of natural numbers. How can we count its elements? Lets model a process of counting. Because we somehow have to remember the current number of already counted objects we store this information in the variable \( x \). At the beginning we have \( x = 0 \) because we haven't counted any objects. First we look whether the number 1 is an element of \( M \) or not (in this article I want to define 1 as the first natural number). If it is an element of \( M \) we add 1 to \( x \) and in the over case we do not change it. Now we add 1 to \( x \), if 2 is an element of \( M \) and do nothing if \( M \) does not contain 2. Then we have a look at 3 and so on and so on...

So we change \( x \) over the time. After having answered whether the number \( n \) is an element of \( M \) or not and eventually having added 1 to \( x \) we have a new actual value \( x_n \) stored in the variable \( x \). This gives us a sequence \( (x_n)_{n\in\N} \). For example for the set \( M = \{ 2k \,|\, k\in\N \} \) of all even numbers we have:

For the set \( \{ 3, 5, 6 \} \) the sequence is:

As I showed you in the above section every sequence of natural numbers represent a hypernatural. I want to define the hypernatural of the above sequence to be the number of elements of the considered set:

Definition: Let \( M \subseteq \N \) be an arbitrary set of natural numbers and let \( \chi_M(n) := \begin{cases} 1 & ; n \in M \\ 0 & ; n \notin M \end{cases} \) be the characteristic function of \( M \). In this article the hypernatural cardinality \( |M|\) (number of elements) of the set \( M \) shall be the hypernatural number \( \left[ \left( \sum_{n=1}^\infty \chi_M(n) \right) \right] \) which is the hypernatural represented by the sequence \( (\chi_M(1), \chi_M(1) + \chi_M(2), \chi_M(1) + \chi_M(2) + \chi_M(3), \ldots ) \).

We now compare two sets \( A \) and \( B \) by comparing the hypernaturals \( |A| \) and \( |B| \):

Definition: Let be \( A \) and \( B \) two arbitrary sets of natural numbers. We say that \( A \) has less or the same number of elements as \( B \), if and only if the hypernatural cardinality \( |A| \) of \( A \) is less or equal to the hypernatural cardinality \( |B| \) of \( B \). In this case we write \( A \le B \). The relations “\( A \) has strictly less elements than \( B \)”, “\( A \) and \( B \) have the same size” and so on are analogously defined.

For example there are less even numbers than natural numbers in our theory because the hypernatural cardinality of the set of even numbers \( [(0,1,1,2,2,\ldots)] \) is strictly smaller than the hypernatural cardinality of \( \N \) which is \( [(1,2,3,4,\ldots)] \).

Properties of the order relation

Our relation is a total preorder

First we have to proof that the above relation really is an order relation. We will see, that it is a total preorder, a reflexive, transitive and total relation which is not antisymmetric:

Proof that \( A \le B \) is reflexive: If \( A = B \) then \( |A| = |B| \) and therefore \( A \le B \).

Proof that \( A \le B \) is transitive: Let \( A \le B \) and \( B \le C \). By definition we have \( |A| \le |B| \) and \( |B| \le |C| \). Because the order relation on the set of hypernaturals is transitive, we have \( |A| \le |C| \) and thus \( A \le C \).

Proof that \( A \le B \) is a total relation: Let \( A \) and \( B \) be two sets of natural numbers. Because the order relation on the hypernaturals is a total relation we have either \( |A| \le |B| \) or \( |B| \le |A| \). Consequently it is either \( A \le B \) or \( B \le A \) which proofs that our considered relation is a total relation.

The above three proofs show us that our relation is a total preorder.

Our order relation extend the standard definition of comparing finite sets

Know lets have a look whether our order relation really extend the known order relation on finite sets. Here we have to proof that the hypernatural cardinality of a finite set with \( n \) elements is \( n \).

Step 1: Proof that \( |A| = n \) for every finite set \( A \) with \( n \) elements. Le \( A \) be a finite set of natural numbers with \( n \) elements. Than \( A \) has a maximum element \( \max(A) \). The sum \( \sum_{k=1}^m \chi_A(k) \) will be \( n \) for all \( m \) greater or equals to \( \max(A) \). Thus the equation \( \sum_{k=1}^m \chi_A(k) = n \) is true for a cofinite set of \(m\)'s and therefore \( \sum_{k=1}^m \chi_A(k) = n \) for almost all \( m \in \N \). From the definition of hypernaturals we can conclude that the sequence \( \left( \sum_{k=1}^m \chi_A(k) \right)_{m\in\N} \) will represent the number \( n \) which means that \( |A| = n \).

Step 2: Proof that \( A \le B \) extend the standard comparing of finite sets. Let \( A \) and \( B \) be two finite sets of natural numbers with \( n_A \) respectively \( n_B \) elements. In the standard definition we say that \( A \) is less or equal sized than \( B \), iff \( n_A \le n_B \). Because \( |A| = n_A \) and \( |B| = n_B \) we have \( n_A \le n_B \) if and only if \( |A| \le |B| \).

Because there are many different sets with the same finite number of elements our total preorder is not antisymmetric.

Proper subsets are strictly smaller

Now I want to present you the grand final, the main property which distinguishes our order relation from Cantors characterization of cardinality.

Proof that every proper subset is strictly smaller: Let be \( A \subsetneq B \subseteq \N \). Then there is an \( m \in B \) which is no element of \( A \). For all \( n \ge m \) we have \( \sum_{k=1}^n \chi_A(k) < \sum_{k=1}^n \chi_B(k) \) and therefore \( \sum_{k=1}^n \chi_A(k) < \sum_{k=1}^n \chi_B(k) \) for almost all \( n \in \N \). This proofs \( |A| < |B| \) as we want to show.

Additional Notes

In this article I showed you a way to compare infinite sets so that proper subsets are also strictly smaller in contradiction to Cantors characterization of cardinality you learned at university. The conclusion I draw is that nothing in mathematics shall be considered as the only possible definition. Of course it is easier for us to formulate a theory as it is the only possible one (and I also do it often) but there are always other solutions, other ways of modeling etc. So open your mind for new theories of analysis or new theories of probability. Are you already familiar with the basic ideas of non-standard analysis?!