I’m told that if you start with x [symbol]Î[/symbol] y and y [symbol]Î[/symbol] x, you can derive a Russell-like paradox. I haven’t been able to figure out how, though. Does anyone know?
John L. Kelley, in the appendix to his General Topology derives the contradiction by appealing to the axiom of regularity ( if x is a non-empty set, then x has an element y disjoint from x), but this seems rather more technical than Russell’s paradox.
I’m not sure I see how that follows. Assume x = {y} and y = {x}. Then the conditions are met, and y is disjoint from x.
For the sake of those of us with standards-compliant browsers, the symbol in question is the “is an element of” symbol, or ∈. I’m not as familiar with set theory as you might think; can you give an example of a Russel-type paradox?
Russell’s paradox is as follows:
Let x be the set of all sets which do not contain themselves. If x contains itself, then x does not contain itself. Similarly, if x does not contain itself, then x contains itself. So x can’t exist.
Let z = {x,y}. By the axiom of regularity, z has an element disjoint from itself and plainly this element is either x or y. But x is not disjoint from z since y is an element of both and similarly y is not disjoint from z, as x is an element of both. Contradiction.
OK. That works. However, I’m pretty sure the book that I found this exercise in didn’t cover the axiom of regularity. I’ll check, though.
What axioms has the book covered? What is the subject-matter of the chapter in which the exercise appears?
Oooooooh… Neato. Sorry to hijack, but what’s the resolution to Russel’s Paradox? Or is it over my head?
It’s Ken Rosen’s Discrete Mathematics and its Applications. Very likely, he forgot that he hadn’t covered that particular axiom.
Russell. I’ll get it right. Sorry.
The resolution is to disallow some collections of objects from being sets. There are several different ways to do that; the most popular is Zermelo-Frankel set theory.
Russell’s paradox implies that not all properties define sets ( roughly speaking, some things are too big to be sets), so you have to place some sort of restriction on what are allowed to be sets.
A favourite approach of mine is Kelley-Morse Set Theory. Here we take “class” as a primitive notion and define a set to be a class which is a member of another class. We further stipulate
u is an element of {x:…x…} if and only if u is a set and …u… ( Here the ellipsis indicates some condition on x). Now Russell’s paradox disappears. Define A = {x: x is not a member of x}. Then, in particular, A is an element of A if and only if A is a set and A is not an element of A. The upshot is that A is not a set ( it is a “proper class”).
Okay. So do Zermelo-Frankel and Kelley-Morse set theory resolve the paradox in the OP as well?
If they both include the axiom of regularity. I hear it’s kinda controversial, though.
But Jabba, can’t you then construct a similar paradox using “class” rather than “set”? I can re-define “set” to mean “banana” if I want, but that doesn’t really address the original paradox.
Aha, I see ultrafilter. From what I can tell of the Axiom of Regularity, it basically says there exist no sets x, y, such that x contains y and y contains x. Am I right about this? I guess that’s a pretty good way to resolve a paradox; assume it’s irrelevant.
Michael D. Potter, in Sets: An Introduction takes a different approach, based on the work of Dana Scott. Here, sets are built up stage by stage. Roughly, you start on day 0 with the individuals. The elements of each subsequent day are the individuals together with the elements and subcollections of the previous day. This avoids both paradoxes. For example, the situation in the OP is impossible because if x is a member of y then x must have formed on an earlier day than y and then y is not a member of x.
Chronos: I’m not sure I understand your point fully but it seems to rely on a Platonist view that we are trying to describe how sets “really” behave. However, this is not the case. The point of axiomatic set thory is that we are trying to retain as many of the results of naive set theory as possible while eliminating the obvious paradoxes. The three most common theories ( Zermelo-Fraenkel, von Neumann-Bernays-Goedel and Kelley-Morse) do this in different ways and it doesn’t matter ( from that point of view) which one you adopt.
Sorry, forgot this bit. No, you can’t. In KM, if x,y are classes with x a member of y and y a member of x then ( by definition of set) both x and y are sets and the proof I gave earlier applies.