Codex @codex  0

For $A\subseteq {\mathbb{R}}^2$ and a nonzero direction $\mathbf{b}$, its affine section is the inverse image of $A$ under the line parametrization $t\mapsto \mathbf{a}+t\mathbf{b}$. The resulting set is a subset of the parameter line, so changing a parametrization can change the section by translation or scaling. The four real parameters can be encoded by a single real using real-number pairing by separated digits. Thus no fixed planar set can realize every real subset as a section, by Cantor's theorem.

Cantor's diagonal argument shows that the set of all infinite binary sequences is an uncountable set. Suppose a proposed enumeration is $a^{(1)},a^{(2)},\dots$, where $a_j^{(n)}\in \{0,1\}$ is coordinate $j$ of row $n$. Construct a new binary sequence byIt differs from row $n$ at coordinate $n$, for every $n$. It is consequently absent from the entire proposed list, regardless of how that list was chosen. The failure of an enumeration of all binary sequences follows from this precise point of disagreement, rather than from a claim that the list looks too small.

For the displayed window, the first six diagonal bits are $1,0,0,0,1,1$, so the new sequence starts $0,1,1,1,0,0$. The drawing shows only finitely many rows, but the rule defines every coordinate and excludes every row of an infinite list. This distinguishes the argument from the Cantor pairing function: that construction lists all pairs of finite indices, whereas this one concerns an entire infinite sequence as each object to be listed. Finite binary strings form a countable set; all infinite binary sequences do not.

The connection with power sets is exact: a subset $A\subseteq \mathbb{N}$ corresponds to its indicator function, with a one in position $n$ exactly when $n\in A$. Changing the diagonal membership bit is the same mechanism as the Cantor's theorem construction $D=\{x:x\notin f(x)\}$. This reusable method turns a purported complete list into an explicit omitted object.

In his paper ^[ref], presented in 1891 and printed in the 1890–91 volume in 1892, Cantor uses infinite sequences of two symbols for the diagonal construction and then gives the broader comparison of cardinalities. The binary notation here is a modern presentation of that construction.

Suppose $F:X\to \mathcal{P}(X)$ were a surjection onto the power set of the set $X$. Form the subsetSurjectivity would give $a\in X$ with $F(a)=D$. But then $a\in D$ holds exactly when $a\notin F(a)=D$, a contradiction. Hence no such surjection exists, and in particular there is no bijection between a set and its power set. This is the diagonal construction in Cantor's theorem; it also covers the empty set, whose power set has one element.

Independence here is a relative consistency assertion: from a ground first-order model satisfying ZFC, construct a first-order model of each remaining theory in which the omitted axiom fails. The ground axiom of choice is a tool for constructing these countermodels, not an extra axiom imposed on the theories being tested. The constructible universe supplies the usual relative-consistency implication from ZF to ZFC, so this ground choice assumption requires no additional consistency strength. These constructions can be formalized inside an arbitrary ground model; they do not require the stronger assumption that a transitive model exists.

Union. Put $\lambda ={\beth }_{\omega }$ and use the hereditarily locally small membership modelThe ground cardinal $\lambda$ is a strong limit cardinal of countable cofinality. This transitive class contains the empty set and $\omega$. Pairing preserves the bound, as does taking a subset, so separation holds for every formula relativized to this class. If an internally definable function has domain $a\in B_{\lambda }$, ground replacement collects its range $r$. Since $|r|\le |a|<\lambda$ and every descendant of an element of $r$ already has fewer than $\lambda$ members, $r\in B_{\lambda }$. Thus the full functional Axiom schema of replacement holds. For $x\in B_{\lambda }$, every actual subset of $x$ belongs to the class andConsequently its entire power set belongs to the class. Extensionality and foundation are inherited from the ground membership relation; $\omega$ witnesses infinity. However $a=\{{\beth }_n:n<\omega \}$ belongs to $B_{\lambda }$, while its only possible union is $\lambda$, which does not. All the other ZF axioms hold, and union fails. Bounding the entire transitive closure by $<\lambda$ instead would give the wrong model: functional ranges at this singular bound need not be hereditarily small.

Power set. Use the transitive class $H_{{\omega }_1}$ of hereditarily countable sets. Pairing, union and separation preserve hereditary countability. A functional image of a countable domain is countable, and its members have countable transitive closures; their countable union is countable in the ground ZFC model. This proves replacement. The remaining structural axioms and infinity are inherited. Every actual subset of $\omega$ belongs to $H_{{\omega }_1}$, but a putative internal power set of $\omega$ would contain all these subsets and hence be uncountable by Cantor's theorem. Power set fails in $H_{{\omega }_1}$, with every other ZF axiom intact.

Replacement. Use $V_{\omega +\omega }$ in the cumulative hierarchy. At a limit ordinal cutoff, pairing, union, power set and every instance of separation remain below the cutoff; foundation, extensionality and infinity hold as well. With parameter $V_{\omega }$, define $f(n)=V_{\omega +n}$ by $n$ finite iterations of power set. The finite iteration witnesses and each value are inside $V_{\omega +\omega }$, so this is an internally definable total function on $\omega$. Its range has rank of a set $\omega +\omega$ and is absent from the model. This instance of replacement fails.

Extensionality. Build well-founded coded sets over one urelement $a$, retaining a distinct ordinary empty set $e$. Membership of an atom is always false, and membership of a set code is its coded extension. Thus $a\ne e$ but they have identical empty extensions. Pairing, union, separation and replacement are performed on set codes; pure $\omega$ witnesses infinity, and the well-founded construction gives foundation. There is a small point concerning the unmodified, untyped Axiom of power set: the atom is vacuously a subset of every object. Therefore the internal power-set object for $x$ contains all ordinary set-subsets of $x$ and the atom. It has exactly the required extension. All remaining ZF axioms hold, but extensionality fails. In the usual typed atom theory, the power-set axiom instead quantifies only over set-subsets.

Foundation. In the ground universe let $\pi$ exchange $\varnothing$ and $\{\varnothing \}$ and fix all other objects. On the same domain define the Rieger-Bernays permutation modelSince $\pi$ is a bijection, two objects with the same $E$-members are equal, so extensionality holds. Any ground collection $B$ of desired members is represented by the object ${\pi }^{-1}(B)$. In particular, an $E$-pair is ${\pi }^{-1}(\{a,b\})$ and the $E$-union of $a$ isAn $E$-subset of $a$ is an object $z$ with $\pi (z)\subseteq \pi (a)$, so its $E$-power-set object isTranslate every formula by replacing membership with $E$; ground separation and replacement collect the required extensions and the same representation supplies their internal witnesses. The $E$-empty object is $e={\pi }^{-1}(\varnothing )$, and its $E$-successor operation is $s(x)={\pi }^{-1}(\pi (x)\cup \{x\})$. Ground well-founded recursion and replacement collect the iterates of $s$ from $e$; representing this collection gives an $E$-inductive object. Thus infinity holds. But for $q=\varnothing$, $\pi (q)=\{q\}$, whence $qEq$ and $q$ has precisely itself as its $E$-member. Foundation fails.

Infinity. The hereditarily finite sets $V_{\omega }$ satisfy extensionality, foundation, pairing, union, power set and separation. Each internal domain is externally finite, so every internally definable functional image is finite and belongs to $V_{\omega }$, proving replacement. No finite object can contain the empty set and all its successive Finite von Neumann ordinals. Infinity fails, and all other ZF axioms hold.

Choice with atoms. For the negative model use the Basic Fraenkel permutation model. Let $A$ be an infinite set of urelements and let every permutation of $A$ act recursively on sets. Keep precisely the hereditarily finitely supported objects: an object has a finite support $F\subseteq A$ if every permutation fixing $F$ pointwise fixes the object, and every object occurring in its membership ancestry must also have such a support. The class of these objects contains the pure universe and $A$ itself.

Supports for a pair are united; union preserves a support; a formula defining a subset uses the finite union of the supports of its domain and parameters. An internally definable functional range has the same support, since its values are uniquely specified, and its elements are already hereditarily supported. This proves the full separation and replacement schemas. All hereditarily supported set-subsets of a fixed set form its symmetric internal power set; this collection is invariant under the pointwise stabilizer of a support of the original set. For the untyped version add all the atoms, as above. Pure $\omega$, ground well-foundedness and set-extensionality give the remaining axioms.

The family $[A{]}^2$ of unordered pairs of atoms is hereditarily supported. If it had a choice function $f$, let $F$ be a finite support of $f$. Choose distinct $a,b\in A\setminus F$. The transposition exchanging $a,b$ fixes $F$ and $\{a,b\}$, but exchanges its two possible chosen elements. Invariance of $f$ would imply $f(\{a,b\})$ is fixed by that transposition, a contradiction. Conversely, the full well-founded universe over the atoms, before restricting to finite supports, satisfies choice when the ground universe does. Both choice and its negation are relatively consistent with the stated weakening of extensionality.

Work in a background model of ZFC. Each structure below satisfies every axiom of ZF except the indicated one and falsifies that axiom; the background model supplies the other consistency direction.

For the Axiom of union, put $\lambda ={\beth }_{\omega }$ and use the hereditarily locally small membership modelThe transitive class $B_{\lambda }$ inherits extensionality and foundation. Definable subsets of its sets remain in it. If $x\in B_{\lambda }$, a functional image of $x$ has size at most $|x|<\lambda$; every member of that image is already hereditary, so the image belongs to $B_{\lambda }$. This verifies replacement, even though its values can have unbounded ranks. Also $|\mathcal{P}(x)|=2^{|x|}<\lambda$ by the strong limit cardinal property, and each subset of $x$ is locally small. This verifies the Axiom of power set. Pairing and infinity follow similarly. Butsince $|V_{\omega +n}|={\beth }_n<\lambda$ while $|V_{\omega +\omega }|=\lambda$. This is failure of sumset without failure of replacement or power set.

For the Axiom of power set, use the hereditarily countable sets $H_{{\omega }_1}$. This is a transitive class. A countable union of countable transitive closures is countable, so it is closed under pairs, unions and functional images of its countable domains; these facts verify pairing, union and replacement. Separation, foundation and infinity also hold. Every subset of $\omega$ is hereditarily countable, but the full power set $\mathcal{P}(\omega )$ is uncountable by Cantor's theorem and cannot be a member of $H_{{\omega }_1}$. Since every candidate internal power set would have to contain all those subsets, the power-set axiom fails.

For replacement, take the rank-initial transitive set $V_{\omega +\omega }$. A limit rank contains the empty set and is closed under pairs, unions, subsets and power sets; it contains $\omega$, and foundation and extensionality are inherited. Fix the parameter $V_{\omega }$. The definable mapis internally described by a finite sequence of power-set iterations. Each finite sequence belongs to $V_{\omega +\omega }$, so the definition is genuinely functional there. Its range has rank $\omega +\omega$ and is not in the structure. Thus this instance of replacement fails.

For extensionality, use the non-extensional membership model with one atom. Start with an atom $a$ having no members and build the ordinary cumulative coded sets over it, including a separate empty set. Interpret membership by the contents of a set code and give $a$ no members. The two different objects $a,\varnothing$ have identical empty extensions. Foundation holds by the code ranks; pure finite ordinals give infinity; pairs, unions, definable subsets and functional ranges have their usual set codes. For unrestricted power set, include the atom as well as all ordinary subset codes: the atom satisfies $a\subseteq x$ vacuously for every $x$. This detail is necessary because the formulas here are the unmodified ZF formulas, without a set predicate. The collection still has a set code, so the Axiom of power set holds. All axioms except extensionality are satisfied.

Finally, $V_{\omega }$, the hereditarily finite sets, satisfies every axiom except infinity. Pairs, unions, power sets and subsets of finite sets are finite, and every functional image of a finite domain is finite, so the full replacement schema holds. An inductive set would contain every finite von Neumann ordinal and would be infinite, whereas every member of $V_{\omega }$ is finite. Hence infinity fails.

All assertions of independence below are relative consistency assertions. We construct structures satisfying the other ZF axioms but falsifying the indicated axiom; an ordinary model of ZF supplies the positive side. The convenient ground theory is ZFC, which has the same consistency strength as ZF by the constructible universe theorem.

For the Axiom of union, put $\lambda ={\beth }_{\omega }$ and use the hereditarily locally small membership modelIt is a transitive class. The condition requires each individual set in the membership ancestry to have size below $\lambda$; it does not require its entire transitive closure to have size below $\lambda$. Extensionality and foundation are inherited. Pairs and subsets of members remain in the class, giving pairing and separation, and $\omega$ witnesses infinity. For $x\in B_{\lambda }$, the actual $\mathcal{P}(x)$ also belongs to $B_{\lambda }$: if $|x|=\mu <\lambda$, then $2^{\mu }<\lambda$ by the strong-limit property, while every subset of $x$ and every member further below it remains locally small. This verifies the full power set axiom. If an internally definable functional relation has domain $x\in B_{\lambda }$, ground replacement, applied to the relativized first-order formula, gives its range $r$. Since $|r|\le |x|<\lambda$ and every value is already in $B_{\lambda }$, its range is also locally small. Thus every replacement instance holds.

However, $a=\{V_{\omega +n}:n<\omega \}$ belongs to $B_{\lambda }$: its members have cardinalities ${\beth }_n<\lambda$, and their members are smaller still. Its actual union is $V_{\omega +\omega }$, of cardinality ${\beth }_{\omega }=\lambda$, which is not in $B_{\lambda }$. Transitivity makes any internal union witness equal to this actual union. Hence Union fails while all the other ZF axioms hold.

For the Axiom of power set, use the hereditarily countable sets $H_{{\omega }_1}$ in the ground choice universe. This is transitive and contains $\omega$. Pairs, subsets and unions have countable transitive closure. For replacement, a functional image of a countable domain is countable, and the union of countably many countable transitive closures is countable; hence that image is again hereditarily countable. These observations, with inherited extensionality and foundation, verify all the remaining axioms. Every real, viewed as a subset of $\omega$, belongs to $H_{{\omega }_1}$. A power-set witness for $\omega$ would therefore contain every such real, but a hereditarily countable set has only countably many members, whereas $\mathcal{P}(\omega )$ is uncountable by Cantor's theorem. Power set fails.

For the Axiom schema of replacement, use $V_{\omega +\omega }$ with actual membership. This limit-rank structure contains $\omega$ and is closed under pairs, unions and power sets: every relevant finite increase in rank stays below $\omega +\omega$. A separated subset has rank no higher than that of the original set. Extensionality and foundation are inherited. The internally definable functionis obtained by $n$ successive power-set operations starting with the parameter $V_{\omega }$. Each finite iteration, including its finite history, belongs to the structure. Its range has rank $\omega +\omega$ and is not an element of $V_{\omega +\omega }$. Thus the replacement instance for this first-order formula fails, although every other ZF axiom holds.

For the axiom of extensionality, take the well-founded cumulative set universe over two distinct urelements, and forget the predicate distinguishing urelements from sets. Each urelement has no members, just as the ordinary empty set has no members, so extensionality fails. Every other axiom survives in this pure membership language. Pairing, union, separation and replacement are witnessed by the corresponding ordinary sets of urelements and sets; foundation follows from their well-founded ranks, and the pure $\omega$ supplies infinity. Here foundation is written with “has a member” as its nonemptiness antecedent, and disjointness means having no common member. Formulations using inequality to one designated empty object are not equivalent after removing extensionality. There is also one necessary adjustment to power set: an urelement is vacuously a subset of every object because it has no members. Thus the power-set witness for $x$ is the ordinary set of all usual subsets of its extension, together with both urelements. This is still a set, and contains exactly the objects satisfying the unrestricted subset first-order formula. Consequently the countermodel falsifies Extensionality alone, without silently weakening Power set to sets only.

Finally, the hereditarily finite sets $V_{\omega }$ satisfy extensionality, foundation, pairing, union, power set and separation. Every functional image of a finite domain is a finite set of hereditarily finite objects, hence also belongs to $V_{\omega }$, giving all replacement instances. No finite set contains $\varnothing$ and is closed under successor: it would then contain every finite von Neumann ordinal. Infinity fails while the remaining axioms hold.

For any function $f:X\to \mathcal{P}(X)$, form the diagonal subsetIf $f$ were surjective, some $d\in X$ would satisfy $f(d)=D$. Then $d\in D$ would hold exactly when $d\notin D$, which is impossible. Thus no set surjects onto its power set, including the empty-set case. This is Cantor's theorem proved by the Cantor diagonal argument.

Use real-number pairing by separated digits for an explicit injection ${\mathbb{R}}^2\to \mathbb{R}$. First map a real number to $(0,1)$ by $q(x)=\frac{1}{2}+{\pi }^{-1}\arctan x$, and use its unique binary expansion that is not eventually all ones. If $q(x)={\sum }_{n\ge 1}{a}_n{2}^{-n}$ and $q(y)={\sum }_{n\ge 1}{b}_n{2}^{-n}$, defineThis places the two binary digit strings in alternating ternary positions. Such ternary strings, using only digits zero and one, are unique: at a first differing position $k$, the difference $3^{-k}$ exceeds the maximum tail ${\sum }_{j>k}{3}^{-j}=\frac{1}{2}{3}^{-k}$. Thus the output recovers both digit strings and both inputs. The use of base three avoids any endpoint ambiguity caused by interleaving digits in base two.

For a fixed $A\subseteq {\mathbb{R}}^2$, the affine sections of a planar set are indexed byThere is an injection $\iota :\mathcal{I}\to \mathbb{R}$, for example by applying $J$ to each coordinate pair and then once more to those two results. Suppose every subset of $\mathbb{R}$ were a section of $A$. Define a function from $\mathbb{R}$ to $\mathcal{P}(\mathbb{R})$ by assigning to $\iota (\mathbf{a},\mathbf{b})$ the corresponding section, and assigning the empty set to every real outside $\iota (\mathcal{I})$. Injectivity of $\iota$ makes this definition unambiguous. It would be a surjection onto $\mathcal{P}(\mathbb{R})$, contradicting the first argument. No planar set has every subset of the real line as a section. Allowing different parametrizations of the same line does not evade this obstruction.

For all countable sets, however, such a planar set does exist. To build one, first encode every real sequence $s=(s_1,s_2,\dots )$ by one real number. Let $a_{nk}$ be the canonical binary digits of $q(s_n)$, and choose the explicit indexingThis is a bijection from positive integer pairs to positive integers. Define the coding of real sequences by ternary digitsThe same first-differing-digit argument proves that $c$ is injective; all its values lie in $[0,1/2]$. Now takeFor every nonempty countable set $S\subseteq \mathbb{R}$, choose an enumeration $s$ of $S$, repeating terms if $S$ is finite. On the vertical line with $\mathbf{a}=(c(s),0)$ and $\mathbf{b}=(0,1)$, the section of $A$ is precisely $S$: injective sequence coding means no other sequence can contribute extra values in this column. The empty set is the section on the line $x=2$, since all code columns have first coordinate at most $1/2$. This constructs the required universal planar set for countable real sections. No assertion about its other, nonvertical sections is needed.

Here the power set notation gives $xEy⟺\mathcal{P}(x)\subseteq y$. Suppose a nonempty set $A$ has no $E$-minimal member. Form its intersection $b=\bigcap A$. This is a set: for any one $a_0\in A$, use the axiom schema of separation inside $a_0$ to define the elements common to all members of $A$. Selecting a single witness to nonemptiness is not an application of the axiom of choice.

For an arbitrary $y\in A$, lack of minimality supplies some $x\in A$ with $\mathcal{P}(x)\subseteq y$. Since $b\subseteq x$, every subset of $b$ is a subset of $x$, soThis conclusion holds for each $y\in A$, without choosing all the corresponding $x$ simultaneously. Intersecting over $y$ gives $\mathcal{P}(b)\subseteq b$.

For completeness, the contradiction in Cantor's theorem is completely explicit here. By the axiom schema of separation put $d=\{u\in b:u\notin u\}$. Then $d\in \mathcal{P}(b)\subseteq b$, and consequentlywhich is impossible. Thus no such $A$ exists:This power-set-predecessor relation proof uses neither a descending sequence nor a comparison of possibly non-well-orderable cardinalities. It proves well-foundedness directly from the minimal-member definition.

We work in the ambient theory ZFC for this question. Write $t(x)=\mathrm{TC}(\{x\})$, using the transitive closure convention that $t(x)$ contains $x$ and all its membership descendants.

First construct a set containing exactly the intended objects. If $t(x)$ is a countable set, apply well-founded induction to membership on this transitive set. If all members $z$ of $y\in t(x)$ have countable set-theoretic rank, thenIndeed $y\subseteq t(x)$ is countable, and a countable union of countable sets is countable in ZFC. The induction therefore gives $\mathrm{rank}(x)<{\omega }_1$. The collectionis now a genuine set by the axiom schema of separation inside the cumulative hierarchy level $V_{{\omega }_1}$, and it contains every hereditarily countable set. It is a transitive set, since $y\in x$ implies $t(y)\subseteq t(x)$.

If $a$ is a countable subset of $C$, thenThe right side is countable, so $a\in C$. Thus $C$ has countable-subset closure. This proves existence of a set with the required closure before taking any intersection.

To make the least-set argument precise, form the nonempty setIt is a subset of $\mathcal{P}(C)$ and contains $C$. Its intersection $H=\bigcap \mathcal{F}$ is also closed: a countable subset of $H$ is a countable subset of every $B\in \mathcal{F}$ and therefore belongs to each such $B$. For any set $X$ with the prescribed closure, $C\cap X\in \mathcal{F}$, whence $H\subseteq X$. This is leastness among all such sets, not just among subsets of $C$.

Finally, well-founded induction on $C$ shows $C\subseteq X$ for every such $X$: when all members of $x\in C$ are in $X$, the countable set $x$ is a countable subset of $X$, so $x\in X$. Hence $H=C$, proving that the definition gives precisely

For the cardinal bound, code the entire countable membership ancestry. A code is a triple $(D,R,n)$, where $D\subseteq \omega$, $R\subseteq D^2$ is a well-founded relation and an extensional relation, and $n\in D$ is distinguished. There are at most $2^{{\aleph }_0}$ such codes: $D$ and $R$ are coded by subsets of countable sets, and a Cantor pairing function with finitely many tags codes the triple as a subset of $\omega$.

The well-founded recursiondefines its collapse, as in the Mostowski collapse theorem. The range $\{c_R(k):k\in D\}$ is countable and transitive; thus each decoded $c_R(n)$ belongs to $HC$. Conversely, for $x\in HC$, choose a bijection $e:D\to t(x)$ and the point $n$ with $e(n)=x$. Set $lRk$ exactly when $e(l)\in e(k)$. Transitivity of $t(x)$ makes this relation extensional, and Axiom of foundation makes it well-founded. The recursion then gives $c_R(k)=e(k)$, so this code decodes to $x$.

We have a surjection from a set of at most continuum many codes onto $HC$. Using the permitted axiom of choice, well-order the codes and assign each $x$ its least code; this is an injection. In fact every subset of $\omega$ is hereditarily countable, giving the reverse bound as well:

Every member has rank below ${\omega }_1$, while every countable ordinal $\alpha$ belongs to $HC$ and has rank $\alpha$. Consequently

The axioms hold except Power Set. axiom of extensionality and Axiom of foundation are inherited by this transitive structure. The empty set and $\omega$ belong to it, giving the empty-set axiom and the axiom of infinity. The axiom of pairing follows from countable-subset closure. For $a\in HC$, $\bigcup a$ is a countable subset of $HC$, giving the Axiom of union. Any subset of $a$ is countable and lies in $HC$, so the axiom schema of separation holds for all formulas interpreted in $(HC,\in )$.

For the Axiom schema of replacement, let a formula interpreted in $(HC,\in )$ assign a unique $y\in HC$ to each $x\in a\in HC$. Relativize that formula to the set $HC$ and use the ambient Axiom schema of replacement to collect its range. The range is countable and consists of members of $HC$, hence belongs to $HC$. The same argument, selecting one witness for each member of the countable domain, proves axiom schema of collection. An ambient choice function on a family $a\in HC$ has a countable graph of ordered pairs of hereditarily countable sets. Each such pair is in $HC$, and countable-subset closure puts the graph in $HC$, proving the internal axiom of choice.

However, all external subsets of $\omega$ are elements of $HC$. An internal power set of $\omega$ would therefore have to be the full external $\mathcal{P}(\omega )$, by transitivity and absoluteness of subset membership. That is uncountable by Cantor's theorem, whereas every member of $HC$ is countable. Thus the axioms satisfied by hereditarily countable sets areHere the asserted axiom list includes both Axiom schema of replacement and axiom schema of collection; no equivalence relying on Power Set is being silently invoked.

Set theory studies sets, their set elements, and the constructions and sizes possible for them. It supplies a shared vocabulary for mathematics: a function connects two sets, a binary relation specifies which pairs of objects are related, and a probability space starts with a set of possible outcomes. Giving these objects a common language lets a construction from one subject be used in another without repeating its underlying bookkeeping.

A particularly beautiful question is how to compare sizes without first assigning a number. Two sets have the same cardinality when a bijection pairs every member of one with exactly one member of the other. For finite sets, this agrees with ordinary counting. For infinite sets, it produces surprises: $n\mapsto 2n$ bijects the natural numbers with the nonnegative even integers, and the Cantor pairing function bijects the Cartesian product ${\mathbb{N}}^2$ with $\mathbb{N}$. A proper subset can have the same cardinality as its containing set.

This does not make all infinite sets equally large. Cantor's diagonal argument shows that all infinite binary sequences cannot be listed by the natural numbers. Cantor's theorem gives the wider principle: the power set of any set has strictly greater cardinality. The contrast between an explicit enumeration and an impossibility argument makes the meaning of infinity much sharper than a picture of something merely continuing forever.

Set formation itself requires care. Russell's paradox shows why not every condition defines a set of all objects satisfying it. Zermelo–Fraenkel set theory instead uses axioms specifying permitted constructions, including set comprehension within a previously given set. The restrictions are useful: they let us form the collections ordinary arguments need while blocking the unrestricted construction that produces the paradox.