Talk:Set Theory
From Wikipedia, the free encyclopedia
This is an archive. Current talk should be at Talk:Set theory or Talk:Axiomatic set theory.
Discussion moved from main page. Any further comments should be added at the end.
One other point about the AxiomOfChoice is that whenever you implicitly assume that the cardinality (i.e. size) of a set exists, you are using AxiomOfChoice in order to do this. Since all constructible sets have distinct cardinalities, you get unconstructible sets either way.
COMMENT: This is not at all true - cardinality can be defined without using AC. The statement about "all constructible sets" having distinct cardinalities makes no obvious sense. What is meant here by a "constructible set"?
The usual way of defining cardinals is by taking a representative ordinal of each size, which you can't do without the axiom of choice. The only other way I've ever seen done is by taking equivalence classes of sets, but these don't end up being ZF sets - i.e. you have to use objects outside the system being considered.
COMMENT: The axiom of choice is not needed to define cardinals in ZF - the equivalence classes can be taken to be sets, by defining the cardinal of x as the set of all sets of minimal rank equivalent to x. We are also perfectly free to simply introduce a special function symbol for cardinals, governed by the axiom card(x)=card(y) <-> x and y are equivalent. (Suppes does it this way.) Associating the axiom of choice with there mere possibility of talking about cardinals is quite unjustified.
RESPONSE: What makes you think these equivalence classes actually exist within the framework of ZF? I think the following proves they don't. Take the equivalence class C containing {{}} and apply the axiom of unions to get a set U. Then for any set X, {X} is in C and so X is a member of U. In other words, U is a set of all sets which is well-known to be impossible within ZF.
Except for the fact that you have ignored the phrase "of minimal rank". Not all singleton sets {X} are sets of minimal rank equivalent to {{}}. (Let's see how horribly messy we can make this page...)
Oops, you're right. I figured I'd probably do something wrong. But in any case, can you guarantee that such equivalence classes exist within ZF? I remember something about it being difficult, even if the above is wrong. (Btw, this page will need some extensive reworking anyways).
RESPONSE: It's trivial to prove the existence of cardinals as equivalence classes in the indicated way in ZF.
RESPONSE II: Ok, would you mind providing a reference is to how? Not that I don't believe you, but it would be nice to have the details...
See e.g. the chapter on set theory in Mendelson, Introduction to Mathematical Logic, for a definition of the cumulative hierarchy of sets: R(0)=the empty set, R(alpha+1)=the power set of R(alpha), R(lambda)=union of R(alpha) for alpha<lambda, for limit lambda. The axiom of regularity is equivalent to the statement that for every set x there is an alpha such that x is in R(alpha).The cardinal of x can be defined as the set of sets in R(alpha) that are equivalent to x, where alpha is the smallest beta such that R(beta) contains a set equivalent to x.
That's not to say the cardinals don't exist, just that they can't be constructed in ZF, unless you use an alternate technique. The standard alternate technique is to choose some representative from each equivalence class, typically the ordinals. But I don't think its easy to do this if the ordinals don't hit every set, which they can't if trichotomy of cardinals doesn't hold. --JG
COMMENT: The cardinals (constructed using AC) are linearly ordered (in fact well ordered for obvious reasons). Under the above sort of definition, one loses the ability to say `either |X| <= |Y| or else |X| >= |Y|' where <= and >= denote the usual cardinal inequalities. This doesn't help its cause as an `intuitive' measure of `infinity size'.
COMMENT: One does not "lose the ability to say" this. What is true is that it cannot be proved without AC that any two cardinals are comparable. This is not to say that the cardinals cannot be defined without AC.
A set X has been constructed if there is a 'way' of determining whether any given element is in it. I'm being deliberately vague, but I think you can see the idea. ZF+AC asserts the real numbers have a basis as a vector space over the rationals, but you are never going to be able to demonstrate an example of some such set. ZF-AC asserts that there is a set which can't be put into one-to-one correspondence with any ordinal, and if I am not mistaken you can't find me one of those either (though I'm not entirely sure, since you're not allowed to use AC to set up the correspondence).
COMMENT: This is not only vague, but it is not a recognizable informal version of anything formally defined in set theory. In particular, it is completely obscure what you mean by saying that all constructible sets have distinct cardinalities.
RESPONSE: I should have been a little more specific. I meant distinct cardinality in the narrow sense, where it is being defined in terms of ordinals. My point was that, though every infinte set you will ever build can be put into 1-to-1 correspondence with the natural numbers or something built by power-setting them, there must be other sets if the generalized continuum hypothesis is false, and ZF-AC asserts that it is. However, I'm not entirely sure that the 1-to-1 correspondences can be constructed without AC, so this might be a mistake on my part. I would love any info on that.
COMMENT: I don't understand what you have in mind in saying that "ZF-AC asserts that it is" - the generalized continuum hypothesis is not implied by ZF-AC. Further, what does "the 1-to-1 correspondences" refer to?
RESPONSE: The generalized continuum hypothesis isn't, but its negation is. Simple contrapostitive of GCH -> AC. The 1-to-1 correspondences are just those, namely, the things we have to set up to prove that a given set has the same cardinality as another given set. In ZF+AC, GCH is undecidable, so everything constructed must satisfy GCH (else it would be false) and so be of the same cardinality as some power set of N, ie have some 1-to-1 correspondence between them. But potentially this 1-to-1 correspondence need not be constructable either, and exist because of AC - this last point I am not sure about.
COMMENT: Yes, if by ZF-AC you mean ZF plus the negation of AC, it is inconsistent with GCH. Your statement that everything constructed in ZF+AC must satisfy GCH has no obvious meaning. Your implication (if I understand you correctly) that if GCH holds every set must be "of the same cardinality of some power set of N" is unclear. What do you mean by "a power set of N"?
Response: I mean the things that GCH usually asserts are the only cardinals...I'm sorry for the bad terminology but I couldn't think of any better way to put it.
COMMENT: I will assume then that by saying that a cardinal satisfies GCH you mean that it is not a counterexample to GCH, i.e. it is not a cardinal k or 2^k such that 2^k is greater than the successor of k. However, that "everything constructed in ZF+AC must satisfy GCH" has no obvious interpretation on which it is correct. For example, is the power set of the set of natural numbers "constructed in ZF+AC"? If so, what does it mean that it satisfies GCH?
