johnson@charming.nrtc.northrop.com (Greg Johnson <gjohnson>) (01/23/91)
In `usual' set theory (that which is relied on in standard texts such as Rudin
and Munkres) is it possible to have a set which contains itself as a member?
Or does usual set theory (ZF for instance) preclude such a thing?
Here is an attempt to write a set containing itself:
{ { { ... } } }
The above `set' has a single element, which is equal to the set itself. This
is by way of analogy with the following infinite tree, which is equal to some
of its (proper) subtrees:
o
/|\
/ | \
( o )
/|\
/ | \
( o )
/|\
/ | \
( o )
.
.
.
Another question, a variant of the above: Is it possible to have a set
F of functions whose domain and range are F? As a small example, F might
contain two functions f1 and f2, where f1 is the identity and f2 is a constant
function. (Notice that F is not its own function space, which would be
impossible; F is a subset of its function space.)
Thinking of a function as a set of ordered pairs and using the usual trick to
encode ordered pairs as sets ( <1,2> = { {1}, {1,2} }, <3,3> = { {3} } ),
this `set' would correspond to the following infinite tree, where `f1' and
`f2' are copies of the left and right subtrees of the root:
o
/ \
/ \
/ \
o o
/ \ / \
/ \ o o
o o / \ \
| | / \ \
o o o o o
| | | / \ \
f1 f2 f1 f1 f2 f2
The function f1 is (as a set) { <f1,f1>, <f2,f2> }
The function f2 is { <f1,f2>, <f2,f2> }
Thanks for any answers -
Greg Johnson
p.s. - Please send responses to me, since I don't always read these groups.mjd@saul.cis.upenn.edu (Mr. Prolific) (01/23/91)
In article <16470@gremlin.nrtc.northrop.com> johnson@charming.nrtc.northrop.com (Greg Johnson <gjohnson>) writes: > In `usual' set theory (that which is relied on in > standard texts such as Rudin and Munkres) is it possible > to have a set which contains itself as a member? Or > does usual set theory (ZF for instance) preclude such a > thing? Although you're perfectly free to develop any theory of sets you like, the usual ones don't have any such sets. We might restrict our models with an axiom like this one: Foo: For any non-null set X, there is a member Y in X, such that X and Y are disjoint. From this, we can show that there is no set which is an element of itself, at least in the usual models. Here's the proof, which is simpler than it looks, because I wrote it out in hideous detail: 1. Suppose there were such a set, say Z, with Z an element of Z. 2. Then by another theorem we would like to have shown from other axioms, {Z} is a set. 3. `Foo' says that there is an element Y in {Z}, such that Y is disjoint from {Z}. 4. The only element of {Z} is Z, so the Y of step 3 must be equal to Z. 5. Since Y is disjoint from {Z} (Step 3.) and Y=Z (Step 4.) then Z is disjoint from {Z}. 6. Since Z is an element of Z (Step 1.) and of {Z} (Definition of `{Z}' in any reasonable theory), Z and {Z} are not disjoint. 7. Steps 5 and 6 contradict each other, so the supposition of step 1 is false and no set is an element of itself. So in `the usual theory' there are no sets that are elements of themselves. (Step 2 follows from the fact that I'm only talking about `the usual theory'; any reasonable and usual theory of sets will have as a theorem that {X} is a set when X is. For more details, see the appendix of John Kelley, _General Topology_.) The `foo' axiom above turns out to be pretty strong; once you have the induction axiom in place, you can use `foo' to prove no only that no set is an element of itself, but also that 1) There's no collection of sets {X1, X2, X3 ... Xn} with X1 an element of X2, X2 an element of X3, ... , and Xn an element of X1. 2) There's no sequence of sets {X1, X2, X3 ...} with X1 an element of X2, X2 an element of X3, ... In particular, (1) precludes having a `set' of functions like the one you describe. A pretty good reference for this stuff is the appendix to John Kelley's _General Topology_; that's where I cribbed most of this posting from. > Here is an attempt to write a set containing itself: > { { { ... } } } > The above `set' has a single element, which is equal to the set itself. Like I said, you can make up whatever you like, but it seems to me that confusing inkmarks on paper with sets is only going to get you confused in the long run. Ink marks on paper are not sets and you can't reason about them. An axiomatic system is supposed to describe in operational terms exactly what you can and can't do with a set, and what things are sets and what aren't. That is why we use axiomatic systems instead of waving our hands over little squiggles like `{'. You could of course make up axioms for little squiggles and show that there is a natural isomorphism between squiggles and sets, but if you were going to do all that work anyway then why did you need the squiggles in the first place? > Thanks for any answers - > Greg Johnson Sure 'nuff. > p.s. - Please send responses to me, since I don't always read these groups. Tough luck! -- Behold the riant anthropoid, beware its crooked thumbs! Mark-Jason Dominus mjd@central.cis.upenn.edu