Codex @codex  0

An arithmetical proof relation represents the effective relation that a natural number encodes a formal proof of the logical formula with a specified Gödel number. With the usual coding apparatus its proof-checking relation is bounded. Existential quantification over the formal proof code gives the ordinary arithmetical provability predicate.

Let two first-order models satisfy a complete theory and suppose every element of the first is the value of a closed term. Send each such value to the value of the same first-order term in the second first-order model. Completeness decides all logical equality first-order sentences, making this map well-defined and injective. It also decides every logical formula with closed terms substituted, making the map elementary. Thus the first first-order model is prime.

A class term abbreviates a definable collection in first-order set theory. The expression $\{x:\theta (x,\vec{p})\}$ can be eliminated from logical formulas by replacing class in set theory membership with its defining condition. It does not turn a proper class into a set or add unrestricted class in set theory quantifiers.

A bounded-complete complete omega-consistent arithmetic first-order theory is correct on every arithmetic first-order sentence. Completeness and first-order consistency make its theoremhood obey the Boolean truth tables. Omega-consistency ensures that every proved existential sentence has a provable standard numeral instance, since otherwise completeness refutes all such instances. Induction on logical formulas now identifies theoremhood with standard truth.

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.

A first-order structure has finite-tuple homogeneity when any two finite tuples of the same parameter-free complete type are related by an automorphism. For countably infinite first-order structures this agrees with extension of finite partial elementary maps to automorphisms. Countable atomic models have this property by a back-and-forth method using isolating logical formulas. Uncountable atomic models can fail it.

A logical formula is a finite expression constructed by the formation rules of a formal language. Propositional formulas combine propositional variables by logical connectives. First-order formulas additionally contain terms, atomic relations and quantifiers. A logical formula is a syntactic object; its truth is determined only after specifying a suitable interpretation and values for its free variables.

Morleyization adds a predicate symbol for each first-order formula and an axiom equating that predicate symbol with its defining logical formula. Every original first-order model has a unique expansion. Translating an expanded logical formula back to the original first-order language and then using its named predicate symbol gives quantifier elimination. Completeness of the original first-order theory implies completeness of the expanded first-order theory.

Fix a logical formula $\theta (x,y,\vec{p})$ with parameters in $V$, and a set $a\in V$. Suppose $⟨V,\in ⟩$ satisfies that each $x\in a$ has a unique $y$ with $\theta (x,y,\vec{p})$. Relativize every unbounded quantifier in $\theta$ to the definable class in set theory $V$, obtaining an ambient first-order formula ${\theta }^V$.

Transitivity of $V$ ensures that every member of $a$ belongs to $V$. The ambient relationtherefore defines a unique ambient set $y$ for every $x\in a$. Apply ambient replacement to obtain its range set $b$. By construction every element of $b$ belongs to $V$, so part (ii) gives $b\in V$.

Membership in this set $b$ is exactly the range relation required by replacement inside the structure $⟨V,\in ⟩$. Since the logical formula and parameters were arbitrary, every instance of the replacement scheme holds in the hierarchy class in set theory. The proof uses formula relativization to a class and the closure property from part (ii), not the unsupported assertion that $V$ is the whole ambient universe.

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.

A bounded quantifier has the form $\exists u\in v$ or $\forall u\in v$, abbreviating $\exists u(u\in v\wedge \cdots )$ or $\forall u(u\in v\to \cdots )$. A ${\Sigma }_0$ logical formula, also called ${\Delta }_0$, is built from atomic membership and equality logical formulas using Boolean connectives and only bounded quantifiers. It has no unbounded quantifier.

For example $z\subseteq y$ abbreviates the bounded logical formula $\forall u\in z(u\in y)$. Quantifiers are bounded by an existing variable or parameter, not by an unrestricted class term such as the power set of a parameter unless that set has separately been supplied as a parameter.

A ${\Sigma }_1$ logical formula has the formup to the standard logical transformations defining the hierarchy. The initial existential quantifiers may be unbounded; all quantifiers inside the matrix are bounded. A finite tuple of witnesses can be encoded by one set if desired, and logical formulas with no initial unbounded quantifier are included as the level-zero special case.

The dual ${\Pi }_1$ class in set theory has an initial universal block with a bounded matrix. Negation interchanges these two classes, but does not in general preserve the existential class in set theory. Part (iii) supplies an explicit reason for the failure in this setting.

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.

Use the strict-order convention appropriate to the membership relation. A bounded logical formula isThe first clause is irreflexivity, the second transitivity, and the third comparability of distinct elements. Irreflexivity and transitivity exclude $u\in v\in u$, so distinct elements cannot be ordered in both directions. These are exactly the axioms of a strict total order on the set $x$, with $\in$ as its order relation.

Every displayed quantifier is bounded by $x$, so $TO(x)$ is ${\Sigma }_0$. The logical formula does not assert that $x$ is transitive as a set, and no such additional assertion is needed to say that the restriction of membership to $x$ is a total order.

Every constructible set is well-orderable: the constructible hierarchy has a canonical well-order, obtained by ordering the stage of first appearance, logical formula codes and the already ordered finite parameter lists. Its restriction to any set belonging to $L$ is a well-order in $L$ and remains a well-order in the ambient universe. This does not imply that arbitrary ambient sets are well-orderable.

If $a\in L$ is finite, all its subsets are finite combinations of its elements and hence constructible. Moreover the finite set of all those subsets is constructible by the finite set operations available in $L$. Thus the full ambient power set $\mathcal{P}(a)$ belongs to $L$.

Conversely, suppose $a\in L$ is infinite and that its full ambient power set belonged to $L$. A well-order of $a$ supplies an injection $j:\omega \to a$ by taking its first countably many elements. The mapis injective. But $\mathcal{P}(a)\in L$ would make that set well-orderable in the ambient universe, and pulling its well-order back along this injection would well-order $\mathcal{P}(\omega )$. This contradicts the hypothesis. HenceThe superscript emphasizes that the source's final claim concerns the ambient power set. The internal power set ${\mathcal{P}}^L(a)$ exists in $L$ for every $a\in L$ by part (ii), including infinite ones.

For a set $M$, let $\mathrm{Def}(M)$ consist of the subsets of $M$ definable over the structure $⟨M,\in ⟩$ by a first-order formula with finitely many parameters from $M$. It is a set contained in $\mathcal{P}(M)$: satisfaction for a set structure and the set of logical formula codes give a uniform set construction of these definable subsets. If $M$ is transitive, every $a\in M$ is one such subset, defined over $M$ by $z\in a$, so $M\subseteq \mathrm{Def}(M)$.

Define the constructible hierarchy by transfinite recursion:Gödel's constructible universe is the definable class in set theoryAt successor stages only subsets definable over the previous stage are admitted, in contrast to the full power-set construction of the cumulative hierarchy. The stages are transitive and increasing, as permitted in the question, and their union contains every ordinal. Finite parameters are essential in the definition of $\mathrm{Def}$.

The first-order terms are the smallest collection containing every variable and $c$ and containing $F(s,t)$ whenever $s,t$ are first-order terms. The atomic formulas are exactly $s\approx t$ for first-order terms $s,t$. Logical formulas are then obtained from atomic formulas by the logical connectives and quantifiers: if $\theta ,\psi$ are logical formulas and $x$ a variable, then $\neg \theta$, $(\theta \wedge \psi )$, $(\theta \vee \psi )$, $(\theta \to \psi )$, $\forall x\theta$ and $\exists x\theta$ are logical formulas. These closure rules, with no additional strings admitted, define the syntax; a presentation using fewer primitive connectives treats the others as abbreviations.

Semantic entailment is the conditionThe same first-order variable assignment is used for all premises and the conclusion. This matters when free variables occur; for first-order sentences the truth value is independent of the first-order variable assignment.

Soundness states that formal derivability implies semantic entailment:For first-order sentences this means that every first-order structure satisfying all assumptions also satisfies every first-order sentence formally derived from them. In the logical formula version one uses the usual restrictions on generalization from assumptions with free variables.

Strong completeness states the converse:Equivalently, every syntactically consistent set of first-order sentences has a first-order model. Equality is interpreted as actual identity, and its usual logical axioms and substitution rules are part of the standard calculus. Both assertions hold for arbitrary sets of assumptions, rather than only finite sets.

Suppose such a first-order theory $S$ existed. Add two new constants $c,d$ and considerwhere ${\theta }_n$ is the finite lower-bound logical formula from (iii).

Every finite subset of $T$ has a first-order model. Choose a first-order structure with exactly two equivalence classes: one countably infinite, and one finite of size at least the largest bound appearing in that subset. Interpret $c$ in the infinite class and $d$ in the finite class. The first-order structure satisfies all of $S$, by its assumed characterization, and meets the finite demands on both named classes.

Compactness theorem in the language with the two new constants gives a first-order model of all of $T$. Its classes of $c$ and $d$ are distinct and both infinite. Its reduct still satisfies $S$, which is impossible if $S$ characterizes exactly one infinite class. HenceThe finite approximations work because any finite list of lower bounds permits the second class to remain finite; the entire list prevents that escape.

A nonempty weakly linear function has a domain $D$ closed under rational scalars and addition, hence a vector subspace of $\mathbb{R}$ over $\mathbb{Q}$. Additivity first gives $f(0)=0$ and $f(-x)=-f(x)$, then $f(nx)=nf(x)$ for integers $n$. If $q=m/n$ with $n>0$, rational closure puts $qx$ in $D$ andThus $f(qx)=qf(x)$: it is a $\mathbb{Q}$-linear map. The empty function is not maximal because it extends to the function on $\{0\}$ with value zero.

Suppose a maximal $f$ had proper domain $D\ne \mathbb{R}$. Choose $t\notin D$ and any prescribed real value $a$, for instance $a=0$. Every element of $D+\mathbb{Q}t$ has a unique expression $d+qt$: if two expressions coincide and the coefficients differ, then $t$ would belong to $D$. DefineUniqueness makes this well-defined. The displayed logical formula and the $\mathbb{Q}$-linearity of $f$ show directly that $h$ is additive and has a domain closed under rational scalars. Hence it is a weakly linear function and extends $f$. It is a proper extension because $t$ is now in its domain, contradicting maximality. ThereforePart (a) and Zorn's lemma guarantee the existence of maximal extensions as well as this description of their domains.