A new definition of Cardinality.
in [Logic]
|
From: David Libert on 24 Nov 2009 15:24 Rupert (rupertmccallum(a)yahoo.com) writes: > On Nov 24, 6:15=A0pm, zuhair <zaljo...(a)gmail.com> wrote: >> On Nov 24, 12:55=A0am, Rupert <rupertmccal...(a)yahoo.com> wrote: >> >> >> >> >> >> > On Nov 23, 10:37=A0pm, zuhair <zaljo...(a)gmail.com> wrote: >> >> > > On Nov 22, 9:20=A0pm, Rupert <rupertmccal...(a)yahoo.com> wrote: >> >> > > > On Nov 23, 11:37=A0am, zuhair <zaljo...(a)gmail.com> wrote: >> >> > > > > On Nov 22, 7:16=A0pm, Rupert <rupertmccal...(a)yahoo.com> wrote: >> >> > > > > > On Nov 23, 10:01=A0am, zuhair <zaljo...(a)gmail.com> wrote: [Deletions] >> > > The sketch of the proof goes like that: >> >> > > First we prove that for every set x there exist a set of exactly all >> > > sets that are >> > > hereditarily strictly subnumerous to it,lets denote that later set by >> > > H_(<x) >> >> > > so we have: for every x there exist H_(<x) >> >> > > =A0H_(<x) =3D {y | y strictly subnumerous to x and >> > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 for all z (z e Tc(y) -> z str= > ictly subnumerous to >> > > x)} >> >> > > as a theorem of ZF. >> >> > Well, 'tis surely a theorem of ZFC, but yeah, why would it be a >> > theorem of ZF? Let's get clear about that first. >> >> > And you were saying you could do it in ZF-regularity. >> >> > But, yeah, I would like to know how you do it in ZF. >> >> That is my personal guess, I don't have a proof of that yet. >> By the way can you help me regarding this issue, and post the complete >> proof of this theorem in ZFC, I think this would be of great help. >> >> Zuhair- Hide quoted text - >> >> - Show quoted text - > > If I assume the axiom of choice, then every set can be well-ordered, > and is equipollent to some cardinal kappa, a cardinal being a von > Neumann ordinal not equipollent to any smaller ordinal. > > Now let R(0) be the empty set, and for any R(alpha), let R(alpha+1) be > the set of all subsets of R(alpha) of cardinality less than kappa, and > for any limit ordinal beta, let R(beta) be the union of all R(alpha) > for alpha<beta. Iterate this up to R(kappa). In ZF I can prove this is > a set, using transfinite recursion and suchlike, and this is the set > you're after. > > Fair enough? > > But without the axiom of choice I know longer know that the set can be > well-ordered... and so it is not really clear what sort of transfinite > recursion to use. > > Do you get that? Do you want me to explain in more detail? In my Nov 23 article in this thread http://groups.google.com/group/sci.math/msg/721cb8170033cf84 I wrote (quoting Rupert and indirectly Zuhair): >>> So at the end I shall write the definition of cardinal again: > >>> A Cardinal is an equivalence class of hereditary sets under >>> equivalence relation "bijection". > >>> x is hereditary <-> >>> =A0for all y (y e Tc(x) -> y strictly subnumerous to x) > >>> Cardinality(x) =3D {y| y is hereditary & y equinumerous to x} > >>> Zuhair > >> But the question arises: can you prove in ZF that every set has a >> cardinality, on this definition? Not quite obvious to me just at the >> moment... > >> I have an idea that it is known that you need choice or regularity in >> order to define cardinals... > > In ZF using regularity and no AC, we can prove every set has a cardinality. >Namely all such sets will be included in the set of all sets hereditarily <= >the cardinal, and from the thread Zuhair refences in this thread, Aatu noted >this is a ZF theorem. The proof uses both regularity and replacement. I was being careless in that writing. I was thinking of the same proof Rupert wrote as quoted earlier above. In general I knew this as a ZFC theorem, but I reviewed that proof, and everything seemed so explicitly definable in that construction I thought AC had not been invoked. I checked that Aatu was talking about the same proof, and since I had just convinced myself AC was not used I wrote the older thread was also about a ZF proof. But Rupert above points out, at the outset we well-order x to find a cardinal kappa to work with, thereby using AC as I overlooked. So I agree, as Rupert and Zuhair wrote, in ZFC and using regularity, replacement and AC, we can prove every set has a set of heritarily smaller sets (as opposed to a proper class), and Zuhair's definition of cardinal is a set and not a proper class. The first quoted article above raised the question of proving this without using regularity. I think I already got a countermodel to this in my mentioned Nov 23 article http://groups.google.com/group/sci.math/msg/721cb8170033cf84 namely a inner model of ZFC with regularity removed with a proper class of infinite descending singletons. We all agree, these proofs are doing definitions by transfinite recursion, and so use replacement. In fact I recall I had never written but in my own thinking produced a model of ZC (Zermelo's theory with AC : no replacement) in which the heritarily finite sets are a proper class. So regularity and replacement are essential: have counterexample models without. What about AC? We know a proof using AC. Can we find a proof not using AC, or can we find a ~AC counterexample model? I can't do either yet, but I will report on some related partial answers I know or have read about. First off, a point about the AC based proof quoted above. I repeat the quote: > If I assume the axiom of choice, then every set can be well-ordered, > and is equipollent to some cardinal kappa, a cardinal being a von > Neumann ordinal not equipollent to any smaller ordinal. > > Now let R(0) be the empty set, and for any R(alpha), let R(alpha+1) be > the set of all subsets of R(alpha) of cardinality less than kappa, and > for any limit ordinal beta, let R(beta) be the union of all R(alpha) > for alpha<beta. Iterate this up to R(kappa). In ZF I can prove this is > a set, using transfinite recursion and suchlike, and this is the set > you're after. kappa is the cardinality of the set in question. The ordinary AC proof actually iterates out to R(kappa+), ie kappa+ the successor cardinal of kappa. With AC, every successor cardinal is regular, that is had cofinality = to itself. This means any subset X of R(kappa+) must actually be a subset of some R(alpha), some alpha dependnig on X < kappa+. So R(kappa+) really closed off the growth and gets the closure properties we wanted. The ordinary proof that successor cardinals are regular uses AC. So this is another way the proof depends on AC, apart from the original production of kappa Ruppert mentioned. I recall Moti Gitik from high large cardinal assumptions produced a model of ZF in which every infinite von Meumann cardinal has vountable cofinality, and indeed every infinite set is a union of countably many subsets each of strictly smaller cardinality than the big set. I have a useful link listing home pages of set theorists: http://www.math.ufl.edu/~jal/set_theory.html In there I found Moti Gitik's home page: http://www.math.tau.ac.il/~gitik/ He has many online papers there, but I didn't find that one. Anyway it sure raises a question, whether the R(alpha) construction above will ever close off in Gitik's model. Here is a bogus arguement attempt to show it doesn't close off. I will attempt a proof by transfinite induction that every R(alpha+1) intriduces new sets. R(0) is {{}}. So R(1) has a new member not in R(0) : {{{}}} . For alpha a limit ordinal: find and alpha_n n in omega sequence cofinal on alpha, by the proeprty of Gitik's model. By induction hypothesis each R(alpha_n + 1) introduces a new sets not previous in the lower R(beta). So form the countable set of such elements, one for each n. This is a new countable set not in any previous stage, so in R(alpha + 1). Next suppose alpha is itself a successor ordinal. By induction hypothesis, it has a new member. So {this new member} is a new member of R(alpha + 1) . So this would appear to finish the proof. But it is actually a bogus proof, because I had to pick one new member for each R(alpha_n + 1). If we had countable choice I could, but the whole point is Gitik's model is a ~AC model. In fact come to think of it, from an omega sequence cofinal in aleph_1 as Gitik's model had, if you had countable choice you could pick an omega enumeration of each piece, and use that to recover an analogue of Cantor's omega x omega ~ omege proof, making aleph_1 countable. So indeed Gitik's model doesn't satisfy countable choice. You might be tempted to make a definable version of the omega sequence of new R(apha_n + 1) by picking the ones previously defined by transfinite recursion. But that still depends on picking for each limit ordinal the omega sequenxce of ordinals cofinal in it, which again is only obvious with AC. Ok so its not clear whether the R(alpha) construction closes off in Gitik's model. But this question depends on the details of how AC fails in his model. So it will at least be a tricky querstion. So these are all the issues that arise in considering that proof in ~AC. Here is a new point though. Rupert pointed out, to find the set of sets hereitarily of card <= x, the usual proof well-orders x, hence invoking AC. I above pointed out the closure of the contruction becomes another point. But I can modify the proof to get around the well-ordering of x issue. Namely redo the construction, so at successor stages R(alpha + 1) adds in all subsets of R(alpha) of cardinality < #x, ie just use #x directyl in the definition. We still iterate over ordinals. ZF proves for any set x there is a set of what I will call the surjective Hartog ordinal. The usual definition of the Hartog ordinal of a set x is the least ordinal which does not inject into x. ZF proves the so called Hartog ordinal exists and is a set. I take instead a surjecive version: the least ordinal alpha such that x does not surject onto alpha. ZF proves there is always such a set sized ordinal. Namely to see this, any surjection of x onto alpha induces an equivalence realtiion on x : x elements are equivalent if they are sent to the same ordinal. So any ordinal surejcted by x is isomorphic to a well-ordering on some subset of P(x), ie pull the wellordering onn the ordinal back to the equivalence class preimages. So all the ordinals less than the surjective Hartog ordinal of x are ismimorphic to various well-orderings on a single set P(x). So the collection of all well-orderings on P(x) has natural well ordeing greater than all these, so its von Neuman ordinal can't be surjected by x, so there is a least such. So let kappa be the surjective Hartog ordinal of x. Suppose there were some lambda > kappa with cofinality(lambda) > kappa. If AC: cofinality(kappa+) = kappa+, so we could take lambda = kappa+. Anyway assuming there is some such lambda, consider R(lambda). Suppse there was an #x sized subset X of R(lambda). Map each element of y of x to the least alpha < lambda containing the X element corresponding to y in the #x enumeration of X. So this map surjects x onto its range below lambda. Since cofinality(lambda) > kappa, the range of this map must be bounded below lambda. So X is a member of the successor of this bound, and hence in R(lambda). So this R(lambda) hasd the desired closure properties. So it all reduces to finding lambda with cofinality(lambda) > kappa. So the AC dependence based on well-ordering x can be replaced, but the cofinality question remains. There is Gitik's difficult model, but as noted above Gitik's model makes it hard for us to prove the construction closes off. But we don't have a proof it doesn't, and we don't have a proof the desired heritary set doesn't exist. Which in turn brings me to the final point. I looked up http://en.wikipedia.org/wiki/Hereditarily_countable_set and they say all H_kappa, hereditarily less than kappa sets can be proven to exist in ZF. They reference http://www.jstor.org/pss/2273380 which is JSTOR for a 1982 article by Thomas Jech in Journal of Symbolic Logic. "On Hereditarily Countable Sets" vol 47, number 1, March 1982 . Jech names the class of hereditarily countable sets HC. Jech notes without AC it is not even obvious HC is a set (as opposed to a proper class). This is like the sort of questions I was raising with Gitik's model. But Jech's paper proves in ZF that it is a set. I don't have insider access to JSTOR, so I can only see the first page which states results. That page says this was received by JSL Oct 15, 1979, so I suppose this was new reseach then. All the old stuff we were discussing the basic AC proofs would have gone back to early 20th century. So this is a much bigger deal. Also, Gitik's model is sure suggestive of a proper class being possible, even for HC. So somehow Jech's proof is going to show that doesn't happen. The Wikipedia page doesn't give details why H_kappa. I wonder if that is just generalizing Jech's HC. Anyway, one point. The H_kappa always add sets < kappa in cardinality, so sets injecting into a well-order and hence well-orderable. So for general non-well-orderable x in ~AC models, we don't get x back into these H_kappa. But I showed above how the H_kappa building techniques can also sometimes apply to other x. So if we understand more the H_kappa case, the general x case might still go either way or might still be hard to answer even knowing H_kappa. We don't even know HC yet. Well we know the claim, but not the proof, since I can't read past the opening page. I just thought to check Jech's pages from http://www.math.ufl.edu/~jal/set_theory.html I found 2, but a quick look didn't find that paper: http://www.math.cas.cz/~jech/ http://www.math.psu.edu/jech/ -- David Libert ah170(a)FreeNet.Carleton.CA
From: Aatu Koskensilta on 24 Nov 2009 17:09 ah170(a)FreeNet.Carleton.CA (David Libert) writes: > Here is a new point though. Rupert pointed out, to find the set of > sets hereitarily of card <= x, the usual proof well-orders x, hence > invoking AC. As you note, this is not where AC comes into play, since in the inductive definition we don't need a (von Neumann) cardinal the size of x because we can just include sets < |x| directly. The problem is, again as you note, proving the existence of a closure ordinal for the inductive definition; or, to put it slightly differently, showing that for every set x there's a V_alpha such that if all members of TC(A) for a set A are of cardinality < |x|, A is in V_alpha. PS. I have e-mailed you a copy of the Jech paper. I haven't myself studied the argument for the existence of the set of hereditarily countable sets in absence of choice, by establishing that the rank of a hereditarily countable set <= omega_2, and so can say nothing about whether it may be generalised beyond the countable case. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechen kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: zuhair on 24 Nov 2009 17:50 On Nov 24, 5:09 pm, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > ah...(a)FreeNet.Carleton.CA (David Libert) writes: > > Here is a new point though. Rupert pointed out, to find the set of > > sets hereitarily of card <= x, the usual proof well-orders x, hence > > invoking AC. > > As you note, this is not where AC comes into play, since in the > inductive definition we don't need a (von Neumann) cardinal the size of > x because we can just include sets < |x| directly. The problem is, again > as you note, proving the existence of a closure ordinal for the > inductive definition; or, to put it slightly differently, showing that > for every set x there's a V_alpha such that if all members of TC(A) for > a set A are of cardinality < |x|, A is in V_alpha. > > PS. I have e-mailed you a copy of the Jech paper. I haven't myself > studied the argument for the existence of the set of hereditarily > countable sets in absence of choice, by establishing that the rank of a > hereditarily countable set <= omega_2, and so can say nothing about > whether it may be generalised beyond the countable case. Can you e-mail me a copy of this paper. Zuhair > > -- > Aatu Koskensilta (aatu.koskensi...(a)uta.fi) > > "Wovon man nicht sprechen kann, darüber muss man schweigen" > - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: zuhair on 24 Nov 2009 17:53 I got the following reply from an authority on set theory. ... Perhaps I misunderstand your definition, but with Foundation one can prove that every non-empty set contains 0 (= empty set} in its transitive closure. If I am correct, then your definition does not work.... Can anybody explain that? Zuhair
From: Tim Little on 24 Nov 2009 19:11
On 2009-11-24, George Greene <greeneg(a)email.unc.edu> wrote: > There are MANY DIFFERENT well-orderings of p(w) under ZFC and they > correspond TO DIFFERENT ordinals! But not to different cardinals. - Tim |