Paul Halmos, Naive Set Theory
Exercises from section 24
We’re nearing the end! Last section introduced countable sets on its way to arriving at the concept of cardinal numbers. Instead of them being defined here, the author takes a slightly unusual detour, and introduces us to the arithmetic of cardinals, leaving their basic construction for the end-section. Okay, I guess. One is supposed to be able to do these operations just keeping in mind for each cardinal number x there exists some set X with card X = x and cardinals are ordered such that card X = card Y iff X ∼ Y and card X < card Y iff X ≺ Y.
Prove that if a,b,c,d are cardinal numbers such that a ≤ b and c ≤ d, then a+c ≤ b+d
We have 4 possible cases here. Let's go through them one by one:
a = b and c = d. It follows a and b are the cardinal of the same disjoint set, call it A, and c and d are the cardinal of the same disjoint set, call it C. a + c = (A∪C), and b + d = (A∪C), so a + c = b + d
a < b and c < d. Again, each letter is the cardinal of some disjoint sets A, B, C, D and such that A ≺ B (so there’s an injection from A to B but not a bijection) and C ≺ D (so there’s an injection from C to D but not a bijection). If we take (A∪C) and (B∪D) and compare them, we can show there’s an injection from (A∪C) to (B∪D). Let f be the injection from A to B and g the injection from C to D. Then there’s an injection h from (A∪C) to (B∪D) such that for any a ∈ A, h(a) = f(a), and for any c ∈ C, h(c) = g(c), so a + c < b + d
a < b and c = d. We start one more time with each letter being the cardinal of some disjoint sets A, B, C, D and such that A ≺ B (so there’s an injection from A to B but not a bijection) and C = D (there’s a bijection between them). Now consider the sets (A∪C) and (B∪D): we know of f, an injection from A to B and of g, a bijection from C to D. The function h mapping (A∪C) → (B∪D) can be defined piecemeal as h(a) = f(a) for all a ∈ A and h(c) = g(c) for all c ∈ C, h(c). This function is an injection from (A∪C) → (B∪D), as not all elements of the second set (namely, those in B) get mapped to, so a + c < b + d
a = b and c < d. This is exactly like the previous case, only now we have A = B and C < D, so when we make the same setup of functions (f such that A → B is bijective; g such that C → D is only injective), we also get an injective function h such that (A∪C) → (B∪D) and which doesn’t map to all elements of the second set (namely, those in D), so a + c < b + d
Prove that if a,b,c,d are cardinal numbers such that a ≤ b and c ≤ d, then ac ≤ bd
I think this works exactly like the case for addition, with the only difference being that multiplication is defined as the Cartesian Product of sets. Let’s do the first case: a = b and c = d. This means we have bijections f from A to B and g from C to D. This allows us to build a bijection h from (AxC) → (BxD) like thus: h(a,b) = (f(a), g(b)), so ac = bd.
Second case (a < b and c < d): there're non-bijective injections f: A → B and g: C → D. This allows us to build a non bijective injection h: AxC → BxC such that h(a,c) → (f(a), g(c)) = (b,d). Not all elements of BxC are mapped to: we know the mapping to the first coordinate doesn't map to *all* first coordinates, and we know the mapping to the second coordinate doesn't map to *all* second coordinates. There then exists some b' in B not mapped to by f and some d' in D not mapped to by g, but (b', d') must be in BxD. Therefore, ac < bd.
Third case (a < b and c = d): we have non-bijective injection f: A → B and bijection g: C → D. For much the same reasons as in the second case, we end up with a non bijective injection h: AxC → BxC, h(a,c) → (f(a), g(c)); as f is not bijective, there exists some b' in B not mapped to by f, so there exists some element (b', d) that can’t be mapped to by h. And for exactly the same reasons, this is what happens in case four (only now the element that can’t be mapped to is (b, d').
If { ai }(i∈I) and { bi } (i∈I) are families of cardinal numbers such that ai < bi for each i ∈ I, then
Okay, another of those exercises where I want to hit Halmos on the head with a big stick. There’s no scaffolding for this exercise, and obviously nothing in the text that seems to hint on how to proceed. I thought of trying to reduce the product to a union of sums by skirting the definition of the infinite product through Cartesian Products, but I couldn’t make any progress.
After browsing around, it seems this result is an important theorem, usually known as König’s theorem. A strategy for solving it seems to employ Axiom of Choice (of which this theorem is another covert manifestation). For avoiding having to use Latex any longer, let us represent the two components of the inequality above as Sum(i)ai and Prod(i)bi. Also, one needs to clarify what these sets actually are: Sum(i)ai is card(∪i Ai). The elements of the parenthetical set are each of the elements of each set Ai, and you can conceive them as indexed by the i of the set they originally belonged to as (a, i) where a ∈ Ai. As for Prod(i)bi, it is card (XiBi). The elements of the parenthetical set are tuples (b0, b1, b2, …, bi) where each bn comes from the Bn set.
Let us imagine function f: Sum(i)ai → Prod(i)bi. f maps each element (a, i) to a tuple (b0, b1, b2, …, bi) in the following way:
As Ai < Bi, there’s an injection g: Ai → Bi
for each index i you fix some arbitrary element b*i ∈ Bi / g(Ai) through the Axiom of Choice. These elements will be the default filler values for the tuple we are creating.
f maps (a,i) to a tuple such that for position i in the tuple we include g(a), which must exist, and for all other positions of the tuple we use the elements b*i
Clearly, the tuple we created exists in Prod(i)bi. Also, f is injective: if f(i,a) = f(j,a′), then both tuples agree at every position. We need to explore two cases:
What if i ≠ j?
Then in position i, the first tuple has g(a) and in position i, the second tuple has some b*i dummy value because i ≠ j. This means g(a) would have to be equal to b*i , but this is impossible, as all were explicitly chosen (though the Axiom of Choice) to exclude images of g, so i = j
What if i = j?
Then both tuples place their non-dummy value in the same position, namely i. For the tuples to be equal, it must be that g(a) = g(a′). But since g is injective, this implies a = a′. So again, the tuples must have come from the same (i, a), and f is injective.
This shows f is an injective function. Last step is to show that it cannot be surjective: there are elements in Prod(i)bi that cannot be mapped to. This is easy to see: consider the tuple (b*0, b*1, b*2, …) ∈Prod(i)bi, that is, the tuple that has only the dummy values b*i in every position. This tuple cannot possibly be the image of any element (a,i) ∈ Sum(i)ai because in the construction of f, every tuple produced by f contains exactly one coordinate (the i-th one) where the value is not a dummy b*i, but rather g(a). So the all-dummy tuple is not in the image of f.
(N.B.: This was horribly painful and required much assistance from ChatGPT. What was Halmos thinking? Maybe there’s a simpler way of proving this?)
Prove that if a, b, and c are cardinal numbers such that a ≤ b, then ac ≤ bc. Prove that if a and b are finite, greater than 1, and if c is infinite, then ac = bc.
Because a ≤ b, there’s an injection f from A to B. Now AC is the set of all functions α from C to A. Consider a composition (f∘α): it will map any function α, and therefore, every c ∈ C, to f(α(c)) ∈ B, so such composite function (f∘α) ∈ BC. Besides, we know that f is an injective function: if α, α* ∈ AC are mapped to BC, then if α ≠ α*, it follows that (f∘α) ≠ (f∘α*), meaning the composite function (f∘α): AC→ BC is an injective function and that ac ≤ bc.
For the second task, what we have to show is that ac ≤ bc and bc ≤ ac. This would imply the equality (ac = bc). For any finite a and b, one of three cases must follow: a = b, a < b or a > b. If any of the first two cases happen, task one already showed us that ac ≤ bc. We are left to check what happens when a > b. A key insight here: this is exactly the same situation covered in the first part, with variables relabeled. If we rewrite the first result as if x ≤ y, then xc ≤ yc, then since b < a, we apply the result with x = b, y = a and it follows that bc ≤ ac. This concludes the proof, showing that no matter the relation between a and b it always follows that ac = bc.
Prove that if a and b are cardinal numbers at least one of which is infinite, then a + b = ab. Prove that if a and b are cardinal numbers such that a is infinite and b is finite, then ab = a.
Given cardinal numbers a and b, we can assume without any loss of generality, that b is the guaranteed infinite one, and that it is greater than a if a is infinite. Then a + b = b, as was shown in the textbook. As for ab: given that b is infinite and a ≤ b, we also know from a previous exercise we did that if a, b, c, d are cardinal numbers and a ≤ b and c ≤ d, then ac ≤ bd. Therefore, aa ≤ bb, and bb = b. Similarly, a ≤ b and b ≤ b, so ab ≤ bb. In this way, we’ve shown ab ≤ b.
Now, to prove the opposite direction (b ≤ ab), I just need to show there’s an injection from set B (who cardinal is b) and set AxB (whose cardinal is ab). A is not empty, so there exists some element a0. The function f such that b ↦ (a0,b) is injective, so b ≤ ab. And given that ab ≤ b and b ≤ ab, ab = b. This concludes the proof for the first task. As a + b = b = ab, a + b = ab.
For the second task: we know that ab = card (AB), where AB is the set of all functions from a finite set B to an infinite set A. If, for example, card (B) = 2, then A2 would be the set of all functions from {0,1} ↦ A. What this means is all possible pairs (a’, a’’) where both a’ and a’’ are elements of A, so this is the same as AxA = aa = a. We can generalize this logic to any finite b: we will end up with a finite Cartesian Product of A with itself, which still has cardinality a if a is infinite.
On a technical note, I think there’s still an issue with this proof. Textbook just showed aa = a, commutativity and associativity of multiplication. Not sure if for a finite product aaaaaaaaaaaaaaa.... it can be assumed that we can break it down as in (aa)(aa)(aa)... . I mean, I think it would be pretty easy to show by induction, but I am not sure I can use it with cardinals (whose definition I still haven’t seen. That’s section 25). Perhaps one can cop out and say induction is being used only in the exponents, in which case:
base case: n = 1 (0 wouldn’t work here). a1 = a
assume true for k, show it follows for k+1. ak+1 = aka = aa = a
This would work for any n ∈ ω, and obviously so for any specific n > 0.
