Skip to main content

Raymond Smullyan gave a very general formulation in terms of representation systems. They appear in his "Theory of Formal Systems", and in the first and last chapters of "Godel's Incompleteness Theorems". They generalise first- and higher-order systems of logic, type theories, and Post production systems.

A representation system consists of:

  1. A countably infinite set $E$ of expressions.

  2. A subset $S \subseteq E$, the set of sentences.

  3. A subset $T \subseteq S$, the set of provable sentences.

  4. A subset $R \subseteq S$, the set of refutable sentences.

  5. A subset $P \subseteq E$, the set of (unary) predicates.

  6. A function $\Phi : E \times \mathbb{N} \rightarrow E$ such that, whenever $H$ is a predicate, then $\Phi(H,n)$ is a sentence.

The system is complete iff every sentence is either provable or refutable. It is inconsistent iff some sentence is both provable and refutable.

We say a predicate $H$ represents the set $A \subseteq \mathbb{N}$ iff $A = \{ n : \Phi(H,n) \in T \}$.

Let $g$ be a bijection from $E$ to $\mathbb{N}$. We call $g(X)$ the Godel number of $X$. We write $E_n$ for the expression with Godel number $n$.

Let $\overline{A} = \mathbb{N} \setminus A$ and $Q^* = \{ n : \Phi(E_n,n) \in Q \}$.

We have:

  1. (Generalised Tarski Theorem) The set $\overline{T^*}$ is not representable.

  2. (Generalised Godel Theorem) If $R^*$ is representable, then the system is either inconsistent or incomplete.

  3. (Generalised Rosser Theorem) If some superset of $R^* $ disjoint from $T^*$ is representable, then the system is incomplete.

In case it's not clear: in a first-order system, we can take $P$ to be the set of formulas whose only free variable is $x_1$, and $\Phi(H,n) = [\overline{n}/x_1]H$.

user7247
  • 316
  • 1
  • 4