russell's paradox

[cesc]

I understand how the argument goes- let X be the set of all sets which don't contain themselves.
If X contains itself, then X is not in X
If X doesnt contain itself, then X is X


the part i dont understand is, What on earth does it mean for a set to contain itself?

garbage in, garbage out?

[mXSCNT]

It means that the set is an element of itself. For example, an expense list might be viewed as a set of items (the items listed on it). If the expense list itself is listed as an item on the expense list, then that set contains itself.

The resolution is to add a type system which prevents sets from containing themselves, even indirectly.

[cesc]

well the example seems kind of frivolous.
Also, I'm not sure if its quite right. The word "list" has the dual meaning of a set, and a piece of paper which is an expense


Are there any examples involving mathematical objects?

[Hurkyl]

the part i dont understand is, What on earth does it mean for a set to contain itself?
X \in X.


The resolution is to add a type system which prevents sets from containing themselves, even indirectly.
Sets containing themselves don't cause a problem. And even if you want to exclude them, you can just use the axiom of foundation, rather than trying to do something more elaborate.

[cesc]

Could you give a concrete example where X is an element of X

[Unknot]

X = {X}

No problem there.

[adriank]

If you look at the ZF axioms, it's not too hard to see that there is no set that contains itself.

Suppose X is a set, and consider the set {X}. Now (following Wikipedia, anyway), the axiom of regularity says: "Every non-empty set x contains a member y such that x and y are disjoint sets." Well, {X} is a nonempty set, and its only member is X. Thus, {X} and X are disjoint; since X is in {X}, X is not in X.

[CRGreathouse]

If you look at the ZF axioms, it's not too hard to see that there is no set that contains itself.

Suppose X is a set, and consider the set {X}. Now (following Wikipedia, anyway), the axiom of regularity says: "Every non-empty set x contains a member y such that x and y are disjoint sets." Well, {X} is a nonempty set, and its only member is X. Thus, {X} and X are disjoint; since X is in {X}, X is not in X.

The axiom of foundation (regularity) doesn't help avoid Russell's paradox. If the paradox can be constructed in a theory X, then it can be constructed in the theory X + foundation (and leads to contradiction, naturally).

Russell's paradox doesn't occur in ZF because such paradoxical sets cannot be constructed in the first place -- the axiom of specification isn't powerful enough.

[csprof2000]

Here's a more practical example.

class LinkedNode
{
public LinkedNode next;
public String data;
...
}

The class in Java defines a "set" which may contain elements, "objects". Saying object A is an instantiation of class B is basically to say that B = {X | X has the given properties} and A is in B.

Here, LinkedNode contains itself. Even if you take a class definition to be a an ordered n-tuple of its properties rather than a set, you still have

(next, data) = {next, {next, data}} or {{next, data}, data} (definition of ordered n-tuple, I think?)

In the first example, next is in LinkedNode because it's the first element in the list... in the second, because it is in the first set, which is in the outside set.

So, despite it all, you can certainly have things like X = {X} and Z = Z x Y...