What is the definition of a definable set of statements, and what is a constructive way to think of this regarding Tarski's Undefinability Theorem?

295 Views Asked by At

Logic and model theory are not my area so my thinking is probably off, but I am curious about this so please go ahead and set me straight.

A definable set is one for which there is a formula that is true precisely on input from that set. For example over $\mathbb{N}$ the formula "$\phi(p):\forall x,y\ \big[(\neg p=1)\wedge(p=xy\rightarrow (p=x)\vee(p=y))\big]$" defines the prime numbers, and over $\mathbb{R^2}$ the formula "$\phi(x,y):y=x^2$" defines the standard parabola. More generally (ignoring n-ary relations now) over a set $S$ a formula $\phi(x)$ defines the set $\{x\in S\mid\phi(x)\equiv T\}$.

Now take $S$ to be the set of all statements in a language. It seems that Tarski's theorem essentially says that there is no formula defining the set $\{x\in S\mid x\equiv T\}$. Since $x$ is a variable and not a formula, we cannot just replace $\phi(x)$ in the definition with $x$ itself and be done with it. I wonder then what is considered a formula in this context.

As far as I know, Tarski's proof involves coding the statements as natural numbers similar to the Gödel numbering, and then showing that the numbers which correspond to true statements cannot be defined by a formula in the same language (regardless of the coding used). But would there be a way to think about this using formulas over a set of statements? Naively, perhaps a formula would look like (for example) "$\phi(x):P\vee Q\rightarrow x$" where $P$ and $Q$ are fixed statements and $x$ represents a variable statement in $S$. In this case though there is nothing stopping us from calling $x$ by itself a formula which is a problem.

When using numbers, the symbols from arithmetic (particularly the "=" symbol) lend another level of truth which avoids nonsense like $\phi(x):x$. In the attempt in the previous paragraph those symbols are absent, or rather they become nested inside the constants/elements. So could we introduce another level of truth by instead taking formulas to be things like "$\phi(x):((P\vee Q\rightarrow x)\equiv(P\vee x))$" and then bumping up our meta-equivalence to 4 bars, writing the defined set as $\{x\in S\mid\phi(x)\underline{\equiv}T\}$?

Is anything like that done? Does this make any sense? If so can it be used to see why the set $T\subset S$ is undefinable?

1

There are 1 best solutions below

2
On

Your question mixes syntax and semantic and it is not completely understandable to me. Below I restate Tarki's paradox keeping the two levels well-separated, maybe this helps.

Fix a model $M$ and a positive integer $n$. By $L(M)$ we denote the set of all formulas with parameters in $M$. Let $x$ be a tuple of variables of length $|x|=n$. An $n$-truth predicate is a formula $\vartheta(x,y)\in L(M)$ such that for every formula $\varphi(x)\in L(M)$ there is an $a\in M^{|y|}$ such that $M\models\forall x\ \big[\vartheta(x,a)\leftrightarrow\varphi(x)\big]$.

Without any further requirement on $M$, existence of $n$-truth predicates is unproblematic. For instance, take for $M$ an infinite dimensional vector space, then $x=y$ is a $1$-truth predicate (by quantifier elimination). In general, the existence of an $n$-truth predicate does not imply the existence of a $(n+1)$-truth predicate.

Now suppose that in $M$ there is a definable encoding of pairs. That is, a definable bijection $\langle\cdot,\cdot\rangle:M^2\to M$. Then from any $1$-truth predicate we can easily construct an $n$-truth predicate for arbitrary $n$.

This is too good to be consistent! In fact, diagonalization strikes:

Suppose $\vartheta(x,y)\in L(M)$ is a $1$-truth predicate. Clealy we can assume $|y|=1$. For better legibility, we also assume that $\langle x,y\rangle$ is a term in the language. Let $\varphi(x)=\neg\vartheta(\langle x,y\rangle)$ and obtain a contradiction as usual.