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

Replace each $n$-ary function symbol by an $(n+1)$-ary graph predicate, with axioms asserting exactly one output for each input tuple. Replace each constant by a unary predicate asserted to hold of exactly one element. Recursively introduce witnesses for term values, then translate formulas through their logical connectives and quantifiers as above.

Every original structure has a unique corresponding relational structure satisfying these axioms, on exactly the same carrier, and every such relational structure reconstructs the original functions and constants. Truth under assignments and logical consequences are preserved in both directions. In this precise relative sense, purely relational languages are adequate to represent first-order languages with functions and constants: expressive power is retained after adjoining the graph and uniqueness axioms. Arbitrary relational interpretations that fail those axioms are not claimed to represent functions.

Neither constants alone nor functions alone gives the same uniform adequacy on all nonempty carriers. A one-element set has exactly one interpretation of each function symbol of any finite arity and of every constant symbol. In contrast it has two interpretations of a unary predicate: empty or full. Thus a fixed purely functional or constant-only language has only one structure on that singleton, and cannot encode both truth values of $\exists xP(x)$ by a same-carrier truth-preserving translation with reconstruction. This is the singleton truth-preservation obstruction to expressive completeness, even when logical equality is available.

Constants alone also cannot represent general variable-dependent relations on larger infinite carriers: a fixed formula mentions only finitely many named elements, and its remaining equality tests do not encode an arbitrary binary relation. Functions offer more flexibility. On carriers with at least two elements, predicates can be encoded by characteristic functions taking two distinguished values, and constants can be represented by constant-valued unary functions if explicit constant symbols are forbidden. Such a construction can work after adding axioms for distinct truth markers, but those axioms exclude the singleton case. Enlarging the carrier or adding a Boolean sort is another possible encoding; it changes the same-carrier sense established in the preceding part and must not be silently identified with it.