# Given a strong enough theory, why is $\operatorname{Richardian}(n)$ ill-defined?

Richard's paradox (on natural numbers) can be summarized as follows: Let $$R$$ be an enumeration of all the possible unary predicates that can apply to natural numbers. Perhaps, for example, $$R_1(n) := n\text{ is even}$$, $$R_2(n) := n\text{ is odd}$$, $$R_3(n) := n\text { is prime}$$, $$...$$, $$R_{53}(n) := \exists m : n^2 = 3m + 1$$, and so on. Then, define the predicate $$\text{Richardian}(n) := \neg R_n(n)$$. If $$N$$ is such that $$R_N = \text{Richardian}$$, then it follows that $$\text{Richardian}(N) \iff \neg R_N(N) \iff \neg \text{Richardian}(N)$$, which is paradoxical.

I assume that the faulty step of the argument above is the assumption that the predicate $$\text{Richardian}$$ is well defined within the language of the theory. However, I'm not sure why this is the case, given a strong enough theory. Here are my assumptions:

1. There exists a formal structure embedded within the theory which is isomorphic with the source language of the theory. (I will distinguish terms of this structure as "formal" functions/predicates.)
2. It is possible to specify an algorithm which, given a number $$n$$, returns a formal unary predicate $$T_n$$, as a bijective correspondence.
3. We may construct a formal binary predicate $$Q$$ such that, for all numbers $$n$$ and $$m$$, the formal propositions $$Q(n,m)$$ and $$T_n(m)$$ represent biconditional propositions in the source language. This is because our language is expressive enough to define formal functions representing the outputs of algorithms of sufficient complexity required for (2), and to assemble the outputs of formal functions into suitable formal $$n$$-ary predicates.
4. We may, from the definition of $$Q$$, define a formal unary predicate $$R := \text{NOT}(\text{DIAG}(Q))$$ which, for each $$n$$, represents a proposition biconditional with that of $$\text{NOT}(Q(n,n))$$.
5. There "really is" a way, within the language of the theory, of associating a formal term with its denotation. As a result, the rest of the argument that the proposition associated with $$R(N)$$ (where $$N$$ is such that $$T_N = R$$) is biconditional with its own negation goes through.

Where is the flaw in my assumptions?

I assume that the faulty step of the argument above is the assumption that the predicate $$\text{Richardian}$$ is well defined within the language of the theory.

That's correct. In fact Richard's paradox is a proof by contradiction showing that $$\text{Richardian}$$ cannot possibly exist.

In more detail here is what goes wrong if you try to construct $$\text{Richardian}$$ in Peano arithmetic, to be concrete. PA is capable of talking about its own predicates; given a predicate $$\varphi$$ we can construct a Gödel code $$\ulcorner \varphi \urcorner \in \mathbb{N}$$. It is crucial to make the Gödel code explicit here. Now we can attempt to write down an enumeration $$R$$ of Gödel codes for predicates in PA. This step is unproblematic.

The problematic step is that $$R$$ outputs a Gödel code, not a predicate, and a Gödel code is just a natural number, so what does $$\neg R_n(n)$$ mean? The notation here equivocates between predicates and their Gödel codes so it obscures the fact that we need a way to take a Gödel code for a predicate $$\varphi$$ and a natural number $$n$$ and assert $$\varphi(n)$$. In other words we need a truth predicate $$\text{True}(\ulcorner \varphi \urcorner, n)$$ which is true iff $$\varphi(n)$$ is true. If we had such a truth predicate, we could define

$$\text{Richardian}(n) = \neg \text{True}(\ulcorner R_n \urcorner, n).$$

So Richard's paradox in this case is a proof by contradiction implying that PA does not have a truth predicate! This is Tarski's undefinability theorem. Because PA does not have a truth predicate, $$\text{Richardian}$$ does not actually exist as a predicate in PA, so it does not have a Gödel code that can be enumerated by $$R$$.

(However, PA does have a provability predicate $$\text{Prov}$$, and running the above argument using the provability predicate instead constructs a statement which asserts its own unprovability, which is unprovable in PA (assuming its consistency) hence true; this is, of course, the first incompleteness theorem.)

So, to pin it down to one sentence in your assumptions, this bit:

There "really is" a way, within the language of the theory, of associating a formal term with its denotation.

is talking about the need for a truth predicate.