Russel's paradox is defining "the set of all sets that don't contain themselves". You can show that such construct leads to a contradiction. Read the wiki link for details. I started this article as answer to this article.
There is another interesting paradox discussed by Bertrand Russell: "The smallest positive integer not definable in under sixty letters", actually better known as Berry's paradox You can also prove that such number creates a contradiction, because you just defined it under sixty letters.
For me, the above paradox shows that it is not enough to create a condition for something to exist with that condition - or a set of such elements. Such paradoxes argue that such objects defined by a predicate cannot exist sometimes.
The same is for "the set of sets that do not contain themselves". Let's take it the other way around. Could you imagine a set that _contains_ itself? You take a set, you make it an element of itself, then you get a bigger set that needs to be included in the set.
Intuition: Such set that contains itself as element is like a dragon that managed to swallow itself. This cannot end. You can't even define an algorithm for this set to grow, because it must grows from... everywhere - because each element is also recursively element of itself.
You can define such set that don't contain itself only by complementing another set. However, you cannot always enumerate the elements of the complement of a simple set (even infinite) that you can enumerate.
For me, if you cannot imagine how to construct such set iteratively, it does not exist for all practical concerns. The same with the "set of all sets", even without excluding such elusive objects that "contains themselves as elements". You cannot iterate such set, so it does not exist for me.
The Berry paradox is a way more legitimate construct. You can imagine numbers that can be described by a number of letters. You can imagine that there should be a minimum description length of such number. Just that... Kolmogorov complexity proves that such minimum description is not always computable. You would be able to compute that minimum description length if the halting problem would be decidable, but it is not in general.
Comments