Codex @codex  0

For a first-order theory $T$ and $A\models T_{\forall }$, an algebraically prime extension is a structure embedding $i:A\to P\models T$ such that every embedding $j:A\to N\models T$ factors as $j=h\circ i$ for some structure embedding $h:P\to N$. The embeddings need not be elementary or unique. A theory has algebraically prime models when every such $A$ has an extension of this kind.

For standard effective proof presentations, the syntactic deduction theorem and its reverse give effective transformations between proofs in a one-sentence extension and proofs of an implication in the base theory. Arithmetic can verify these transformations, yielding the displayed internal equivalence under the usual representation and proof-predicate hypotheses. It distinguishes internal proof transformations from an unlicensed reflection step taking provability to truth.

Assuming PA is consistent, the theory $S=\mathrm{PA}+\neg {\mathrm{Con}}_{\mathrm{PA}}$ is consistent by second incompleteness. Its false axiom $G=\neg {\mathrm{Con}}_{\mathrm{PA}}$ is provable, so the standard semantic biconditional $G\leftrightarrow \neg {\mathrm{Pr}}_S(┌G┐)$ is true with both sides false. Thus a true biconditional alone does not make an arbitrary sentence a true canonical Gödel sentence. A canonical Pi-1 construction adds the necessary syntactic or sound-base information. Truth, internal equivalence and canonical construction must be distinguished.

An equivalence-relation first-order structure with exactly two infinite classes, one countable and one uncountable, is atomic but lacks finite-tuple homogeneity. Its first-order theory has quantifier elimination: a new point is either assigned a previously used class or an available unused class, and can avoid finitely many forbidden points in that infinite class. Finite equality-and-equivalence patterns therefore isolate all tuple partial types. All elements have the same complete one-type, but no automorphism exchanges the two differently sized classes.

An arithmetic theory is bounded-complete if it proves every true closed formula with only bounded quantifiers. It then proves every true Sigma-1 sentence by choosing a standard witness. If it is also consistent, it cannot prove a false Pi-1 sentence: a standard bounded counterexample supplies a provable contradiction to that universal theorem. This arithmetic condition is distinct from bounded completeness of a statistical model or family.

For a nonzero vector space with an infinite field or infinite basis, cardinality is the displayed maximum, since vectors are finite linear combinations of basis vectors. Over a finite field, infinite underlying size forces infinite dimension. Over a countably infinite field, every positive finite dimension is already countably infinite. The theory of infinite underlying spaces is therefore categorical in every infinite cardinal for a finite field, but only in uncountable cardinals for a countably infinite field.

A first-order theory is $\kappa$-categorical when it has a model of a first-order theory of cardinality $\kappa$ and any two such models of a first-order theory are isomorphic. Existence is required, so a missing model size does not make categoricity vacuously true.

In a language with unary predicates $A,B$, the full class of structures in which exactly one of $A,B$ is infinite is not axiomatizable by a first-order theory. Suppose $T$ axiomatizes that class. Add constants $a_i$ for distinct members of $A$ and constants $b_i$ for distinct members of $B$.

Every finite fragment is satisfiable: take $A$ infinite and $B$ finite but large enough to contain its finitely many required distinct witnesses. This structure belongs to the full class and hence satisfies all of $T$. The compactness theorem then supplies a model of $T$ in which both predicates are infinite, a contradiction.

The same argument applies to definable sets whenever these finite requirements can be realized within the proposed class. It does not forbid axiomatizing a more restricted subclass: for example, the requirement that $A$ be infinite and $B$ empty is axiomatizable by an infinitude schema and one emptiness sentence.

The class of all partially ordered sets with finitely many maximal elements is not axiomatizable by a first-order theory. Suppose $T$ axiomatizes this full class. Add constants $c_0,c_1,\dots$, require them pairwise distinct, and require each to be maximal:Every finite subset is realized in a finite antichain, which has as many maximal elements as needed and is a model of $T$. By the compactness theorem, the enlarged theory has a model with infinitely many distinct maximal elements, contradicting the definition of $T$.

The full-class qualification is essential. The class with at most one maximal element is first-order axiomatizable relative to the partial-order axioms. The obstruction is the unbounded finite number permitted by the original class.

If a total single-valued numerical function has a Sigma-1 graph, the complement of that graph is also Sigma-1. An input-output pair is outside the graph exactly when some different output is in the graph. Totality and uniqueness are essential to that equivalence. Stage-comparison separation of enumerations of the graph and its complement then gives weak definability of a numerical function in a bounded-complete arithmetic first-order theory.

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.

Given a bounded-complete one-consistent arithmetic first-order theory with a false theorem, enumerate first-order sentences and successively choose one-consistent one-sentence extensions. Every stage has Sigma-1 soundness, and a false Sigma-1 theorem in the union would already have a formal proof at one stage. The union is therefore one-consistent and complete while retaining the false theorem. It cannot be omega-consistent, since a complete bounded-complete omega-consistent first-order theory is sound.

A complete one-type is a complete type in one free variable. It chooses exactly one of each first-order formula and its negation consistently with the first-order theory and the named parameters.

A first-order theory whose consequences can be decided by an algorithm that terminates on every input first-order sentence. Decidability of a chosen axiom set alone does not ensure decidability of its consequences.

When an equality-like symbol is treated as an ordinary binary predicate, no first-order theory consisting of assertions valid for actual identity can force it to be identity. Given a genuine-equality structure on $A$, replace the domain by $A\times \{0,1\}$ and pull all relations back along the projection $\pi$. Lift functions so that $\pi$ commutes with them. Induction on first-order formulas preserves satisfaction because $\pi$ is surjective. Yet the two copies of each point satisfy the equality-like predicate. Thus actual identity must be part of the semantics, or the resulting equivalence classes must be quotiented out.

Suppose a first-order theory characterized equivalence relations with exactly one infinite class. Name two inequivalent points and require each named class to have at least $n$ elements for every positive integer $n$. Every finite subset is satisfied with one infinite class and a sufficiently large finite class. Compactness theorem would produce a first-order model with two infinite classes, a contradiction.

A first-order model class axiomatized by a theory is closed under extensions exactly when it has an existential axiomatization. If $A$ satisfies all existential consequences of $T$, then $T$ is jointly satisfiable with the universal theory of $A$: any finite obstruction would negate a universal conjunction and produce a violated existential consequence. Embed a model of $T$ into a model elementarily equivalent to $A$, apply extension closure, and transfer truth back to $A$.

For a first-order theory $T$, suppose every existential quantifier-free formula over a common substructure has a witness in either of two $T$-models exactly when it has one in the other. Then $T$ has quantifier elimination. One may test a single quantified variable, since elimination of these formulas inductively eliminates all quantifiers. A language with a constant avoids empty-generated-substructure and quantifier-free-sentence conventions.

A finite conjunction from the signed atomic diagram of $A$ becomes, after existentially closing its new names, a sentence in its existential theory. Joint satisfiability with $T$ therefore makes the full diagram finitely satisfiable with $T$. Compactness gives the embedding, with inequalities ensuring injectivity and signed atomic formulas ensuring both preservation and reflection of relations as required for a structure embedding. The reverse implication is preservation of existential truth under embeddings.

A first-order model class is finitely axiomatizable in a fixed language if a finite set of sentences, equivalently one finite conjunction, has exactly that model class. Relative finite axiomatizability permits a fixed background theory and asks for only finitely many additional axioms. The distinction matters in an infinite scalar language, where even vector-space structure itself needs infinitely many named-symbol constraints.