What is a universal function in model theory?

Question

What does it mean that a function in a model is universal?

Let A be the domain of a model. As I understand it, an empty function is a function that is not defined for any object in A; an empty n-ary relation is an empty set; a universal n-ary relation is a set which includes all n-tuples in A.

Is all the above correct, and if so, what is a universal function?

For context, 'universal function' occurs in the paper 'The Metamathematics of Putnam’s Model-Theoretic Arguments' by Tim Button, in the proof of the Permutation Theorem, which states that a theory with a non-trivial model has multiple isomorphic models.

Thanks in advance.

Answer 1

I have never heard the term "universal function" in model theory, and, like you, I was rather confused about what it could mean. So I had a look at Button's paper (thanks for providing context in your question!).

The relevant lemma in the paper, Lemma 2 in Section 8.1, claims that if $\mathcal{A}$ is a structure with at least two elements, such that the signature contains

1. a constant, or
2. a relation which is not empty or universal in $\mathcal{A}$, or
3. a function which is not empty or universal in $\mathcal{A}$,

then there is a a structure $\mathcal{B}\cong \mathcal{A}$ with the same underlying set as $A$, but $\mathcal{B}\neq \mathcal{A}$.

This lemma is incorrectly stated. In fact there is a simple characterization of the conclusion Button wants to draw: there should be a symbol in the signature whose interpretation in $\mathcal{A}$ is not preserved by all permutations of the underlying set - equivalently, there should be a symbol whose interpretation is not definable in the empty language (containing just equality). Let's go through the conditions and see how they match up with this characterization.

1. is ok. Since $|A|\geq 2$, there's a permutation moving any particular element, so no constant is preserved by all permutations.

2. is wrong, for relations of arity greater than $1$. The only relations of arity $1$ that are preserved by all permutations are the empty relation and the universal relation, as claimed. But there are plenty of relations of higher arity which are definable in the empty language. For example, the relation $R\subseteq A^3$ consisting of $\{(a,b,c)\mid a = b\}$ is preserved by all permutations.

3. is really wrong, partially because the conditions don't make sense (usually in model theory we require the domain of an $n$-ary function to be all of $A^n$, so there are no empty functions, and it's unclear what's meant by a universal function). Also, there are plenty of "nontrivial" functions definable in the empty language and hence preserved by all permutations. For a complicated-looking example, consider the $3$-ary function $A^3\to A$ given by $$f(a,b,c) = \begin{cases} a \text{ if }b = c\\ b \text{ if }b\neq c.\end{cases}$$