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

A logical derivation of $\alpha$ from $\Gamma$ is a finite sequence ${\delta }_1,\dots ,{\delta }_n=\alpha$ in which each line belongs to $\Gamma$, is an instance of one of the three specified axiom schemes, or follows from two earlier lines ${\delta }_j$ and ${\delta }_j\to {\delta }_i$ by the modus ponens rule. $\Gamma ⊢\alpha$ means that such a finite derivation exists. In particular, a derivation uses only finitely many assumptions even if $\Gamma$ is infinite.

A theorem is derivable with no assumptions: $⊢\alpha$ abbreviates $\varnothing ⊢\alpha$. Its logical derivation consists entirely of axiom instances and applications of the modus ponens rule to earlier lines.

The following is a logical derivation using only A1, A2 and the modus ponens rule. The first two lines are assumptions:Thus $\boxed{\{\alpha \to \beta ,\beta \to \gamma \}⊢\alpha \to \gamma }$.

An instance of A3 isThe second assumed theorem and the modus ponens rule therefore give $\Gamma ⊢\beta \to \alpha$. Apply the preceding implication-composition derivation to this theorem and $\Gamma ⊢\neg \alpha \to \beta$. We obtain $\Gamma ⊢\neg \alpha \to \alpha$. The permitted theorem $(\neg \alpha \to \alpha )\to \alpha$ and one more modus ponens rule application yield $\boxed{\Gamma ⊢\alpha }$.

Logical equivalence means that the two propositional formulas receive the same truth value under every Boolean valuation of the propositional variables. Equivalently, $\alpha \leftrightarrow \beta$ is a tautology:

Assign to each propositional formula its finite symbol length. The set of lengths of formulas logically equivalent to $\alpha$ is a nonempty subset of the natural numbers, because it contains the length of $\alpha$. The well-ordering principle for the natural numbers gives a least such length, and hence a shortest equivalent formula.

A shortest equivalent formula need not be unique. For example $(p_0\to p_0)$ and $(p_0\leftrightarrow p_0)$ are distinct tautologies of the same minimal length. A shorter formula would contain no binary connective and hence be a variable with some number of negations, which is not a tautology. This counts each propositional variable as one symbol, as in the stated language, and proves that a shortest equivalent formula need not be unique.

A conjunctive normal form is a finite conjunction of clauses, each clause being a finite disjunction of literals. A literal is a propositional variable or the negation of one. Thus its shape isA single clause or single literal is allowed; the necessary parentheses can be inserted according to the grammar.

First eliminate implication and biconditional using the logical equivalencesPush negations inwards using De Morgan's laws and eliminate double negations. Structural induction leaves only literals joined by conjunction and disjunction.

Now induct on that remaining expression. A literal is already in conjunctive normal form. A conjunction of two conjunctive normal forms is again one after associating its clauses. For a disjunction, write the two inductively obtained forms as ${\bigwedge }_i{C}_i$ and ${\bigwedge }_j{D}_j$ and use distributivity:Each $C_i\vee D_j$ is a clause. All operations preserve logical equivalence, proving the required form exists.

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.

A logical derivation is a finite proof in the specified calculus, with conclusion $\Gamma ⊢\varphi$. Assumptions from $\Gamma$ and instances of A1–A7 are available; the rules are the modus ponens rule, universal generalization rule, and weakening.

In judgement form the universal generalization rule takes $\Delta ⊢\theta$ to $\Delta ⊢\forall x_i\theta$ only if $x_i$ is not free in any undischarged assumption in $\Delta$. Weakening permits $\Delta ⊢\theta$ to become $\Delta \cup \Sigma ⊢\theta$. All instances of A4 and A5 must meet their stated substitution and free variable conditions. Derivability means existence of such a finite proof with assumptions contained in $\Gamma$. Equivalently one tracks the finite assumption set used by each proof line.

The first-order term $t$ is free for substitution for $x_i$ in $\varphi$ if, at every free occurrence of $x_i$ to be replaced, no enclosing quantifier binds a variable occurring in $t$. Equivalently, the substitution introduces no variable capture. Only free occurrences of $x_i$ are replaced.

Take $\varphi =\forall x_1(x_0=x_1)$. The term $x_2$ is free for substitution for $x_0$: its variable is not bound by the enclosing quantifier. The term $x_1$ is not free for substitution for $x_0$, because insertion under $\forall x_1$ captures that occurrence.

Thus the first substitution gives $\forall x_1(x_2=x_1)$; the second, illegitimate substitution would give $\forall x_1(x_1=x_1)$.

In a two-element first-order structure, $\varphi =\forall x_1(x_0=x_1)$ is false for every first-order variable assignment. Blind substitution of $x_1$ for $x_0$ yields $\forall x_1(x_1=x_1)$, which is true. This does not express the original property evaluated at the value of the inserted term: it has changed a free parameter into a bound variable.

For a direct failure of the substitution axiom, use $\theta (x_0)=\exists x_1(x_0\ne x_1)$. On a two-element domain, $\forall x_0\theta (x_0)$ is true, whereas the captured instance $\exists x_1(x_1\ne x_1)$ is false. Consequently an unrestricted A4 would prove a false implication. The free for substitution condition is necessary for soundness.

Write $E(x,y)$ for the displayed equality predicate. A6 and A4 give $⊢E(x,x)$, establishing a reflexive relation.

An instance of A7, replacing just the first occurrence of $x$ in $E(x,x)$, isAssume $E(x,y)$, apply the modus ponens rule twice using reflexivity, and obtain $E(y,x)$. The deduction theorem for propositional logic discharges the assumption. This proves symmetry.

For transitivity, A7 suppliesby replacing $y$ in the atomic formula $E(x,y)$. From assumptions $E(x,y)$ and $E(y,z)$, two applications of the modus ponens rule give $E(x,z)$. Discharging assumptions and universally generalizing givesThus the predicate defines an equivalence relation within the calculus.

No such first-order axiom collection can force actual identity when the displayed symbol is treated as an ordinary relation. The duplication obstruction to axiomatizing identity proves this even for an infinite collection of extra axioms.

Start with any nonempty first-order structure $\mathcal{A}$ in which the symbol is identity. Form $B=A\times \{0,1\}$ and the surjection $\pi :B\to A$. Interpret each relation by pulling it back along $\pi$; in particular,Interpret every function on first coordinates as in $\mathcal{A}$ and choose second coordinate zero; likewise lift constants with second coordinate zero. Induction on first-order terms gives $\pi (t^{\mathcal{B}}(v))=t^{\mathcal{A}}(\pi v)$. Induction on first-order formulas then givesThe quantifier steps use surjectivity of $\pi$, so every witness in $A$ lifts to $B$.

Every proposed axiom valid with actual equality is therefore true in $\mathcal{B}$ under every assignment, along with A1–A7. But $E^{\mathcal{B}}((a,0),(a,1))$ holds for two different domain elements. Thus those axioms cannot enforce identity. The usual interpretation of logical equality as identity is a semantic requirement.