Cardinal Numbers
Nyaa!~
I have too many drafts :c
Hi everyone! Today, we are going to learn about infinite cardinal numbers! I hope this'll be fun! ^^
I was also planning to explain something about the axiom of choice, but I decided that it's better if that becomes its own blog-post.
So, first: what is a cardinal number?
✦ Motivation ✦
Well, cardinal numbers are numbers that represent the size of a set of things. For example, {owo, uwu} is a set of cardinality 2: it has two elements, owo and uwu.
However, we can't simply count the elements of a set to figure out its cardinality. What if we come across a set like {0, 1, 2, 3, ...}? I mean... you can try counting the elements, but it's gonna take you a veryy long time.
So! What do we do?
Well,,, first, observe that cardinals can't exist in a vacuum. If we say that {owo, uwu} has cardinality 2, what does that actually mean? ‘2’ is just a symbol we use to describe the cardinality of {owo, uwu}, but has no meaning on its own. Where it gets interesting is when we compare the cardinality of {owo, uwu} to {10, 3}: they're the same! Now, that is interesting.
So, we use ‘2’ to describe the cardinality of sets like {owo, uwu} and {10, 3}, and we use this symbol so we can more easily recognize when two sets have the same cardinality, without having to search for statements like “this set has the same size as this other set” exhaustively having to apply transitivity of (cardinal) equality.
But what makes {owo, uwu} and {10, 3} so similar that they can be considered ‘equinumerous’?
Well,,, observe that the cardinality of a set doesn't change when we replace some of the elements with other elements: the cardinality of a set is completely independent from what the members of that set actually are. If we have a set like {catgirl lucy, my dearest friend, Semi}, and I replace ‘my dearest friend’ with ‘my worst enemy’ (so we get {catgirl lucy, my worst enemy, Semi}), the size of the set doesn't change!
I hope these two observations are enough to motivate the definition of a cardinal number:
～ Cardinal Equality ～
[Definition] Two sets, A and B, have the same cardinality, denoted |A| = |B|, iff there exists a bijection f: A → B.
There are three kinds of functions that will be important to us in this blog-post:
An injection is a function f: A → B from some set A to some set B so that, for all x,y ∈ A, if f(x) = f(y), then x = y.
A surjection is a function f: A → B from some set A to some set B so that, for all y ∈ B, there is some x ∈ A so that f(x) = y.
A bijection is a function f: A → B from some set A to some set B that is both an injection and a surjection.
A bijection thus pairs every element of A with a unique element of B, and vice versa.
So now, we need to show that this definition of cardinal numbers actually makes sense. I.e., that it is an equivalence relation:
An equivalence relation is a relation ~ such that:
~ is reflexive: x ~ x for all x
~ is symmetric: if x ~ y then y ~ x
~ is transitive: if x ~ y and y ~ z, then x ~ z
...
What?
OK, fine... I'll give you the answer: reflexivity of cardinal equality is witnessed by the identity function on a set, symmetry is from the functions inverse and transitivity comes from composition. I do want you to start thinking about how to solve these problems in the future!
Given an equivalence relation ~ on some class C, we can define a function F with domain C so that, for all x,y ∈ C, F(x) = F(y) iff x ~ y. If ~ fails one of the conditions of an equivalence relation, such a function does not exist.
This time, I will leave you to ponder why~
So! We can choose some function |·| that maps sets X to objects |X| such that |X| = |Y| iff X and Y have the same cardinality, the choice of mapping doesn't really matter.
The cardinality of ℕ, the set of natural numbers, is denoted ℵ₀ (‘aleph-nought’), this is also the cardinality of ℤ, the set of integers, and ℚ, the set of rational numbers. ℵ₀ is an infinite cardinal (not 0, 1, 2, 3, etc), but it isn't the only infinite cardinal!
|P(ℕ)| = 𝔠, the continuum, is another infinite cardinal. It is the cardinality of the set of subsets of ℕ, i.e. the set of sets of natural numbers.
Why are these cardinals different? Well, given some function f: ℕ → P(ℕ), try to find some subset of ℕ that is not in the range of f~ Thus, show that f cannot be surjective!~
Here is a hint for when you get stuck: if there is some x for which A and B disagree on whether they contain it (x is in A but not in B, or x is in B but not in A), then A and B are different.
Now, that we have gone over the basics of cardinal equality, let's look at something more exciting~ cardinal comparison:
⊰ Cardinal Comparison ⊱
[Definition] For two sets A and B, |A| ≤ |B| iff there exists an injection f: A → B.
≤ is a partial order on cardinal numbers:
≤ is reflexive: x ≤ x for every cardinal x
≤ is transitive: if x ≤ y and y ≤ z, then x ≤ z
≤ is antisymmetric: if x ≤ y and y ≤ x, then x = y
Reflexivity and transitivity are easy exercises for the reader~ (the proof is literally just the same as refl and trans for cardinal equality :p). Antisymmetry, on the other hand, is a lot more difficult!
That cardinals are antisymmetric is known as the Shröder-Bernstein theorem. The proof may be hard to follow, so good luck! :D
Let A and B be sets and suppose there are injections f: A → B and g: Β → A. We want to define a bijection h: A → B.
We can see that f and g form chains a₁ ↦{f} b₁ ↦{g} a₂ ↦{f} b₂ ↦{g} ... alternating between elements of A and elements of B. Since g is an injection, for every a ∈ A, we either have that it comes from some b (i.e. g(b) = a), or from nothing. The same holds for f. So every element in A and B belongs to a unique chain ... ↦ * ↦ * ↦ ... defined by f and g. Some of these chains have a sudden start (i.e. some a ∈ A or some b ∈ B that doesn't have an inverse under g or f), and some of these chains are infinite.
For a ∈ A, we can define h(a) based on what kind of chain a belongs to. If the chain a belongs to starts in A, we can set h(a) = f(a). If the chain a belongs to starts with some element in B, we can set h(a) = g⁻¹(a) (i.e. we set h(a) to an element b in B such that g(b) = a). If a belongs to a chain that goes infinitely far left, we do whatever. I'm just going to choose h(a) = f(a).
I'll leave it to you to verify that h is indeed a bijection.
We can also define strict comparison:
[Definition] For cardinals x and y, x < y iff x ≤ y and x ≠ y.
Since ℵ₀ ≠ 𝔠, as shown in the previous chapter, and n ↦ {n} forms an injection from ℕ to P(ℕ), we have ℵ₀ < 𝔠. In fact, for every cardinal x, there is some cardinal y so that x < y.
Here is some basic terminology for partial orders:
[Definition] Let ≤ be a partial order on some class P and let A ⊂ P be a subclass of P. A maximum element of A is some x ∈ A so that, for all y ∈ A, x ≤ y → x = y. A minimal element of A is some x ∈ A so that, for all y ∈ A, y ≤ x → x = y. The greatest element of A, if it exists, is some x ∈ A so that, for all y ∈ A, y ≤ x. The least element of A, if it exists, is some x ∈ A so that, for all y ∈ A, x ≤ y. An upper bound of A is some x ∈ P so that, for all y ∈ A, y ≤ x. A lower bound of A is some x ∈ P so that, for all y ∈ A, x ≤ y. The infimum of A, denoted inf(A), if it exists, is the greatest lower bound of A. The supremum of A, denoted sup(A), if it exists, is the least upper bound of A.
Given x,y ∈ P, the meet of x and y, often denoted x ∧ y, is the infimum of {x,y}. The join of x and y, often denoted x ∨ y, is the supremum of {x,y}. If every pair of elements in a poset (partial ordered set) has a meet and a join, then that poset is called a lattice. x and y are comparable iff x ≤ y or y ≤ x, x ⊥ y is used to denote that x and y are incomparable. Examples of lattices are: the powerset lattice (P(X),⊂) of any set X, where x ∧ y = x ∩ y and x ∨ y = x ∪ y, linear orders like ℚ, where x ∧ y = min(x,y) and x ∨ y = max(x,y), etc.
Without assuming the axiom of choice, two cardinals needn't have a meet or join. Now you know random useless stuff about posets!!
Oh, and: ℵ₀ is a minimum infinite cardinal. Proof is left as an exercise~
❈ Cardinal Arithmetic ❈
Cardinal numbers are numbers, so it'd make sense if we could do arithmetic on them. And we can!
[Definition] For sets A and B, |A| + |B| is the cardinality of the set A ⊔ B, i.e. the disjoint union of A and B. Members of A ⊔ B are (0,a) and (1,b) for a ∈ A and b ∈ B.
[Definition] For sets A and B, |A| · |B| is the cardinality of the Cartesian product A × B of A and B. Members of A × B are ordered pairs (a,b) for a ∈ A and b ∈ B.
Arithmetic on finite cardinals works as you'd expect: 6 + 3 = 9 and 12 · 2 = 24. Addition and multiplication on infinite cardinals, however, is actually quite boring, as x+y and xy are simply max(x,y). Well, that is, if you assume AC. Without AC, cardinal arithmetic can actually get very interesting (and weird af).
I am not that familiar with cardinal arithmetic without the axiom of choice, so you'll have to do more research on that on your own if you're interested!
Cardinal addition and multiplication are commutative, x+y = y+x, xy = yx, associative, (x+y)+z = x+(y+z), (xy)z = x(yz), and multiplication distributes over addition, x(y+z) = xy+xz.
Personally, I think cardinal exponentiation is more interesting than addition or multiplication:
[Definition] For sets A and B, |A|^|B| is the cardinality of the set of functions from B to A.
For cardinals x and y, if x ≥ 2, then we can prove that x^y > y. 𝔠, the cardinality of the continuum, is equal to 2^ℵ₀ and to ℵ₀^ℵ₀. Also, it's the cardinality of the set of real numbers ℝ. Here's a vid I found that explains why.
I think I might be getting too eepyy to write. I'll write more tomorrow.
[zzz]
Good morning!
Cardinal exponentiation has all the properties you'd think it has: x^y · x^z = x^(y+z) and (x^y)^z = x^(yz). Also, 0⁰ = 1.
There are also infinite sums and infinite products:
[Definition] Σ_(i ∈ I) A_i is the set of tuples (i,a) for i ∈ I and a ∈ A_i. Σ_(i ∈ I) |A_i| = |Σ_(i ∈ I) A_i| is the cardinality of this set.
[Definition] Π_(i ∈ I) A_i is the set of functions f with I as domain and f(i) ∈ A_i for all i. Π_(i ∈ I) |A_i| = |Π_(i ∈ I) A_i| is the cardinality of this set.
Σ_(i ∈ {1,...,k}) x_i = x₁ + ... + xₖ and Π_(i ∈ {1,...,k}) x_i = x₁ · ... · xₖ, so this is a valid extension of sums and products. The sum of x many y's, i.e. Σ_(i ∈ I) x for |I| = y, is the same as the product of x and y. The product of x many y's, Π_(i ∈ y) x, is equal to x^y. If X is a family of sets, I also sometimes write ΣX and ΠX for Σ_(A ∈ X) A and Π_(A ∈ X) A.
Here is a fun fact that idk where to place in this blog post: a Dedekind infinite cardinal is a cardinal x = |A| for which there exists an injection f: A → A that is not surjective. In other words, x+1 > x. Without the axiom of choice, infinite Dedekind finite cardinal numbers (aka mediate/Dedekind cardinals) can exist, and these cardinals are incomparable to ℵ₀.
Here is a fun question: is the product of any number of non-zero cardinals always non-zero?
Well?~
◈ Axiom of Choice ◈
The axiom of choice (AC) states that the product of any number of non-zero cardinals is always non-zero. I.e. for any family X of non-empty sets, ΠX is non-empty (a member of ΠX is called a choice function for X).
Eh... I didn't really plan what to write in this chapter besides what the axiom of choice is. Oh, well!
...
Wait-
Wait, WHAT THE F---
So.. apparently, you cannot take infinite products of cardinals without assuming the axiom of choice. ℵ₀ is the cardinality of ℕ, but ℕ is not the only set with cardinality ℵ₀. If A has cardinality ℵ₀, then in how many ways does it have cardinality ℵ₀? Well, if a bijection f: A → ℕ exists, then 𝔠 many of those bijections exist. If we take ℵ₀ different sets A₀, A₁, A₂, ... all with cardinality ℵ₀, we have, for each k, multiple bijections f: Aₖ → ℕ. We would expect |Π_(k ∈ ℕ) Aₖ| = ℵ₀^ℵ₀ = 𝔠, but how do we choose a bijection f: Aₖ → ℕ for each natural number k? If we only had a finite amount of Aₖ, this wouldn't be a problem. However, we have an infinite amount of Aₖ... so we need to make an infinite amount of choices. So, we can define the set X = {{f | f: Aₖ → ℕ is a bijection} | k ∈ ℕ}, and a choice function for X gives us a bijection for each Aₖ! But... we need AC to prove such a choice function exists.
...
HOW AM I SUPPOSED TO LEARN AD WHEN THIS F----D UP SH-- HAPPENS?
..sorry for screaming at you.
Luckily, infinite cardinal addition still works as normal without AC... probably.
Maybe.
Nope, it doesn't.
【 Aleph Cardinals 】
As you can see, we have run out of symbols to put on the sides of the chapter titles.
Anyways! So, a well order is an order (A,≤) where:
≤ is a partial order on A.
≤ is total/linear: for all x and y in A, x and y are comparable by ≤.
≤ is well-founded: all non-empty S ⊂ A have a minimum element.
Well, ig those random facts about posets weren't completely useless.
I might make a blog post about ordinals later, which'll go more in-depth on well-orders and linear orders.
[Definition] An aleph cardinal is an infinite cardinal number |A| for which there exists a well-order (A,≤).
An example of an aleph cardinal is ℵ₀: ℵ₀ = |ℕ| and the usual order on ℕ is a well-order. The n-th aleph cardinal is written as ℵₙ, starting at 0th of course :3
The statement ‘ℵ₁ = 𝔠’ is known as the continuum hypothesis (CH), which is both unprovable and undisprovable. I might make a blog post about forcing in the future! ^^
Although cardinals (without AC) don't need to be linearly ordered, aleph cardinals are linearly ordered and even well-ordered. A proof of this is left as an exercise~ Because, well, of course it is :P
The well-ordering principle states that every set A has a well-order (A,≤). Equivalently, every infinite cardinal is an aleph cardinal.
It turns out: AC and the well-ordering principle are equivalent! Although AC, when written in its original form, seems more obviously true (to me at least), I think the well-ordering principle is a lot more useful.
I might go more in depth on why this is in my post about ordinal numbers. (why AC and the well ordering principle are equivalent)
❖ Cofinality ❖
There are two definitions of cofinality: one for cardinals, and one for ordinals. Since this blog-post is about cardinals, I'll give the one for cardinals:
[Definition] The cofinality of a cardinal x = |A| is the minimum cardinality of a partition X of A into sets of cardinality <x.
I often use cf(x) to denote the cofinality of x and cof(x) to denote the class of cardinals with cofinality x, though people also often use cof(x) to denote the cofinality of x. A partition of a set A is a set X such that all members of X are subsets of A, none of the members of X intersect and the union of all members of X is A.
We have cf(0) = 0, cf(1) = 1, cf(2) = 2 and for every finite n > 2, cf(n) = 2. 3 = |{a,b,c}| can be partitioned into {{a},{a,b}}, the partition {{a,b,c}} doesn't work as this has a set {a,b,c} of cardinality 3, which is not < 3.
[Definition] A cardinal κ is regular iff cf(κ) = κ.
Equivalently, every partition of κ either has cardinality κ or an element of cardinality κ.
We have cf(cf(x)) = cf(x) for every cardinal number x, so cf(x) is always regular.
0, 1 and 2 are examples of finite regular cardinals, though often, 2 is not regarded as regular. ℵ₀ also is a regular cardinal.
A cardinal that is not regular is called a singular cardinal. An example of a singular cardinal is ℵ_ω, which is the sum of ℵₙ for finite n. cf(ℵ_ω) = ℵ₀ as {ℵ₀,ℵ₁,ℵ₂,...} is a partition of ℵ_ω = Σ_(n ∈ ω) ℵₙ into ℵ₀ many cardinals each of which is <ℵ_ω.
Here is the ordinal definition of cofinality, which is (a lot) more often used if you have the axiom of choice:
[Definition] The cofinality of an order (A,≤) is the minimum cardinality of a cofinal subset S ⊂ A. S is cofinal if ∀x ∈ A ∃y ∈ S, x ≤ y.
Assuming the axiom of choice, the cofinality of a cardinal κ is often defined as the cofinality of the minimum ordinal α such that |α| = κ. An ordinal is the order-type of a well-order, and one ordinal is less than another if there exists an order preserving injection from one to the other. cf(κ) with the above definition agrees with the one I gave earlier for infinite κ, but if κ > 0 is finite, then cf(κ) is 1 instead of 2. I might talk more about this in my blog-post about ordinal numbers. For now, we'll just use the partition definition of cofinality.
If x is infinite Dedekind finite, then cf(x) is 2, which I think is kinda funni. We can also have cf(𝔠) = 2 if we omit choice :3 Though with choice, cf(𝔠) is uncountable (i.e. >ℵ₀).
I don't know how to end this blog, so here is some random terminology:
A cardinal x is finite iff κ is 0, 1, 2, 3, etc.
A cardinal x is countable iff it's ≤ℵ₀. It is uncountable if it's not ≤ℵ₀.
An alpeh cardinal is an infinite well-orderable cardinal.
A strong limit cardinal is a cardinal x for which, for all y < x, we have 2^y < x.
ℶ_0 = ℵ_0, ℶ_(n+1) = 2^(ℶ_n) and ℶ_λ = sup{ℶ_α | α < λ} for limit ordinal λ. A cardinal of the form ℶ_n is called a beth cardinal and ℶ₁ = 𝔠.
Assuming AC, x⁺ is the next cardinal after x, called the successor cardinal. AC is needed to ensure there exists a cardinal directly after κ.
The continuum hypothesis (CH) states that ℵ₁ = 𝔠. The generalized continuum hypothesis (GCH) states that 2^x = x⁺ for all infinite x. Both are unprovable and undisprovable from the usual axioms of ZFC.
Assuming AC, a weak limit cardinal (or simply limit cardinal) is a cardinal x for which, for all y < x, y⁺ < x. Assuming GCH, weak and strong limit cardinals are the same.
A strongly inaccessible cardinal (or simply, inaccessible cardinal) is a regular strong limit cardinal. Assuming AC, a weakly inaccessible cardinal is a regular weak limit cardinal. The existence of an inaccessible cardinal implies the consistency of ZFC, and thus, by Gödel's incompleteness theorems, ZFC cannot prove the existence of an inaccessible cardinal.
That's all I had to say about cardinals (for now), bye!~
