Countable Sets
Two sets, A and B, are considered equinumerous or of the same cardinality, denoted as A ≡ B, if there exists a bijection, which is a one-to-one mapping, from A onto B This concept allows us to determine the equivalence of the sizes of sets A, B, and C through the existence of such mappings.
1 These are produced here from my article [117] with the permission of the Indian
A set A is considered finite if there exists a bijection between the set {0, 1, , n-1} (where n is a natural number) and A; for n = 0, this set is defined as the empty set ∅ Conversely, if A does not meet this criterion, it is classified as infinite Additionally, a set A is termed countable if it is either finite or if a bijection can be established between the set of natural numbers N = {0, 1, 2, } and A If a set cannot be counted in this manner, it is referred to as uncountable.
A set is considered countable if its elements can be enumerated in a sequence such as a₀, a₁, a₂, and so on, which may include repetitions This means that a set A is countable if there exists a mapping function f from the natural numbers N onto the set A.
Exercise 1.1.2 Show that every subset of a countable set is countable.
Example 1.1.3 We can enumerateN×N, the set of ordered pairs of nat- ural numbers, by the diagonal method as shown in the following diagram
That is, we enumerate the elements of N×Nas (0,0),(1,0),(0,1),(2,0),
(1,1),(0,2), By induction on k, k a positive integer, we see that N k , the set of allk-tuples of natural numbers, is also countable.
Theorem 1.1.4 Let A 0 , A 1 , A 2 , be countable sets Then their union
Proof For eachn, choose an enumeration a n 0 , a n 1 , a n 2 , of A n We enumerateA n A n following the above diagonal method.
Example 1.1.5 LetQbe the set of all rational numbers We have
Exercise 1.1.6 LetX be a countable set Show that X× {0,1}, the set
X k of allk-tuples of elements ofX, andX < N , the set of all finite sequences of elements ofX including the empty sequencee, are all countable.
A real number is called algebraic if it is a root of a polynomial with integer coefficients.
Exercise 1.1.7 Show that the setKof algebraic numbers is countable.
The most natural question that arises now is; Are there uncountable sets? The answer is yes, as we see below.
Theorem 1.1.8 (Cantor) For any two real numbersa, b with a < b, the interval [a, b]is uncountable.
In this proof by Cantor, we consider a sequence \((a_n)\) within the interval \([a, b]\) We define an increasing sequence \((b_n)\) and a decreasing sequence \((c_n)\) inductively, starting with \(b_0 = a\) and \(c_0 = b\) Assuming that the sequences have been defined for some \(n \in \mathbb{N}\) such that \(b_0 < b_1 < \ldots < b_n < c_n < \ldots < c_1 < c_0\), we identify \(i_n\) as the first integer satisfying \(b_n < a_{i_n} < c_n\) and \(j_n\) as the first integer where \(a_{i_n} < a_{j_n} < c_n\) Given that the interval \([a, b]\) is infinite, both \(i_n\) and \(j_n\) are guaranteed to exist We then set \(b_{n+1} = a_{i_n}\) and \(c_{n+1} = a_{j_n}\).
Letx= sup{b n :n∈N} Clearly,x∈[a, b] Supposex=a k for some k.
The sequence (a_n) does not cover the entire interval [a, b], as demonstrated by the existence of an integer i such that b_i exceeds a_k, where a_k equals x This contradiction indicates that the range of (a_n) is limited, confirming that the result applies to any arbitrary sequence.
Let X and Y be sets The power set of X, denoted P(X), is the collection of all subsets of set X Similarly, the set of all functions from Y to X is represented as X^Y.
Theorem 1.1.9 The set{0,1} N , consisting of all sequences of 0’s and 1’s, is uncountable.
Proof.Let (α n ) be a sequence in{0,1} N Define α∈ {0,1} N by α(n) = 1−α n (n), n∈N.
Thenα=α i for alli Since (α n ) was arbitrary, our result is proved.
Exercise 1.1.10 (a) Show that the intervals (0,1) and (0,1] are of the same cardinality.
(b) Show that any two nondegenerate intervals (which may be bounded or unbounded and may or may not include endpoints) have the same cardinality Hence, any such interval is uncountable.
A number is calledtranscendentalif it is not algebraic.
Exercise 1.1.11 Show that the set of all transcendental numbers in any nondegenerate interval is uncountable.
Order of Infinity
So far we have seen only two different “orders of infinity”—that ofNand that of{0,1} N Are there any more? In this section we show that there are many.
The cardinality of a set A is defined as less than or equal to that of set B, denoted as A ≤ c B, if there exists a one-to-one function f mapping elements from A to B It is important to note that the empty set, denoted as ∅, has a cardinality that is less than or equal to the cardinality of any set A This relationship holds true for any sets A, B, and C.
If A ≤ c B but A ≡ B, then we say that the cardinality of A is less than the cardinality of B and symbolically write A < c B Notice that
Theorem 1.2.1 (Cantor) For any setX,X < c P(X).
Proof.First assume thatX =∅ Then P(X) ={∅} The only function on X is the empty function ∅, which is not onto {∅} This observation proves the result whenX =∅.
Now assume thatX is nonempty The mapx−→ {x} fromX toP(X) is one-to-one Therefore, X ≤ c P(X) Letf : X −→ P(X) be any map.
We show thatf cannot be ontoP(X) This will complete the proof. Consider the set
This contradiction proves our claim.
Remark 1.2.2 This proof is an imitation of the proof of 1.1.9 To see this, note the following IfAis a subset of a setX, then itscharacteristic functionis the mapχ A :X −→ {0,1}, where χ A (x) 1 ifx∈A,
The mapping A−→χ A establishes a one-to-one correspondence from P(X) to {0,1}^X Furthermore, it has been demonstrated that no mapping f exists from X onto P(X), similar to the proof that {0,1}^N is uncountable.
Let T be the union of all sets including N, P(N), P(P(N)), and so on, resulting in T having a cardinality greater than each of these sets This process can be continued indefinitely, creating an infinite class of sets with progressively higher cardinalities A fascinating question arises: Is there an infinite set with a cardinality distinct from all previously obtained sets? Specifically, is there an uncountable set of real numbers with a cardinality less than that of R? These inquiries represent some of the most fundamental challenges in set theory and mathematics as a whole.
We shall briefly discuss these later in this chapter.
The following result is very useful in proving the equinumerosity of two sets It was first stated and proved (using the axiom of choice) by Cantor.
Theorem 1.2.3 (Schr¨oder – Bernstein Theorem) For any two setsX and
Proof (Dedekind) Let X ≤ c Y and Y ≤ c X Fix one-to-one maps f : X −→Y and g :Y −→X We have to show that X and Y have the same cardinality; i.e., that there is a bijectionhfromX ontoY.
We first show that there is a setE⊆X such that g −1 (X\E) =Y \f(E) (∗)
(See Figure 1.1.) Assuming that such a setEexists, we complete the proof as follows Defineh:X −→Y by h(x) f(x) ifx∈E, g −1 (x) otherwise.
The maph:X −→Y is clearly seen to be one-to-one and onto.
We now show the existence of a set E⊆X satisfying ( ) Consider the map H:P(X)−→ P(X) defined by
It is easy to check that
Now define a sequence (A n ) of subsets ofX inductively as follows:
LetE n A n Then,H(E) =E The setE clearly satisfies ( ).
Here are some applications of the Schr¨oder – Bernstein theorem.
Example 1.2.5 Definef :P(N)−→R, the set of all real numbers, by f(A) n ∈ A
Then f is one-to-one Therefore, P(N) ≤ c R Now consider the map g :
Clearly, g is one-to-one and so R ≤ c P(Q) As Q ≡ N, P(Q) ≡ P(N).Therefore,R ≤ c P(N) By the Schr¨oder – Bernstein theorem, R≡ P(N).SinceP(N)≡ {0,1} N ,R≡ {0,1} N
Example 1.2.6 Fix a one-to-one mapx−→(x 0 , x 1 , x 2 , ) fromRonto
{0,1} N , the set of sequences of 0’s and 1’s Then the function (x, y) −→
(x 0 , y 0 , x 1 , y 1 , ) from R 2 to {0,1} N is one-to-one and onto So, R 2 ≡ {0,1} N ≡R By induction on the positive integersk, we can now show that
Exercise 1.2.7 Show that Rand R N are equinumerous, where R N is the set of all sequences of real numbers.
Exercise 1.2.8 Show that the set of points on a line and the set of lines in a plane are equinumerous.
Exercise 1.2.9 Show that there is a familyAof infinite subsets ofNsuch that
(ii) for any two distinct setsAandB in A, A
The Axiom of Choice
The comparability of sizes between any two sets, X and Y, raises an intriguing question: is it always the case that either X is less than or equal to Y, or Y is less than or equal to X? To address this query, we must consider the axiom of choice, a fundamental hypothesis in set theory.
The Axiom of Choice (AC) If {A i } i ∈ I is a family of nonempty sets, then there is a functionf :I−→ i A i such thatf(i)∈A i for everyi∈I.
A choice function for a collection of sets {A_i: i ∈ I} exists when I is finite, as demonstrated through induction However, the existence of such a function remains unproven for infinite sets For instance, consider a sequence of shoe pairs where a choice function can be easily defined, such as selecting the left shoe from each pair In contrast, when dealing with pairs of socks, it becomes impossible to establish a definitive choice function The Axiom of Choice (AC) posits the existence of such a function without providing a specific rule or construction, leading to initial criticism due to its nonconstructive nature Nevertheless, AC is crucial for the theory of cardinal numbers and various other mathematical fields.
From now on, we shall be assuming AC.
Note that we usedACto prove that the union of a sequence of countable sets A 0 , A 1 , is countable For each n, we chose an enumeration of A n
Typically, there are infinitely many enumerations available, and we did not establish a specific method for selecting one However, it's important to highlight that in certain significant cases, the Axiom of Choice (AC) is not required For example, we proved the countability of the set of rational numbers and demonstrated that the set X, which is countable, is also countable when X is less than N.
The next result shows that every infinite setX has a proper subsetY of the same cardinality asX We useACto prove this.
Theorem 1.3.1 IfX is infinite andA⊆X finite, thenX\AandX have the same cardinality.
To demonstrate the existence of distinct elements beyond a given set A = {a₀, a₁, , aₙ}, we utilize the Axiom of Choice (AC) By applying AC, we can identify distinct elements aₙ₊₁, aₙ₊₂, and so forth from the set difference X \ A We establish a choice function f: P(X) \ {∅} → X, ensuring that for every nonempty subset E of X, f(E) is an element of E This choice function allows us to inductively define new elements such that aₙ₊ₖ₊₁ = f(X \ {a₀, a₁, , aₙ₊ₖ}) for k = 0, 1, Furthermore, we define a mapping h: X → X \ A, where h(x) equals aₙ₊ₖ₊₁ if x equals aₖ, and x otherwise.
Clearly,h:X−→X\Ais one-to-one and onto.
Corollary 1.3.2 Show that for any infinite set X, N ≤ c X; i.e., every infinite setX has a countable infinite subset.
Exercise 1.3.3 LetX, Y be sets such that there is a map from X onto
Zorn's lemma is a significant equivalent form of the Axiom of Choice (AC) that has numerous applications across various fields of mathematics This chapter will explore several applications of Zorn's lemma specifically related to the theory of cardinal numbers, providing a deeper understanding of its implications and uses in mathematical contexts.
Apartial orderon a setP is a binary relation Rsuch that for anyx, y,zin P, xRx(reflexive),
(xRy &yRz) =⇒xRz(transitive), and
A partially ordered set, or poset, is defined as a set equipped with a partial order In a linear order on a set X, every pair of elements is comparable, meaning for any x, y in X, either xRy or yRx must be true However, if X contains more than one element, the inclusion relation on the power set P(X) serves as a partial order that does not qualify as a linear order Additionally, there are various examples of partial orders that do not meet the criteria for linear orders.
Example 1.3.4 Let X and Y be any two sets Apartial function f :
X −→Y is a function with domain a subset of X and range contained in
In the context of partial functions, if f: X → Y and g: X → Y, we say that g extends f, or that f is a restriction of g, denoted as g f or f g, when the domain of f is a subset of the domain of g and f(x) equals g(x) for every x in the domain of f If f is a restriction of g and the domain of f is A, we express this relationship as f = g|A.
F n(X, Y) ={f :f a one-to-one partial function fromX toY}.
SupposeY has more than one element andX =∅ Then (F n(X, Y), ) is a poset that is not linearly ordered.
Example 1.3.5 LetV be a vector space over any fieldF andP the set of all independent subsets ofV ordered by the inclusion⊆ ThenP is a poset that is not a linearly ordered set.
Fix a poset (P, R) AchaininP is a subsetCofPsuch thatRrestricted toCis a linear order; i.e., for any two elementsx,yofCat least one of the relationsxRyor yRxmust be satisfied LetA⊆P Anupper boundfor
Ais anx∈P such thatyRxfor ally∈A Anx∈P is called amaximal elementofP if for noy∈P different fromx,xRy holds In 1.3.4, a chain
C in F n(X, Y) is a consistent family of partial functions, their common extension
In a partially ordered set (poset), an upper bound for a set C exists, and any partial function f defined on domain X or range Y can yield a maximal element It is important to note that a poset may contain multiple maximal elements, particularly when it is not linearly ordered.
In 1.3.5, LetC be a chain inP Then for any two elementsE and F of
P, eitherE⊆F orF ⊆E It follows that
Citself is an independent set and so is an upper bound ofC.
In a linearly ordered set (L,≤), an element x is defined as the first element if x ≤ y for all y in L, and as the last element if y ≤ x for all y in L A set L is considered order dense if, for any two elements x and y where x < y, there exists an element z such that x < z < y Additionally, two linearly ordered sets are termed order isomorphic if there exists a one-to-one, order-preserving mapping from one set onto the other.
Exercise 1.3.6 (i) LetL be a countable linearly ordered set Show that there is a one-to-one, order-preserving mapf :L−→Q, whereQhas the usual order.
(ii) LetLbe a countable linearly ordered set that is order dense and that has no first and no last element Show thatLis order isomorphic to
Zorn’s Lemma IfP is a nonempty partially ordered set such that every chain in P has an upper bound in P, then P has a maximal element.
As mentioned earlier, Zorn’s lemma is equivalent toAC We can easily prove AC from Zorn’s lemma To see this, fix a family {A i : i ∈ I} of
In the context of set theory, we define a partial choice function for a collection of nonempty subsets {A_i : i ∈ I} as a choice function applicable to a subfamily {A_i : i ∈ J}, where J is a subset of I The set P encompasses all such partial choice functions Within this framework, we establish a relation between functions f and g in P, denoting that g extends f This relationship allows us to consider the poset (P, ≤), which adheres to the conditions outlined by Zorn’s lemma To demonstrate this, we identify a chain C = {f_a : a ∈ A} within P.
D a ∈ A domain(f a ) Define f :D−→X by f(x) =f a (x) if x∈domain(f a ).
The function \( f \) is consistently defined and serves as an upper bound for the set \( C \) By applying Zorn's lemma, we can identify a maximal element \( g \) within the partially ordered set \( P \) If \( g \) is not a choice function for the family \( \{A_i : i \in I\} \), it follows that the domain of \( g \) is equal to \( I \) Consequently, we can select an index \( i_0 \) from \( I \) that is not included in the domain of \( g \), along with an element \( x_0 \) from the set \( A_{i_0} \).
A i be the extension of g such that h(i 0 ) = x 0 Clearly, h ∈ P, g h, and g=h This contradicts the maximality ofg.
We refer the reader to [62] (Theorem 7, p 256) for a proof of Zorn’s lemma fromAC.
Here is an application of Zorn’s lemma to linear algebra.
Proposition 1.3.7 Every vector spaceV has a basis.
In the context of the poset P defined in 1.3.5, where P consists of all independent subsets of V, it is established that every singleton set {v}, where v = 0, is an independent set, leading to the conclusion that P is not empty It has been demonstrated that every chain within P possesses an upper bound Consequently, by applying Zorn's lemma, it follows that P contains a maximal element, denoted as B If B does not span V, one can find an element v in V that is not included in the span of B.
{v} is an independent set properly containingB This contradicts the maximality of B ThusB is a basis ofV.
In an infinite-dimensional vector space \( V \) over a field \( F \), the space \( V^* \), consisting of all linear functionals on \( V \), is recognized as a vector space over \( F \) It can be demonstrated that there exists an independent set \( B \) within \( V^* \) that is isomorphic to \( \mathbb{R} \).
Exercise 1.3.9 Let (A, R) be a poset Show that there exists a linear order
R onAthat extendsR; i.e., for everya, b∈A, aRb=⇒aR b.
Exercise 1.3.10 Show that every set can be linearly ordered.
More on Equinumerosity
In this section we use Zorn’s lemma to prove several general results on equinumerosity These will be used to develop cardinal arithmetic in the next section.
Theorem 1.4.1 For any two setsX andY, at least one of
To demonstrate the existence of a one-to-one mapping between two nonempty sets X and Y, we can either establish a one-to-one function f: X → Y or a one-to-one function g: Y → X This can be achieved by examining the poset F n(X, Y), which encompasses all one-to-one partial functions from X to Y.
In accordance with section 1.3.4, the set Y is confirmed to be nonempty It has been previously established that every chain within F n(X, Y) possesses an upper bound Consequently, applying Zorn's lemma indicates that the set P includes a maximal element, denoted as f 0 This leads to the conclusion that either the domain of f 0 is equal to X or its range is equal to Y.
If domain(f 0 ) =X, thenf 0 is a one-to-one map fromX toY So, in this case,X ≤ c Y If range(f 0 ) =Y, thenf 0 −1 is a one-to-one map fromY to
As a corollary to the above theorem and the Schr¨oder – Bernstein theo- rem, we get the following trichotomy theorem.
Corollary 1.4.2 Let AandB be any two sets Then exactly one of
Theorem 1.4.3 For every infinite setX,
Since X is infinite, it contains a countably infinite set, say D By 1.1.3,
D× {0,1} ≡D Therefore, P is nonempty Consider the partial order ∝ onP defined by
Following the argument contained in the proof of 1.4.1, we see that the hypothesis of Zorn’s lemma is satisfied byP So,P has a maximal element,say (A, f).
To finalize the proof, we need to demonstrate that A is equivalent to X (A ≡ X) Given that X is infinite, it suffices to prove that the set difference X \ A is finite Assuming otherwise, we can find a subset B of X \ A that is equivalent to the natural numbers (B ≡ N), which implies the existence of a one-to-one mapping g.
B× {0,1} ontoB Combining f andg we get a bijection h: (A
B that extendsf This contradicts the maximality of (A, f) Hence,X\Ais finite Therefore,A≡X The proof is complete.
Corollary 1.4.4 Every infinite set can be written as the union of kpair- wise disjoint equinumerous sets, wherek is any positive integer.
Theorem 1.4.5 For every infinite setX,
Consider the partial order∝onP defined by
According to Zorn's lemma, we select a maximal element (A, f) from P, as demonstrated in the proof of 1.4.3, and it is important to note that A must be infinite To finalize the proof, we aim to establish that A is equivalent to X If we assume otherwise, it follows that A is less than c X We begin by proving that the set difference X\A is also equivalent to X If X\A is less than c X, then based on 1.4.1, we have two possibilities: either A is less than or equal to c X\A or X\A is less than or equal to c A.
first X\A ≤ c A Using 1.4.3, take two disjoint sets A 1 , A 2 of the same cardinality asAandA 1
This is a contradiction Similarly we arrive at a contradiction from the other inequality Thus, by 1.4.2,X\A≡X.
Now chooseB⊆X\Asuch thatB≡A By 1.4.4, writeB as the union of three disjoint sets, sayB 1 ,B 2 , andB 3 , each of the same cardinality as
A Since there is a one-to-one map fromA×AontoA, there exist bijections f 1 :B×A −→B 1 ,f 2 :B×B −→B 2 , and f 3 :A×B −→B 3 Let C A
B Combining these four bijections, we get a bijectiong:C×C−→C that is a proper extension off This contradicts the maximality of (A, f). Thus,A≡X The proof is now complete.
Exercise 1.4.6 LetX be an infinite set Show that X,X < N , and the set of all finite sequences ofX are equinumerous.
AHamel basisis a basis ofRconsidered as a vector space over the field of rationalsQ Since every vector space has a basis, a Hamel basis exists.
Exercise 1.4.7 Show that ifB is a Hamel basis, thenB≡R.
The next proposition, though technical, has important applications to cardinal arithmetic, as we shall see in the next section.
Proposition 1.4.8 (J K¨onig, [58]) Let {X i :i ∈I} and {Y i : i∈I} be families of sets such that X i < c Y i for each i∈I Then there is no map f from i X i ontoΠ i Y i
Proof.Letf : i X i −→Π i Y i be any map For anyi∈I, let
A i =Y i \π i (f(X i )), where π i : j Y j −→Y i is the projection map Since for evry i,X i < c Y i , eachA i is nonempty ByAC, Π i A i =∅ But Π i A i range(f) =∅.
It follows thatf is not onto.
Arithmetic of Cardinal Numbers
For setsX,Y, andZ, we know the following.
So, to each set X we can assign a symbol, say |X|, called itscardinal number, such that
In general, cardinal numbers are denoted by Greek lettersκ, λ, àwith or without suffixes However, some specific cardinals are denoted by special symbols For example, we put
Cardinal numbers, like natural numbers, can be added, multiplied, and compared For two cardinal numbers λ and à, we can establish sets X and Y where |X| equals λ and |Y| equals à The sum of these cardinal numbers is defined as λ + à = |(X ∪ {0})|.
(Y × {1})|, λãà = |XìY|, λ à = |X Y |, λ≤à if X ≤ c Y, and λ < à if X < c Y.
The definitions provided are independent of the specific choices of sets X and Y, and they extend the concepts applicable to natural numbers It is important to note that if the cardinality of set X is λ, then 2 raised to the power of λ equals the cardinality of the power set of X, denoted as |P(X)| Additionally, we can define the sum and product of infinitely many cardinal numbers For a given set of cardinal numbers {λ_i : i ∈ I} and a corresponding family of sets {X_i : i ∈ I} where the cardinality of each set |X_i| equals λ_i, we define the product of these cardinalities as Π_i λ_i = |Π_i X_i|.
To define i λ i , first note that there is a family {X i : i∈ I} of pairwise disjoint sets such that |X i | =λ i ; simply take a family {Y i :i∈I} of sets such that|Y i |=λ i and putX i =Y i × {i} We define i λ i =| i
With these notations, note that
Whatever we have proved about equinumerosity of sets; i.e., the results concerning union, product, ≤ c , etc., translate into corresponding results about cardinal numbers For instance, by 1.2.1,
The Schr¨oder – Bernstein theorem translates as follows: λ≤à&à≤λ=⇒λ=à.
The result on comparabilty of cardinals (1.4.1) becomes; For cardinals λ andàat least one of λ≤àandà≤λ holds If λis infinite, then λ=λ+λ=λãλ.
Exercise 1.5.1 Letλ≤à Show that for anyκ, λ+κ≤à+κ, λãκ≤àãκ, λ κ ≤à κ , andκ λ ≤κ à
= 2 ℵ 0 ãc (since for nonempty sets X, Y, Z,(X Y ) Z ≡X Y ì Z )
So, by the Schr¨oder – Bernstein theorem, 2 c =ℵ c 0 =c c It follows that
Exercise 1.5.3 (Kăonig’s theorem, [58]) Let {λ i :i∈ I} and {à i :i∈I} be nonempty sets of cardinal numbers such that λ i < à i for eachi Show that i λ i