A new definition of Cardinality.
in [Logic]
|
From: Jesse F. Hughes on 23 Nov 2009 06:34 zuhair <zaljohar(a)gmail.com> writes: > On Nov 22, 11:43 pm, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: >> zuhair <zaljo...(a)gmail.com> writes: >> > As far as I know, all the definitions of cardinality are limited in a >> > way or another, lets take them one after the other: >> >> [...] >> >> > 2) Frege-Russell Cardinals: >> >> > A cardinal is an equivalence class of sets under equivalence relation >> > "bijection". >> >> [...] >> >> > 2) Frege-Russell cardinals contradict Z set theory, since their >> > existence would imply the existence of the set of all sets, which is >> > in contradiction with Z. >> >> > However in NBG and MK class theories, we can define >> > Frege-Russell cardinals, but by then they would be proper classes and >> > not sets, which is a great draw back, since proper classes cannot be >> > members of other classes, and they are hard to work with. >> >> [...] >> >> > I would like to suggest the following definition: >> >> [...] >> >> > A Cardinal is an equivalence class of hereditary sets under >> > equivalence relation "bijection". >> >> > x is hereditary <-> >> > for all y (y e Tc(x) -> y strictly subnumerous to x) >> >> > Cardinality(x) = {y| y is hereditary & y equinumerous to x} >> >> How is this any better than the Frege-Russell definition? It's much >> more complicated and doesn't avoid the issue you called the difficult >> point, does it? >> >> Consider the set {0,1}. By your definition, >> >> Card({0}) = { y | y is hereditary and y is a pair } >> = { y | y is a pair and (Az)(z in Tc(y) -> z is empty or a >> singleton) } >> >> Let s be any set. The set {0,{s}} is in Card({0}), thus Card({0}) is >> a proper class. >> >> So what advantage have you here? > > I think you missed the point of transitive closure here, you said let > s be any set right, then as you know not any s have all members in its > transitive closure > being a pair. so the set {0,{s}} might not be in Cardinality of > {0,1} Yes, you're right. Given a set S, is there a simple argument that your definition Card(S) is a set and not a proper class? Seems plausible, but I'm not sure how to prove it. > by they way I think you made a typo since you right Card({0}) That's right too. I changed from {0} to {0,1} midstream, but screwed up. > I think you mean Card({0,1}) since as you know > {0} is not equi-numerous to {0,{s}} for all s. > > Card({0})= { y | y is hereditary and y equinumerous to {0} } -- Jesse F. Hughes "Sigh. Back to figuring out how to solve the factoring problem and ending the world as we know it." -- James S. Harris
From: zuhair on 23 Nov 2009 06:46 On Nov 23, 2:01 am, ah...(a)FreeNet.Carleton.CA (David Libert) wrote: > Rupert (rupertmccal...(a)yahoo.com) writes: > > On Nov 23, 10:01=A0am, zuhair <zaljo...(a)gmail.com> wrote: > >> Hi all, > > >> As far as I know, all the definitions of cardinality are limited in a > >> way or another, lets take them one after the other: > > >> 1) Von Neumann's Cardinals: > > >> A cardinal is the least of all equinumerous ordinals. > > >> 2) Frege-Russell Cardinals: > > >> A cardinal is an equivalence class of sets under equivalence relation > >> "bijection". > > >> 3) Scott-Potter Cardinals: > > >> A cardinal is a class of all equinumerous sets from a common level. > > >> Now lets come to discuss each one of them: > > >> 1) Von Neumann's cardinals has the limitation of being dependent on > >> choice, without choice one cannot know what is the cardinality of > >> Power(omega) for example.Accordingly in any theory which do not have > >> the axiom of choice among its axioms most of its sets would be of > >> indeterminable cardinality, which is a big draw back. > > >> 2) Frege-Russell cardinals contradict Z set theory, since their > >> existence would imply the existence of the set of all sets, which is > >> in contradiction with Z. > > >> However in NBG and MK class theories, we can define > >> Frege-Russell cardinals, but by then they would be proper classes and > >> not sets, which is a great draw back, since proper classes cannot be > >> members of other classes, and they are hard to work with. > > >> In NF and related theories, Frege-Russell cardinals are sets, but > >> these theories generally depend on the concept of stratification > >> of formulas, which is a complex concept, and even finite > >> axiomatization of NF and NFU and related theories is a complicated > >> approach, and at the end it also resort to stratification for most of > >> its inferences. All that make these cardinals undesirable. > > >> 3) Scott-Potter Cardinals: depend on the concept of "level" which > >> depends on the concept of type (Scott) and the iterative concept > >> (Potter), both concepts of which are complex and difficult to work > >> with, besides they are not the basic > >> concepts we use to compare set sizes. > > >> I would like to suggest the following definition: > > >> 4) The cardinality of any set x is: The class of all sets > >> that are equinumerous to x were every member of their transitive > >> closure is strictly subnumerous to x. > > >> So for any set x, any y is a member of the cardinality of x, > >> =A0if and only if, y is equinumerous to x and every member of the > >> transitive closure of y is strictly subnumerous to x. > > >> In symbols: > > >> Define(cardinality(x)):- > > >> z=3Dcardinality(x) <-> > >> =A0for all y (y e z <-> > >> (y equi-numerous to x & > >> =A0for all m (m e Tc(y)->m strictly subnumerous to x))) > > >> Were Tc(y) stands for the 'transitive closure of y' defined > >> in the standard manner. > > >> Tc(y)=3DU{y,Uy,UUy,UUUy,......} > > >> We can actually better define these cardinals through defining the > >> concept of "hereditary sets" > > >> Define(hereditary): > >> =A0x is hereditary <-> > >> =A0for all y (y e Tc(x) -> y strictly subnumerous to x) > > >> So a cardinal can be defined in the following manner: > > >> A Cardinal is an equivalence class of hereditary sets under > >> equivalence relation "bijection". > > >> Or simply > > >> A Cardinal is a class of all equinumerous hereditary sets. > > >> So cardinality of x would be written shortly as: > > >> Cardinality(x) =3D {y| y is hereditary & y equinumerous to x} > > >> Now it can be proven in ZF that those cardinals would be 'sets', so > >> they are not proper classes! which makes them easy to handle. > > >> These cardinals don't require choice. > > >> They don't require complex concepts like "stratification,type, > >> iteration" > > >> They simply depend on the basic concept used to compare set sizes, > >> which is the presence or absence of injections between the compared > >> sets. > > >> To me this definition seems to be simpler, more general, and it works > >> with or without choice, with or without regularity. > > >> 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. He did? The proof uses both regularity and replacement. It would be of great help if you post the proof please. But definitely replacement is needed no doubt. > > Many common theorems of math don't require replacement. > > But if we drop regularity it is not provable, even if we add AC back in fact. > > For example, in a ZF model construct an inner model as follows. Declare each > set of form <alpha, n>, wherre alpha is an ordinal > 0 and n in omega, > to be an atom. > > These atoms will look like sets in the final model, so we stipulate > membership facts for them. > > Make each <alpha, n> become the singleton of <alpha, n+1>. > > Namely we declare <beta, m> member <alpha, n> <-> > m = n+1 and beta = alpha . > > Now grow this into an inner ZF model without regularity though. > > Namely declare certain sets of form <0, s> to be in the model > iteratively, by transfinitie recursion. > > At stage alpha+1 we add atoms <alpha, n> and also all <0, s> > where s is a subest of stage alpha and s is not the singleton of > an atom. Dedine t member <0, s> iff t epsilon s . > > Unions of stages at limit ordinals. > > Singleton atoms are respresented by other atoms so we didn't add such > <0, s>. > > <0, s> versus <alpha, n> alpha > 0 avoids confusion atoms versus > other sets so keeps the defintiion of membership well devined. > > We also define <0, s> never member of atoms. > > Avoiding singleton atoms in <0, s> avoided some coutnerexamples > to exensionality. > > The atoms avoid contradicting etensionanlty by having other atoms > below them to stay distinct as members. Since the omega chain > never hits {} there is no day of reckoning. > > So we end up with a proper class (by alpha varying) of singletons > that are hereditarily singeltons. > > So there is no set to be cardinal 1. > > This all relates to an axiom: > > http://en.wikipedia.org/wiki/Aczel's_anti-foundation_axiom > > That says that the shape of the graph of interated members determines the set. > (Well is existence and uniqueness). > > My model above fails the uniqueness clause of that axiom. > > What if we ad that axiom? > > With AC also, we do get back only a set of solutions. > > Without AC we don't though. Start with a ~AC ground model with <Ui | i in omega> > and <Wi | i in omega> so that each Ui bijective with each Wj, > yet there is no omega sequence of bijectioins f_i : Ui >->> Wi. > > Basically: lots of bijections around so with AC picking bijectiins you could > make such an f_i sequence, but not really being able to is an AC failure. > > Form a non-reguilarity models similoar to above, making a descnding chain of > Ui or Wi memebers. > > Ok its a little more complicated, because these aren't singelons. Make the > iterated members be finsite equence of respective members in the Ui or Wi.. > > The point being: with regualrity, when you keep make isomorphic copies > all the way down to {}, the {} 's are =, and then iteratively up the ranks > the isomprphoc copoes of actually ='s become =. > > Without reguilarity you never hit bottom, so extensionaloty can keep failing > based on lower failures. > > I did that already in ther singleton example. > > But the singleton example, Aczel's axiom could recognize the common shape and > so enforce = that way. > > So I am making a more complicated example to fool Aczel's axiom. At each level > I am putting in isomorphisms to make it heriedary, but using a AC failure to > block the global comparison that would let Aczel's axiom kick in. > > Anyway, cpmpying a version of the singletons along lines as above, which > I haven;t done in detail byu not spelling out all defintions, obtain > Ui and Wi based sets so U0 W0 that was each hereditarily <= a copy of U0, > but that are not recognized by Aczel's axiom as having the same shape. > > So we can still get 2 non-= correspondings to the U0 copy. > > Now do a fancier version, with a proper class of copies according to > the starting model, instead of only 2. > > So again, mess up a set cardinal like in the singleton example, all > slipping by the guard of Aczel's axiom. > > Ya, so construct exverything so Aczel's axiom was true also in the model. > > (Gee, my hands are getting tired from waving so much :) ). > > Anyway, with AC. and Aczel's, we can get back to up to iso only > a set of examples, so then get back a set. > > -- > David Libert ah...(a)FreeNet.Carleton.CA
From: zuhair on 23 Nov 2009 06:51 On Nov 23, 6:34 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > zuhair <zaljo...(a)gmail.com> writes: > > On Nov 22, 11:43 pm, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > >> zuhair <zaljo...(a)gmail.com> writes: > >> > As far as I know, all the definitions of cardinality are limited in a > >> > way or another, lets take them one after the other: > > >> [...] > > >> > 2) Frege-Russell Cardinals: > > >> > A cardinal is an equivalence class of sets under equivalence relation > >> > "bijection". > > >> [...] > > >> > 2) Frege-Russell cardinals contradict Z set theory, since their > >> > existence would imply the existence of the set of all sets, which is > >> > in contradiction with Z. > > >> > However in NBG and MK class theories, we can define > >> > Frege-Russell cardinals, but by then they would be proper classes and > >> > not sets, which is a great draw back, since proper classes cannot be > >> > members of other classes, and they are hard to work with. > > >> [...] > > >> > I would like to suggest the following definition: > > >> [...] > > >> > A Cardinal is an equivalence class of hereditary sets under > >> > equivalence relation "bijection". > > >> > x is hereditary <-> > >> > for all y (y e Tc(x) -> y strictly subnumerous to x) > > >> > Cardinality(x) = {y| y is hereditary & y equinumerous to x} > > >> How is this any better than the Frege-Russell definition? It's much > >> more complicated and doesn't avoid the issue you called the difficult > >> point, does it? > > >> Consider the set {0,1}. By your definition, > > >> Card({0}) = { y | y is hereditary and y is a pair } > >> = { y | y is a pair and (Az)(z in Tc(y) -> z is empty or a > >> singleton) } > > >> Let s be any set. The set {0,{s}} is in Card({0}), thus Card({0}) is > >> a proper class. > > >> So what advantage have you here? > > > I think you missed the point of transitive closure here, you said let > > s be any set right, then as you know not any s have all members in its > > transitive closure > > being a pair. so the set {0,{s}} might not be in Cardinality of > > {0,1} > > Yes, you're right. > > Given a set S, is there a simple argument that your definition Card(S) > is a set and not a proper class? Seems plausible, but I'm not sure > how to prove it. 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) H_(<x) = {y | y strictly subnumerous to x and for all z (z e Tc(y) -> z strictly subnumerous to x)} as a theorem of ZF. this is the lemma behind this definition, however Aatu presented a proof of it in the link I wrote in one of the posts to this topic, so you can refer to it, still I need the details of weather it requires choice or not, I mean I want the complete proof. The next step is to take Power(H_(<x)) which is a set of course, Now using separation on Power(H_(<x)) with the formula " y equinumerous to x " then we get : for every set x there exist c such that c= { y | y e Power(H_(<x)) and y equinumerous to x } and of course c is the cardinal I that I defined. So in ZF (with or without choice) one can prove the existence of these cardinals for every set, however as David Libert points out it seems that this depends on Regularity, but as he said it doesn't depend on choice, but I will know that for sure if he post the proof of the lemma above. Zuhair > > > by they way I think you made a typo since you right Card({0}) > > That's right too. I changed from {0} to {0,1} midstream, but > screwed up. > > > I think you mean Card({0,1}) since as you know > > {0} is not equi-numerous to {0,{s}} for all s. > > > Card({0})= { y | y is hereditary and y equinumerous to {0} } > > -- > Jesse F. Hughes > > "Sigh. Back to figuring out how to solve the factoring problem and > ending the world as we know it." -- James S. Harris
From: George Greene on 23 Nov 2009 08:09 On Nov 22, 6:01 pm, zuhair <zaljo...(a)gmail.com> wrote: > Hi all, > > As far as I know, all the definitions of cardinality are limited in a > way or another, lets take them one after the other: > > 1) Von Neumann's Cardinals: > > A cardinal is the least of all equinumerous ordinals. > Now lets come to discuss each one of them: > > 1) Von Neumann's cardinals has the limitation of being dependent on > choice, without choice one cannot know what is the cardinality of > Power(omega) for example.Accordingly in any theory which do not have > the axiom of choice among its axioms most of its sets would be of > indeterminable cardinality, which is a big draw back. Even WITH choice, the ZFC definition of cardinality STILL has a serious drawback. You STILL CANNOT determine the cardinality of p(w) under ZFC. The collection of all countable ordinals (aleph-one) cannot possibly be bigger than p(w), but it could be equally large-- the cardinality of p(w) could be aleph-one, aleph-2, or any finite aleph.
From: Rupert on 24 Nov 2009 00:55
On Nov 23, 10:37 pm, zuhair <zaljo...(a)gmail.com> wrote: > On Nov 22, 9:20 pm, Rupert <rupertmccal...(a)yahoo.com> wrote: > > > > > > > On Nov 23, 11:37 am, zuhair <zaljo...(a)gmail.com> wrote: > > > > On Nov 22, 7:16 pm, Rupert <rupertmccal...(a)yahoo.com> wrote: > > > > > On Nov 23, 10:01 am, zuhair <zaljo...(a)gmail.com> wrote: > > > > > > Hi all, > > > > > > As far as I know, all the definitions of cardinality are limited in a > > > > > way or another, lets take them one after the other: > > > > > > 1) Von Neumann's Cardinals: > > > > > > A cardinal is the least of all equinumerous ordinals. > > > > > > 2) Frege-Russell Cardinals: > > > > > > A cardinal is an equivalence class of sets under equivalence relation > > > > > "bijection". > > > > > > 3) Scott-Potter Cardinals: > > > > > > A cardinal is a class of all equinumerous sets from a common level. > > > > > > Now lets come to discuss each one of them: > > > > > > 1) Von Neumann's cardinals has the limitation of being dependent on > > > > > choice, without choice one cannot know what is the cardinality of > > > > > Power(omega) for example.Accordingly in any theory which do not have > > > > > the axiom of choice among its axioms most of its sets would be of > > > > > indeterminable cardinality, which is a big draw back. > > > > > > 2) Frege-Russell cardinals contradict Z set theory, since their > > > > > existence would imply the existence of the set of all sets, which is > > > > > in contradiction with Z. > > > > > > However in NBG and MK class theories, we can define > > > > > Frege-Russell cardinals, but by then they would be proper classes and > > > > > not sets, which is a great draw back, since proper classes cannot be > > > > > members of other classes, and they are hard to work with. > > > > > > In NF and related theories, Frege-Russell cardinals are sets, but > > > > > these theories generally depend on the concept of stratification > > > > > of formulas, which is a complex concept, and even finite > > > > > axiomatization of NF and NFU and related theories is a complicated > > > > > approach, and at the end it also resort to stratification for most of > > > > > its inferences. All that make these cardinals undesirable. > > > > > > 3) Scott-Potter Cardinals: depend on the concept of "level" which > > > > > depends on the concept of type (Scott) and the iterative concept > > > > > (Potter), both concepts of which are complex and difficult to work > > > > > with, besides they are not the basic > > > > > concepts we use to compare set sizes. > > > > > > I would like to suggest the following definition: > > > > > > 4) The cardinality of any set x is: The class of all sets > > > > > that are equinumerous to x were every member of their transitive > > > > > closure is strictly subnumerous to x. > > > > > > So for any set x, any y is a member of the cardinality of x, > > > > > if and only if, y is equinumerous to x and every member of the > > > > > transitive closure of y is strictly subnumerous to x. > > > > > > In symbols: > > > > > > Define(cardinality(x)):- > > > > > > z=cardinality(x) <-> > > > > > for all y (y e z <-> > > > > > (y equi-numerous to x & > > > > > for all m (m e Tc(y)->m strictly subnumerous to x))) > > > > > > Were Tc(y) stands for the 'transitive closure of y' defined > > > > > in the standard manner. > > > > > > Tc(y)=U{y,Uy,UUy,UUUy,......} > > > > > > We can actually better define these cardinals through defining the > > > > > concept of "hereditary sets" > > > > > > Define(hereditary): > > > > > x is hereditary <-> > > > > > for all y (y e Tc(x) -> y strictly subnumerous to x) > > > > > > So a cardinal can be defined in the following manner: > > > > > > A Cardinal is an equivalence class of hereditary sets under > > > > > equivalence relation "bijection". > > > > > > Or simply > > > > > > A Cardinal is a class of all equinumerous hereditary sets. > > > > > > So cardinality of x would be written shortly as: > > > > > > Cardinality(x) = {y| y is hereditary & y equinumerous to x} > > > > > > Now it can be proven in ZF that those cardinals would be 'sets', so > > > > > they are not proper classes! which makes them easy to handle. > > > > > > These cardinals don't require choice. > > > > > > They don't require complex concepts like "stratification,type, > > > > > iteration" > > > > > > They simply depend on the basic concept used to compare set sizes, > > > > > which is the presence or absence of injections between the compared > > > > > sets. > > > > > > To me this definition seems to be simpler, more general, and it works > > > > > with or without choice, with or without regularity. > > > > > > 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 <-> > > > > > for all y (y e Tc(x) -> y strictly subnumerous to x) > > > > > > Cardinality(x) = {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... > > > > Well, to say the truth I am not sure either. But from my prior > > > discussions > > > I got the impression that working in ZF minus Regularity minus Choice, > > > it is provable that: > > > > for any set there exist a set of exactly all sets that are > > > hereditarily strictly sub-numerous to it. > > > That is certainly not a problem in ZFC but I certainly don't see right > > now how to do it without regularity or choice. You should look into > > that one carefully, I should think. > > 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) > > H_(<x) = {y | y strictly subnumerous to x and > for all z (z e Tc(y) -> z strictly 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. |