lew (02/07/83)
First, let me apologize for my horrible mangling of the Continuum Hypothesis in a recent posting. Partly as a result of this, I sought to gain an elementary understanding of Axiomatic Set Theory. I am stuck on the "Axiom of Comprehension", and in particular, its relation to Russell's Paradox. Using "A" for "for all", "E" for "there exists", "<" for "is an element of", "^" for "and", and "<->" for "if and only if", Kunen states this axiom in "Set Theory, an Introduction to Independence Proofs" as the universal closure of: Ey Ax (x < y <-> x < z ^ phi) where phi is a formula NOT INVOLVING y. (Emphasis mine) Kunen then proceeds to use Russell's paradox to prove the nonexistence of the universal set. He first lets phi = x ~< x and then resorts to english description. I can't complete the proof without using y in phi. To complete my confusion, Monk in "Intro. to Set Theory" uses this axiom to prove the non-existence of "the set of all non-self-members" and then uses the same axiom to define the universal set! Monk uses "x is a set" in place of "x < z" in the axiom. Who out there comprehends Comprehension? As a footnote, Kunen uses an undefined notation in the "Replacement Scheme" axiom. He doesn't define "!" anywhere, but states the axiom: A (x < B) E !y phi(x,y) -> E Y A (x < B) E (y < Y) phi(x,y) Can anybody explain this? Lew Mammel, Jr. ihuxr!lew
arens@UCBKIM (02/07/83)
From: arens@UCBKIM (Yigal Arens)
Received: from UCBKIM.BERKELEY.ARPA by UCBVAX.BERKELEY.ARPA (3.300 [1/17/83])
id AA04646; 7 Feb 83 15:13:26 PST (Mon)
To: net-math@ucbvax, harpo!ihnp4!ihuxr!lew@decvax.UUCP
In-Reply-To: Your message of 7 Feb 1983 1413-PST (Monday)
What the comprehension axiom says is that every subcollection of elements of
a set defined as those elements of the set that satisfy some formula -- is
also a set. In the formulation you gave,
Ey Ax (x < y <-> x < z ^ phi) where phi is a formula NOT INVOLVING y.
z is the original set, phi is the defining formula, and y is the new set
this axiom claims exists.
This can be used to prove the non-existence of a universal set in the
following way (using Russel's paradox).
We prove by assuming a universal set ("the set of all sets") exists, and
proving a contradiction.
Let's assume the set of all sets exists and call it U. We'll now use the
axiom of comprehension with phi = x ~< x (i.e. "x doesn't belong to x"),
and z = U.
The axiom in this particular case will read:
Ey Ax (x < y <-> x < U ^ x ~< x)
(i.e. there exists a set such that it is made up exactly of all sets in U
which do not contain themselves). Let's call this set that the axiom tells
us exists, P.
So, Ax (x < P <-> x < U ^ x ~< x). This is a universal statement, stated
for ALL x, and so must be true for P too. In that particular case it will
say,
P < P <-> P < U ^ P ~< P.
A contradiction can be gotten easily from this, since trivially P < U.
Therefore U doesn't exist.
This should take care of what Kunen is doing. It isn't clear to me from
your description what Monk is trying to do in his book.
The notation E!x is read as "there exists a unique x".
Yigal Arens
UC Berkeleyleichter (02/08/83)
The Axiom of Comprehension - a terrible name, that - lets you build arbitrary subsets of sets you already have. The axiom as you wrote it is also qualified by (A z A phi). Suppose there was a univeral set. Let z be this set, and let phi(x) = ~x<x. The axiom then says we have a "Russell's paradox" set. But the existance of such a set is a contradiction - i.e., if such a thing existed, we would have a set S such that the statement S<S ^ ~S<S was true. But we can prove from our other axioms that no statement of the form P ^ ~P is true. Hence, the result is false. This does not, as in naive set theory, imply a contradiction - we ASSUMED the existence of a universal set, but did not prove it. Hence, what we just got was a simple proof by contradiction - assuming a universal set lets us prove a falsehood; hence, no such set exists. (Unless, of course, the set theory involved is inconsistent - but then EVERYTHING is true anyway.) I don't see why you need to use y in phi(). Once you have used the axiom to show that the set S exists, you can operate on it any way you like. You asked about the "other form" of the Axiom of Comprehension, with "x is a set" in place of "E z with x < z". These statements are from different forms of set theory (although they come out pretty much the same in this case). The "x < z" form is from Zermelo-Frankel set theory. This is in some ways the most natural, but is almost the most restrictive about the kind of objects you can talk about. The "x is a set" form comes from Hilbert-Von Neuman-Bernays (I think) set theory. In this theory, there are "sets" and "classes". "Classes" are sort of like big sets; there is a class of all sets, but no set of all sets. You don't get the obvious paradoxes because most of axioms you need to build them - like comprehension - apply to sets, but not to classes. If I remember right, in this theory x is a set iff there is a set y with x < y; hence, the condition in the axiom of comprehension is exactly the same. (Exactly as in the case of Zermelo-Frankel, you need to have some things that you KNOW are sets to be able to build more of them. Both, as I recall, allow you to build finite sets easily, and have a specific "Axiom of Infinity" that says that at least on "large" (infinite) set exists; it turns out this is enough.) There is actually a third form of set theory, due to Quine. It is rarely used because of some unnatural properties; for example, in Quine's set theory, "atomic" objects x always have the property that x < x. Working mathematicians tend to use H-VN-B when they think about it at all. I don't know whether there is any difference between the properties of sets in H-VN-B and the properties of sets (the only things there are) in ZF; this may not even be know. Finally, as to "!" - the construct E! is usually taken to mean "there exists uniquely"; i.e. Ay E!x such that x = -y. -- Jerry decvax!yale-comix!leichter