Paradoxes

The importance of formalism

Recall the unrestricted comprehension principle in set theory: for every property, there is a set whose elements are exactly all objects satisfying that property.

Russel's paradox

Consider the property of not being an element of oneself, which is expressed by the formula \(x \notin x\). By the unrestricted comprehension principle, we can definitely consider the set \(A = \{x \colon x \notin x\}\). Then \(A \in A\) if and only if \(A \notin A\), which entails a contradiction in classical logic.

What is going on? A naive notion of set leads to inconsistencies. This is why, in axiomatic set theory, there is a crucial distinction between aggregates and sets:

  • An aggregate is any collection of objects. Aggregates can only appear on the right of the membership symbol \(\in\).
  • A set is an aggregate which is itself an object. Sets can appear on the left or on the right of the symbol \(\in\).

More formally, what we call a set is an element of a model of a first-order set theory like \(\mathit{ZF}\). What is called \(A\) in the previous argument is an aggregate, but not a set. Hence, the expressions \(A \in A\) and \(A \notin A\) are improper.

Russel's paradox compels us to correct the previous formulation of the comprehension principle as follows: for every property, there exists an aggregate whose elements are exactly all objects satisfying that property.

Berry's paradox

Let \(\mathbb{N}\) be the set of non negative integers and consider the property of being a non negative integer definable by a sentence in English of maximum \(200\) characters. By the comprehension principle, we can consider the set \(a\) whose elements are all non negative integers satisfying that property. Since the English alphabet contains \(27\) characters (we also include among its symbols the blank space), there are at most \(27^{200}\) sentences in English of maximum \(200\) characters. Each of these sentences defines at most one integer. Therefore, the complement of \(a\) in \(\mathbb{N}\) is a non-empty set. Recall the well-ordering principle: every non-empty set of \(\mathbb{N}\) contains a least element. By this principle, the least element \(n_0\) of \(\mathbb{N} \hspace{-0.5mm} \setminus \hspace{-0.5mm} a\) exists. Since \(n_0 \notin a\), by definition of \(a\) there is no sentence in English of maximum \(200\) characters which defines \(n_0\). But this contradicts the fact that \(n_0\) is definable by the sentence "the least element non definable by a sentence in English of maximum \(200\) characters", that is a sentence in English containing less than \(200\) characters.

What is going on? The use of an informal language leads to inconsistencies. What is exactly the meaning of the word "definable" in the previous argument? To resolve this paradox, the use of natural language is restricted: only properties which are expressible in a formal language are accepted.

Berry's paradox compels us to correct the previous formulation of the comprehension principle as follows: for every property expressible by a formula of some formal language, there exists an aggregate whose elements are exactly all objects satisfying that property.

A proof-theoretic characterization

Some authors argue that paradoxical expressions are peculiar in that:

  • Their introduction and elimination rules display the kind of harmony characteristic of the logical connectives.
  • But the natural deduction systems containing them fail to normalize.
Man falling from Penrose stairs

If you are interested, you can take a look at some slides prepared in collaboration with Luis Sánchez Polo for the Summer School "Proofs, arguments and dialogues: history, epistemology and logic of justification practices" organized by the Tübingen University from 8 to 12 August 2022. In that occasion, we shortly presented the idea of paradox as non-normalizability and the main objections raised against it.