Past exam of the logic and set theory course of the University of Oxford / 2011 / A / 2

A first-order structure for this language is $\mathcal{A}=(A,f^{\mathcal{A}})$, where $A$ is a nonempty set and $f^{\mathcal{A}}:A\to A$ is a total function. The logical equality symbol is interpreted as actual equality on $A$; there are no other nonlogical symbols to interpret.

Use an involution with exactly one fixed point:The first conjunct makes every orbit of the function $f$ have size one or two. The second says precisely one orbit has size one. A finite model therefore has $1+2m$ elements, an odd number.

Conversely, on any set of size $2m+1$, fix one element and partition the remaining $2m$ elements into pairs; let $f$ swap the two members of each pair. This defines a model of $\varphi$. The case $m=0$ gives a one-element model. Thus the finite model sizes are exactly the positive odd integers.

Extend the first-order variable assignment recursively to first-order terms byFor atomic formulas, $\mathcal{A}\models t=s[v]$ exactly when $\tilde{v}(t)=\tilde{v}(s)$. Extend to the Boolean connectives by their truth tables, for example implication is false exactly when its antecedent is true and its consequent false. Quantifiers use modified first-order variable assignments:This recursion defines satisfaction for a set structure for every first-order formula.

Semantic consequence under an assignment means that for every first-order structure $\mathcal{A}$ with the relevant first-order variable assignment $v$ into its domain,More explicitly, in a fixed structure this is the satisfaction implication at $v$; logical consequence requires that implication in all structures and assignments. An assignment takes values in a particular domain, so a single set map is not silently shared between unrelated domains.

By induction on first-order formulas, their truth values depend only on the values of their free variables. A first-order sentence has none. If all formulas here are sentences, every displayed satisfaction statement, and therefore the consequence condition, is independent of $v$.

The antecedent says that the nonempty domain has at most two elements: its two witnesses need not be distinct. The consequent says it has exactly one element. ThusOne-element structures satisfy both sides; domains of size at least three, including infinite domains, make the antecedent false. The function $f$ has no bearing on this condition.

A two-element model of $\varphi$ would be a finite model with even size, contrary to the defining property established in part (b). Every model of $\varphi$ therefore has size other than two, and the preceding interpretation of $\psi$ gives $\boxed{\{\varphi \}\models \psi }$. This includes infinite models, since the antecedent of $\psi$ is false there.

The compactness theorem states that a set of first-order sentences has a model if every finite subset has a model.

For each $n\ge 1$, let ${\chi }_n$ assert that at least $n$ distinct elements exist. Consider $T=\{\varphi \}\cup \{{\chi }_n:n\ge 1\}$. A finite subset requires only some finite lower bound $N$ on the size. Choose an odd integer $m\ge N$; the given property of $\varphi$ supplies a model of that size, satisfying the finite subset. By the compactness theorem, $T$ has a model. Its domain has at least $n$ elements for every $n$, so $\varphi$ has an infinite model. This argument applies to every sentence with the finite-model-size property in (b), irrespective of its behavior on infinite structures.