Finite satisfiability means that every finite subset $T_0\subseteq T$ has an $L$-structure satisfying all its sentences. Different finite subsets may have different witnessing structures. The first-order compactness theorem says this condition is equivalent to satisfiability of the entire set, but finite satisfiability itself is defined by the finite-subset condition.

The Tarski-Vaught test says that a substructure $A\subseteq B$ is elementary exactly when for every formula $\varphi (x,\bar{y})$ and tuple $\bar{a}\in A$, if $B\models \exists x\varphi (x,\bar{a})$, some $b\in A$ satisfies $B\models \varphi (b,\bar{a})$. Thus every existential assertion with parameters from $A$ that has a witness in $B$ already has a witness in $A$. The matrix may contain quantifiers; restricting it to quantifier-free formulas would not state the full test.

The relation $A\subseteq B$ means that the domain of $A$ is a subset of the domain of $B$ and the inclusion map is an $L$-embedding. Thus it contains all named constants, is closed under every named function, and uses the restrictions of the ambient relations.

The stronger relation $A\preccurlyeq B$ means that for every first-order formula $\varphi (\bar{x})$ and tuple $\bar{a}$ from $A$,This includes formulas with quantifiers ranging over the respective domains. Elementary inclusion implies ordinary substructure inclusion, but the latter need only preserve quantifier-free truth. In particular an existential witness available in $B$ need not lie in an arbitrary substructure.

An $L$-embedding $\pi :A\to B$ is an injective map preserving the interpretations of all constants and functions and preserving and reflecting every relation. Explicitly $\pi (c^A)=c^B$, $\pi (f^A(\bar{a}))=f^B(\pi \bar{a})$, and $A\models R(\bar{a})$ if and only if $B\models R(\pi \bar{a})$. Injectivity handles logical equality. Equivalently it is an isomorphism onto an $L$-substructure of $B$, or a map preserving the truth of all quantifier-free formulas. Preserving relations in only one direction would instead give a weaker homomorphism notion, not an embedding.

Reuse the complete free-bijection theory from part (e). Quantifier elimination shows that every one-variable atomic statement is already decided by the no-finite-cycle axioms. Thus there is exactly one complete one-type, isolated by $x=x$.

For two logical variables, each integer $k$ gives a different complete type isolated byThere is also the complete typesaying that the two elements lie in different orbits. These exhaust the possibilities by quantifier elimination. In particularThe last complete type is a nonprincipal complete type. Any logical formula uses only finitely many integer offsets after quantifier elimination; a pair in a single orbit with a sufficiently different offset agrees with a different-orbit pair on those tests. Hence no single logical formula can isolate $p_{\infty }$.

The one-orbit first-order model $(\mathbb{Z},f(n)=n+1,g(n)=n-1)$ omits $p_{\infty }$, while a two-orbit first-order model realizes it. This illustrates the omitting types theorem and shows concretely why finitely many complete one-types alone cannot replace the all-arities condition in Ryll-Nardzewski.

Use the first-order theory $T_{\mathbb{Z}}$ of a bijection $f$ with named inverse $g$ and no finite cycles. Its axioms areEvery first-order model is a disjoint union of free two-sided integer orbits. Write $f^k$ for positive powers of $f$ and for powers of $g$ when $k$ is negative.

This first-order theory is complete and eliminates quantifiers. Every first-order term reduces to $f^k(x_i)$, and atomic logical formulas reduce to statements $x_j=f^k(x_i)$. To eliminate an existential logical variable in a conjunction of literals, first remove self-equalities using the no-finite-cycle axioms. If an equation fixes that logical variable as an integer translate of another logical variable, substitute that value. If no such equation remains, only finitely many points are excluded by the remaining inequalities, so some value exists in the infinite domain. Apply this to disjunctive normal form and then induct on logical formulas. The resulting parameter-free first-order sentences are decided, proving completeness.

For each fixed finite $n$, a complete type records a partition of the logical variables into common orbits and finitely many integer offsets within each block. There are countably many possibilities. Countable first-order models with one orbit and with two orbits are not isomorphic, so the first-order theory is not ${\aleph }_0$-categorical.

Thus this example has the source's explicitly defined countable-type property. In fact it also satisfies ordinary omega-stability: over a countable parameter set, an element is either a specified integer translate of a parameter, giving countably many possibilities, or lies in an entirely new orbit, giving one further complete one-type. The same finite-orbit-pattern description handles finite tuples. ThereforeThe source prints the label “$0$-stable”; the construction meets its stated definition as well as the usual stronger omega-stability condition. The difference between countably many and finitely many partial types is exactly why Ryll-Nardzewski does not yield categoricity here.

The same complete theory $T_{\infty }$ of an infinite pure set provides this property directly. For $n$ logical variables, each complete type specifies exactly which logical variables are equal. First-order consistency requires an equivalence relation on the finite index set, and infinitude ensures every such partition is realizable. Hencewhere $B_n$ is the $n$th Bell number, counting partitions of an $n$-element set. For example the first values are $B_1=1$, $B_2=2$ and $B_3=5$. The isolating conjunction lists logical equality within blocks and inequality between blocks. This explicitly verifies the hypothesis which Ryll-Nardzewski identifies with ${\aleph }_0$-categoricity.

Take the first-order theory of an infinite set in the first-order language of logical equality alone, with an axiom asserting at least $n$ distinct elements for each positive integer $n$. It is complete and eliminates quantifiers: a new logical variable either equals a specified old logical variable or is required to avoid only finitely many existing values, which an infinite domain permits.

For every infinite cardinal $\kappa$, any two first-order models of size $\kappa$ are isomorphic because every bijection between their underlying sets preserves logical equality, the whole first-order language. ThusIts complete $n$-types record only the partition of coordinate indices according to logical equality. There are finitely many such partitions, and each is isolated by the corresponding logical equalities and inequalities. Ryll-Nardzewski therefore recovers countable categoricity; there are no nonprincipal complete finite-arity partial types to omit in this example.

Use $AC{F}_0$, the complete theory of algebraically closed fields of characteristic zero. Its quantifier elimination is a standard characterization of this complete theory. Algebraically closed fields of a fixed characteristic are classified up to isomorphism by transcendence degree over their prime field.

For such a field $K$,when the transcendence degree is infinite, while finite transcendence degree also gives a countable field. This follows by counting rational functions in a transcendence basis and then algebraic elements over that field. Thus every first-order model of cardinality ${\aleph }_1$ has transcendence degree ${\aleph }_1$, and the classification gives a unique such first-order model.

On the other hand $\overline{\mathbb{Q}}$ and an algebraic closure of $\mathbb{Q}(t)$ are countably infinite first-order models with transcendence degrees zero and one, so are not isomorphic. HenceThe transcendental complete one-type consists of $f(x)\ne 0$ for every nonzero polynomial over $\mathbb{Q}$. Quantifier elimination makes it complete. It is nonprincipal: any parameter-free one-variable logical formula containing a transcendental element defines a cofinite set, hence contains algebraic elements as well and cannot isolate this partial type. The first-order model $\overline{\mathbb{Q}}$ omits it, concretely illustrating the omitting types theorem. The existence of infinitely many algebraic complete one-types, together with this nonprincipal complete type, also agrees with the failure of the Ryll-Nardzewski finiteness condition.

Use the complete theory of dense linear orders without endpoints in the first-order language $\{<\}$. It eliminates quantifiers: existential conditions on one new point reduce to finitely many logical equality constraints and interval bounds, and density and absence of endpoints decide whether a suitable point exists. Its countably infinite first-order models are all isomorphic to the rational order by the usual back-and-forth method, extending finite order-preserving maps alternately along enumerations of the two first-order models. Thus it is ${\aleph }_0$-categorical.

To distinguish first-order models of size ${\aleph }_1$, letwith ordered sums. Both are dense without endpoints and have cardinality ${\aleph }_1$. The first has cofinality ${\aleph }_1$: countably many points lie in a bounded set of block indices and cannot be cofinal. The second has cofinality ${\aleph }_0$, supplied by its final rational block. Cofinality of a linear order is preserved by isomorphism, so they are not isomorphic. ThereforeFor Ryll-Nardzewski, its $n$-types are precisely the finitely many equality-and-order patterns on $n$ coordinates. Each is isolated by the conjunction specifying that pattern, agreeing with the theorem's prediction.

Use the arithmetical proof relation and coding just constructed. A formal proof of $C$ cannot have code $0$, since that code was reserved for $\neg C$. Every candidate code $v$ for a formal proof of $C$ is therefore positive. But code $0\le v$ is already a formal proof of $\neg C$, so the no-earlier-negation condition fails for every candidate. HencePA proves $C$ by induction, while $S$ has $\neg C$ as an added axiom. Thus $S$ is inconsistent and its ordinary arithmetical provability predicate is true of every first-order sentence, including $C$. The displayed negative Rosser assertion can nevertheless be true, because the Rosser condition compares the order of opposite formal proofs rather than asking for their mere existence.

There is an important coding qualification. The PDF refers to a course formal proof coding but does not specify its numerical ordering. The truth of this Rosser assertion for an inconsistent first-order theory is not coding-invariant, so formal proof length alone cannot establish it for an unspecified fixed coding. For example, a different legitimate numbering could reserve code $0$ for a known PA formal proof of $C$, code $1$ for the new axiom $\neg C$, and higher codes for all other derivations. Then code $0$ would witness ${\mathrm{Pr}}_S^{\ast }(┌C┐)$ instead. The explicit allowed construction in part (i) supplies a convention under which the requested assertion holds; interpreting it as a claim about some externally fixed course numbering requires that numbering's corresponding order property.

Let $C$ denote the addition-commutativity first-order sentence and put $d=┌\neg C┐$. In the ordinary checker for PA derivations, replace the axiom test ${\mathrm{Ax}}_{PA}(u)$ byKeep all tests for sequence formation, earlier lines, logical axiom schemes and inference rules unchanged. This gives a formal proof checker $Q_S(u,w)$ which recognizes exactly ordinary $S$-derivations. The finite syntactic modification is arithmetizable by the same bounded coding apparatus as the original checker.

For the proof-order comparison in the next part, make the choice of coding explicit. Reserve code $0$ for the one-line derivation of the newly added axiom $\neg C$, and give an ordinary derivation with code $w$ the new code $w+1$. A corresponding bounded relation isEvery code has a specified decoding, every genuine formal proof is represented, and no false formal proof is admitted. The reserved code duplicates one genuine derivation, which is harmless. This is one explicit arithmetized arithmetical proof relation obtainable from the PA checker by the requested axiom change and a simple renumbering. Stating the proof-order convention matters because a Rosser predicate symbol uses code order, not merely the existence of formal proofs.

One-consistency says that no bounded arithmetic formula $F(x)$ has a provable existential closure while each of its standard numeral instances is refutable. It implies first-order consistency, since an inconsistent classical first-order theory proves every logical formula.

If $P$ is one-consistent, (i) gives $P⊬G$, so $a\notin D$. Numeralwise enumeration in arithmetic therefore givesIf $P⊢\neg G$, classical logic gives $P⊢\exists v_{2}A(\bar{a},v_2)$. The matrix is bounded, and the preceding displayed derivations refute every standard instance. This violates one-consistency. ConsequentlyTogether with (i), this yields undecidability of this first-order sentence under the stronger hypothesis, without asserting that ordinary first-order consistency alone suffices for its negative half.

Use the numeralwise enumeration in arithmetic convention in the first-order theory: membership supplies a standard stage with a provable enumerating instance, while nonmembership makes every standard-stage instance refutable. Put $D=\{n:P⊢E_n(\bar{n})\}$. By the definition of $a$, the diagonal instance $E_a(\bar{a})$ is exactly $G$.

If $P⊢G$, then $a\in D$. Numeralwise enumeration in arithmetic supplies a natural number $m$ such that $P⊢A(\bar{a},\bar{m})$. But universal instantiation of $G$ gives $P⊢\neg A(\bar{a},\bar{m})$. This contradicts first-order consistency. ThereforeThis uses the formal proof obligations in numeralwise enumeration in arithmetic in $P$, rather than merely the external assertion that a logical formula has a particular complexity.

In dimension one, the Sobolev embedding theorem gives $H^1(\Omega )\hookrightarrow L^{\infty }(\Omega )$. Thereforeand, for fixed $w$,Hence the operator is well-defined and monotone in one dimension.

In every dimension $n\ge 2$ it is not well-defined on all of $H^1\times H^1$. We exhibit $w=u=v\in H^1$ for which the purported pairing $\int w^2|\nabla w{|}^2$ is infinite. Choose a ball compactly contained in $\Omega$, put $r=|x-x_0|$, and multiply each following radial expression by a smooth cutoff function that equals one near $r=0$.

For $n\ge 3$, set $w=r^{-\alpha }$ with $\alpha =(n-2)/3$. The local Sobolev norm is finite becausewhereassince $n-3-4\alpha =(-n-1)/3<-1$.

For $n=2$, take $w=(\log (1/r){)}^{1/3}$ on a sufficiently small ball. With $s=\log (1/r)$, the gradient integral is proportional to ${\int }^{\infty }{s}^{-4/3}ds<\infty$, while the weighted integral is proportional to ${\int }^{\infty }{s}^{-2/3}ds=\infty$. Its $L^2$ integral is finite because the area factor contributes exponential decay in $s$. These singular functions have the indicated weak derivatives; deleting a small central ball and passing to the limit in integration by parts leaves no boundary term.

Thus $w^2\nabla u\cdot \nabla v$ need not be integrable in dimensions at least two. This is the squared Sobolev gradient counterexample. With the additional restriction $w\in L^{\infty }$, the form is well-defined and monotone in any dimension.

The operator is well-defined in every dimension: $|\cos w|\le 1$ givesFor fixed $w$, its monotonicity condition isThus $\cos w\ge 0$ almost everywhere is sufficient. It is also necessary, by the positivity criterion for a scalar gradient form. Indeed, if the bounded coefficient $c=\cos w$ is negative on a set of positive measure, choose a Lebesgue point $x_0$ with $c(x_0)<0$ and a nonconstant compactly supported smooth $\psi$. Set $z_{\epsilon }(x)=\epsilon \psi ((x-x_0)/\epsilon )$, supported inside $\Omega$. Thencontradicting monotonicity. Therefore $\boxed{A(w,\cdot )\text{ is monotone exactly when }\cos w\ge 0\text{ almost everywhere}}$. In particular it is not monotone for every $w$: the admissible constant $w\equiv \pi$ makes it the negative Dirichlet form.

Give $H_0^1$ the equivalent Hilbert space norm $\Vert u{\Vert }_H=\Vert \nabla u{\Vert }_2$, using the Poincaré inequality. DefineThe Cauchy-Schwarz inequality gives $|a(u,v)|\le (1+C_P\Vert b{\Vert }_{\infty })\Vert u{\Vert }_H\Vert v{\Vert }_H$ and $|\ell (v)|\le C_P\Vert f{\Vert }_2\Vert v{\Vert }_H$.

For $\phi \in C_0^{\infty }(\Omega )$, the definition of weak divergence, applied to ${\phi }^2/2$, givesThe left side is continuous in the $H_0^1$ norm. Approximate any $u\in H_0^1$ by test functions and pass to the limit on the left to obtain $\int (b\cdot \nabla u)u\ge 0$. This density argument is essential: local integrability of $\mathrm{div}b$ alone does not justify treating $(\mathrm{div}b)u^2$ as integrable for arbitrary $u\in H_0^1$.

Consequently $a(u,u)\ge \Vert u{\Vert }_H^2$, so $a$ is a coercive bilinear form. The Lax-Milgram theorem supplies a unique weak solution with $\boxed{\Vert \nabla u{\Vert }_2\le C_P\Vert f{\Vert }_2}$. The reusable estimate is coercivity from a drift with nonpositive weak divergence.

A weak solution belongs to the zero-boundary Sobolev space $H_0^1(\Omega )$ and satisfiesThe boundedness of $b$ and the Cauchy-Schwarz inequality make the drift term integrable. This weak formulation moves one derivative from the Laplacian onto the test function, while retaining the first-order drift term.

Introduce coordinates $s=x+y$, $t=x-y$, so $dxdy=\frac{1}{2}dsdt$. For a test function $\phi (x,y)=\Phi (s,t)$,almost everywhere. HenceThe first derivative integrates to zero in $s$, and the second to zero in $t$, using compact support. Thus $\boxed{\mathrm{div}V=0}$ as a weak divergence. Geometrically, the jump across $x+y=0$ is $(1,-1)$, perpendicular to its normal $(1,1)$; there is no distributional flux concentrated on the interface.

The real Lax-Milgram theorem states: let $H$ be a Hilbert space and let $a:H\times H\to \mathbb{R}$ be a bounded bilinear form such that $a(v,v)\ge \alpha \Vert v{\Vert }_H^2$ for some $\alpha >0$ and every $v\in H$. For every bounded linear functional $\ell \in H^{\ast }$ there exists a unique $u\in H$ satisfyingSymmetry of $a$ is not required. The complex version replaces bilinearity by sesquilinearity and the lower bound by $\mathrm{Re}a(v,v)\ge \alpha \Vert v{\Vert }_H^2$.