An Ultrafinite Set Theory
in [Theory]
|
Prev: Now Win a laptop computer from (EZ laptop) free of charge
Next: Prizes worth 104,000 INR at stake for RAD. Certificates to all participants.
From: RussellE on 9 Mar 2010 18:08 On Mar 9, 8:16 am, MoeBlee <jazzm...(a)hotmail.com> wrote: > On Mar 8, 9:26 pm, RussellE <reaste...(a)gmail.com> wrote: > > > On Mar 8, 5:27 pm, MoeBlee <jazzm...(a)hotmail.com> wrote: > > > It's a theorem that if a theory has arbitrarily large finite models > > > then it has an infinite model. The proof is available in virtually any > > > textbook on mathematical logic. > > > Would this forbid a theory which doesn't allow arbitrarily large > > models? > > First, to be clear, I should have mentioned that I'm referring to > first order theories in this context. (So, in this context, when I say > 'theory', that is short for 'first order theory'). > > Now, to answer your qutestion: If a theory has an infinite model, then > it has arbitrarily large infinite models. And, if a theory has > arbitrarily large finite models, then it has an infinite model, so it > has arbitrarily large infinite models. On the other hand, there are > theories that only have models less than a certain finite cardinality, > so those theories don't have arbitrarily large models. Thanks! I would consider a theory where the only models are less than a certain finite cardinality to be an ultrafinite theory. Could you point me to references about such theories? Russell - Mathematics is the only true religion
From: MoeBlee on 9 Mar 2010 20:09 On Mar 9, 5:08 pm, RussellE <reaste...(a)gmail.com> wrote: > On Mar 9, 8:16 am, MoeBlee <jazzm...(a)hotmail.com> wrote: > > On Mar 8, 9:26 pm, RussellE <reaste...(a)gmail.com> wrote: > > > > On Mar 8, 5:27 pm, MoeBlee <jazzm...(a)hotmail.com> wrote: > > > > It's a theorem that if a theory has arbitrarily large finite models > > > > then it has an infinite model. The proof is available in virtually any > > > > textbook on mathematical logic. > > > > Would this forbid a theory which doesn't allow arbitrarily large > > > models? > > > First, to be clear, I should have mentioned that I'm referring to > > first order theories in this context. (So, in this context, when I say > > 'theory', that is short for 'first order theory'). > > > Now, to answer your qutestion: If a theory has an infinite model, then > > it has arbitrarily large infinite models. And, if a theory has > > arbitrarily large finite models, then it has an infinite model, so it > > has arbitrarily large infinite models. On the other hand, there are > > theories that only have models less than a certain finite cardinality, > > so those theories don't have arbitrarily large models. > > Thanks! > I would consider a theory where the only models are less > than a certain finite cardinality to be an ultrafinite theory. > Could you point me to references about such theories? Just pick up a book on mathematical logic. Here's an axiomatization of theory that has only models of cardinality 1: Axy x=y. So what? MoeBlee
From: FredJeffries on 9 Mar 2010 21:42 On Mar 9, 3:08 pm, RussellE <reaste...(a)gmail.com> wrote: > > Thanks! > I would consider a theory where the only models are less > than a certain finite cardinality to be an ultrafinite theory. > Could you point me to references about such theories? > http://www.csc.liv.ac.uk/~sazonov/papers.html See especially "On Feasible Numbers" http://www.csc.liv.ac.uk/~sazonov/papers/lcc.ps and the slides from a lecture where it is discussed http://www.csc.liv.ac.uk/~sazonov/papers/lcc-sli-07.ps
From: RussellE on 10 Mar 2010 15:37 On Mar 9, 6:42 pm, FredJeffries <fredjeffr...(a)gmail.com> wrote: > On Mar 9, 3:08 pm, RussellE <reaste...(a)gmail.com> wrote: > > > > > Thanks! > > I would consider a theory where the only models are less > > than a certain finite cardinality to be an ultrafinite theory. > > Could you point me to references about such theories? > > http://www.csc.liv.ac.uk/~sazonov/papers.html > > See especially "On Feasible Numbers"http://www.csc.liv.ac.uk/~sazonov/papers/lcc.ps > and the slides from a lecture where it is discussedhttp://www.csc.liv.ac.uk/~sazonov/papers/lcc-sli-07.ps Thank you for the reference. I notice Sazonov says modus ponens can't be true in an ultrafinite theory. If it were, it would be possible to prove the existence of infeasible numbers. Modus ponens does not hold in some three value logics. Assume we have the truth values: True, False, and Unknown. We can easily come up with truth tables for this logic. If A is False and B is Unknown, A AND B is False. If A is True and B is Unknown, A AND B is Unknown. etc. From these truth tables we can derive a three value logic version of modus ponens. Given A is True and A IMPLIES B, we can deduce B is True or Unknown. In this logic, we can not eliminate the possiblity B is Unknown using modus ponens. Replacing Unknown with Infeasible might be a workable system. Sazonov also writes about "small" natural numbers. Let N={0,1,2,3} be a set of small natural numbers. Define "finite" addition as no more than one addition per member of a set. How large does a set have to be to "complete" finite addition for a set of small natural numbers? The largest finite addition for N is 3+3+3+3. So, we can always complete finite addition for set N with a set of size |N| * (|N|-1). This shows not all mathematical operations are equal in an ultrafinite theory. I would need a much larger set to complete finite exponentiation: 3^3^3^3 Assume I have a finite set of natural numbers. I can now define the set of "small" natural numbers as the set for which finite addition is complete. Russell - 2 many 2 count
From: Transfer Principle on 12 Mar 2010 01:58
On Mar 10, 12:37 pm, RussellE <reaste...(a)gmail.com> wrote: > On Mar 9, 6:42 pm, FredJeffries <fredjeffr...(a)gmail.com> wrote: > > See especially "On Feasible Numbers"http://www.csc.liv.ac.uk/~sazonov/papers/lcc.ps > > and the slides from a lecture where it is discussedhttp://www.csc.liv.ac.uk/~sazonov/papers/lcc-sli-07.ps > Sazonov also writes about "small" natural numbers. I decided not to post in this thread for a few days, in order to let RE answer the standard theorists' questions without any of my interference. > Let N={0,1,2,3} be a set of small natural numbers. > Define "finite" addition as no more than one addition per member of a > set. > How large does a set have to be to "complete" finite addition > for a set of small natural numbers? > The largest finite addition for N is 3+3+3+3. > So, we can always complete finite addition for set N > with a set of size |N| * (|N|-1). Interestingly enough, these last few posts by RE sound _very_ similar to what Archimedes Plutonium has been posting lately. In the past few months, AP has turned towards ultrafinitism. We compare this post of RE's to an AP post from the last day of January (8:25AM, Greenwich time): "For in Algebra, if we use the 100-Model, that there is a clearcut boundary or upper limit to multiplication in that 10 x 10 is the upper limit and we cannot be doing 11x 10. We can do 11 x 9. So I am wondering if the 8.3% is a sort of reflection of the 9 x 9 = 81 and allowed in the 100-Model but that the true upper bound is the square root of 100 = 10." By "100-Model," AP refers to the model of some ultrafinitist theory in which the largest number is 100. In this theory, AP states that the largest possible multiplication is 10x10. We compare this to RE's post, in which he gives a model in which the largest number is 12 and the largest multiplication is 3x4. Both AP and RE realize that if M is the cardinality of their model, then sqrt(M) is an upper bound on the numbers which can be multiplied in their models. AP would say something like, multiplication stops working past 10, while RE writes that three is the largest "small" natural number. Of course, AP doesn't actually believe that 100 is the largest number any more than RE believes that twelve is. Both are using these as examples for their main model which has a much larger upper bound. For AP, this upper bound is 10^500. So far, RE has yet to settle on what he wants his upper bound to be. In this thread, Virgil argues that one problem with setting a fixed upper bound is that the universe is expanding. Therefore, if an ultrafinitist chose, say, the diameter of the known universe in Planck units, or even the volume of the known universe in cubic Planck units, that number is always changing, and so it would be a lousy upper bound for physics. (Of course, an expanding universe stems from the Big Bang Theory -- a theory to which AP doesn't subscribe. Instead, AP believes in his own Atom Totality Theory. I'm not sure what adherents of Atom Totality say about the changing size of the universe, since a plutonium atom doesn't expand in the same way that Big Bangers say that the universe is expanding. Since I'm not an Atom Totalitarian, I have nothing more to say about this save that the upper bound 10^500 is suspect due to its connection to Atom Totality.) But RE was interested in a theory which has arbitrarily large finite models -- that way, if the universe expands sufficiently , or there's some other need in physics for a larger number, then we can just switch to a larger model. But the standard theorists point out that theories with arbitrarily large finite models also have infinite models, and thus models of all alephs as cardinality, via compactness and Lowenheim-Skolem. This is unacceptable to the ultrafinitist RE, and so we need a theory with a fixed upper bound M on the cardinality of any of its models. MoeBlee gives a theory for which M=1 -- that darned theory whose lone axiom is "Axy (x=y)." Of course, M=1 is much too small -- we seek a theory in which M exceeds the largest number that can ever appear in physics, no matter how large the universe expands. So we ask, how large is a suitable value of M? AP gives 10^500 (but we reject this due to Atom Totality). RSA gives around 2^2048 (which is about 10^617) as the largest number that currently appears in the science of cryptography. Some standard theorists have suggested the possibility of numbers in which the above appear as exponents (such as 10^10^500 or 2^2^2048) appearing in physics. Then again, some number such as Graham's Number are so large that it seems inconceivable that there's a need for a number larger than Graham's Number in any science. We can do much better than Graham's Number as our M. > This shows not all mathematical operations are equal > in an ultrafinite theory. I would need a much larger set > to complete finite exponentiation: > 3^3^3^3 Since RE mentions this number (which is also known as 3^^4, to be read "three tetrated to the four"), maybe this is a suitable upper bound M for our theory. So now we search for a theory such that the largest possible model for the theory has cardinality 3^^4. (Note that 3^^4 still falls short of the number 10^10^500 that I alluded to above.) I'm actually partial to tetrations of _two_, rather than _three_, as cardinalities for our models, since these are exactly the cardinalities of the finite sets of the cumulative hierarchy V_n (where card(V_(1+n)) = 2^^n). The set V_7 has cardinality 2^^6, which is larger than all of the numbers that I've mentioned so far in this post (save Graham's Number). So it may be helpful to find a theory T such that V_7 is a model of T. (Note the similarity to ZF-Infinity having a model V_omega, NBG-Infinity having a model V_(omega+1), PST having a model V_(omega+2), ZF-Replacement Schema having a model of V_(omega+omega), and so on.) |