Hubbry Logo
Uncountable setUncountable setMain
Open search
Uncountable set
Community hub
Uncountable set
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Uncountable set
Uncountable set
Uncountable set
View on Wikipedia
from Wikipedia

In mathematics, an uncountable set, informally, is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than aleph-null, the cardinality of the natural numbers.

Examples of uncountable sets include the set ⁠⁠ of all real numbers and set of all subsets of the natural numbers.

Characterizations

[edit]

There are many equivalent characterizations of uncountability. A set X is uncountable if and only if any of the following conditions hold:

  • There is no injective function (hence no bijection) from X to the set of natural numbers.
  • X is nonempty and for every ω-sequence of elements of X, there exists at least one element of X not included in it. That is, X is nonempty and there is no surjective function from the natural numbers to X.
  • The cardinality of X is neither finite nor equal to (aleph-null).
  • The set X has cardinality strictly greater than .

The first three of these characterizations can be proven equivalent in Zermelo–Fraenkel set theory without the axiom of choice, but the equivalence of the third and fourth cannot be proved without additional choice principles.

Properties

[edit]

If an uncountable set X is a subset of set Y, then Y is uncountable.

Examples

[edit]

The best known example of an uncountable set is the set ⁠⁠ of all real numbers; Cantor's diagonal argument shows that this set is uncountable. The diagonalization proof technique can also be used to show that several other sets are uncountable, such as the set of all infinite sequences of natural numbers ⁠⁠ (see: (sequence A102288 in the OEIS)), and the set of all subsets of the set of natural numbers. The cardinality of ⁠⁠ is often called the cardinality of the continuum, and denoted by , or , or (beth-one).

The Cantor set is an uncountable subset of ⁠⁠. The Cantor set is a fractal and has Hausdorff dimension greater than zero but less than one (⁠⁠ has dimension one). This is an example of the following fact: any subset of ⁠⁠ of Hausdorff dimension strictly greater than zero must be uncountable.

Another example of an uncountable set is the set of all functions from ⁠⁠ to ⁠⁠. This set is even "more uncountable" than ⁠⁠ in the sense that the cardinality of this set is (beth two), which is larger than .

A more abstract example of an uncountable set is the set of all countable ordinal numbers, denoted by Ω or ω1.[1] The cardinality of Ω is denoted (aleph-one). It can be shown, using the axiom of choice, that is the smallest uncountable cardinal number. Thus either , the cardinality of the reals, is equal to or it is strictly larger. Georg Cantor was the first to propose the question of whether is equal to . In 1900, David Hilbert posed this question as the first of his 23 problems. The statement that is now called the continuum hypothesis, and is known to be independent of the Zermelo–Fraenkel axioms for set theory (including the axiom of choice).

Without the axiom of choice

[edit]
Main article: Dedekind-infinite set

Without the axiom of choice, there might exist cardinalities incomparable to (namely, the cardinalities of Dedekind-finite infinite sets). Sets of these cardinalities satisfy the first three characterizations above, but not the fourth characterization. Since these sets are not larger than the natural numbers in the sense of cardinality, some may not want to call them uncountable.

If the axiom of choice holds, the following conditions on a cardinal are equivalent:

  • and
  • , where and is the least initial ordinal greater than

However, these may all be different if the axiom of choice fails. So it is not obvious which one is the appropriate generalization of "uncountability" when the axiom fails. It may be best to avoid using the word in this case and specify which of these one means.

See also

[edit]

References

[edit]

Bibliography

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Uncountable set

View on Grokipedia
from Grokipedia
In set theory, an uncountable set is an infinite set for which there exists no bijection with the natural numbers, meaning its elements cannot be enumerated in a sequence that includes every member exactly once. This property distinguishes uncountable sets from countable ones, which are either finite or equinumerous with the naturals via a one-to-one correspondence. The cardinality of an uncountable set is strictly greater than the countable infinity denoted by ℵ₀ (aleph-null). The notion of uncountability emerged from the foundational work of Georg Cantor (1845–1918), a German mathematician who revolutionized the understanding of infinity in the late 19th century. Cantor first demonstrated the uncountability of the real numbers in 1874 using a proof based on nested intervals, and later in 1891 provided the more famous diagonal argument to show that the interval (0,1) cannot be listed exhaustively. His diagonalization method assumes an enumeration of real numbers as infinite decimals and constructs a new number differing in the nth decimal from the nth listed number, proving no such complete list exists. Cantor's insights, initially met with controversy from figures like Leopold Kronecker, established set theory as a distinct branch of mathematics and introduced transfinite cardinalities. Uncountable sets play a central role in measuring the "sizes" of infinities, with the real numbers ℝ serving as the prototypical example, possessing cardinality 2^ℵ₀ known as the continuum c. Cantor's theorem generalizes this by proving that the power set of any set A, denoted 𝒫(A), has strictly greater cardinality than A itself, implying that the power set of the naturals 𝒫(ℕ) is also uncountable and equicardinal to the continuum. Other notable uncountable sets include the Cantor set, a fractal subset of [0,1] with measure zero yet cardinality c, and the set of all functions from ℕ to {0,1}. These concepts underpin broader implications in analysis, topology, and logic, such as the independence of the continuum hypothesis—which posits that no set has cardinality between ℵ₀ and c—from standard axioms like ZFC.

Fundamentals

Definition

In set theory, a set SS is defined as uncountable if it is infinite and there exists no bijection between SS and the set of natural numbers N\mathbb{N}. This means that the elements of SS cannot be listed in a sequence that exhausts the set, distinguishing it from sets that can be paired one-to-one with N\mathbb{N}. Equivalently, an uncountable set SS has cardinality ∣S∣>ℵ0|S| > \aleph_0, where ℵ0\aleph_0 denotes the cardinality of N\mathbb{N}, representing the smallest infinite cardinal. To contextualize uncountability, countability serves as the foundational prerequisite. A set is countable if it is finite or if it possesses cardinality ℵ0\aleph_0, meaning it is countably infinite (also termed denumerable, indicating a bijection with N\mathbb{N}). Thus, uncountable sets are precisely those infinite sets that exceed this countable threshold, marking the onset of larger infinities in the hierarchy of cardinals. The notion of uncountable sets was coined by Georg Cantor in the late 19th century, emerging from his pioneering investigations into the nature of infinite sets and their sizes. In set theory, cardinality ∣S∣|S| quantifies the "size" of a set SS, with infinite cardinals indexed by alephs starting from ℵ0\aleph_0 for countable infinities and proceeding to ℵ1\aleph_1 and beyond for uncountable ones.

Countability Comparison

A fundamental distinction between countable and uncountable sets lies in their structural behaviors under unions and their cardinal sizes. Countable sets, which include both finite sets and those bijectable with the natural numbers N\mathbb{N}, can be combined in limited ways while remaining countable, whereas uncountable sets exhibit strictly larger cardinality that prevents such combinations from encompassing them. A key theorem illustrating this contrast is that the union of countably many countable sets is itself countable. To see this, suppose {An∣n∈N}\{A_n \mid n \in \mathbb{N}\} is a countable collection of countable sets. For each nn, enumerate An={an,k∣k∈N}A_n = \{a_{n,k} \mid k \in \mathbb{N}\}. The union ⋃n∈NAn\bigcup_{n \in \mathbb{N}} A_n can then be enumerated using a pairing function that bijects N×N\mathbb{N} \times \mathbb{N} onto N\mathbb{N}, such as the Cantor pairing function π(m,n)=(m+n)(m+n+1)2+n\pi(m,n) = \frac{(m+n)(m+n+1)}{2} + n, which maps each pair (m,n)(m,n) to a unique natural number. By composing enumerations of each AnA_n with this pairing, the entire union admits a bijection with N\mathbb{N}, hence countable. This theorem has a direct implication for uncountable sets: no uncountable set can be expressed as a countable union of countable sets, as such a representation would render it countable by the above result. Thus, uncountable sets must transcend any such countable layering, underscoring their infinite and "larger" nature. Notably, while countable sets encompass finite sets (with cardinality less than or equal to ℵ0\aleph_0), uncountable sets are invariably infinite, possessing cardinality strictly greater than ℵ0\aleph_0. The Schröder-Bernstein theorem reinforces this inequality by establishing that if injections exist in both directions between two sets, then a bijection exists; however, since no injection maps an uncountable set onto a countable one (or vice versa, as countable sets inject into uncountable ones), their cardinalities cannot be equal, confirming the strict separation.

Characterizations

Cardinality Criteria

A set SS is uncountable if its cardinality ∣S∣|S| satisfies ∣S∣>ℵ0|S| > \aleph_0, where ℵ0\aleph_0 denotes the cardinality of the natural numbers N\mathbb{N}. Under the axiom of choice, the smallest such uncountable cardinal is ℵ1\aleph_1, which exceeds all countable cardinals and marks the onset of transfinite infinities beyond the countable realm. Transfinite cardinals are indexed by ordinals via the aleph numbers ℵα\aleph_\alpha, where α\alpha ranges over all ordinals, providing a hierarchy of infinite sizes. Specifically, ℵ0\aleph_0 is the smallest infinite cardinal, corresponding to countably infinite sets, while uncountable cardinals commence at ℵ1\aleph_1 and proceed as ℵ2,ℵ3,…,ℵω,…\aleph_2, \aleph_3, \dots, \aleph_\omega, \dots, each strictly larger than the previous under the standard ordering of cardinals. This sequence ensures that no uncountable cardinal lies between ℵ0\aleph_0 and ℵ1\aleph_1, establishing ℵ1\aleph_1 as the minimal uncountable size in the cardinal hierarchy. The continuum hypothesis (CH) posits that the cardinality of the real numbers ∣R∣=2ℵ0|\mathbb{R}| = 2^{\aleph_0} equals ℵ1\aleph_1, implying no cardinal exists strictly between ℵ0\aleph_0 and the continuum. However, Kurt Gödel demonstrated in 1940 that CH is consistent with Zermelo-Fraenkel set theory with the axiom of choice (ZFC), and Paul Cohen proved in 1963 its independence from ZFC, leaving its truth undecided within the standard axioms. Uncountable cardinals arise from well-orderings of sets, where each cardinal κ\kappa corresponds to an initial ordinal, the smallest ordinal of that cardinality. The countable ordinals culminate at ω\omega, the order type of N\mathbb{N}, beyond which uncountable ordinals begin; the least uncountable ordinal ω1\omega_1 has cardinality ℵ1\aleph_1 and serves as the prototype for uncountable well-orderings, as every proper initial segment of ω1\omega_1 is countable. Thus, uncountable cardinals are precisely the cardinalities of uncountable initial ordinals, which are limit ordinals exceeding ω\omega.

Bijection and Injection Tests

One practical criterion for establishing that a set SS is uncountable is the absence of a bijection between SS and the set of natural numbers N\mathbb{N}. Equivalently, SS is uncountable if there exists no injection from SS into N\mathbb{N}, or no surjection from N\mathbb{N} onto SS. This bijection test directly contrasts countability, where such a one-to-one correspondence exists, and serves as a foundational method to verify uncountability without invoking higher cardinalities. Cantor's theorem provides a generalized diagonalization argument to demonstrate the absence of a surjection from N\mathbb{N} onto certain uncountable sets, such as the power set P(N)\mathcal{P}(\mathbb{N}). Specifically, assume for contradiction a surjection f:N→P(N)f: \mathbb{N} \to \mathcal{P}(\mathbb{N}), and define the set D={n∈N∣n∉f(n)}D = \{ n \in \mathbb{N} \mid n \notin f(n) \}; then DD cannot equal f(k)f(k) for any kk, as k∈Dk \in D if and only if k∉f(k)k \notin f(k), yielding a contradiction. This diagonalization technique extends to prove no surjection from N\mathbb{N} onto P(S)\mathcal{P}(S) for any set SS, confirming P(S)\mathcal{P}(S) is uncountable whenever SS is infinite. An injection-based test for uncountability applies when a set SS admits an injection into the real numbers R\mathbb{R} but no injection into N\mathbb{N}. Since R\mathbb{R} is uncountable—established via diagonalization or nested intervals—and any subset of a countable set is countable, the lack of an injection into N\mathbb{N} implies SS cannot be countable. For instance, if an injection g:S→Rg: S \to \mathbb{R} exists and SS is infinite, verifying no bijection with N\mathbb{N} (e.g., by assuming an enumeration and deriving a contradiction) confirms uncountability. Under the axiom of choice, uncountable sets are Dedekind-infinite, meaning they admit a bijection with a proper subset of themselves, but the key bijection test emphasizes the absence of any bijection with N\mathbb{N}. A set is Dedekind-infinite if there exists an injection from N\mathbb{N} into it (equivalently, if it contains a countably infinite subset), allowing a proper subset to match its cardinality via shifting. However, the diagnostic focus remains on failing the bijection or injection test with N\mathbb{N}, distinguishing uncountable sets from countable infinite ones. For ordered sets, the nested intervals method offers a constructive test for uncountability, particularly in complete ordered fields like R\mathbb{R}. Assume an enumeration {xn}n=1∞\{x_n\}_{n=1}^\infty of a bounded interval such as (0,1)(0,1); construct nested closed intervals In=[an,bn]I_n = [a_n, b_n] with bn−an=1/2nb_n - a_n = 1/2^n, ensuring xn∉Inx_n \notin I_n at each step, and In+1⊆InI_{n+1} \subseteq I_n. By the nested interval property, the intersection ⋂n=1∞In\bigcap_{n=1}^\infty I_n contains a point xx not in the enumeration, contradicting countability. This bisection-inspired approach generalizes to linearly ordered sets with completeness axioms, providing a mapping-free verification of uncountability through interval avoidance.

Properties

Cardinal Operations

Cardinal arithmetic extends the operations of addition, multiplication, and exponentiation to infinite cardinals, revealing behaviors that differ markedly from finite arithmetic, particularly for uncountable cardinals. For addition, the sum of two infinite cardinals κ≥ℵ0\kappa \geq \aleph_0 and λ\lambda is given by κ+λ=max⁡(κ,λ)\kappa + \lambda = \max(\kappa, \lambda). This holds because the disjoint union of sets of these cardinalities can be bijected with the larger set. For uncountable cardinals, such as the smallest uncountable cardinal ℵ1\aleph_1, adding a countable infinity yields ℵ1+ℵ0=ℵ1\aleph_1 + \aleph_0 = \aleph_1. Multiplication of infinite cardinals κ≥ℵ0\kappa \geq \aleph_0 and λ>0\lambda > 0 satisfies κ⋅λ=max⁡(κ,λ)\kappa \cdot \lambda = \max(\kappa, \lambda), as the cardinality of the Cartesian product aligns with the dominant size. Thus, multiplying an uncountable cardinal by any countable or smaller infinite cardinal preserves the uncountable size, for instance, ℵ1⋅ℵ0=ℵ1\aleph_1 \cdot \aleph_0 = \aleph_1. Exponentiation is defined as κλ\kappa^\lambda being the cardinality of the set of functions from a set of size λ\lambda to one of size κ\kappa. Cantor's theorem states that for any cardinal κ\kappa, 2κ>κ2^\kappa > \kappa, implying that the power set cardinality strictly exceeds the original. In particular, 2ℵ02^{\aleph_0}, the cardinality of the continuum, is uncountable and greater than ℵ0\aleph_0. A key absorption property arises from these operations: the countable union of sets each of uncountable cardinality κ\kappa has cardinality κ\kappa, since it equals ℵ0⋅κ=κ\aleph_0 \cdot \kappa = \kappa. This underscores how uncountable cardinals dominate countable additions and multiplications without growth.

Subset and Union Behaviors

One key structural property of uncountable sets in Polish spaces is the perfect set property, which asserts that every uncountable Polish space contains a perfect subset—a closed set with no isolated points, hence uncountable itself. This follows from the fact that Polish spaces, being separable complete metric spaces, allow the construction of such nonempty perfect subsets via a Cantor-Bendixson-like decomposition, where the scattered part is countable, leaving an uncountable perfect kernel if the space is uncountable. Consequently, uncountable Polish spaces cannot be scattered and contain a subset homeomorphic to the Cantor space, highlighting their topological richness despite potential pathologies in subsets. Bernstein sets provide a striking example of uncountable sets with atypical subset behaviors, constructed using the axiom of choice as subsets of the real line that intersect every uncountable closed set but contain no uncountable closed subset themselves. Such sets are uncountable, as they meet every perfect set, yet both the set and its complement avoid containing any perfect subset, rendering them "totally imperfect" in a strong sense. This construction relies on well-ordering the continuum and enumerating perfect sets to ensure transversal intersections, demonstrating how the axiom of choice enables sets that evade standard closure properties. Vitali sets exemplify non-measurable uncountable subsets of the reals, constructed by selecting one representative from each equivalence class under rational translations within [0,1), yielding a set that is uncountable but lacks Lebesgue measurability. The non-measurability arises because the countable disjoint union of its rational translates covers [0,1) up to measure zero, yet assigning a measure to the Vitali set leads to a contradiction with countable additivity and translation invariance of Lebesgue measure. Thus, not every uncountable subset of R\mathbb{R} is Lebesgue measurable, underscoring limitations in measure theory for arbitrary subsets. Regarding unions, the union of any collection containing at least one uncountable set is uncountable. In particular, the union of any number of uncountable sets is uncountable. In cardinal arithmetic, the cardinality of the union satisfies ∣⋃i∈IAi∣≤∣I∣×sup⁡i∈I∣Ai∣|\bigcup_{i \in I} A_i| \leq |I| \times \sup_{i \in I} |A_i|, providing an upper bound controlled by the index set cardinality and the individual set sizes. For uncountable index sets, this bound is uncountable, though the actual cardinality depends on overlaps and specific sizes. Regarding decompositions, uncountable sets in separable metric spaces can possess countable dense subsets while remaining uncountable overall, as seen in the reals where the rationals form a countable dense subset. This separability ensures that the topology is generated by countably many basic open sets, allowing a countable dense subset to approximate the entire space, yet the uncountable cardinality persists due to the presence of continuum-many limit points. Such decompositions illustrate how uncountable sets can be "sparsely" populated topologically without sacrificing their size.

Examples

Real Numbers

The set of real numbers R\mathbb{R} serves as the canonical example of an uncountable set, illustrating a cardinality strictly larger than that of the natural numbers N\mathbb{N}. To demonstrate this, Georg Cantor employed his diagonal argument, which shows that no surjective function exists from N\mathbb{N} to the open interval (0,1)(0,1), and hence to R\mathbb{R}. Assume, for contradiction, that there is an enumeration {rn}n=1∞\{r_n\}_{n=1}^\infty of all real numbers in (0,1)(0,1), where each rnr_n has a decimal expansion rn=0.dn1dn2dn3…r_n = 0.d_{n1}d_{n2}d_{n3}\dots with digits dni∈{0,1,…,9}d_{ni} \in \{0,1,\dots,9\}. Construct a new real number x=0.x1x2x3⋯∈(0,1)x = 0.x_1 x_2 x_3 \dots \in (0,1) by defining xi=4x_i = 4 if dii≠4d_{ii} \neq 4 and xi=5x_i = 5 if dii=4d_{ii} = 4 for each ii. This xx differs from every rnr_n in the nnth decimal place, so xx is not in the enumeration, contradicting the assumption of surjectivity. The cardinality of R\mathbb{R}, denoted ∣R∣=c|\mathbb{R}| = \mathfrak{c} (the continuum) or 2ℵ02^{\aleph_0}, is uncountable and equals the cardinality of the power set of N\mathbb{N}. This follows from the existence of an injection from (0,1)(0,1) to the set of all subsets of N\mathbb{N} via binary expansions (with care for non-unique representations like 0.0111⋯=0.1000…0.0111\dots = 0.1000\dots), and Cantor's theorem that ∣P(S)∣>∣S∣|\mathcal{P}(S)| > |S| for any set SS. Under the continuum hypothesis (CH), formulated by Cantor in 1878, c=ℵ1\mathfrak{c} = \aleph_1, the smallest uncountable cardinal, though CH is independent of standard set theory axioms. The sets R\mathbb{R} and (0,1)(0,1) have the same cardinality, as shown by the bijection f:(0,1)→Rf: (0,1) \to \mathbb{R} given by f(x)=tan⁡(π(x−1/2))f(x) = \tan(\pi(x - 1/2)), which is continuous, strictly increasing, and maps the endpoints asymptotically to ±∞\pm \infty. Despite this equivalence, Q\mathbb{Q} is countable and dense in R\mathbb{R}, meaning that between any two distinct reals a<ba < b, there exists q∈Qq \in \mathbb{Q} with a<q<ba < q < b; this follows from the Archimedean property, as one can find integers m,nm,n such that a<m/n<ba < m/n < b. Cantor's enumeration proves ∣Q∣=ℵ0|\mathbb{Q}| = \aleph_0 by listing positives as p/qp/q in lowest terms via a diagonal traversal of the grid, extending to all rationals. Thus, the uncountability of R\mathbb{R} arises from the irrationals, which are dense as well.

Power Sets and Generalizations

One fundamental example of an uncountable set arises from the power set operation applied to the natural numbers. The power set 𝒫(ℕ) is the set of all subsets of ℕ, and by Cantor's theorem, its cardinality satisfies |𝒫(ℕ)| > |ℕ| = ℵ₀, establishing that 𝒫(ℕ) is uncountable. More precisely, the cardinality of 𝒫(ℕ) is 2^{ℵ₀}, which equals the cardinality of the continuum 𝔠. Cantor's theorem generalizes beyond ℕ: for any set S, the cardinality of its power set satisfies |𝒫(S)| > |S|, implying that the power set of any infinite set is uncountable. In particular, since ℕ is infinite and countable, 𝒫(ℕ) provides a concrete uncountable set of cardinality 2^{ℵ₀}. This construction highlights how power sets generate larger infinities iteratively, producing an infinite hierarchy of uncountable cardinals. Applying the power set to larger sets yields even greater uncountable cardinalities. For instance, the power set 𝒫(ℝ) of the real numbers has cardinality 2^𝔠, which exceeds 𝔠 and thus represents a strictly larger uncountable infinity. Uncountable sets also emerge in function spaces. The set of all functions from ℕ to ℕ, denoted ^ℕℕ, is uncountable with cardinality 2^{ℵ₀}. This follows from an injection into 𝒫(ℕ × ℕ) via graphs of functions (subsets where each first coordinate appears exactly once), since |ℕ × ℕ| = ℵ₀ and |𝒫(ℕ × ℕ)| = 2^{ℵ₀}, implying |^ℕℕ| ≤ 2^{ℵ₀}. For the reverse inequality, the set of functions from ℕ to {0,1} (subsets of ℕ, cardinality 2^{ℵ₀}) injects into ^ℕℕ by identifying {0,1} with {0,1} ⊆ ℕ, so |^ℕℕ| = 2^{ℵ₀}. In cardinal arithmetic, such exponentiations generalize the power set construction to mappings between sets of arbitrary sizes.

Without Axiom of Choice

Dependent Properties

The axiom of choice (AC) implies the well-ordering theorem, which states that every set can be well-ordered, including uncountable sets. A well-ordering on a set is a total order such that every nonempty subset has a least element, allowing the assignment of an ordinal number to represent the order type of the set. For uncountable sets like the real numbers, this yields an ordinal of cardinality c\mathfrak{c}, the continuum, though the explicit well-ordering remains non-constructive without additional assumptions. This property enables the extension of transfinite induction and recursion to uncountable domains, facilitating proofs in set theory and analysis. AC also ensures the comparability of cardinals, meaning that for any two cardinal numbers κ\kappa and λ\lambda, either κ≤λ\kappa \leq \lambda or λ≤κ\lambda \leq \kappa. Without AC, there exist models where infinite cardinals are incomparable, but under AC, every uncountable cardinal can be compared to others, such as ℵ1≤2ℵ0\aleph_1 \leq 2^{\aleph_0} or the negation thereof via the continuum hypothesis. This comparability underpins the structure of the cardinal hierarchy and is equivalent to AC via Zorn's lemma applied to chains of cardinals. The Vitali construction provides an example of an uncountable non-Lebesgue measurable set in R\mathbb{R}, relying on AC to select representatives. Consider the equivalence relation on R\mathbb{R} where x∼yx \sim y if x−y∈Qx - y \in \mathbb{Q}; the equivalence classes form a partition of R\mathbb{R} into uncountably many disjoint sets, each dense in R\mathbb{R}. AC allows choosing one representative from each class to form the Vitali set V⊆[0,1]V \subseteq [0,1], which is uncountable and cannot be assigned a Lebesgue measure, as the countable disjoint translates V+qV + q for q∈Q∩[−1,1]q \in \mathbb{Q} \cap [-1,1] cover [0,2][0,2] while overlapping minimally. This demonstrates the existence of pathological uncountable subsets incompatible with intuitive measure properties. The Banach-Tarski paradox illustrates a counterintuitive decomposition of uncountable sets using AC. Specifically, the unit ball in R3\mathbb{R}^3 can be partitioned into finitely many (as few as five) non-measurable pieces that can be rigidly reassembled via isometries into two copies of the unit ball. The construction exploits the free group structure within the rotation group SO(3) and applies AC to select representatives from orbits under group actions, yielding sets without well-defined volume. This uncountable phenomenon highlights how AC enables paradoxical behaviors in geometric measure theory, where volume preservation fails for such decompositions.

Models and Counterexamples

In set theory without the axiom of choice (AC), various models demonstrate the independence of statements involving uncountable sets, highlighting how the failure of AC can lead to counterintuitive cardinal behaviors. One prominent example is provided by Cohen forcing, a technique developed by Paul Cohen to construct models of ZF where the continuum hypothesis (CH) fails. Specifically, Cohen showed that it is consistent with ZF that the cardinality of the continuum, 2ℵ02^{\aleph_0}, equals ℵ2\aleph_2, meaning the power set of the natural numbers has cardinality strictly larger than ℵ1\aleph_1 but not arbitrarily large. This model illustrates that uncountable cardinals like the continuum can take on values beyond the immediate successor in the aleph hierarchy without violating ZF axioms. Fraenkel-Mostowski (FM) permutation models offer another class of counterexamples, constructed using a set of atoms and group actions to interpret the universe in a way that violates AC while preserving ZF minus AC (ZFA). In the basic Fraenkel model, the set of atoms AA is infinite, but every subset of AA that is "symmetric" (invariant under finite-support permutations) lacks a countable infinite subset. This implies that AA is not countable, as there is no injection from ω\omega into AA, yet proofs of uncountability relying on AC—such as well-ordering principles—fail, rendering AA a paradoxical infinite set whose uncountability cannot be established via choice-dependent methods. Without AC, Dedekind-finite infinite sets provide further counterexamples to standard notions of infinity tied to uncountability. A set is Dedekind-finite if it is not equinumerous to any proper subset of itself, meaning no injection from ω\omega exists into the set. In ZF alone, it is consistent that infinite Dedekind-finite sets exist, such as amorphous sets where every subset is finite or cofinite, but the set itself admits no countably infinite subset. These sets are uncountable in the sense of lacking a bijection with ω\omega, yet they defy the ZFC equivalence between Dedekind-finiteness and actual finiteness, complicating the characterization of uncountable structures. The Russell socks analogy underscores the failure of AC in handling families of pairs, particularly when extended to uncountable collections. Bertrand Russell illustrated that while one can select the left shoe from each pair in an infinite collection of distinguishable shoe pairs without AC (via an explicit rule), selecting one sock from each pair in an infinite collection of identical pairs requires arbitrary choice, as no distinguishing feature exists. In models without AC, this extends to uncountable families of two-element sets, where no choice function can be defined without additional assumptions, leading to counterexamples where uncountable unions or products cannot be well-defined in the expected way.

References

  1. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/An_Introduction_to_Number_Theory_(Veerman)/01%3A_A_Quick_Tour_of_Number_Theory/1.04%3A_Countable_and_Uncountable_Sets
  2. https://www.whitman.edu/mathematics/higher_math_online/section04.10.html
  3. https://www.cs.cmu.edu/afs/cs/academic/class/15251-f03/Site/Biographies/cantor.htm
  4. http://galileo.math.siu.edu/Courses/452/F16/frankscantor.pdf
  5. https://plato.stanford.edu/entries/set-theory/
  6. https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/09%253A_Finite_and_Infinite_Sets/9.02%253A_Countable_Sets
  7. http://people.whitman.edu/~guichard/260/halmos__naive_set_theory.pdf
  8. https://mathworld.wolfram.com/PairingFunction.html
  9. https://mathworld.wolfram.com/UncountablyInfinite.html
  10. https://mathworld.wolfram.com/Aleph-1.html
  11. https://mathworld.wolfram.com/Aleph.html
  12. https://mathworld.wolfram.com/ContinuumHypothesis.html
  13. https://plato.stanford.edu/entries/continuum-hypothesis/
  14. https://www.math.ucdavis.edu/~hunter/intro_analysis_pdf/intro_analysis.pdf
  15. https://people.math.harvard.edu/~auroux/112s19/Notes_Math_112_march5.pdf
  16. https://www.andrew.cmu.edu/course/15-251/Lectures/lecture20.pdf
  17. https://metaphor.ethz.ch/x/2023/hs/401-1261-07L/ex/LectureNotesWeek12.pdf
  18. http://pirate.shu.edu/~wachsmut/ira/infinity/proofs/dedekind.html
  19. https://people.math.wisc.edu/~miller/res/ded.pdf
  20. https://tildesites.geneseo.edu/~aguilar/public/assets/courses/324/real-analysis-cesar-aguilar.pdf
  21. https://mathworld.wolfram.com/CardinalAddition.html
  22. https://mathworld.wolfram.com/CardinalMultiplication.html
  23. https://mathworld.wolfram.com/CardinalExponentiation.html
  24. http://homepages.math.uic.edu/~marker/math512/dst.pdf
  25. https://www2.math.uconn.edu/~solomon/notes/desc2.pdf
  26. https://projecteuclid.org/journals/real-analysis-exchange/volume-19/issue-2/SOME-REMARKS-ON-DIFFERENCE-SETS-OF-BERNSTEIN-SETS/10.2307/44152397.pdf
  27. https://www.math.toronto.edu/ivan/mat327/docs/notes/04-countability.pdf
  28. https://www.math.ucdavis.edu/~hunter/m127a_19/rat_dense.pdf
  29. https://www.palomar.edu/math/wp-content/uploads/sites/134/2017/12/Infinity-and-its-cardinalities.pdf
  30. https://legacy.earlham.edu/~peters/writing/infapp.htm
  31. https://tildesites.geneseo.edu/~baldwin/math239/spring2019/Uncountable.pdf
  32. https://plato.stanford.edu/entries/axiom-choice/
  33. https://plato.stanford.edu/entries/axiom-choice/notes.html
Add your contribution
Related Hubs
User Avatar
No comments yet.