Self-referential paradoxes #

I’d like to present paradoxes in different forms - or, mejor dicho, use different “languages” to represent them.

The options are:

Casual/informal/verbal - pretty meaningless but the most popular. Essentially, this is the goal of the website: use formal methods for foggy utterances, and see what we can get. There is no guarantee that the translation would be faithful, but, otherwise, there is not much to discuss either :))
Logic (first-order logic or modal logic)
ST: Set Theory language.
Comp: Theory of Computation language. Or just code in some programming language (e.g. Python)

Russel’s paradox & Diagonalization. #

Casual: Barber paradox

The barber is the “one who shaves all those, and those only, who do not shave themselves”. The question is, does the barber shave himself?

This form doesn’t belong to Betrand Russell, but was suggested to Russell as an alternative form of Russell’s paradox.
ST:

Assuming that U is the universal set, we can construct a set Y, s.t.: @@ Y := \{ A \in U: A \not \in A\} @@

But, then @@ Y \in Y \equiv Y \not\in Y @@ - contradiction.
Logic:

Barber: $$ \exists x \forall y: person(x) \wedge person(y) \wedge shaves(x,y) \equiv \neg shaves(y,y) $$

Russell: $$ \exists x \forall y: y \in x \equiv y \not\in y $$

After substituting x for y, we get @@ x \in x \equiv x \not\in x @@ or, in case of Barber paradox, @@ shaves(x,x) \equiv \neg shaves(x,x) @@ - contradiction.
Comp:

Quoting from Why can’t Russell’s Paradox be solved with references to sets instead of containment?

“The important thing is we can certainly implement the universal set [here a set is just a predicate that returns true or false as the response to the question whether the parameter X is its element ]:


     bool Universe(Object X) { return true; }

and we can implement what ostensibly should be the set of all things which do not contain themselves:


     bool Russell(Object X) { return !X(X); }

So what’s wrong with this set Russell? Well, if you plug Russell into itself [ Russel(Russell) ], then it will call itself, creating an infinite recursive loop.

Therefore, Russell fails to return anything when plugged into itself as a parameter, so it cannot be a set.”

See also A programmer’s take on Russell’s Paradox and the refs to Dijkstra there:

E.W.Dijkstra. Where is Russell’s paradox?
E.W.Dijkstra. For brevity’s sake

“Set” of all sets, “Set” of all Truths & Omniscience #

The set of all sets (universal set) does not exist, because otherwise we would be able to construct the set Y above (Russell’s paradox, ST) using Axiom schema of specification

Similarly, there does not exist the {Z} which contains all other sets (except Z), because the set {X := Z \cup \{Z\}} would the set of all sets.

Alternatively: In order to prove that universal set does not exist we can use Cantor’s Diagonal Argument. Namely, {2^U}, where U is the universal set, would be strictly greater than U, but it’s not possible since U is universal.

Generalization: by Francis William Lawvere - cf. Lawvere’s Fixed-point Theorem below.

Also, Andrej Bauer. On a proof of Cantor’s theorem

Omniscience #

By the same reason (we can match a truth with any subset of truths), the set of all truths does not exist. Since there is not such set (and classes exist in name only) God cannot be omniscient.

This argument was maintained by Patrick Grim, but other people don’t find it very convincing.

See Alvin Plantinga and Patrick Grim, “Truth, Omniscience, and Cantorian Arguments: An Exchange,” Philosophical Studies 71 (1993), doi:10.1007/BF00989730. As for Grim’s Cantorian argument, its underlying set theoretical mechanism is presented in Grim, “There Is No Set of All Truths,” Analysis 44 (1984), doi:10.1093/analys/44.4.206.

Patrick Grim. Problems with Omniscience

E.g. Martin Lembke. Grim, Omniscience, and Cantor’s Theorem

See, also Absolute_infinite.

Burali-Forti paradox #

See, also Absolute_infinite.

Grelling’s #

Turing’s Halting Problem, Turing with Oracle, Turing degree #

Goedel’s Theorems #

Tarski (Liar) #

Loeb #

Richard’s #

Yablo #

Possibly:

Jokes collected by Gardner;
Analysis by Smullian;
Hofstadter: self-referential sentences
Quines,
Programmatical quines

and more.

Some references:

John Buridan on Self-Reference: Chapter Eight of Buridan’s ‘Sophismata’, with a Translation, an Introduction, and a Philosophical Commentary.

Liar Paradox

Quine Paradox

Quines

Quines in programming etc.

Brandenburger-Keisler paradox and here and here and comments and more.

Probabilistic:

“…Наконец, уже сознательное применение вероятностный подход может находить для разрешения старинных логических парадоксов, например парадокса лжеца. Этот парадокс связан с утверждением, что сам я лжец, а это противоречит истинности утверждаемого. Но парадокс просто снимается, если отказаться от радикализма однозначности в утверждении «я лгу». Лжецом можно назвать человека, у которого правдивые высказывания встречаются с малой степенью вероятности, и сейчас он говорит правду,хотя обычно лжет. Так высказывание приобретает смысл, хотя В.В. Налимов считает, что любая попытка понимания этой фразы, состоящей всего из двух слов и лишенной конкретизации, все равно неэффективна.”

Золотухина-Аболина Е. В Налимов.

Lawvere’s General Approach #

In 1969 Francis William Lawvere suggested a categorical scheme that encompasses virtually all kinds of diagonal arguments and also covers some fixed point results:

Lawvere’s Fixed-point Theorem

Some important corollaries of this are:

Cantor’s theorem
Cantor’s diagonal argument
Diagonal lemma
Russell’s paradox
Gödel’s first incompleteness theorem
Tarski’s undefinability theorem
Turing’s proof
Löb’s paradox
Roger’s fixed-point theorem
Rice’s theorem

Lawvere’s original article, 1969 Lawvere, Francis William (1969). “Diagonal arguments and Cartesian closed categories”. Category Theory, Homology Theory and their Applications II (Lecture Notes in Mathematics, vol 92). Berlin: Springer.

Lawvere’s article with commentaries

Soto-Andrade, Jorge; J. Varela, Francisco (1984). “Self-Reference and Fixed Points: A Discussion and an Extension of Lawvere’s Theorem”

A super-easy take on Lawvere’s in Andrej Bauer. On a proof of Cantor’s theorem

Easy explanation of Lawvere’s approach - “What A General Diagonal Argument Looks Like (Category Theory)”

In 2003, Noson S. Yanofsky popularized Lawvere’s ideas (which very few people noticed by that time) in his article: A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points

“Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the same simple scheme. We demonstrate these similarities by showing how this simple scheme encompasses the semantic paradoxes, and how they arise as diagonal arguments and fixed point theorems in logic, computability theory, complexity theory and formal language theory.”

Yanosfsky’s explanation was non-categorical (for pedagogical reasons).

“Noson S. Yanofsky - Diagonalization, Fixed Points, and Self-reference (Gödel Conference)” on YouTube:

And beyond:

Some Applications of Lawvere’s Fixpoint Theorem

“For example, this paper will use it to construct uncomputable real number, unnameable real number, partial recursive but not potentially recursive function, Berry paradox, and fast growing Busy Beaver function. Many interesting lambda fixpoint combinators can also be fitted into this schema. Both Curry’s Y combinator and Turing’s Θ combinator follow from Lawvere’s theorem, as well as their call-by-value versions. At last, it can be shown that the lambda calculus version of the fixpoint lemma also fits Lawvere’s schema.”

From Lawvere to Brandenburger-Keisler: interactive forms of diagonalization and self-reference

Prisoner’s Dilemma: #

Lawvere’s ideas may have corollaries for Prisoner’s Dilemma (worth of reviewing, I think):