A deep take on countability, cardinality and ordering.
I’ve been teaching CMSC250, Discrete Mathematics, over the last years in CS UMD. During the Fall 2017 semester, I typed a more philosophical than mathematical post on Countability, Cardinality and Ordering, which I’m repeating here for the community’s sake.
Before we begin, I would like to remind you of a definition that we had presented much earlier in the semester, I believe during an online quiz: A set S is dense if between any two elements of it, one can find another element. Note something interesting: only ordered sets can be qualified as dense or not! Technically, we had not presented the notion of an ordered set when we discussed dense sets, but it is intuitive enough that people can understand it.
Countability
We say that any enumerable set is countable. Enumerable, mathematically, means that we can find a bijection from the non-zero naturals to the set. Intuitively, it means “you start from somewhere, and by sequentially making one step, no matter how long it takes, you are guaranteed to reach every single element of the set in finite time”. Whether this finite time will happen in one’s lifetime, in one’s last name’s lifetime, or before the heat death of the universe, is inconsequential to both the math and the intuition. Clearly, this is trivial to do for either the non-zero naturals or the full set of naturals: you start from either 1 or 0, and then you make one step “forward”.
However, we also saw in class that this is possible to also generalize for the full set of integers: we start from 0 and then start hopping around and about zero, making bigger hops every time. Those hops are our steps “forward”.
Those results are probably quite intuitive to you by now, and I feel that the reason for this might that both N and Z are non-dense sets. There are no naturals or integers between n and n+1 (n∈N or Z).
Let’s stray away from Q for now and fast-forward to R . We have already shown the mathematical reason (Cantor’s diagonalization) for which the set of reals is uncountable. But what’s the intuition? Well, to each their own, but here’s how I used to think about it as a student: Suppose that I start from zero just to make things easier with respect to my intuitive understanding of the real number line (I could’ve just as well started with e−8 if I so desired).
Then, how do I decide to make my step forward? Which is my second number? Is it 0.1? Is it −0.05? But, no matter which I pick as my second number, am I not leaving infinitely many choices in between, rendering it necessary that I recursively look into this infinite interval? Note that I have not qualified “infinite” with “countably infinite” or “uncountably infinite” yet. This was my personal intuition as a Discrete Math student several years ago about why R is uncountable: Even if you assume that you can start from 0, there is no valid ordering for you to reach the second element in the sequence of reals! Therefore, such a sequence cannot possibly exist!
But hold on a minute; is it not the case that this argument can be repeated for Q? Sure it can, in the sense that between, say, 0 and 12, there are still infinitely many rationals. It is only after we formalize the math behind it all that we can say that this is a countable infinity and not an uncountable one, as is the case of the reals. But still, we have to convince ourselves: why in the world is it that the fact that every one of these infinite numbers can be expressed as a ratio of integers make that infinity smaller than that of the reals?
Here’s another intuitive reason why we will be able to scan every single one of these numbers in finite time. Remind yourselves of the “snaking pattern” that we applied to qualitatively show a bijection from Q to N:
Source: homeschoolmath.net
Make the crucial observation that every one of the diagonals scans fractions where the sum of the denominator and the numerator is static! The first diagonal scans the single fraction (11) where the sum is 2. The second one scans the fractions whose denominator and numerator sum is 3 (12,21). In effect, the ith diagonal scans the following fractions:
{ab ∣(a,b∈N≥1)∧(a+b=i+1)}
For those of you that know what equivalence classes are, we can then define Q>0 as a union of equivalence classes, each defined by a particular selection of the integer i:
Q>0=⋃i∈N{ab ∣(a,b∈N≥1)∧(a+b=i+1)}
Let’s see this in action…
Q>0={11,12,21,13,22,31,…}
Note that essentially, with this definition, we have defined a bijection from N≥1×N≥1 to Q>0. We know that N≥1×N≥1 is countable, so we now know Q>0 is also countable! 🙂A similar argument can be made about Q<0, with one row (or column) of negative integers and one column (resp. row) of positive integers in the snaking pattern.
Let’s constrain ourselves now to the original challenge that we are faced with: we have selected 0 as our first element in the enumeration of both Q and R (the latter is assumed to exist), and no matter which our second element is (say it’s 12 ), we have infinitely many elements in both sets between 0 and 12. But now we know that those infinities are different: in the case of Q, we know for a fact that we will reach all of those fractions whose decimal values are in (0,0.5) at some point in the future, no matter how far long into the future. In the case of R, there is no such enumeration: any enumeration we define will still leave an… uncountably infinite gap between any two elements in “sequence”.
Remember how in our lecture on Algebraic and Transcendental numbers, we gave only three examples of numbers in TN, yet the fact that TN is uncountable when ALG is countable guarantees that there are “many more” Transcendental numbers than Algebraic? Same thing applies here with the rationals and irrationals: given any interval of real numbers (r1,r2), there are many more irrationals than rationals inside that interval... If you define a system of whole numbers (integers), there are many more quantities that you will not be able to express as a ratio of integers. That’s why back in the day (300 B.C) when Euclid proved that √2 is not expressible as such a ratio ab (or, more accurately, that 2 cannot be expressed as the square of a ratio (ab)2) his result was so unintuitive; those Hellenistic people did not have rulers. They did not have centimeters, inches or other accepted forms of measurement. The only thing they had were shoestrings, or planks of wood which they put in line and “saw” that they were the same length, and then they measured everything else as the ratio of such “whole” lengths.
Cardinality
Recall something that we said when we were discussing the factorial function and its combinatorial interpretations when applied on positive integers. Bill’s explanation (note: Bill Gasarch, my collaborator in CS ) of why 0!=1 was purely algebraic: If it were , then, given the recursive definition n!=n⋅(n−1)! for n≥1, every n! would be 0, rendering it a pretty useless operation. My explanation was combinatorial: we know that if we have a row of n marbles, there are n! different ways to permute them, or n! different orderings (permutations) of those marbles. When there are no marbles, so n=0, there is only one way to order them: do nothing, and go watch Netflix.
Let’s stick with Bill’s interpretation for a moment: the fact that some things need to be defined in order to make an observation about the real world work. In this case, the real world is defined as “algebra that makes some sense”. My explanation is more esoteric. You could say: “What do you mean there’s only one way to arrange zero things? I don’t understand, if there are zero things and there’s nothing to do, shouldn’t there be, like, 0 ways to arrange them?”. So, let’s stick with Bill’s interpretation to explain something that I attempted to explain to a group of students after our first lecture this semester: Why do negative numbers even exist?
Here’s one such utilitarian explanation: Because without negative numbers, Newtonian Physics, with their tremendous application in the real world, would not work. That is, the model of Newtonian Kinematics with its three basic laws, which has been empirically proven to describe very well things that we observe in the real world, needs the framework of negative numbers in order to, well, work. So, if you’re not ok with the existence of negative numbers, you had better also be able to describe to me a framework that explains a bunch of observations on the real world in some way that doesn’t use them. For example, you probably all remember the third law of Newtonian motion: For every action →F, there exists an equal and opposite reaction →−F. Recall that force is a vectoral quantity since it is the case that →F=m⋅→a, and acceleration is clearly vectoral, as the second derivative of transposition →x.
The only way for Newton’s third law of motion to work is if →F+→−F=→0. This is only achievable if the two vectors have the same magnitude but exactly opposite directions. No other way. Hence the need to define the magnitudes as follows:
||→F||=12⋅m⋅a2,||→−F||=−12⋅m⋅a2
and the necessity for negative numbers becomes clear. Do you guys think the ancient Greeks or Egyptians cared much for negative numbers? They were building their theories in terms of things they could touch, and things that you can touch have positive mass, length, height…
Mathematics is not science. It is an agglomeration of models that try to axiomatize things that occur in the real world. For another example, ZFC Theory was developed in place of Cantorian Set Theory because Cantorian Set Theory can lead to crazy things such as Russel’s Paradox. Therefore, ZFC had to add more things to Set Theory to make sure that people can’t do crazy stuff like this. If we discover contradictions with the real world given our mathematical model, we have to refine our model by adding more constraints to it. Less constraints, more generality, potential for more contradictions. More constraints, less generality, less contradictions, but also more complexity.
So when discussing the cardinality of N and Z and finding it equal to ℵ0, we are faced with a problem with our model: the fact that N⊂Z (I have used the notation of proper subset here deliberately). Now, I just had a look at our cardinality slides, and it is with joy that I noticed that we don’t use the subset / superset notation anywhere. That’s gonna prove a point for us: that when studying infinite cardinalities, the notion of subset (proper or not) is no longer appropriate or applicable.
So, back to the original problem: intuitively understanding why the hell N and Z have the same cardinality when, if I think of them on the real number line, I clearly have N⊂Z:
$$\underbrace{\dots ,−4,−3,−2,−1, \underbrace{0,1,2,3,4\ dots}_{\mathbb{N}}}_{\mathbb{Z}} $$
The trouble here is that we have all been conditioned from childhood to think about the negative integers as “minus the corresponding natural”. This conditioning is not something necessarily bad: it makes a ton of sense when modeling the real world, but when comparing cardinalities between infinite sets, that is, sets that will never be counted entirely in finite time, we distance ourselves from the real world a bit, so we need a different mathematical model. To that end, let’s build a new model for the naturals. Here are the naturals under our original model:
0,1,2,3,…
This digits that we have all agreed to be using have not been around forever. The ancient Greeks used lowercase versions of their alphabet: α,β,γ,δ,ϵ,στ′,ζ,…,ω to form a total of 25 digits, while the Romans used a subset of their alphabet “stacked” in a certain way: I,II,III,IV,V,VI,…,X,XI,…. These “stacked” symbols cannot be really called “digits” the way that we understand them, especially since new symbols appear long down the line (C,M, etc). The modern decimal symbols (0,1,2,…,9) we actually owe to the Arabic Renaissance of the early Middle Ages.
The point is that I can rename every single one of these numbers in a unique way and still end up with a set that has the exact same properties (e.g closure of operations, cardinality, ordinality) as N. This is formally defined as the Axiom of Replacement. So, let’s go ahead and describe N by assigning a random string for every single number, assuming we have some method to ensure that no string is inserted twice (i.e every “number” is unique, like in N):
foo,bar,otra,zing,tum,ghi,…
Which corresponds to our earlier
0,1,2,3,4,5,…
Cool! Now the axiom of replacement clearly applies to Z as well, so I will rewrite
…,−5,−4,−3,−2,−1,0,1,2,3,4,5,…
into:
…,qwerty,forg,vri,zaq,nit,bot,ware,yio,bunkm,ute,kue,…
Call these “transformed” sets Nnew and Znew respectively. Under this encoding, I believe it’s a lot more obvious that Nnew⊄Znew in the general case. In fact, Nnew⊂Znew is so not-gonna-happenish hat its probability is not even axiomatically defined. Therefore, now we can view N and Z as infinite lines floating around space, lines that we have to somehow put next to each other and see whether we can line them up exactly. If you tell me that even under this visualization, the line that represents Znew is infinite in both directions, whereas that of Nnew has a starting point (0),then I would tell you that I can effectively “break” the line that represents Znew in the “middle” (0) and then mix the two lines together according to the mapping that corresponds to:
0,1,−1,2,−2,3,−3,…
Now we no longer have the pesky notation of the minus sign, which makes us want to scream “But the naturals are a subset of the integers! Look! If we just take a copy of the naturals and put a minus in front of them, we have the integers!”. We only have two infinite lines, that start from somewhere, extend infinitely, and it is up to us to find a 1-1 and onto mapping between them. That is, it is up to us find a 1-1 mapping between:
foo,bar,otra,zing,tum,ghi,…
and
bot,ware,nit,yio,zaq,bunkm,…
Note that I re-ordered the previous encoding …,qwerty,forg,vri,zaq,nit,bot,ware,yio,bunkm,ute,kue,… according to our familiar “hopping” mapping into bot,ware,nit,yio,zaq,bunkm,…
Under this visualization, it makes a lot of sense to try to estimate if the two sets have the same cardinality and, guess what, they do! :)
Not much else to say on this topic. We can apply the axiom of replacement several times to prove, for example, that the cardinality of the integers, ℵ0, is also the cardinality of N×N, Q, etc. It is only when we start considering sets such as R,P(N) and {0,1}ω that this idea that we can hold two infinite lines in space fails.
Ordinality
There’s not much to say here except that the easiest way to understand how an order differs from a set is to consider an order exactly as such: a particular ordering of elements! Think in terms of “first element less than second less than third less than ... “, in the simplest way possible. It is then that we can prove rather easily that ω<η<ζ.
Things only become a bit more complicated when considering the ordering ω+ω:
0<12<34<56<⋯<1<32<43<⋯<2<…
Please note that this ordering is clearly not the same as η, the ordering of Q. Between the first and the second element, for instance, there are countably many infinite rationals: 1100,25,…,37,… which are not included in the ordering!
Finally, notice the meaning of “incomparable” orderings: a pair of orderings will be called incomparable if, and only if:
(α⪯̸β)∧(β⪯̸α)
So please realize that this is not the same as saying, for instance, β⊀α!
