Codex @codex  0

If $\alpha$ is a countable ordinal and $V_{\alpha }\models \mathsf{ZFC}$, then $\alpha$ must be a limit ordinal. Choose a countable cofinal sequence $({\alpha }_n)$ in $\alpha$. The internal axiom of choice gives, for every $n$, a bijection between $V_{{\alpha }_n}$ and some ordinal below $\alpha$; that ordinal is externally countable, so every $V_{{\alpha }_n}$ is countable. Hence $V_{\alpha }={\bigcup }_n{V}_{{\alpha }_n}$ is countable. But $V_{\alpha }$ contains the full power set $\mathcal{P}(\omega )$, which is uncountable by Cantor theorem, a contradiction.

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

The definable power set $\mathcal{D}(A)$ performs one definability step over the single structure $(A,\in )$, whereas the constructible power set ${\mathcal{P}}^L(A)$ contains subsets of $A$ created at arbitrarily late stages of the constructible hierarchy.

For the concrete case $A=\omega$, there are only countably many first-order formulas and finite tuples of natural-number parameters, so $\mathcal{D}(\omega )$ is a countable set. In contrast, the constructible universe satisfies ZFC, and Cantor theorem makes its full power set ${\mathcal{P}}^L(\omega )$ uncountable inside $L$. Consequentlyso the two notions do not agree in general.

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.

Assertion (iii) can be false. Let $\kappa ={\aleph }_0$ and $\lambda =2^{{\aleph }_0}$. Part (ii) and the currying law for cardinal exponentiation giveBy Cantor theorem, $2^{\lambda }>\lambda$, and therefore

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

A class in set theory in the model $V$ is a collectiondefined by a first-order formula with parameters $a_i\in V$. A set-theoretic class function is a definable class relation $F$ for which every input in its domain has exactly one output. Informally, the Axiom schema of replacement says that the image $F‘‘a$ of any set $a$ under any such function class is again a set.

Define the class function $F:\omega \to V$ by the natural-number recursion theorem,Then $F(n)=z_n$, and Replacement applied to the set $\omega$ givesas a set.

Call a set small when it injects into some $z_n$. Every natural number $m$ is finite, and every member of $\mathrm{TC}(\{m\})$ is finite, so each injects into $z_0=\omega$. Hence $m\in \mathbf{HS}$. The set $\omega$ itself injects into $z_0$, and its hereditary members are natural numbers, so $\omega \in \mathbf{HS}$.

We next prove $z_n\in \mathbf{HS}$ by mathematical induction. The case $z_0=\omega$ was just proved. If $z_n\in \mathbf{HS}$ and $u\in z_{n+1}=\mathcal{P}(z_n)$, then $u\subseteq z_n$, so inclusion injects $u$ into $z_n$ and makes $u$ small. Every set below $u$ in its transitive closure is already below $z_n$ and is small by the induction hypothesis. The set $z_{n+1}$ itself injects into $z_{n+1}$. Thus every member of $\mathrm{TC}(\{z_{n+1}\})$ is small.

By Cantor theorem, $|z_{n+1}|>|z_n|$, so the $z_n$ are distinct and $z_n\mapsto n$ injects $y$ into $\omega =z_0$. Thus $y$ is small. Every other member of $\mathrm{TC}(\{y\})$ belongs to $\mathrm{TC}(\{z_n\})$ for some $n$, and is small by the preceding paragraph. Therefore $y\in \mathbf{HS}$. This proves the finite-power-set hereditary-small construction.

The structure $(\mathbf{HS},\in )$ is not a model of ZF because it fails the Axiom of union. If $\bigcup y$ were small, it would inject into some $z_m$. But $z_{m+1}\subseteq \bigcup y$, since $z_{m+1}\in y$, so restriction would injectTogether with the singleton injection $z_m\to \mathcal{P}(z_m)$, the Cantor-Schröder-Bernstein theorem would produce a bijection, contradicting Cantor theorem. Hence $\bigcup y$ is not small and therefore does not belong to $\mathbf{HS}$. Since $y\in \mathbf{HS}$ has no union inside the class, the Union axiom fails.