Editing Cardinality (section)

== Paradoxes ==
During the rise of set theory, several [[paradoxes]] (see: ''[[Paradoxes of set theory]]''). These can be divided into two kinds: ''real paradoxes'' and ''apparent paradoxes''. Apparent paradoxes are those which follow a series of reasonable steps and arrive at a conclusion which seems impossible or incorrect according to one's [[intuition]], but aren't necessarily logically impossible. Two historical examples have been given, ''Galileo's Paradox'' and ''Aristotle's Wheel'', in {{Section link|2=History|nopage=y}}. Real paradoxes are those which, through reasonable steps, prove a [[Contradiction|logical contradiction]]. The real paradoxes here apply to [[naive set theory]] or otherwise informal statements, and have been resolved by restating the problem in terms of a [[Set theory#Formalized set theory|formalized set theory]], such as [[Zermelo–Fraenkel set theory]].

=== Apparent paradoxes ===

==== Hilbert's hotel ====
{{Main|Hilbert's paradox of the Grand Hotel}}
[[File:Hilbert's Hotel.png|thumb|259x259px|Visual representation of Hilbert's hotel]]
[[Hilbert's Hotel]] is a [[thought experiment]] devised by the German mathematician [[David Hilbert]] to illustrate a counterintuitive property of infinite sets (assuming the axiom of choice), allowing them to have the same cardinality as a [[proper subset]] of themselves. The scenario begins by imagining a hotel with an infinite number of rooms, all of which are occupied. But then a new guest walks in asking for a room. The hotel accommodates by moving the occupant of room 1 to room 2, the occupant of room 2 to room 3, room three to room 4, and in general, room n to room n+1. Then every guest still has a room, but room 1 opens up for the new guest.<ref name=":5">{{Cite book |last=Gamov |first=George |title=One two three... infinity |title-link=One Two Three... Infinity |publisher=Viking Press |year=1947 |language=English |lccn=62-24541}} [https://archive.org/details/OneTwoThreeInfinity_158/ Archived] on 2016-01-06</ref>

Then, the scenario continues by imagining an infinite bus of new guests seeking a room. The hotel accommodates by moving the person in room 1 to room 2, room 2 to room 4, and in general, room n to room 2n. Thus, all the even-numbered rooms are occupied, but all the odd-numbered rooms are vacant, leaving room for the infinite bus of new guests. The scenario continues by assuming an infinite number of these infinite buses arrive at the hotel, and showing that the hotel is still able to accommodate. Finally, an infinite bus which has a seat for every [[real number]] arrives, and the hotel is no longer able to accommodate.<ref name=":5" />

==== Skolem's paradox ====
{{Main|Skolem's paradox}}
[[File:Lowenheim-skolem.svg|thumb|Illustration of the [[Löwenheim–Skolem theorem]], where <math>\mathcal{M}</math> and <math>\mathcal{N}</math> are models of set theory, and <math>\kappa</math> is an arbitrary infinite cardinal number.]]
In [[model theory]], a [[Model (mathematical logic)|model]] corresponds to a specific interpretation of a [[formal language]] or [[Theory (mathematical logic)|theory]]. It consists of a [[Domain of discourse|domain]] (a set of objects) and an [[Interpretation (logic)|interpretation]] of the symbols and formulas in the language, such that the axioms of the theory are satisfied within this structure. The [[Löwenheim–Skolem theorem]] shows that any model of set theory in [[first-order logic]], if it is [[consistent]], has an equivalent [[Structure (mathematical logic)|model]] which is countable. This appears contradictory, because [[Georg Cantor]] proved that there exist sets which are not countable. Thus the seeming contradiction is that a model that is itself countable, and which therefore contains only countable sets, [[Satisfiability|satisfies]] the first-order sentence that intuitively states "there are uncountable sets".<ref name=":6">{{Citation |last=Bays |first=Timothy |title=Skolem's Paradox |date=2025 |encyclopedia=The Stanford Encyclopedia of Philosophy |editor-last=Zalta |editor-first=Edward N. |url=https://plato.stanford.edu/entries/paradox-skolem/ |access-date=2025-04-13 |edition=Spring 2025 |publisher=Metaphysics Research Lab, Stanford University |editor2-last=Nodelman |editor2-first=Uri}}</ref>

A mathematical explanation of the paradox, showing that it is not a true contradiction in mathematics, was first given in 1922 by [[Thoralf Skolem]]. He explained that the countability of a set is not absolute, but relative to the model in which the cardinality is measured. Skolem's work was harshly received by [[Ernst Zermelo]], who argued against the limitations of first-order logic and Skolem's notion of "relativity", but the result quickly came to be accepted by the mathematical community.<ref>{{cite journal |last1=van Dalen |first1=Dirk |author-link1=Dirk van Dalen |last2=Ebbinghaus |first2=Heinz-Dieter |author2-link=Heinz-Dieter Ebbinghaus |date=Jun 2000 |title=Zermelo and the Skolem Paradox |url=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=9d51449b161b9e1d352e103af28fe07f5e15cb4b |journal=The Bulletin of Symbolic Logic |volume=6 |pages=145–161 |citeseerx=10.1.1.137.3354 |doi=10.2307/421203 |jstor=421203 |s2cid=8530810 |number=2 |hdl=1874/27769}}</ref><ref name=":6" />

=== Real paradoxes ===

==== Cantor's paradox ====
{{Main|Cantor's paradox}}
[[Cantor's theorem]] state's that, for any set <math>A,</math> possibly infinite, its [[powerset]] <math>\mathcal{P}(A)</math> has a strictly greater cardinality. For example, this means there is no bijection from <math>\N</math> to <math>\mathcal{P}(\N) \sim \R.</math> [[Cantor's paradox]] is a paradox in [[naive set theory]], which shows that there cannot exist a "set of all sets" or "[[Universe (mathematics)|universe set]]". It starts by assuming there is some set of all sets, <math>U := \{x \; | \; x \,\text{ is a set} \},</math> then it must be that <math>U</math> is strictly smaller than <math>\mathcal{P}(U),</math> thus <math>|U| \leq |\mathcal{P}(U)| .</math> But since <math>U</math> contains all sets, we must have that <math>\mathcal{P}(U) \subseteq U,</math> and thus <math>|\mathcal{P}(U)| \leq |U|.</math> Therefore <math>|\mathcal{P}(U)| = |U|,</math> contradicting Cantor's theorem. This was one of the original paradoxes that added to the need for a formalized set theory to avoid these paradoxes. This paradox is usually resolved in formal set theories by disallowing [[unrestricted comprehension]] and the existence of a universe set.

==== Set of all cardinal numbers ====
Similar to Cantor's paradox, the paradox of the set of all cardinal numbers is a result due to unrestricted comprehension. It often uses the definition of cardinal numbers as ordinal numbers for representatives. It is related to the [[Burali-Forti paradox]]. It begins by assuming there is some set <math>S := \{ X \, | X \text{ is a cardinal number}\}.</math> Then, if there is some largest element <math>\aleph \in S ,</math> then the powerset <math>\mathcal{P}(\aleph)</math> is strictly greater, and thus not in <math>S.</math> Conversly, if there is no largest element, then the [[Union (set theory)#Arbitrary union|union]] <math>\bigcup S</math> contains the elements of all elements of <math>S,</math> and is therefore greater than or equal to each element. Since there is no largest element in <math>S,</math> for any element <math>x \in S,</math> there is another element <math>y \in S</math> such that <math>|x| < |y|</math> and <math>|y| \leq \Bigl| \bigcup S \Bigr|.</math> Thus, for any <math>x \in S,</math> <math>|x| < \Bigl| \bigcup S \Bigr|,</math> and so <math>\Bigl| \bigcup S \Bigr| \notin S.</math>