Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Yes the type theoretic analog to Russel's (set theoretic) paradox is Girard's (as mentioned in the abstract) paradox.


This is incorrect. The set paradox it’s analogous to is the inability to make the set of all ordinals. Russel’s paradox is the inability to make the set of all sets.


Since we're being pedantic, Russel's paradox involves the set of all sets that don't contain themselves.


Technically speaking, because it's not a set, we should say it involves the collection of all sets that don't contain themselves. But then, who's asking...


The paradox is about the set of all sets that do not contain themselves, or a theorem that such a set does not exist.

In the context of the paradox you need to call it a set, otherwise it would not be a paradox


I'm asking. What prevents that collection from being a set?


This is the easiest of the paradoxes mentioned in this thread to explain. I want to emphasize that this proof uses the technique of "Assume P, derive contradiction, therefore not P". This kind of proof relies on knowing what the running assumptions are at the time that the contradiction is derived, so I'm going to try to make that explicit.

Here's our first assumption: suppose that there's a set X with the property that for any set Y, Y is a member of X if and only if Y doesn't contain itself as a member. In other words, suppose that the collection of sets that don't contain themselves is a set and call it X.

Here's another assumption: Suppose X contains itself. Then by the premise, X doesn't contain itself, which is contradictory. Since the innermost assumption is that X contains itself, this proves that X doesn't contain itself (under the other assumption).

But if X doesn't contain itself, then by the premise again, X is in X, which is again contradictory. Now the only remaining assumption is that X exists, and so this proves that there cannot be a set with the stated property. In other words, the collection of all sets that don't contain themselves is not a set.


Let R = {X \notin X}, i.e. all sets that do not contain themselves. Now is R \in R? Well this is the case if and only if R \notin R. But this clearly cannot be.

Like the barber that shaves all men not shaving themselves.


They redefined sets specifically to exclude that construction and related ones.


The paradox. If you create a set theory in which that set exists, you get a paradox and a contradiction. So the usual "fix" is to disallow that from being a set (because it is "too big"), and then you can form a theory which is consistent as far as we know.


Perhaps I overstated how related the two were. I was pulling mostly from the Lean documentation on Universes [0]

> The formal argument for this is known as Girard's Paradox. It is related to a better-known paradox known as Russell's Paradox, which was used to show that early versions of set theory were inconsistent. In these set theories, a set can be defined by a property.

[0]: https://lean-lang.org/functional_programming_in_lean/Functor...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: