Grelling-Nelson Paradox

This article needs to be tidied. In particular: Rewrite into $\mathsf{Pr} \infty \mathsf{fWiki}$ style Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Tidy}} from the code.

Paradox

Define an adjective to be autological if it is true when applied to itself.

For instance, the word "English" is autological, as it is a word in English.

The word "multisyllabic" is also autological, as it contains multiple syllables.

Define an adjective to be heterological if it is not true when applied to itself.

For instance, the word "long" is heterological, as it is not a long word.

The word "monosyllabic" is also heterological, as it does not contain only one syllable.

All adjectives must either be autological or heterological, as they either apply to themselves or they don't.

"Autological" and "heterological" are thus each defined as the negation of the other.

The Grelling-Nelson paradox arises when trying to apply one of these adjectives to the word "heterological".

If "heterological" is autological, then it does apply to itself.

But then by the definition of "heterological", it does not apply to itself, making it heterological.

If "heterological" is heterological, then it does not apply to itself.

But then by the definition of "heterological," it is not the case that "heterological" does not apply to itself, and so it does apply to itself, making it autological.

We thus have:

heterological is autological $\iff$ heterological is heterological

for the contradictory predicates "heterological" and "autological".

This paradox is closely related to Russell's Paradox: Corollary:

$\not \exists x: \forall y: \paren {\map \RR {x, y} \iff \neg \map \RR {y, y} }$

Define $x$ to be the predicate "heterological," and define the relation $\map \RR {x, y}$ to mean "the predicate $x$ applies to $y$".

The sentence:

$\map \RR {x, y} \iff \neg \map \RR {y, y}$

is thus interpreted:

$y$ is heterological if and only if $y$ does not apply to itself.

The assertion that the predicate "heterological" exists and is defined as such for all $y$ is then equivalent to:

$\forall y: \paren {\map \RR {x, y} \iff \neg \map \RR {y, y} }$

This leads to the same contradiction as Russell's Paradox: Corollary - when we instantiate $y$ as $x$, we obtain:

$\map \RR {x, x} \iff \neg \map \RR {x, x}$

Also known as

The Grelling-Nelson paradox is also known as:

Grelling's paradox

Weyl's paradox, as it is sometimes mistakenly attributed to Hermann Klaus Hugo Weyl.

Source of Name

This entry was named for Kurt Grelling and Leonard Nelson.

Sources

• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Grelling-Nelson paradox