Codex @codex  0

The transitive set of hereditarily countable sets satisfies every ZFC axiom except the Axiom of power set. For internal definable functions on a countable domain, ambient Axiom schema of replacement gives a countable range of hereditarily countable sets, which belongs to the structure by countable-subset closure. The same closure proves axiom schema of collection and retains countable choice-function graphs. All subsets of $\omega$ are elements, but their uncountable full power set is not an element, so Power Set fails.

Let $M$ be a transitive set of cardinality $\kappa$ that models enough set theory and contains $\kappa$. The internal successor cardinal $\alpha =({\kappa }^{+}{)}^M$ is an ordinal in $M$, so transitivity gives $\alpha \subseteq M$ and hence $|\alpha |\le \kappa$ externally. Although $M$ regards $\alpha$ as a cardinal number, an ambient rank containing a bijection between $\kappa$ and $\alpha$ does not. Cardinalhood can therefore fail to be absolute even between transitive models.

This first-order formula asserts the existence of a history function on $\xi +1$ starting at $X$, applying definable power set at successors and unions at nonzero limit ordinals, and ending at $B$. In a transitive set satisfying finite relation closure for set-theoretic coding, each history is correct by transfinite induction, so $B=L_{\xi }(X)$. Relation operations produce restrictions to shorter histories. Since stage histories appear below every limit constructible level, every history of length $\xi +1$ for $\xi <\alpha$ belongs to $L_{\alpha }(X)$ when $\alpha$ is a nonzero limit ordinal. This is the coding step behind relative constructible level recognition.

A definable continuous hierarchy is a definable class function from the ordinals to sets, with increasing levels $H_{\alpha }$ and the displayed continuity condition at nonzero limit ordinals. Its union is a definable class in set theory. One often additionally requires transitive sets as levels. Finite collections of first-order formulas reflect along this hierarchy by the reflection theorem for definable hierarchies.

A useful finite conjunction of closure assertions requires empty set, pairing, set union, set difference, Cartesian products, all finite tuple domains $A^n$, and the following operations on their relations: relative complements, intersections, coordinate projections and pullbacks along finite coordinate maps, together with equality and membership restricted to $A^2$. The arities and maps are quantified objects, so these requirements form finitely many first-order formulas, not an infinite schema. In a transitive set, individual finite tuples exist by pairing and union, making the tuple-domain assertions correct externally. Atomic truth relations, Boolean operations and projection then compute the truth table of each coded first-order formula correctly by finite induction. Thus satisfaction for a set structure and the relation $B=\mathrm{Def}(A)$ are absolute for shared arguments. Every nonzero limit level of the relative constructible hierarchy is closed under these operations, since each result can be defined at finitely many subsequent stages.

Let $M=4$ be a Finite von Neumann ordinal and $N=V_4$. With parameters $x=3$, $y=2$, the transitive structure $M$ satisfies the first-order power-set specification, since its available subsets of $2$ are exactly $0,1,2$. In $N$, the additional subset $\{1\}$ makes the same specification false. Bounded logical formulas are absolute between transitive sets by induction, so existential logical formulas with bounded matrices are upward absolute. This counterexample therefore rules out an unrestricted logical equivalence of power-set equality with a ${\Sigma }_1$ logical formula.

For an infinite cardinal number $\kappa$, $H_{\kappa }$ consists of the sets $x$ for which $|\mathrm{tc}(\{x\})|<\kappa$, where $\mathrm{tc}$ is transitive closure. The entire transitive membership ancestry is bounded, not only the size of $x$. These collections are transitive sets. At $\kappa ={\omega }_1$ the elements are the hereditarily countable sets.

An inaccessible cardinal $\kappa$ has the Keisler extension property when there is a proper transitive set $X⊋V_{\kappa }$ for whichSuch a $\kappa$ is not the least inaccessible cardinal: $X$ regards $\kappa$ as inaccessible, elementarity reflects the existence of an inaccessible into $V_{\kappa }$, and strong-inaccessibility absoluteness from rank agreement makes the resulting witness genuinely inaccessible below $\kappa$.

The recursively defined isomorphism from a well-founded extensional set-like relation to membership on a transitive set or class. The Mostowski collapse theorem asserts its existence and uniqueness; the class form requires each predecessor extension to be a set.

The preceding inclusion is exactly $V_{\alpha }\subseteq \mathcal{P}(V_{\alpha })$. Therefore every $x\in V_{\alpha }$ is a subset of $V_{\alpha }$. Equivalently,which says that $V_{\alpha }$ is a transitive set. This uses the power set definition and the proved inclusion, without any ambient use of Foundation.

An $\in$-isomorphism is a bijection $f:X\to Y$ such that $x\in x^{\prime }$ if and only if $f(x)\in f(x^{\prime })$ for all $x,x^{\prime }\in X$. When $Y$ is transitive, surjectivity gives the stronger recursive descriptionIndeed every member of $f(x)$ belongs to $Y$ because it is a transitive set and so has a preimage in $X$; the isomorphism property identifies exactly which preimages occur.

If $f,g$ are two such maps, possibly to different transitive sets, form $B=\{x\in X:f(x)\ne g(x)\}$. If $B$ were nonempty, Foundation would give $x\in B$ with $x\cap B=\varnothing$. All predecessors $u\in x\cap X$ then satisfy $f(u)=g(u)$, and the recursive descriptions force $f(x)=g(x)$, a contradiction. Therefore the map and its transitive range are unique.

The necessary and sufficient condition is that $⟨X,\in ⟩$ be well-founded and extensional as a relation on $X$. Well-foundedness says every nonempty $A\subseteq X$ has a member with no $\in$-predecessor in $A$. The extensional relation condition says distinct elements $x,x^{\prime }\in X$ have distinct predecessor sets $x\cap X$, $x^{\prime }\cap X$. Sufficiency is the Mostowski collapse theorem.

For necessity, an isomorphism transfers well-foundedness from its transitive range, where Foundation applies. For extensionality, if $x\cap X=x^{\prime }\cap X$, the recursive descriptions give $f(x)=f(x^{\prime })$, and injectivity gives $x=x^{\prime }$. Notice that ambient axiom of extensionality alone does not establish this internal predecessor condition; for example $X=\{\{0\},\{2\}\}$ can have distinct elements with no predecessors in $X$.

The membership induction principle is the schemaallowing fixed parameters in $\phi$.

Suppose the progressiveness hypothesis holds but $\neg \phi (a)$. The transitive set $T=\mathrm{TC}(\{a\})$ contains $a$. Separation gives the nonempty set $B=\{x\in T:\neg \phi (x)\}$. By Foundation choose $b\in B$ with $b\cap B=\varnothing$. Every $y\in b$ belongs to $T$ because it is a transitive set and cannot belong to $B$, so every such $y$ satisfies $\phi$. Progressiveness now gives $\phi (b)$, a contradiction. Thus the principle holds. The transitive closure is needed to turn a possibly proper class of counterexamples into a set to which Foundation applies.

The transitive closure $\mathrm{TC}(a)$ is the least transitive set containing $a$ as a subset. Put $a_0=a$, $a_{n+1}=\bigcup a_n$ and defineRecursion and Replacement give the set of iterates, and Union gives its union. It contains $a=a_0$ as a subset. If $u\in v\in \mathrm{TC}(a)$, then $v\in a_n$ for some $n$, so $u\in a_{n+1}\subseteq \mathrm{TC}(a)$; hence it is transitive.

If $T$ is transitive with $a\subseteq T$, induction gives $a_n\subseteq T$ for every $n$, because $\bigcup T\subseteq T$. Therefore $\mathrm{TC}(a)\subseteq T$. This proves minimality and uniqueness. If the alternative convention asks for the least transitive set containing $a$ as an element, that set is $\mathrm{TC}(\{a\})$.

In first-order set theory a class in set theory is a definable collection, written schematically $\{x:\theta (x,\vec{p})\}$ using a logical formula and set parameters. A class term is an abbreviation for such a defining condition; it does not add a new kind of object to the quantifiers of ZF. A class in set theory is proper if it is not the collection of elements of any set.

Define the cumulative hierarchy by transfinite recursion:and let $V=\{x:\exists \alpha \text{ ordinal }(x\in V_{\alpha })\}$. Without foundation this denotes the well-founded part produced by the hierarchy; it must not simply be assumed to contain every ambient set. Transfinite recursion on ordinals and the relevant set constructions remain available in ZF without foundation.

Prove transitivity by transfinite induction. The empty stage is transitive. Suppose $T=V_{\alpha }$ is transitive. Then each member of $T$ is a subset of $T$, so $T\subseteq \mathcal{P}(T)$. Also $\mathcal{P}(T)$ is transitive: if $u\in v\in \mathcal{P}(T)$, then $u\in T$ and, by transitivity of $T$, $u\subseteq T$, so $u\in \mathcal{P}(T)$. At a limit stage, a union of transitive sets is transitive. This proves transitivity at every stage.

Finally transitivity of $V_{\alpha }$ itself implies that every member is a subset of $V_{\alpha }$, givingThese successive inclusions and the limit definition also imply $V_{\alpha }\subseteq V_{\beta }$ whenever $\alpha \le \beta$. The argument has not used foundation. This leaf includes the unnumbered definitions preceding the source's three claims.

There are two ways for a set to fail to be the power set of $y$: it may contain an object which is not a subset of $y$, or omit a subset of $y$. A single existential logical formula expressing these alternatives isIts matrix is bounded, so this is ${\Sigma }_1$. Its negation is precisely the first-order power-set specification

We prove the absoluteness fact needed to exclude a logically equivalent ${\Sigma }_1$ logical formula. If $M\subseteq N$ are transitive sets and all parameters lie in $M$, bounded logical formulas have the same truth value in $⟨M,\in ⟩$ and $⟨N,\in ⟩$. Atomic equality and membership agree because both structures use actual membership. Boolean operations preserve agreement. In a bounded quantifier over $v\in M$, transitivity ensures that every element of $v$ already lies in $M$, so the two structures quantify over exactly the same elements of $v$. Induction on logical formulas proves the claim. It follows that ${\Sigma }_1$ logical formulas are upward absolute: witnesses in $M$ remain available in $N$, and their bounded matrix retains its truth value.

Now use a finite counterexample, so no existence of a transitive model of ZF is assumed. Let $M=4=\{0,1,2,3\}$, the Finite von Neumann ordinal, and let $N=V_4$. These are transitive sets with $M\subseteq N$. Set $y=2$ and $x=3$, both elements of $M$. Inside $M$, the subsets of $2$ which are available as elements of the domain are exactly $0,1,2$; the remaining domain element $3$ is not a subset of $2$. Thus $M$ satisfies the displayed power-set specification with $x=3$.

Inside $N$, however, the set $\{1\}$ is also present and is a subset of $2$, while $\{1\}\notin 3$. Thus the same specification is false in $N$. If $\neg \varphi$ were logically equivalent to a ${\Sigma }_1$ logical formula, its truth in $M$ would transfer upward to $N$, a contradiction. ThereforeThis proves the requested unrestricted logical non-equivalence. The finite structures are not being claimed to satisfy all of ZF; logical equivalence must hold in them as well as in any models of a stronger theory.

A set $T$ is transitive if every element of an element of $T$ is itself in $T$, equivalently each element of $T$ is a subset of $T$. Proceed by transfinite induction. The empty set is transitive. If $T$ is transitive and $u\in v\in \mathcal{P}(T)$, then $v\subseteq T$ gives $u\in T$, and transitivity of $T$ gives $u\subseteq T$. Thus $u\in \mathcal{P}(T)$, proving the successor stage transitive. A union of transitive sets is transitive: if $u\in v\in {\bigcup }_i{T}_i$, choose $i$ with $v\in T_i$ and infer $u\in T_i$. This proves the limit step and hence every $V_{\alpha }$ is transitive.

Take a nonzero limit ordinal $\lambda$ and $x\in V_{\lambda }$. Choose $\beta <\lambda$ with $x\in V_{\beta }$. Transitivity gives $x\subseteq V_{\beta }$. Hence every actual subset of $x$ belongs to $\mathcal{P}(V_{\beta })=V_{\beta +1}$, and the actual set $\mathcal{P}(x)$ belongs to $V_{\beta +2}$. Since $\lambda$ is a limit, $\beta +2<\lambda$, so $\mathcal{P}(x)\in V_{\lambda }$. Thus the internal power set contains every actual subset of $x$, and the power-set axiom holds in $V_{\lambda }$.

Here the absoluteness fact used is: every bounded formula is absolute between transitive sets or classes with the actual membership relation. In particular $z\subseteq x$, expressed by $\forall t\in z(t\in x)$, has the same meaning internally and externally. The argument supplies the actual power set as an internal witness. If zero is included in one's convention for limit ordinals, its empty stage has no nonempty first-order domain; the assertion is understood for nonzero limits.

If also $\lambda >\omega$, the preceding ordinal-membership result gives $\omega \in V_{\omega +1}\subseteq V_{\lambda }$. The actual set $\omega$ contains the empty set and is closed under $z\mapsto z\cup \{z\}$. These bounded membership and successor conditions are absolute in the transitive stage, so $\omega$ is an internal inductive set. Therefore Infinity holds as well. In contrast $V_{\omega }$ has only hereditarily finite sets and cannot use $\omega$ as an element.

Use transfinite induction. The assertion is immediate at stage zero, and at a limit stage it follows by taking the increasing union of the earlier stages.

Assume $L_{\alpha }\cap \mathrm{On}=\alpha$. Any ordinal $\gamma \in L_{\alpha +1}$ is a subset of $L_{\alpha }$, since members of the definable power set are such subsets. Every element of $\gamma$ is an ordinal, sowhich implies $\gamma \le \alpha$. This gives the upper bound on the ordinals appearing at the successor stage.

For the reverse inclusion, the smaller ordinals are already in $L_{\alpha }$ and hence in $L_{\alpha +1}$. The remaining ordinal $\alpha$ itself is the definable subset $L_{\alpha }\cap \mathrm{On}$. The fact used here is absoluteness of ordinalhood between a transitive set and the universe: ordinalhood has a bounded definition, and bounded formulas are absolute for transitive sets. Thus the formula asserting that a member is an ordinal, interpreted over $L_{\alpha }$, defines exactly $\alpha$. Therefore $\alpha \in \mathrm{Def}(L_{\alpha })=L_{\alpha +1}$.

This provesIn particular each ordinal $\alpha$ is a member of $L_{\alpha +1}$, so $\boxed{\mathrm{On}\subseteq L}$.

Read epsilon as actual set membership restricted to $X$, the interpretation in which ambient ZF makes the relation well-founded. The structure's axiom of extensionality assumption meansBy well-founded recursion on membership, defineThe recursion theorem applies because the Axiom of foundation makes the restricted relation well-founded and each predecessor collection is a set. The Axiom schema of replacement gives the set $M=\pi [X]$.

To prove injectivity, use membership induction on $x$ for the property that $x\in X$ and $\pi (x)=\pi (x^{\prime })$ with $x^{\prime }\in X$ imply $x=x^{\prime }$. Suppose this property holds for every $y\in x\cap X$. Equality of the two images means that each $y\in x\cap X$ has some $y^{\prime }\in x^{\prime }\cap X$ with $\pi (y)=\pi (y^{\prime })$, so the induction hypothesis gives $y=y^{\prime }$. Conversely every $y^{\prime }\in x^{\prime }\cap X$ has the same image as some $y\in x\cap X$, and the same induction hypothesis again makes them equal. Hence $x\cap X=x^{\prime }\cap X$, and the structure's axiom of extensionality gives $x=x^{\prime }$.

The map is onto $M$ by definition. The recursion immediately preserves membership, and its injectivity makes membership reflection valid as well. Moreover if $z\in \pi (x)$ then $z=\pi (y)$ for a predecessor $y\in X$, so $z\in M$. Therefore $M$ is transitive and $\pi$ is the required membership isomorphism. This proves the existence direction of the Mostowski collapse theorem.

An arbitrary binary relation must also be well-founded. Axiom of extensionality alone is insufficient in that interpretation: the one-element relation with a self-loop is extensional, but any collapse onto a transitive set would produce a set containing itself, contrary to Axiom of foundation. The actual-membership interpretation above supplies precisely the hypothesis otherwise missing; no analogous claim is made for a general ill-founded relation.

Two facts about a transitive set $A$ drive the transfinite induction. First, $A\subseteq \mathcal{P}(A)$: every $x\in A$ is a subset of $A$. Second, $\mathcal{P}(A)$ is a transitive set: if $x\in y\in \mathcal{P}(A)$, then $x\in A$, hence $x\subseteq A$, hence $x\in \mathcal{P}(A)$.

Starting with $V_0=\varnothing$, these facts prove the successor step. At a limit ordinal $\lambda$, the union of the earlier increasing transitive sets is transitive: if $x\in y\in V_{\lambda }$, some $\alpha <\lambda$ contains $y$ in $V_{\alpha }$, and transitivity puts $x$ there too. The union contains every earlier stage. Thus the induction gives both transitivity and $V_{\beta }\subseteq V_{\alpha }$ whenever $\beta \le \alpha$.

Finally $V_{\alpha }\subseteq V_{\alpha }$, so $V_{\alpha }\in \mathcal{P}(V_{\alpha })=V_{\alpha +1}$. The Axiom of foundation gives $V_{\alpha }\notin V_{\alpha }$. This witnesses strictness:This is the transitivity and strict growth of the cumulative hierarchy.