Recursive Cardinals.
in [Math]
|
Prev: Summation of 2^(1/n)-1 (or generally: x^(1/n)-1)
Next: COLLAPSIBILTY OF THE ZERO- Why Your Mathematics Paris burns? CREDIBLE DAVID BERNIER/ROBERT ISRAEL, check your mettle
From: zuhair on 7 Jan 2010 22:12 On Jan 2, 11:34 pm, Transfer Principle <lwal...(a)lausd.net> wrote: > On Dec 25 2009, 6:28 am, zuhair <zaljo...(a)gmail.com> wrote: > > > Here I have presented an example of these x-Recursive Cardinals > > were x is singleton, It shows that we cannot have > > uncountably many recursive singletons, at least at informal level, > > here these recursive singletons shall be called "singleton towers" > > As I've said earlier, I wanted to avoid these set theory debate > threads until February. But I've been lurking this thread for a > while now, and this discussion is turning out to be rather > interesting, and so I make this post now (as it may be hard to > find this thread in February). > > In this thread, zuhair declares that he is trying to define a > new type of cardinality, "recursive cardinality." We already > know that many so-called "cranks" would also like to redefine > cardinality as well, so perhaps zuhair's "recursive cardinality" > will turn out to be more acceptable to "cranks" than standard > cardinality as defined by Cantor. > > Now zuhair begins by defining a "singleton tower": > > > First, a singleton tower, or what I call a "recursive singleton" can > > be defined in the following manner: > > x is a singleton tower iff > > x is singleton & > > For all y ( y e TC(x) -> y is singleton ) & > > For all y ( y e TC(x) -> ~ y e TC(y) ) > > So singleton towers are: hereditarily non circular singleton > > hereditarily singletons. > > Then zuhair attempts to construct a "recursive singleton": > > > So in general the singleton tower xi+1 with bracket sequence of > > <i+1,i+2,i+3,....> will be the member of the singleton tower xi with > > bracket sequence of <i,i+1,i+2,i+3,...> > > I think this is clear, so we have xi+1 e xi for all singleton towers > > defined above. > > But then, as zuhair noted earlier in this thread, most > standard theories, in particular ZF, prove that no recursive > singleton exists. The well-known proof of the nonexistence of > recursive singletons uses Foundation/Regularity, and so zuhair > proceeds by working in ZF-Regularity rather than ZF. > > Yet I've mentioned in previous threads that Regularity alone > doesn't prove the nonexistence of most illfounded sets, but > usually requires additional axioms of ZF to prove. After all, > the axiom of Regularity only directly prescribes that every > nonempty be disjoint with one of its elements (its lone > element in the case of singletons). So we know that a set x > such that: > > x = {x} > > can't exist using Regularity alone, since the set x fails to > be disjoint with its lone element, namely itself. But to > prove the nonexistence of distinct sets x,y such that: > > x = {y} > y = {x} > > Regularity alone fails, since both x and y are disjoint with > their respective lone elements, namely each other. Of course, > we know that it's neither x nor y, but the set: > > z = {x, y} > > that fails to be disjoint with either of its elements. Notice > that this set is the _transitive closure_ of both x and y, > and its existence is guaranteed by the Axiom of Pairing. In > general, it's not the illfounded set itself that fails to be > disjoint with all of its elements, but its transitive closure > (or a subset thereof) that fails, and so we need other axioms > in addition to Regularity that guarantee the existence of the > transitive closure. This is why zuhair frequently refers to > the transitive closure in his posts, going so far as to > introduce the notation TC(x) for the transitive closure of x. > > So to prove that no recursive singleton exists, we must look > first at its transitive closure, as zuhair does here: > > > Now lets take the tower were i=0, i.e. x0 with bracket sequence of > > <0,1,2,3,....> > > Now what is the transitive closure of x0 > > This would be > > TC(x0)= {x1,x2,x3,..........} > > right! > > And we see that TC(x0) fails to be disjoint with any of its > elements, since (TC(x0) intersect xi) = xi+1 for any natural > number i. Thus, we can contradict the existence of x0 by > showing that its existence implies that of TC(x0). The usual > proof in ZF thereof begins by using the Axiom of Infinity to > derive the existence of an inductive set, omega. Then we use > the Replacement Schema to replace the natural number i in the > set omega with xi+1. The resulting set is TC(x0). > > Therefore the proof that no singleton tower exists requires > not just Regularity, but Infinity and Replacement Schema. So > we now have choice of three theories, namely ZF-Regularity, > ZF-Infinity, and ZF-Replacement Schema (in other words, the > theory Z+Regularity) in which to work. In any of these three > theories, the proof that no singleton tower exists falls > through, and so we may attempt to work with singleton towers. > > Of course, zuhair chose to drop Regularity, and this is what > most set theorists would do in this situation. But recall how > at the start of this post, my goal was to present zuhair's > recursive cardinality as acceptable to "_cranks_." And, given > a choice among Regularity, Infinity, and Replacement Schema > to drop, most "cranks" would choose _Infinity_ as the axiom > they'd like to drop. (Note that nearly every set theoretic > "crank" thread is basically an argument over the Axiom of > Infinity in ZF.) Notice that the general proof in ZF that > every set has a transitive closure requires Infinity. > > Thus, instead of ZF-Regularity, I will choose to work in > ZF-Infinity for the remainder of this post. This theory > should be more acceptable to "cranks," including even the > ultrafinitists, since even an ultrafinitist should have no > problem with the existence of _singletons_, since all of > these sets xi are merely singletons! (On the other hand, > sometimes I'd prefer to work with sets in which not only is > xi+1 an element of xi, but a _subset_ of xi as well, so that > we can mimic von Neumann ordinals. But we won't do so here.) > > I've attempted this approach in several previous threads, > but always seem to run into trouble. The problem is that > I want to look at the theory: > > ZF-Infinity+"a singleton tower exists" > > but the problem is that there appears to be no way to write > "a singleton tower exists" using only FOL and the language > of ZF-Infinity. For zuhair gives two definitions of his > concept "singleton tower," one using transitive closures and > the other using natural numbers as indices, but neither of > these are permitted in ZF-Infinity. Thus, even though that > there is likely a (nonstandard, of course) model of the > theory ZF-Infinity in which singleton towers exist, there's > no way to add an axiom prescribing there existence. (At > least I haven't found a way, yet.) > > In another thread, someone -- possibly either of the other > posters is this thread, Hartley or Libert -- attempted to > give a theory of nonstandard arithmetic but noting that if > Goldbach's Conjecture is undecidable in PA, then GC would be > true in the standard model of PA, and so PA+~GC would give a > theory of nonstandard arithmetic. The language of the theory > would add an additional symbol "w" to the language of PA, > and w would be treated as a nonstandard natural number and a > counterexample of GC. But to me, this is unsatisfactory as > we don't _know_ whether GC is decidable in PA or not. I'd > prefer a statement that is _known_ to be undecidable in PA, > perhaps Goodstein's Theorem, and let "w" be a counterexample > to Goodstein rather than Goldbach. > > And so we'd like to do the same in this set theory, adding > the symbol "ST" to the language of ZF-Infinity and stipulate > that ST is a singleton tower. But we can't do so unless we > know how to write "there exists a singleton tower" as a > (first-order) axiom in the language of ZF-Infinity. > > Thus concludes this post for now. For February, I've already > stated that I'll return to working on the problem of finding > a rigorous definition of the "crank" ellipsis, and so I'll > work of that before returning to "recursive cardinality" for > the "cranks." > > (BTW, someone asked me what a "crank" ellipsis is, so let me > answer that. We know that in standard analysis, some real > numbers, such as 1/3, cannot be written in decimal notation > with only finitely many digits, and so one often resorts to > using an ellipsis, so 1/3 = 0.333... now. But some "cranks" > want to extend the standard ellipsis in order to include > nonstandard reals such as 0.333...3, and often numbers such > as 0.999...9 as distinct from unity, with the difference > being something like 0.000...1. The "crank" ellipsis problem > entails finding a rigorous definition of ellipsis so that > these claims are provable.) Thanks lwal, that was a nice account. Zuhair
From: zuhair on 8 Jan 2010 00:32
On Jan 3, 2:21 am, ah...(a)FreeNet.Carleton.CA (David Libert) wrote: > Transfer Principle (lwal...(a)lausd.net) writes: > > On Dec 25 2009, 6:28=A0am, zuhair <zaljo...(a)gmail.com> wrote: > > [Deletion] > > > Now zuhair begins by defining a "singleton tower": > > >> First, a singleton tower, or what I call a "recursive singleton" can > >> be defined in the following manner: > >> x is a singleton tower =A0iff > >> x is singleton & > >> For all y ( y e TC(x) -> y is singleton ) & > >> For all y ( y e TC(x) -> ~ y e TC(y) ) > >> So singleton towers are: hereditarily non circular singleton > >> hereditarily singletons. > > > Then zuhair attempts to construct a "recursive singleton": > > >> So in general the singleton tower xi+1 with bracket sequence of > >> <i+1,i+2,i+3,....> will be the member of the singleton tower xi with > >> bracket sequence of <i,i+1,i+2,i+3,...> > >> I think this is clear, so we have xi+1 e xi for all singleton towers > >> defined above. > > > But then, as zuhair noted earlier in this thread, most > > standard theories, in particular ZF, prove that no recursive > > singleton exists. The well-known proof of the nonexistence of > > recursive singletons uses Foundation/Regularity, and so zuhair > > proceeds by working in ZF-Regularity rather than ZF. > > > Yet I've mentioned in previous threads that Regularity alone > > doesn't prove the nonexistence of most illfounded sets, but > > usually requires additional axioms of ZF to prove. After all, > > the axiom of Regularity only directly prescribes that every > > nonempty be disjoint with one of its elements (its lone > > element in the case of singletons). So we know that a set x > > such that: > > > x =3D {x} > > > can't exist using Regularity alone, since the set x fails to > > be disjoint with its lone element, namely itself. But to > > prove the nonexistence of distinct sets x,y such that: > > > x =3D {y} > > y =3D {x} > > > Regularity alone fails, since both x and y are disjoint with > > their respective lone elements, namely each other. Of course, > > we know that it's neither x nor y, but the set: > > > z =3D {x, y} > > > that fails to be disjoint with either of its elements. Notice > > that this set is the _transitive closure_ of both x and y, > > and its existence is guaranteed by the Axiom of Pairing. In > > general, it's not the illfounded set itself that fails to be > > disjoint with all of its elements, but its transitive closure > > (or a subset thereof) that fails, and so we need other axioms > > in addition to Regularity that guarantee the existence of the > > transitive closure. This is why zuhair frequently refers to > > the transitive closure in his posts, going so far as to > > introduce the notation TC(x) for the transitive closure of x. > > > So to prove that no recursive singleton exists, we must look > > first at its transitive closure, as zuhair does here: > > >> Now lets take the tower were i=3D0, i.e. x0 with bracket sequence of > >> <0,1,2,3,....> > >> Now what is the transitive closure of x0 > >> This would be > >> TC(x0)=3D {x1,x2,x3,..........} > >> right! > > > And we see that TC(x0) fails to be disjoint with any of its > > elements, since (TC(x0) intersect xi) =3D xi+1 for any natural > > number i. Thus, we can contradict the existence of x0 by > > showing that its existence implies that of TC(x0). The usual > > proof in ZF thereof begins by using the Axiom of Infinity to > > derive the existence of an inductive set, omega. Then we use > > the Replacement Schema to replace the natural number i in the > > set omega with xi+1. The resulting set is TC(x0). > > > Therefore the proof that no singleton tower exists requires > > not just Regularity, but Infinity and Replacement Schema. So > > we now have choice of three theories, namely ZF-Regularity, > > ZF-Infinity, and ZF-Replacement Schema (in other words, the > > theory Z+Regularity) in which to work. In any of these three > > theories, the proof that no singleton tower exists falls > > through, and so we may attempt to work with singleton towers. > > Yes, that's right. In ZF, refuting singleton towers depends > on all three of regularity, infinity and replacement. > > As you say, by dropping any one we can then get models > with singleton towers (if ZF is consistent). > > > Of course, zuhair chose to drop Regularity, and this is what > > most set theorists would do in this situation. But recall how > > at the start of this post, my goal was to present zuhair's > > recursive cardinality as acceptable to "_cranks_." And, given > > a choice among Regularity, Infinity, and Replacement Schema > > to drop, most "cranks" would choose _Infinity_ as the axiom > > they'd like to drop. (Note that nearly every set theoretic > > "crank" thread is basically an argument over the Axiom of > > Infinity in ZF.) Notice that the general proof in ZF that > > every set has a transitive closure requires Infinity. > > > Thus, instead of ZF-Regularity, I will choose to work in > > ZF-Infinity for the remainder of this post. This theory > > should be more acceptable to "cranks," including even the > > ultrafinitists, since even an ultrafinitist should have no > > problem with the existence of _singletons_, since all of > > these sets xi are merely singletons! (On the other hand, > > sometimes I'd prefer to work with sets in which not only is > > xi+1 an element of xi, but a _subset_ of xi as well, so that > > we can mimic von Neumann ordinals. But we won't do so here.) > > > I've attempted this approach in several previous threads, > > but always seem to run into trouble. The problem is that > > I want to look at the theory: > > > ZF-Infinity+"a singleton tower exists" > > > but the problem is that there appears to be no way to write > > "a singleton tower exists" using only FOL and the language > > of ZF-Infinity. For zuhair gives two definitions of his > > concept "singleton tower," one using transitive closures and > > the other using natural numbers as indices, but neither of > > these are permitted in ZF-Infinity. Thus, even though that > > there is likely a (nonstandard, of course) model of the > > theory ZF-Infinity in which singleton towers exist, there's > > no way to add an axiom prescribing there existence. (At > > least I haven't found a way, yet.) > > You are right. It is hard in this theory to even define > what a singleton tower is. > > Zuhair have a definition above. But he was working in > ZF - regularity, so he had infinity and replacement. > > Based on those two, he had transitive closures exist > and are definable, so he could use them in his definition > of singleton tower. > > I think I have a reasonable way to proceed in the theory > ZF - infinity. > > In this theory we can't prove transitive closures exist > as a set. > > It is not even so easy at first to define transitive > closures as a definable class. > > The obvious way to define transitive closure of x, > TC(x) as a class would be the class of all y such that > there is a finite sequence of membership from x to y. > > But that depends on having a definition of finite. > > The usual definition of finite, with axiom of infinity > available, would be having cardinality a member of omega. I think you meant ...having *finite* as a member of omega. Actually the definition of "finite" has nothing to do with weather omega exist or not. The standard definition which is after one of Tarski's definitions of 'finite' is: x is finite iff x is equinumerous to some natural number. The definition of 'natural number' has no reference to omega at all. x is a natural number iff x is ordinal & for all y ((y subset of x & y is ordinal & ~y=0) -> Uy e y ). as one can see, Omega has nothing to do with this definition at all. Or even a better definition of "finite" which is equivalent to the above in Z would be: x is finite iff Exist R ( R is well ordering on x & converse(R) is well ordering on x ) besides many other ways to do that. Zuhair > > This doesn't work in ZF - infinity. > > I think I do have a reasonable definition of TC(x) > as a class in ZF - infinity. > > It is trying to formalize the idea above: a finite > chain of membership from x to y. > > Any first order formalization will never fully capture > this full definition as seen from outside models. > > But I think this one is a reasonable first order > approximation, just as the usual ZF definition > of omega is a reasonable first order approximation > to the notion of the set of finite ordinals, even > though there are nonstandard models of ZF with > interpretion of the omega definition including more > than finite ordinals as viewed from outside the model. > > So here is the proposed definition of the class > TC(x) in ZF - infinity. > > TC(x) is the class of those y such that there exists > a set A such that > A is linearly ordered by set inclusion & > that linear ordering on A has smallest and largest > elements & > {x} is a member of A & > {x} is the smallest member of A by set inclusion & > y is a member of the largest element of A by set > inclusion & > every member of A other than the largest element has > an immediate successor by set inclusion & > every member of A other than {x} has an immediate > predecessor by set inclusion & > for every members B, C of A, if B is immediate > predecessor of C then there is some z > such that C = B union {z} and z is not member > of C & > for every C, D members of A if C is immediate > predecessor of D and for z1, z2 such that > (C = {x} and z1 = x > or > there exists B in A such that B is immediate > predecessor of C and C = B union {z1} > and z1 not member of B) & > D = C union {z2} and z2 not member C > then z2 member of z1 & > if C is the largest member of A by set inclusion > and B is the immdediate successor of C then > C = B union {y} & > every subset E of A has a smallest element with > respect to set inclusion . > > The set A above will code a finite sequence of distinct > members in a chain from x to y. > > The coding above assumes A has more than one member. > > If x member x we would want to use instead {{x}} > as the sequence, which my coding above won't allow for. > > But I am working over ZF - infinity, so x member x > is imposible. > > If you want this to work also without regularity and > handle x member x, easiest is disjunct the above > with disjunct : x member x and y = x . > > That last conjunct above about E is trying to say in > first order that A is well-founded with respect to > set inclusion. > > So a "well-founded" linear order with immediate > successors and predecessors except at endpoints, > this is trying to formalize A being finite. > > This definition is strong enough to allow proofs > by induction on all TC(x) members by level of > membership nesting below x. > > So I think this is a reasonable first order coding > of TC(X). > > If you add back in infinity, and have the usual > definition of TC(x), that theory proves the two > TC(x) definitions are equivalent. > > So accepting for the moment this formalization > of TC(x), we can now repeat Zuhair's definition > of singleton tower, using this TC(x) where Zuhair's > definition used TC(x). > > So we come to a definition in ZF - infinity > of what a singleton tower is. > > And it is possible to construct a model of > ZF - infinity + there is a singleton tower. > > This even with regularity in the constructed model. > > I did that in > > [1] David Libert > "Axiom of infinity and the set of all hereditary finite sets" > sci.logic Oct 3, 2007 > http://groups.google.com/group/sci.logic/msg/7593d4adf17732b7 > > Note, as [1] explictly noted, this is also a model with a set > x having no set TC(x). > > [Deletion] > > > And so we'd like to do the same in this set theory, adding > > the symbol "ST" to the language of ZF-Infinity and stipulate > > that ST is a singleton tower. But we can't do so unless we > > know how to write "there exists a singleton tower" as a > > (first-order) axiom in the language of ZF-Infinity. > > I think above was a reasonable try at that. > > [Deletion] > > -- > David Libert ah...(a)FreeNet.Carleton.CA |