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

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.