Past exam of the logic and set theory course of the University of Oxford / 2010 / A / 3

A consistent set of formulae, restricted here to sentences, does not derive a contradiction in the chosen classical deductive system. Equivalently there is no sentence $\theta$ for which both $\Sigma ⊢\theta$ and $\Sigma ⊢\neg \theta$ hold. By explosion, an inconsistent set derives every sentence; a consistent set does not.

This is a syntactic condition about finite derivations, rather than a definition in terms of models.

A set of sentences is maximal consistent if it is consistent and no proper extension by further sentences remains consistent. Equivalently it is consistent, deductively closed, and decides every sentence: for each $\theta$, exactly one of $\theta$ and $\neg \theta$ belongs to it.

For example, if $\Sigma ⊢\theta$ but $\theta \notin \Sigma$, adding $\theta$ does not create a new contradiction, contrary to maximality. Thus maximality includes deductive closure, not only having as many independent axioms as possible.

A set of sentences is satisfiable if some nonempty first-order structure in its language makes every sentence in the set true. Because the formulas are sentences, their truth is independent of the assignment in a first-order structure.

This is a semantic existence condition. Its equivalence with syntactic consistency is the content of the classical Gödel's completeness theorem, together with soundness.

Order the consistent sets of sentences extending $\Sigma$ by inclusion. This collection is nonempty. The union of a chain is consistent: any derivation of a contradiction uses finitely many assumptions, which all lie in one member of the chain. Zorn's lemma therefore supplies a maximal member, which is a maximal consistent extension of $\Sigma$.

For a countable language one can instead enumerate all sentences and successively add either a sentence or its negation while preserving consistency. At least one choice is consistent, since inconsistency of both extensions, together with the deduction theorem for propositional logic and classical reasoning, would make the previous stage inconsistent. The union of the stages is consistent by finite use of assumptions and decides every sentence, so it is maximal consistent.

The chain proof covers arbitrary set-sized languages; no restriction on the language cardinality was printed here. The later prohibition on choice applies to the cardinal-arithmetic question, not this logic construction.

Suppose a structure satisfies every sentence of $\Sigma$. By the soundness theorem for first-order logic, every sentence derivable from $\Sigma$ is true in this structure. In particular it cannot derive both a sentence and its negation, because they cannot both be true under the usual semantics.

Therefore $\boxed{\Sigma \text{ satisfiable}⟹\Sigma \text{ consistent}}$. This direction uses soundness alone, without constructing a model from a proof-theoretic assumption.

In the Henkin construction, first extend the consistent sentence set to a complete consistent theory with witnesses in an expanded language containing fresh constants. Its term model has closed terms modulo provable equality as elements:Functions are interpreted by applying their symbols to representative terms, and an atomic predicate holds of term classes exactly when the corresponding atomic sentence belongs to $T$. Equality axioms make these definitions independent of representatives. The Henkin witness property handles the existential step in the truth lemma, so the resulting structure satisfies $T$ and hence the original $\Sigma$.

An arbitrary sentence set need not already have enough closed terms or witnesses. Calling this a term model for $\Sigma$ means a term-model construction of a model satisfying $\Sigma$, usually through that witnessed completion; it does not assert that every arbitrary $\Sigma$ itself already supplies the construction.

The downward Löwenheim-Skolem theorem says that a structure in a countable language has a countable elementary substructure containing any specified finite or countable set of its elements. More generally the size bound is $\max (|\mathcal{L}|,|C|,{\aleph }_0)$ for a required parameter set $C$. In particular any satisfiable theory in a countable language has a model of size at most countable.

To see the last assertion directly from the completeness construction, add only countably many witness constants in the Henkin construction. There are then countably many finite closed terms, and taking their quotient cannot increase cardinality. The resulting term model is therefore countable. For the elementary-substructure version, perform the witness construction inside the given structure, choosing actual witnesses and closing under the function symbols. The induced substructure is elementary by the Tarski-Vaught test. This is the same witness mechanism as the completeness construction, with the ambient structure supplying the chosen witnesses.

The upward companion states that a theory with an infinite model has models in every sufficiently large infinite cardinal, at least $|\mathcal{L}|+{\aleph }_0$. Add that many pairwise unequal constants, apply compactness, and then the size-bounded construction. The countable consequence is the part needed below.

Use the axioms for a strict dense linear order without endpoints:The first three give strict linear order; the next gives density; the final two exclude endpoints. Domains are nonempty under the adopted first-order semantics, and these axioms force them to be infinite.

Yes. The usual order on the rational numbers is strict and linear. Between $a<b$ lies the rational midpoint $(a+b)/2$, and $a-1,a+1$ witness absence of endpoints. Thus it is a dense linear order without endpoints.

Yes. The usual order on the real numbers is strict and linear, midpoints witness density, and translation by $\pm 1$ supplies points on either side. It therefore satisfies the same dense linear order without endpoints axioms.

No. With its induced usual order, the closed interval has a least element and a greatest element. At zero there is no smaller domain element, and at one there is no larger domain element. It fails the no-endpoint axioms, although it is densely ordered.

Yes. The induced order is strict and linear and remains dense. For $0<x<1$, the points $x/2$ and $(x+1)/2$ lie in the domain and are strictly below and above $x$. Hence the open interval is a dense linear order without endpoints.

Yes. Removing zero leaves the induced order strict and linear, with no endpoints. For any $a<b$ there are infinitely many points in the real interval between them, so one can choose an intermediate point different from zero. More explicitly, the midpoint works unless it is zero, in which case $(2a+b)/3$ is nonzero and lies strictly between the endpoints. Thus density also survives.

The missing point is a cut, not a pair of adjacent elements; the axioms do not require all cuts to be filled.

Enumerate both countable models. Build an increasing sequence of finite order-preserving partial bijections. At an even stage, take the first unmatched element of the first model. Its position relative to the finitely many already matched points determines an open interval or exterior ray in the second model. Density and absence of endpoints supply an unused point there, so the map extends.

At an odd stage perform the symmetric operation starting from the second model, extending the inverse map. Every required interval has infinitely many points, so avoiding the finitely many used values is possible. The union is a total bijection, by the alternating enumeration requirements, and it preserves and reflects order because every finite stage does. Hence it is an isomorphism of structures.

This is the back-and-forth method, proving countable categoricity of the dense-order theory.

The theory is consistent because the rational order is a model. If some sentence $\theta$ were not decided by the theory, both extensions by $\theta$ and by $\neg \theta$ would be consistent. By Gödel's completeness theorem and the countable-model consequence of Löwenheim-Skolem theorem, each would have a countable model. The two models would disagree on $\theta$, so could not be isomorphic. This contradicts part (iii).

Therefore the theory decides every sentence and is complete. Under the standard convention that a theory includes all its logical consequences, this makes it maximal consistent.

If one takes only the displayed finite list of axioms as a raw set, that list is not literally maximal consistent: one can add further theorems without inconsistency. The conclusion applies to its deductive closure, which is the complete theory of dense linear order without endpoints.