What does it mean to say that a theory is more expressive than another?

Question

Mathematicians sometimes say, "ZFC set theory is more expressive than Peano Arithmetic". But what does this mean, rigorously? After all, ZFC set theory has only one binary relation symbol $\in$ besides equality, while Peano Arithmetic has the constants $0$ and $1$, the unary operation $S$ of successor, and the binary operations $+$ and $\cdot$. So, on the face of it, it would seem that Peano Arithmetic is more expressive than ZFC. Anyway, what is the real definition of a theory being more expressive than another?

Answer 1

First of all, note that we have an obvious way to "translate" a sentence $\sigma$ in the language of arithmetic into a sentence $\hat{\sigma}$ in the language of set theory ("replace $\mathbb{N}$ with $\omega$," essentially). We then have the following:

Whenever $\mathsf{PA}\vdash\sigma$ we have $\mathsf{ZFC}\vdash\hat{\sigma}$ but not conversely.

But of course this is contingent on the specific translation used. The real power of $\mathsf{ZFC}$ over $\mathsf{PA}$ is seen when we consider all possible translations of an appropriately "structurally meaningful" type: these are the interpretations. The idea of interpreting one theory $T$ inside another theory $S$ is an extremely important one. The definition of an interpretation is a bit tedious, but basically an interpretation of $T$ in $S$ consists of

• a "domain formula" $\delta(x_1,...,x_n)$;

• an "equivalence formula" $\eta(x_1,...,x_{2n})$; and

• for each $k$-ary relation symbol $R$ in the language of $T$, a $kn$-ary formula $\varphi_R(x_1,...,x_{kn})$ (WLOG the language of $T$ is relational),

such that

• $S$ proves that $\eta$ defines an equivalence relation on (the set picked out by) $\delta$ and each $\varphi_R$ is well-defined up to $\eta$, and

• $S$ proves the translation of $T$ into $S$ provided by the tuple of formulas above (replace each "$\forall x$" with "$\forall x_1,...,x_n\in\delta$," each "$=$" with "$\eta$," and each "$R$" with "$\varphi_R$" appropriately).

For example, the usual "implementation" of the rationals as equivalence classes of ordered pairs of integers with second coordinate nonzero corresponds to an interpretation of $Th(\mathbb{Q};+,\times)$ into $Th(\mathbb{Z};+,\times)$ with domain formula $\delta(x_1,x_2)\equiv \neg x_2=0$ and equivalence formula $\eta(x_1,x_2,x_3,x_4)\equiv x_1\times x_4=x_3\times x_2$.

(Note that there's also a notion of a single structure being interpretable in another structure; I'm guilty of this usage here. Additionally, the word "interpretation" gets used to describe the assignment of relations/functions to symbols in the definition of a structure. Logic has serious terminology problems.)

The connection to your question is the following:

$\mathsf{PA}$ is interpretable in $\mathsf{ZFC}$ but not conversely.

The map $\sigma\rightarrow\hat{\sigma}$ does in fact come from an interpretation (namely the usual interpretation of $\mathbb{N}$ as $\omega$), so this point strictly refines the previous one. Of course at a very coarse level $\mathsf{PA}$ and $\mathsf{ZFC}$ are computationally equivalent, in the sense that the deductive closure of each has Turing degree ${\bf 0'}$, but this is so coarse as to be basically useless; by contrast, interpretability strength is extremely interesting and well-studied.