Difficulty in understanding significance of Grelling's Paradox.

If $A, A_a,$ and $A_h$ actually "make sense" - more on this below - then we clearly have that $A_a$ and $A_h$ partition $A$: $A_h$ is defined to be $A\setminus A_a$. So your proposal doesn't work.

The fix is that $A_a$ and $A_h$ are in fact more complicated than they appear. We only have a paradox if the adjective "heterological" is in $A$. But it turns out that this doesn't happen: basically, in order to define heretologicity we need to use a truth predicate for $A$ and we don't have one of those in $A$ itself.

Here's one way to see the paradox in action.

Let $\ulcorner\cdot\urcorner$ be your favorite Godel numbering function and let $Form$ be the set of all first-order formulas in the language of arithmetic. For simplicity, let's write "$\mathbb{N}$" for the structure $(\mathbb{N};+,\times,0,1,<)$. Then the set $$X=\{\ulcorner\varphi\urcorner: \mathbb{N}\models\neg\varphi(\underline{\ulcorner\varphi\urcorner})\},$$ the version of $A_h$ for first-order formulas of arithmetic, cannot itself be definable by a first-order formula of arithmetic: if $X$ were defined by some formula $\theta$ of first-order arithmetic, that is if we had $$X=\{n: \mathbb{N}\models\theta(\underline{n})\}$$ for some formula $\theta$ of first-order arithmetic, we would get a contradiction by considering whether $\mathbb{N}\models\theta(\ulcorner\theta\urcorner)$.

More generally, we can generalize the particular setting above to any setting where we have some logic $\mathcal{L}$, some structure $\mathfrak{A}$, and some appropriate "coding" mechanism of $\mathcal{L}$-formulas into $\mathfrak{A}$. Getting the details right takes some thought, but the point is that Grelling's paradox illustrates a fundamental "stepping-up" phenomenon that we can't avoid: the Grelling set for a particular logic/structure/coding system is not definable in that structure by a formula of that logic.

(Note that $X$ can indeed be defined in broader contexts: for example, it's definable in $\mathbb{N}$ by a formula of second-order logic, and it's definable by a first-order formula in the universe of sets, of which $\mathbb{N}$ forms a very small piece.)

Tags:

Logic

Elementary Set Theory

Related

$0 \leq u - \ln(1+u) \leq u^2$ for $\mid u\mid < \frac{1}{2}$ Why doesn't the fact we can force the continuum hypothesis outright prove the continuum hypothesis? Olympiads Number Theory Problem: Show that there are no positive $a,b,c\in\Bbb Z$ such that $\frac{a^2+b^2+c^2}{3(ab+bc+ca)}\in\Bbb Z$ Is there a bijective function $f:[0,1] \to [0,1]$ such that the graph of $f$ in $\mathbb{R}^2$ is a dense subset of $[0,1] \times [0,1]$? Degree of a field extension by a transcendental element If two graphs are isomorphic then will their determinants be equal? Prove that $_4F_3\left(\frac13,\frac13,\frac23,\frac23;1,\frac43,\frac43;1\right)=\frac{\Gamma \left(\frac13\right)^6}{36 \pi ^2}$ Show that if $a,b \in \mathbb{R}^n$, then $|||a|| - ||b||| \leqslant ||a+b||$ Verification of a solution to a mathematical logic problem To show the center of homothety of the biggest and smallest circle lies in the common tangent over T How to calculate $\int _{-\infty }^{\infty }\frac{x\sin \left(x\right)}{1+x^4}\,dx$ How were amplitudes of the $\cos$ and $\sin$ chosen?

Recent Posts