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

The alphabet of a first-order language separates logical symbols from nonlogical symbols. In the standard presentation here the logical symbols are the variables $x_0,x_1,\dots$, equality $\dot{=}$, negation $\neg$, logical implication $\to$, the universal quantification $\forall$, and the punctuation symbols parentheses and comma. The nonlogical symbols are constant symbols, function symbols of each specified finite arity, and predicate symbols of each specified finite arity, such as $f_n^{(k)}$ and $P_n^{(k)}$.

Constants can equivalently be treated as zero-ary function symbols. Their arities belong to the language specification. Other logical connectives, and $\exists x\varphi$ as an abbreviation for $\neg \forall x\neg \varphi$, need not be primitive alphabet symbols. This distinction matters in counting literal symbol occurrences.

The first-order terms are the least collection containing every variable and constant and closed under formation of $f(t_1,\dots ,t_k)$ whenever $f$ has arity $k$ and the $t_j$ are terms. A closed term has no variables.

The first-order formulas are the least collection containing the atomic formulas $t_1\dot{=}{t}_2$ and $P(t_1,\dots ,t_k)$ of the appropriate arities, and closed under negation, logical implication, and universal quantification: from formulas $\varphi ,\psi$ one may form $\neg \varphi$, $(\varphi \to \psi )$, and $\forall x_i\varphi$, with the chosen fully parenthesized grammar. Only finite expressions obtained by these rules are formulas. No additional strings belong to either collection.

Terms denote elements under an assignment in a first-order structure; formulas receive truth values in a first-order structure. The two syntactic categories have different formation rules even when they use some of the same punctuation.

False. A ternary atomic predicate gives a counterexample:This string contains one opening parenthesis and two commas. Thus its number of opening parentheses is smaller than its number of commas. A high-arity argument list contributes several commas while requiring only one pair of parentheses.

False. Choose a variable $x_j$ different from $x_i$ and takeThe variable $x_i$ does not occur at all, so in particular it is not free. Yet the formula has one universal-quantifier symbol and zero occurrences of $x_i$. The hypothesis on free occurrences of one variable does not control quantifiers binding other variables.

False. Let $\varphi$ be $x_i\dot{=}{x}_i$ and let $t=x_j$ with $j\ne i$. There is no quantifier that could capture a variable, so $t$ is free for $x_i$ in $\varphi$. Capture-avoiding substitution givesThe number of occurrences of $x_i$ falls from two to zero, contradicting the proposed strict increase. Even capture-avoiding substitution of $x_i$ itself would leave the formula unchanged and refute the strict inequality.

True. In the formation rules, commas occur only between arguments in a function application or an atomic predicate application. Each such argument list includes an opening parenthesis. Subsequent construction of larger terms or formulas retains those symbols.

Equivalently prove by simultaneous structural induction on terms and formulas that an expression containing no opening parenthesis contains no comma. Variables and constants have neither; a comma-bearing function or predicate application already has an opening parenthesis; equality, connectives, and quantifiers cannot introduce a comma outside their constituent expressions. Taking the contrapositive proves the claim.

A collection of logical connectives is adequate, or has functional completeness, if every Boolean function of finitely many propositional variables can be expressed by a formula using those connectives and variables, with the usual convention for nullary truth constants stated if those are included.

An adequate example is $\boxed{\{\neg ,\to \}}$. An inadequate example is $\boxed{\{\to \}}$: formulas using logical implication alone preserve truth when every input is true, so cannot express negation. These examples concern truth functions, rather than mere syntactic formation of formulas.

Use structural induction on formulas. Every term denotes the unique element. Every atomic predicate is true by hypothesis, and every equality is true because its two terms denote that same element.

If both immediate subformulas of an logical implication are true, their logical implication is true. A universal or existential quantification ranges over the singleton domain; its matrix is true for the only possible value by induction, so either quantified formula is true. These are all the formation cases in the reduced language. Hence

No. The full language can express $\neg (x_0\dot{=}{x}_0)$, which is false in the singleton structure from part (i). Every formula of the reduced language is true in that structure under every assignment in a first-order structure. Therefore no formula of the reduced language can be logically equivalent to this negated equality.

This is a singleton truth-preservation obstruction to expressive completeness. Adding both quantifiers to logical implication does not repair the failure: on this particular nonempty singleton model, quantification cannot create a false formula from true atomic formulas.