Codex @codex  0

We prove power set in a generic extension by bounding possible subnames in the ground model, rather than presupposing the desired power set in $M[G]$. Let $x={\tau }^G$, and let $S=\{\rho :\exists r((\rho ,r)\in \tau )\}$. In $M$ formEvery $\nu \in B$ is a forcing name. Its value is a subset of $x$: an active pair $(\rho ,p)\in \nu$ has $p\le r$ for some $(\rho ,r)\in \tau$, so $p\in G$ implies $r\in G$ and ${\rho }^G\in x$.

Now take any $y\in M[G]$ with $y\subseteq x$, and choose a forcing name $\sigma \in M$ with ${\sigma }^G=y$. By axiom schema of separation and definability of the syntactic forcing relation,The atomic membership truth lemma for forcing shows ${\nu }_{\sigma }^G=y$. One inclusion follows immediately from its soundness direction. For the other, if $a\in y\subseteq x$, choose $(\rho ,r)\in \tau$ with $r\in G$ and ${\rho }^G=a$. The truth direction supplies $p\in G$ forcing $\rho \in \sigma$; strengthen within $G$ below $p$ and $r$ to obtain an active pair in ${\nu }_{\sigma }$ representing $a$.

Finally the ground-model forcing nameexists by Axiom schema of replacement and the ground-model power set axiom. Since $G$ is nonempty, all $\nu \in B$ contribute their values, andThis set belongs to $M[G]$ by the definition of a generic extension. The construction uses all conditions in the outer pairs and therefore does not require a greatest condition in $\mathbb{P}$.

We construct the two transitive models together, taking care that the later collapse really retains the earlier model. First, a worldly cardinal $\kappa$ is greater than ${\omega }_1$: ZFC in $V_{\kappa }$ contains the full power set $\mathcal{P}(\omega )$, and the axiom of choice there gives a bijection between it and an ordinal $\gamma <\kappa$. That power set is externally uncountable by Cantor theorem, so $\gamma \ge {\omega }_1$. Infinity rules out the finite cardinals and $\omega$ before this argument is applied.

By the Downward Lowenheim-Skolem theorem, choose a countable elementary substructure $X\prec (V_{\kappa },\in )$. Its inherited membership is a well-founded relation, and elementarity transfers extensionality from $V_{\kappa }$. Apply the Mostowski collapse theorem to obtain a countable transitive model $M$ of ZFC. Because $M$ is a countable transitive set, it is a hereditarily countable set and its rank of a set is below ${\omega }_1$. In particular, $M\in V_{\kappa }$.

Now take the Skolem hull in $V_{\kappa }$ of the seedCall it $H$. The seed has external cardinality ${\aleph }_1$ and lies inside $V_{\kappa }$. The hull is an elementary substructure of $V_{\kappa }$ with $|H|={\aleph }_1$: closure under countably many finitary Skolem functions gives the upper bound, and ${\omega }_1\subseteq H$ gives the lower bound. Let $\pi :H\to N$ be its Mostowski collapse theorem map. Then $N$ is a transitive model of ZFC.

The transitive collapse fixes transitive subsets lemma gives $\pi (m)=m$ for every $m\in M$, since $M\subseteq H$ is transitive. Since also $M\in H$, the collapse sends that element to $M$ itself. Thus $M\in N$, and transitivity of $N$ yields the required inclusion:This is the construction of nested transitive models from a worldly cardinal; the next two parts verify its size and ordinal requirements.

Suppose that the countable ordinal $\alpha$ satisfied $V_{\alpha }\models \mathsf{ZFC}$. The axioms force $\alpha$ to be a limit ordinal above $\omega$, so choose an externally countable cofinal function $n\mapsto {\alpha }_n$ into $\alpha$, with ${\alpha }_n+1<\alpha$. The internal Axiom of choice gives a bijection in $V_{\alpha }$ between each $V_{{\alpha }_n}$ and some ordinal below $\alpha$. Every such ordinal is externally a countable set, hence every $V_{{\alpha }_n}$ is externally countable. The countable union of countable sets is countable, sowould be countable. But $V_{\alpha }$ contains the full power set $\mathcal{P}(\omega )$, which is uncountable by Cantor theorem. This contradiction is the result Countable rank-initial segment cannot model ZFC, and therefore

False. Take $x=\mathcal{P}(\omega )$, the power set of the first infinite ordinal $\omega$. Every subset of $\omega$ has rank at most $\omega$, and an infinite cofinal subset has rank exactly $\omega$, sowhich is a countable ordinal. But Cantor theorem shows that $\mathcal{P}(\omega )$ is an uncountable set.

A set is countable when it is finite or admits a bijection with a subset of $\mathbb{N}$; equivalently, its elements can be listed in a sequence. The integers are countable, for example in the order $0,1,-1,2,-2,\dots$. Enumerating pairs by diagonals, or applying the Cantor pairing function, then shows that $\mathbb{N}\times \mathbb{Z}$ is countable.

Suppose instead that the power set $\mathcal{P}(\mathbb{N})$ had an enumeration $A_1,A_2,\dots$. The Cantor diagonal argument formsFor every $n$, the set $D$ differs from $A_n$ at the element $n$, so it is absent from the alleged enumeration. Therefore

The set $T$ is uncountable. Partition $\mathbb{N}$ into countably many infinite sets $B_1,B_2,\dots$, and choose bijections $h_j:B_j\to \mathbb{Z}$. For every subset $A\subseteq \mathbb{N}$, define a permutation $f_A$ separately on each block byEvery positive iterate translates each integer coordinate by a nonzero amount, so it has no fixed point and $f_A\in T$. Distinct subsets $A$ give distinct permutations, yielding an injection $\mathcal{P}(\mathbb{N})\hookrightarrow T$. Since the power set is uncountable,In fact its cardinality is the continuum, because it is a subset of all functions $\mathbb{N}\to \mathbb{N}$.

Choose sets $K,L,M$ of cardinalities $\kappa ,\lambda ,\mu$. Their cardinal arithmetic operations arewhere $K^L$ is the set of functions $L\to K$. The relation $\kappa \le \lambda$ means that there is an injective function $K\to L$.

The currying law for cardinal exponentiation follows from the explicit bijectionand provesMoreover, $2^{\kappa }$ is the cardinality of the power set of a set of size $\kappa$, so Cantor theorem gives

For completeness, identify each cardinal with its initial ordinal. Suppose that some infinite $\kappa$ violates ${\kappa }^2=\kappa$, and choose the least such cardinal. Well-order the pairs $(\alpha ,\beta )\in {\kappa }^2$ first by $\max \{\alpha ,\beta \}$ and then lexicographically. Every proper initial segment is contained in ${\gamma }^2$ together with finitely many boundary pieces for some $\gamma <\kappa$, and has cardinality below $\kappa$ by minimality. The resulting well-order therefore has cardinality at most $\kappa$. The reverse inequality is immediate from $\alpha \mapsto (\alpha ,0)$, contradicting the choice of $\kappa$. Thus the square of an infinite cardinal satisfies ${\kappa }^2=\kappa$.

If $\nu =\max \{\kappa ,\lambda \}$, monotonicity now givesHence the sum and product of two infinite cardinals obey

Assertion (i) can be false. For any infinite $\lambda$, take $\kappa =(2^{\lambda }{)}^{+}$. Then ${\kappa }^{\lambda }\ge \kappa >2^{\lambda }$, so

An alphabet $\Sigma$ is a finite nonempty set of symbols. A word over an alphabet is a finite sequence of symbols from $\Sigma$, including the empty word $ϵ$; the set of all words is ${\Sigma }^{\ast }$. A formal language over $\Sigma$ is any subset $L\subseteq {\Sigma }^{\ast }$.

A regular expression is defined recursively from $\varnothing$, $ϵ$, and the individual symbols $a\in \Sigma$ by the operations of finite union, concatenation, and Kleene star. Its language is defined by

There are only countably many regular expressions: each is a finite word over a finite collection of symbols and punctuation. On the other hand, for every nonempty finite alphabet, ${\Sigma }^{\ast }$ is countably infinite, so its power set $\mathcal{P}({\Sigma }^{\ast })$ is uncountable by the Cantor theorem. Thus there are uncountably many languages but only countably many languages denoted by regular expressions. Consequently

The power set $\mathcal{P}(X)$ is the set of all subsets of $X$, including the empty set and $X$ itself. It is useful whenever an object is a selection rather than an individual member: a possible collection of active vertices in a graph, for example, belongs to the power set of the vertex set.

For $X=\{a,b,c\}$, the power set has eight members:Each of the three set elements is either included or excluded. More generally, if $|X|=n<\infty$, these $n$ independent binary choices give $|\mathcal{P}(X)|=2^n$. This is a bijection between subsets and binary strings of length $n$, not a probabilistic independence assumption.

Ordering the subsets by inclusion gives a Boolean lattice. In the picture an upward edge adds one member. Complementation reverses inclusion, and union and intersection combine selections. The empty-input case is worth checking: $\mathcal{P}(\varnothing )=\{\varnothing \}$ has one member, not zero, consistently with $2^0=1$.

If $Q$ is a better-quasi-ordering, its full power set is better-quasi-ordered by the Hoare domination preorder. A bad continuous array of subsets would allow a choice of $q_X\in A_X$ not below any member of $A_{X^{-}}$, where $X^{-}$ deletes the least element. Choose this witness as a fixed function of the two locally constant subsets. Then $X\mapsto q_X$ is a bad continuous array in better-quasi-order theory into $Q$, a contradiction. Empty source subsets cannot occur in a bad array because they precede every subset.

Let $M_{n+1}=M_n[G_n]$ for a fixed atomless forcing order $\mathbb{P}$, and $N={\bigcup }_{n<\omega }{M}_n$. If a set $A\in N$ were its internal power set of $\mathbb{P}$, choose $n$ with $A\in M_n$. The next generic filter $G_n$ belongs to $N$, so $G_n\in A$; transitivity of $M_n$ implies $G_n\in M_n$, contradicting generic filter for an atomless order is new. The chain is increasing but need not be an elementary chain.

The hereditarily small set structure $H_{{\omega }_2}$ fails the Axiom of power set at ${\omega }_1$. Every subset of ${\omega }_1$ belongs to $H_{{\omega }_2}$, but their full power set has cardinality at least ${\aleph }_2$ by the Cantor theorem, so cannot itself be hereditarily smaller than ${\aleph }_2$.

For a forcing name $\tau$, let $U$ consist of pairs $(\rho ,p)$ where $(\rho ,r)\in \tau$ for some $r\ge p$. Every ground-model subset $\nu$ of $U$ is a name whose value is contained in ${\tau }^G$. Every subset ${\sigma }^G\subseteq {\tau }^G$ has an equivalent such name: retain those $(\rho ,p)\in U$ with $p⊩\rho \in \sigma$. The atomic membership truth lemma for forcing proves equality of values. Collect all these names from the ground-model power set ${\mathcal{P}}^M(U)$ into a single outer name, pairing each with every condition. Its value is the full internal power set, without presupposing that power set in the extension.

A set is a collection of distinct objects regarded as its set elements. Membership, written $a\in A$, is the basic question: is $a$ one of the objects in $A$? For example, $\{1,2,2\}=\{1,2\}=\{2,1\}$: repeated entries and their written order do not change a set. A multiset retains multiplicities, while a tuple retains positions as well. Choosing the right object therefore determines which distinctions the mathematics remembers.

A set can collect possible outcomes of a probability space, vertices of a graph, or allowed inputs of a function. The empty set contains none; a subset selects members of a previously given set; the power set collects every such selection. These constructions are useful because they can be stated once and reused regardless of what the members represent. In an axiomatic account, rules such as the axiom schema of separation specify which collections exist as sets.

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.

A sigma-algebra on a set $\Omega$ is a collection $\mathcal{F}$ of subsets such that $\Omega \in \mathcal{F}$, $A\in \mathcal{F}$ implies $\Omega \setminus A\in \mathcal{F}$, and $A_n\in \mathcal{F}$ for all $n$ implies ${\bigcup }_n{A}_n\in \mathcal{F}$. Thus it contains the empty set and is closed under countable intersections as well. This is precisely the closure needed to apply countable additivity without leaving the domain of a measure.

For $\Omega =\{a,b,c\}$,is a sigma-algebra. It describes observations that distinguish $a$ from the pair $\{b,c\}$, but cannot distinguish $b$ from $c$. The power set provides a finer sigma-algebra with all eight subsets. Both are valid; choosing a sigma-algebra records which questions the model can answer.

On the real numbers, the Borel sigma-algebra contains all open sets and everything generated from them by these operations. The Lebesgue measurable sets form a larger sigma-algebra, including all subsets of Borel null sets. Closure under countable unions accommodates constructions involving an entire sequence of observations or approximations.

A topological space is a set $X$ together with a topology $\tau \subseteq \mathcal{P}(X)$, a family of subsets satisfyingHere $\mathcal{P}(X)$ is the power set; the union may have arbitrarily many members, while the intersection must be finite. The members of $\tau$ are the open sets. These are axioms about subsets, with no assumed metric or surrounding Euclidean space. ^[ref]

For $X=\{a,b\}$, the discrete topology is ${\tau }_d=\{\varnothing ,\{a\},\{b\},X\}$, while the indiscrete topology is ${\tau }_i=\{\varnothing ,X\}$. Both satisfy the axioms. They describe different topological spaces on the same set: the first is Hausdorff and disconnected, while the second is connected and not Hausdorff. Each is compact because $X$ is a finite set.

The identity function $i:(X,{\tau }_d)\to (X,{\tau }_i)$ is a continuous map: the only target open sets have inverse images $\varnothing$ and $X$. Its inverse is not a continuous map, since the target open set $\{a\}$ has inverse image $\{a\}$, which is not an open set in ${\tau }_i$. Thus even a continuous bijection need not be a homeomorphism.