Cardinality once more
in [Logic]
|
From: zuhair on 3 Jan 2010 18:02 On Jan 3, 5:16 pm, MoeBlee <jazzm...(a)hotmail.com> wrote: > On Jan 2, 6:51 pm, zuhair <zaljo...(a)gmail.com> wrote: > > > ZF(-Regularity) + "AxE!y Phi(x y) & > > Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)" > > > is Equi-interpretable with > > > ZF(-Regularity) + Tarski axiom. > > Yes, NOW you've got a precise mathematical question and it is indeed > equi-interpretability that it s appropriate to ask about. > > MoeBlee Yes, thanks Moe, for letting me put my question into exact formal detail. Why I am asking this question? Two matters, first David Libert has presented a model of ZF minus Regularity in which we cannot *define* cardinality. also T.E.Forster spoke about Gaunett's models, although these models violate Extesnionality, yet they do prove that we cannot come with a defined concept of Cardinality in ZF minus Regularity . This was T.E.Forster's reply: Further to my last: a modifcation rather than an outright retraction. Gauntt's model violates extensionality rather than foundation beco's it has distinct empty sets (urelemente). What would be needed to answer Zuhair's question is a Gauntt model with Quine atoms (objects x = {x}) instead. I am 99% certain that Gauntt's construction works with these objects instead but we live in an imperfect world and i should check it - unless some other list member does it first! From these replies I had two questions in my mind (1) is ZF(minus Regularity) + Tarski's axiom Equi-interpretable with ZF minus Regularity. (2) Can we have a formula Phi(x y) in FOL(=,e) such that: ZF(-Regularity) + "AxE!y Phi(x y) & Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)" is Equi-interpretable with ZF(-Regularity) + Tarski's axiom. These were the two questions in my mind. Zuhair
From: David Libert on 5 Jan 2010 17:20 zuhair (zaljohar(a)gmail.com) writes: > On Jan 3, 5:16=A0pm, MoeBlee <jazzm...(a)hotmail.com> wrote: >> On Jan 2, 6:51=A0pm, zuhair <zaljo...(a)gmail.com> wrote: >> >> > ZF(-Regularity) + "AxE!y Phi(x y) & >> > Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)" >> >> > is Equi-interpretable with >> >> > =A0ZF(-Regularity) + Tarski axiom. >> >> Yes, NOW you've got a precise mathematical question and it is indeed >> equi-interpretability that it s appropriate to ask about. >> >> MoeBlee > > Yes, thanks Moe, for letting me put my question into exact formal > detail. > > Why I am asking this question? > > Two matters, first David Libert has presented a model of ZF minus > Regularity in which we cannot *define* cardinality. > > also T.E.Forster spoke about Gaunett's models, although these models > violate Extesnionality, yet they do prove that we cannot come with a > defined concept of Cardinality in ZF minus Regularity . > > This was T.E.Forster's reply: > > Further to my last: a modifcation rather than an outright retraction. > Gauntt's model violates extensionality rather than foundation beco's > it > has distinct empty sets (urelemente). What would be needed to answer > Zuhair's question is a Gauntt model with Quine atoms (objects x =3D {x}) > instead. I am 99% certain that Gauntt's construction works with > these > objects instead but we live in an imperfect world and i should check > it - > unless some other list member does it first! As T.E.Forster was indicating, in general you can replace urelements from a ZFU model by Quine atoms and make a ZF - regularity model. The other sets of the original ZFU model can retain their old membership, and no new sets need be added. So this provides lots of transfer between ZFU and ZF - rerularity. Similarly, you can replace each urelement from a ZFU model by a new downward chain of recursive singletons, in similar fashion, changing nothing else in the model. Or similarly by higher cardinality than singletons. A downward binary tree of recursive doubeltons, or any other cardinality from the starting ZFU model. I discussed a similar point in my first detailed presentation with cardinality undefinable below. Well that wasn't working from ZFU to start but same idea of using recursive doubletons instead of recursive signletons and so on. > From these replies I had two questions in my mind > > (1) is ZF(minus Regularity) + Tarski's axiom > Equi-interpretable with > ZF minus Regularity. > > (2) Can we have a formula Phi(x y) in FOL(=3D,e) such that: > > ZF(-Regularity) + "AxE!y Phi(x y) & > Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)" > > is Equi-interpretable with > > ZF(-Regularity) + Tarski's axiom. > > These were the two questions in my mind. > > Zuhair I will be discussing these questions below, and realting them to some of my earlier constructions of models. Before I begin that, this seems like a good time to collect references to those previous articles about models, since I will be referring to some of them. So I will note references then return to the questions. I first had five models. General references for these and the main articles discussing them were collected in [1] David Libert "Recursive Cardinals" sci.logic, sci.math Dec 31, 2009 http://groups.google.com/group/sci.logic/msg/c26de32a0acd6dd2 Since then I noted some further models about alpha-well-orderability: [2] David Libert "Cardinality once more" sci.logic, sci.math Jan 3, 2010 http://groups.google.com/group/sci.logic/msg/6eca3be8b1e319f9 In [1] I noted a previous article collecting the core refernces about those first four of those give models ([1] also added some additional later discussions): > I have had some other models besides [1]. > These and [1] and background were referenced in > [2] David Libert " Extensionality and Circular objects" > sci.logic, sci.math Dec 23, 2009 > http://groups.google.com/group/sci.logic/msg/f3ed79cb6bf9fb5e In that [1] reference to "[2]" (as opposed to the current [2]) I noted the specfic four models, including two I want to single out now: > In > >[4] David Libert "Why Define Cardinality?" > sci.logic, sci.math Dec 10, 2009 > http://groups.google.com/group/sci.logic/msg/0803f45348c83967 > >I posted a proof outline of a claimed construction of a ZF - regularity >model in which cardinality is undefinable. > > In > >[5] David Libert "The General Backround of Cardinality" > sci.logic Dec 22, 2009 > http://groups.google.com/group/sci.logic/msg/16dc3c6329a74e35 > >I wrote the [4] proof in more detail, also modifying the definition >to make the proof go through. > > In > >[6] David Libert "The General Backround of Cardinality" > sci.logic Dec 22, 2009 > http://groups.google.com/group/sci.logic/msg/b11fcb00f55fa7ff > >I wrote a variant of [5] which also had all H_(x) being sets. That concludes the previous references. I return to your questions, which I will repeat: > From these replies I had two questions in my mind > > (1) is ZF(minus Regularity) + Tarski's axiom > Equi-interpretable with > ZF minus Regularity. > > (2) Can we have a formula Phi(x y) in FOL(=3D,e) such that: > > ZF(-Regularity) + "AxE!y Phi(x y) & > Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)" > > is Equi-interpretable with > > ZF(-Regularity) + Tarski's axiom. > > These were the two questions in my mind. You reformulated these questions in this theread over several articles in discussion with Moe Blee. Your original article asked these differently, in what I interpreted as different questions than these. I think the original version is probably more illumonating. I will discuss all of these. First off, I think the questions as phrased now, as I understand them have a sort of dodge answer which makes them not so interesting. I am considering interpretabilty to be as in Tarski. So into the interpeting theory we interpret the universe of the interpeted theory as a definable subclass of the universe (or sometimes even a Cartesian product of the universe if we use a tuple of variables to interpret one variable. We interpret the relation and function symbols of the interpreted theory as definable relatiins and functions on that defined universe, definable in the interpreting theory. So the interpreting theory is allowed to make nonstandard interpetations of the relation and function symbols, and as such can construct models very different from itself. Reading your (1) and (2) questions this way, we can make literal answers to them that are trick answers, not really getting to an illuminating relation between definable cardinality and your Tarski axiom. Note that ZF - regularity is a subtheory of ZF ie regularity added back in. So if I construct a model of ZF I have constructed a model of ZF - regularity. In any ZF - regulariyu model, there is the definable class of all well-founded sets. This is a ZF model. So every ZF - regularity model has a definable inner submodel of ZF. So ZF interprets into ZF - regularity. But ZF can do Scott's trick to define cardinality. So we can interpret ZF - regularity + Tarski's axiom into ZF - regularity. (A sort of cheat interpretation, since our intepretation actuially adds regularity back). So this trick gets an answer to > (1) is ZF(minus Regularity) + Tarski's axiom > Equi-interpretable with > ZF minus Regularity. namely adding Tarski's axiom back in. And dropping Tarski's axiom direction is more trial: just reduce back throwing away the Card symbol. So both directions are yes, by a sort of trick answer to interpret Tarski's axiom in. As for > (2) Can we have a formula Phi(x y) in FOL(=3D,e) such that: > > ZF(-Regularity) + "AxE!y Phi(x y) & > Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)" > > is Equi-interpretable with > > ZF(-Regularity) + Tarski's axiom. To go from the first (definable cardinality) to Tarski's axiom just interpret card in Tarski's axiom by that definition. In general the hard direction should be from Tarski's axiom to the definable version, other direction. But there is trick answer to that too. From Tarski's axiom just cut back same way to well-founded and get back ZF and from there Scott's trick and use that as the Phi. We could try to rule out these trivial answers I just gave by replacing ZF - regularity by ZF - regularity + ~regularity everywhere. That would rule out my cheat answers above. But I can still do something similar to get around that. Cut back to well-founded sets again and get ZF, then inside there make a construction of a model with one maximal chain of recursive singletons only. That is similar to the first model in [1]. Everything in this model is well-founded over that maximal chain. So we can still make a growing hierarchy through the universe like the V_alphas from ZF, except start with the maxinal chain instead of {}. This is enough to do as Scott's trick with this hierarchy and define cardinality that way. So this also gets trivial yes answers to both (1) (2) even over ZF - regularity + ~regularity. There would be more complex versions of this than one maxinal chain of recursive singletons, to get around a new version of the questions blocking that case. I think the interesting questions like (1) and (2) should be asking about closer connections between the definable cardinality and the axiomatized one. So I think the interesting version of (1) ands (2) should ask this when the interpretation is not allowed to redfine the universe, or = or epsilon. So to interpret Tarski axiom, we insist on an interpretation of Card over the original =, epsilon and the original universe. And for the other direction in (2), the defined cardinality should be using the underyling universe behind Tarski's axiom. So to repeat (1) and (2) : > (1) is ZF(minus Regularity) + Tarski's axiom > Equi-interpretable with > ZF minus Regularity. > > (2) Can we have a formula Phi(x y) in FOL(=3D,e) such that: > > ZF(-Regularity) + "AxE!y Phi(x y) & > Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)" > > is Equi-interpretable with > > ZF(-Regularity) + Tarski's axiom. The reworked version would say, can we interpret Tarski's axiom over those base theories by just an defining Card. And for the other direction it would say: (for (2)) in the big language with Card and the theory with Tarski's axiom, can we prove the statement above about Phi for some Phi from the smaller sublangyuage not mentioning Card. These are questions about a more direct connection between defined and axiomatized cardnality. So I turn to that now. In the revised (1), to drop Tarski's axiom is trivial. It is the identity interpretation where every formula translates to itself. For the other direction, can we interepret ZF - regularity + Tarski's axiom into ZF - regularity in this special form of interpretation, just to interpret Card as a definition, my [5] & [6] models are a counterexamples. ([5] itself included several variant versions. And [6] was a further variatiant. The reason to have these alternatives was to have examples with various additional side properties.) So that direction the answer is no. ZF - regulairty + Tatrski's axioms can't interpret in this restiricted sense into ZF - regularity. Regarding: > (2) Can we have a formula Phi(x y) in FOL(=3D,e) such that: > > ZF(-Regularity) + "AxE!y Phi(x y) & > Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)" > > is Equi-interpretable with > > ZF(-Regularity) + Tarski's axiom. One direction is easy. Given any formula Phi, starting with theory > ZF(-Regularity) + "AxE!y Phi(x y) & > Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)" we can interpret ZF - regularity + Tarski's axiom into that by interpreting Card by Phi. (This even if that theory with Phi is inconsistent. For example, suppose ZF - regularity proves Phi does not define cardinalitry, ie the negation of the extra axiom you gave above about Phi. We can still add your axiom to ZF - rgularity and get an inconsistent theory. This still interprets ZF - regualrity + Tarski's axiom by making any definition for Card, and this is indeed an interpretation since the interpretation of every axiom is probable in ZF - regulairty + your Phi axiom since that is inconsistent.) The hard direction is to go the other way: Is there is Phi so the Phi theory interprets in the revised sense to ZF - regularity + Tarski's axiom. Namely in the revised reading of (2) this is asking if ZF - regularity + Tarski's axiom actually shows some formula Phi not mentioning Card defines cardinality. This is not immediately obvious from any of the previous writing or models. If we want to prove no, one way would be to find models where cardinality is undefinable in = , epsilon. So far we have models [5] & [6]. But it is not clear how Tarski's axiom relates to these. (For one thing it is not in the same language. And it looks dubious to expand the language and add Tarski's axiom, since the thigns built into the model to make cardinality undefinable look like they will mess up Tarski's axiom.) So its not immediately obvious how to get a counterexample to an implication here. I think I have found how to modify the [5] and [6] definitions, to be still similar enough to the original [5] & [6] to still let me argue cardinality is undfinable just using =, epsilon, but I can make these exapnded models with Card built into the model to satisfy Tarski's axiom. I turn to that now. Recall [5] and [6] have their definitions over a base model of ZFC. I will add the assumption that this base is a GB model, including global choce. You can get that with Godel's L. Recall [5] and [6] had proper classes A_n (n in omega in the base model). Each A_n had members A_n,alpha, as alpha varied in the base model pver all ordinals. Each A_n,alpha had members A_n,alpha,m,l as m,l varied over omega in the base model. (The first singleton towers model in [5] took l > 0, the other models of [5] and the [6] model took all l in omega as A_n,alpha members). All these models made finite support permutation models based on simul;taneous permutations on all of n, alpha, m. My new proposed models will be as before, except don't permute the alphas. Also make these GB models, except without regularity and choice. I will call that theorty GB-. (GB as normally formulated includes global choice, which is strictly stronger than makng set many choices at a time as usual AC from ZFC. So I am leaving this off as well). So we define the classes of the GB- model to be ther classes over the iner set model with finite support under the group action, lifting the group action from sets to classes by extensionalilty. By leaving off the alpha permutation, I gave myself back choice functions in the cosntructed inner model, picking A_n,0 for each A_n, ie to pick among the alphas. So the [5] and [6] original models were not able to make a definition of cardinality over all the A_n,alpha 's. Now we can do this much by making C(A_n,alpha) = A_n,0 . To see how to define Card for all sets of the constructed model, not just A_n,alpha. I will define in the base model a class defining an OR length sequence of sets, which union to the universe. I will argue this class has empty support, so it becomes a class in the constructed GB- model. I will not be doing this definition inside the constructed model. Instead I work in the base model, the starting ZFC model where we defined the construction. This model has access to the indexing of the labelled constructed sets by the n,alpha,m,l . Any definition using this indexing has the potetial to define an object outside the conteructed model. But that's why I check the support at the end. So here is the definition. We use global choice in the base GB model to enumerate the universe in type OR (the ordinals), and so induce an enumeration of the sets of the constructed inner model. (We phave already constructed the inner model, I am cpnstructing a specfic class within in). Reindex the subsequence that just enumerates the inner model, to still be over OR. Suppose this sequence at ordinal alpha enumerated set a. I now form the set, the orbit of a, under the full action of ther permutation group. All permutations of n,l.m . Since I no longer permutate a proper class of alphas, these each vary over omega, these orbits are each sets and not proper classes. (If I tried the corresponding over the original [5] and [6] some of the corresponding orbits would be proper classes. That's why I modified the defnition.) So consider the class sized function, enumerating in type OR all these orbits. This class is fixed by any permutation. Any orbit just has its members moved around inside by any permutation. So this class is in our constructed GB- model. So the universe of this GB model is an OR indexed union of sets. Since every set was originally enumerated, so gets into the the orbit there. (The OR listing of orbits will not be 1-1 but that doesn't matter). So this is enough to use that class as parameter and do as Scott's trick on that hierarchy to make a definition in class parameter of class Card and satisfying Tarski's axiom. So make this class interpret Card, and we have a model of ZF - regularity + Card. It remains to be seen in this model that no formula in = , epsilon only can define cardinality. Here is the big point. I used a small permutation group not moving the alphas to define this model. But now that the model is in place, I can consider a bigger permutation group acting on it. Go back to the original permutation group from [5] and [6], including permuting the alphas. We can still make this act on the atoms of our new model and so by extensionality lift to the sets and classes. These new permutatiions, will in general move Card. But they just move it to another class in the GB- model. But we are interested in definitions of cardinality that don't use Card, only = and epsilon. This bigger group action reosects = and epsilon. To define our model with Card, I went to a GB- model, to give me other classes to give me something to send Card to. But if the theory with =, epsilon, Card had a defintion of cardinality only using =, epsilon, then the GB model would also have such a definition, only using =, epsilon. The theory under discussion for Tarski's axiom was ZF - reguilaroity style not GB- style. It didn't have many proper classes. Instead it just had one new function symbol that was like a proper class sized function : Card. I constructed a model for that by constructing a full GB- model, and interpreting Card as a proper class in that GB- model. But we are interested in the Tarski axiom thery, with only set quiantification, and Card the only symbol beyond = epsilon and sets, and we want definitions only using =, epsilon. So to relate this to the GB- theory, what this amounts to is a definition in =, epsilon only and no class parameters. I will argue there is no definition of cardinality definable in the GB- model by a formula with only set paraters and =, epsilon. By the discussion this shows in the Tarski axiom theory with =, epsion, Card there is not definition of cardinality in set parameters usnig only =, epsilon not Card. I will be using the bigger group action on the GB- model. That moves Card but that's ok since our definition didn't use Card. So for contradiction suppoose C is a cardinality definition defined in the GB- model by a formula with set parameters but no class parameters and =, epsilon but no Card. Find an n outside the finite unions of the supports of all parameters in the C defintion. By n ourside I mean no A_n,alpha,m,l is in and no f_n,alpha1,alpha2 is in. (Actuallty I could even drop those from the definition since we don't permute alpha's any more). Consider C(A_n,0). In our constucted GB- model consider TC(A_n,0). I claim this must contain some member of form A_n',alpha',m'.l' for some n' in omega also completely outsude the support of C, and alpha' ordinal, m', l' in omega. If not, it has no such members with n' = n, since n is also outside the support. The support is finite, so we could find another n' completely outside of it. The TC(C(A_n,0)) wouldn't contain anything of form A_n,alpha,m,l or of form A_n,alpha',m',l'. So consider the permutation n <-> n' and nothing else. These are both outside support C, so it is not moved. Nothing on TC(C(A_n,0)) is moved, so C(A_n,0) isn't moved. So permuting on the equation C(A_n0) = the C definition applied to A_n,0 and treating LS as constant we get C(A-n,0) = the C definition applied to A_n',0 So C(A_n,0) = C(A_n',0). As in [5] I argued members from proper classes A_n, A_n' for n ~= n' have are not isomorphic. This depended on the permutations on the n's and is not affected by the new change droping the alpha permutations. So A_n,0 and A_n',0 are not isomporphic, so C defining cardinality was not supposed to assign them same value. So TC(C(A_n,0)) must contain as member some set of form A_n',alpha',m',l' for n' completely outside support C. I don't want the 0 in A_n,0 to match that alpha'. But if it did I can find some other alpha ~= 0. Then A_n,0 and A_n,alpha are isomorpjic since the model coonstuction in [5] made it so. So C defining cardinality would assign A_n,0 and A_n,alpha the same. So I conclude TC(C(A_n,alpha)) has member A_n',alpha',m',l' , where alpha ~= alpha' one way or other. Now inside A_n' we can permute this alpha'. This permutation is no longer part of the permutation group defining the inner model, but it still acts on that model. n' was completely outside the support of C, so the C definition is not moved. As I write this I realize this new model has cross connections between the A_n 's not in the old [5] anf [6]. So permute alpha' to alpha'' also out of support C in any coordinate, ie even for diff n's. Still only finitlely many to avoid A_n,alpha only depends on n and alpha, so permute alpha' <-> alpha'' and leave A_n,alpha fixed. Also avoid support C. We can still send alpha' to a proper class of different alpha'', one at a time with alpha' <-> alpha''. Apply these in turn to A_n',alpha' member TC(C(A_n,alpha)) and get a proper class of different A_n'_alpha'' to be members of TC(C(A_n,alpha)). Contradicting that TC(C(A_n,alpha)) is a set since C(A_n,alpha) is a set. So we got a contradiction from assumuing the constructed GB- model had a definition C of cardinality from =. epsilon, even using set parameters. That concludes the proof. I haven't reread it recently, but from memory this argument is similar to the permutation argument in [5]. The idea is the same, maybe I used different variable labelling. So basically, the [5] argument was never maknig heavy use of support facts about alpha. Also, [5] was arguing that actuially no set could act on vertain elements in this fashion. Now I just arguing no definition can so act. In this new model there are sets doing it, they just aren't definable. [5] and [6] have several variant models. They were adjusted to have different side properties. The point was these adjustments did not affect the undeyling permutation argument as above. So the same will apply now. Each of those various versions in [5] and [6] could copy over into this reworking, and so get special versions in which those extra properties could be added to the theories under discussion here, as extra axioms. And with those, there is still the constructiion above against getting a cardinality definition from the axiomatic Card in Tarski's axiom. -- David Libert ah170(a)FreeNet.Carleton.CA
From: zuhair on 9 Jan 2010 09:17 On Jan 5, 5:20 pm, ah...(a)FreeNet.Carleton.CA (David Libert) wrote: > zuhair (zaljo...(a)gmail.com) writes: > > On Jan 3, 5:16=A0pm, MoeBlee <jazzm...(a)hotmail.com> wrote: > >> On Jan 2, 6:51=A0pm, zuhair <zaljo...(a)gmail.com> wrote: > > And with those, there is still the constructiion above > against getting a cardinality definition from the > axiomatic Card in Tarski's axiom. > > -- > David Libert ah...(a)FreeNet.Carleton.CA Thanks a lot David. I understand that the answer is no, hmmm,...; the outstanding question here would be if we can have a maximal definition of cardinality, informally speaking a definition of cardinality in ZF- Reg.(=,e) that is the nearest to the primitive cardinality, can there be such a thing? Lets say that "D is a Cardinal proper class", to mean that D is a proper class having every member as an ordered pair <x,card(x)> so we have the cardinal proper class of primitive cardinality which is the same as D above were card is a primitive symbol, also we can have a cardinal proper class were card is a defined symbol after some cardinality defining formula phi (in FOL(e,=)). Can we have a maximal cardinal proper class with card being defined in FOL(e,=) what I mean by maximal is supernumerous to any cardinal proper class having card defined in FOL(e,=). Is this possible? Zuhair
First
|
Prev
|
Pages: 1 2 3 4 5 6 Prev: Fitch's paradox and OWA Next: Cardinality and Hereditary sets. |