arithmetic in ZF
in [Logic]
|
Prev: What is wrong with this argument?
Next: Courage?
From: Barb Knox on 27 Apr 2005 03:15 In article <1114578134.863164.264280(a)l41g2000cwc.googlegroups.com>, "Ross A. Finlayson" <raf(a)tiki-lounge.com> wrote: [snip] >For some's perception of standards of truth, >the powerset result, to begin as applied to infinite sets, does not >hold (true). Which "powerset result"? I don't see any intuitive objection to he *existence* of the powerset of any given set, since if some set exists then subsets of that set equally exist, and the powerset it just the collecting together of those subsets. If the result you mean is that the powerset is always strictly larger than its underlying set, then there are decent set theories in which that is not the case (e.g. NFU), so if you object to that powerset result maybe you should work with NFU rather than ZFC. (BTW, NFU+Infinity+Choice and ZFC have been proven to have equivalent power). [snip] >Consider. > >a. The proper class would be necessarily unique. Phrased that way, "the" *anything* is being presupposed to be unique by the grammer of the statement. But in actual fact, in ZF "proper classes" are just predicates (over sets) with eliminable definitions, and there are many of these; and in MK there are also many proper classes. >b. Quantification over sets implies a a universal set. Not per se. As you know, in ZF there is a universal proper class but not a universal set. In NFU there *is* a universal set. It looks like NFU is more conducive to your preferred way of thinking; and Randall Holmes' introductory NFU book is now available online: <http://math.boisestate.edu/~holmes/holmes/head.ps>. >c. To theories with no non-logical axioms, of which there is obviously >only one, the results of Goedelian incompleteness do not apply. True, but then the only theorems are the universal validities, which say nothing at all about sets, numbers, or any other mathematical subject-matter. >d. An incomplete theory is inconsistent. No. For example PA is probably consistent, and if so is also (by Goedel) incomplete. But every inconsistent theory is complete (for whtever that's worth). >e. An inconsistent theory does not contain any truths. It has no models, so certainly in that sense it has /a fortiori/ no model-theoretic truths. But I suspect you're meaning something else. [snip] -- --------------------------- | BBB b \ Barbara at LivingHistory stop co stop uk | B B aa rrr b | | BBB a a r bbb | Quidquid latine dictum sit, | B B a a r b b | altum viditur. | BBB aa a r bbb | -----------------------------
From: Ross A. Finlayson on 27 Apr 2005 04:26 Hi Barb, Those are some good points, although I don't totally agree because I actually say that some of these statements affect _any_ theory. In ZF, and I'm not a particular expert, in ZF, many ask "where's my universal set", and so a standard extension of ZF is "ZF with classes". I'm against ZF with classes, it illustrates in a way the slippery slope fallacy, something like the "set of all sets" brings in a systemic inconsistency to ZF, largely for reasons of the powerset bijection result, so a new collection called a "class" is used instead of "set". They might then ask: where's the class of all classes? At that point, promoters of ZF with classes vary in respose among catatonia, abject denial, barking, handwaving, and subtle and not-so-subtle hints that a theory without the axiom of regularity might better suit the learner's proclivity towards rationality and the importance of reason within studies of mathematical logic in deep foundations. You suggest to consider NFU, among various other developing theories, it has basically "small" and "large" infinities, with the full complement of all the transfinite cardinals, small infinities, and then more infinities besides to which the powerset result doesn't apply, large infinities. I don't very well agree with that theory, I think that if Skolemization as is being discussed here would apply to any infinite sets, then any set that is infinite is "large". I prefer the Axiom-Free Set Theory, where theorems of ZF not using regularity are theorems, where each infinite set is irregular or with dually represented elements, as the ur-element is the singular proper class, dually minimal and maximal often as the empty set or universal set, and the computer is the anticomputer: through the looking glass. In considering those statements, and I assert that they're each true, one purpose of stating them in that manner is to illustrate some plain language statements, with acceptably specific technical terms, that are completely restrictive over all possible theories. I hope not to be detracting from the specific technical considerations of arithmetic in ZF. There is much to it. Ross
From: george on 27 Apr 2005 14:05 > ANY infninite set CAN be MADE to be the domain of *a* model of ZF. > ZF has a model whose domain is the natural numbers, in which every set, > no matter how huge and uncountable it may be, is encoded as a natural > number. Bhupinder Singh Anand wrote: > Interesting. The above appears to hold that every set is denumerable!? *Appears* to, yes. In this particular case, appearances are deceiving. The point is that this is only one countable model of the theory and its terms. There are other bigger models that come closer to getting it right. > Is this intentional? No, quite the opposite -- it is upsetting, some would even say embarrassing. When it was first discovered it was so scary that it was dubbed "Skolem's Paradox". Please Google that phrase if you want to investigate the history. Personally I found it fascinating. Not fascinating enough to actually write a dissertation on, though (even though I did major in philosophy of language as an undergrad) -- that honor goes to one Timothy Bays of Notre Dame. The abstract of his dissertation is at http://www.nd.edu/~tbays/professional/abstract.html This paradox arises not out of anything weird about sets but rather about the fact that we are using first-order logic over a first-order langauge to talk about them, and the usual definition of a first-order language requires the LANGUAGE to be countable: conjunctions and disjunctions and quantifier-prefixes all MUST be FINITELY long, in order to be well-formed. Within any single term, functions and predicates MUST be applied to a FINITE number of arguments. This means that there are only denumerably many TERMS available in the [first-order] LANGUAGE of ZF. The fact that you must have a denumerable model (if you have a model at all) is just a very basic corollary of the fact that you are talking in a denumerable language. It's an accidental artifact from your [formal/linguistic] machinery. > > G>> We have somewhat lost the original thrust of your argument, which > was, basically, that by translating PA into ZF,we can decide > arithmetic. <<G > Not merely by 'translating', but by defining a domain in which the ZF > translations of PA formulas can be effectively defined as 'true' or > 'false'. Well, we know the natural numbers are in some sense the "right" domain. And "the set required-to-exist-by-ZF's-axiom-of-infinity" is in some sense the "right" ZF-representation of that domain. But it turns out that first-order ZF is still not strong enough to pin down either of these. And it wouldn't help even if it could. WHAT your domain is is simply never the issue; it's how the interpretation maps different parts of it to each other that matters. ZF in general is incomplete. There is no algorithm for telling whether something is or isn't a theorem of ZF. ZF's sets are so hugely infinite that even specifying them is a challenge, let alone evaluating infinitary predicates over them. > G>> You were apparently hoping that some individual model of ZF would > decide the sentences that PA didn't prove or disprove. <<G > > The problem that I find in every individual model of ZF is that we need > some effective method for deciding whether a ZF proposition is 'true' > or 'false' in the model. This is indeed a problem. > If the domain of every model of ZF is, again, > a ZF set - as I understand you to suggest - then there seems to be an > element of circularity involved in such decidability. My "suggestion" was extreme. My point was simply that ZF allows a lot of powerful reasoning to be brought to bear, for ANY theory, upon its models and their behavior, PROVIDED you are willing to satisfy ZF's demands. ZF's primary demand is that EACH thing in the universe be thought of as a set, while ALL things (collectively) in the universe canNOT be thought of as a set. If it is ZF itself that you are trying to study, this demand becomes philosophically unreasonable. But for all smaller theories, it is no loss. > I was seeking to avoid such circularity by attempting to define the > 'truth' and 'falsity' of PA propositions in terms of ZF-provability in > a model of PA, not in terms of ZF-truth in some model of ZF. Yes, that is a good way to avoid the ciruclarity, but it is not a good way to achieve the decidability. The problem with doing it that way is that for any sentence that is not provable from PA, you can use ZF to define 1 model of PA that ZF-provably decides the sentence one way, and you can use ZF to define another model of PA that ZF-provably decides the same sentence the opposite way. And you can design both of these differing models with the SAME domain. And it is provable in ZF that all of this is doable. In what follows, you try to rebut that via a non-standard model. I will have to address that separately.
From: george on 27 Apr 2005 14:40 Bhupinder Singh Anand wrote: > These, no doubt, reflect accepted interpretations of Goedel's > incompleteness theorem. > > However, the questions arise: Are such interpretations definitive, and > are there substantive grounds for seeking alternative interpretations > of Goedel's reasoning? > > For instance, consider Goedel's 'unprovable but true' PA formula > [(Ax)R(x, p)]. > > This is unprovable from the axioms of Peano Arithmetic, but such that > [R(n, p)] is provable for any given numeral [n]. Right. The first question this raises is, "How can this be?! How is this even possible?" If the numerals [n] are the ONLY things in the domain, then the truths of all these R(n,p) ARE, collectively, equivalent to the truth of Ax[ Rxp ]. We KNOW that Ax[ Rxp ] is true in this case. So why can't we prove it? The first problem is that there are models of PA in which there are MORE things than the natural numbers. These things are all greater-than all the natural numbers. I, personally, therefore, like to say that non-standard models of PA contain "supernatural" numbers. In these models, Rsp will be false for some super- natural s (and it will not be provable, although ~Rsp may be), so Ax[ Rxp ] will be false. By FOL's *completeness* theorem, the fact that there are models where Ax[ Rxp ] is false entails that Ax[ Rxp ] is not provable. The second problem is that even when the [n] are the only thing in the domain, you STILL can't use them to PROVE Ax[ Rxp ], because FOL also has a *compactness* theorem associated with the fact that proofs and conjunctions HAVE to be FINITE. You can't combine all these R(n,p) into one long conjunction and try to prove Ax[ Rxp ] from that, because it would be infinitely long, and conjunctions have to be finite. And you can't prove it from the infinite collection of R(n,p) premises because the inference rules of FOL don't take infinitary inputs; anything that you can prove, in FOL, from an infinite set of premises, you can ALSO prove from a finite subset of those premises. So, now, at least, we know why the problem is arising. > Hence, under the > standard interpretation, the corresponding arithmetical proposition, > R(x, p), is true for any given natural number n. .... > Now, by definition, the arithmetical relation R(x, p) is > instantiationally equivalent to the primitive recursive relation > ~xB(Sb(p 19|Z(p))). > > Further, again by Goedel's definitions, the primitive recursive > relation, ~xB(Sb(p 19|Z(p))), symbolically expresses the assertion > that: > > (*) x is not the Goedel number of a PA-proof of [(Ax)R(x, p)]. > > Since Goedel has shown that R(x, p) is true for all natural numbers - > as also is ~xB(Sb(p 19|Z(p))) - it follows that the assertion (*) is > true for all natural numbers, and, so, there is no proof of the > PA-proposition [(Ax)R(x, p)] from the axioms of PA. > > Now, if we add [~(Ax)R(x, p)] as an additional axiom to PA, we would > get a system PA+[~(Ax)R(x, p)]. > > Under its standard interpretation, [~(Ax)R(x, p)] would interpret as > asserting that ~R(x, p) is true for some natural number n. Under the standard interpretation, yes. The point is that there are non-standard interpretations, and provability is only available for things that hold under both the standard AND non-standard interpretations. > Hence nB(Sb(p 19|Z(p))) would hold, and so n would be the > Goedel number of a PA-proof of [(Ax)R(x, p)]. In the non-standard models, there is such a thing, but it is not an n; it is not a natural number. It is bigger than every natural number. It is not finite. In some sense this means that it CANNOT encode a "real", true, STANDARD proof, because what we INTENDED by proof was something that HAD to be finite. The problem is, finitude is not definable in first-order PA (or in first-order ZF either, it turns out, although one CAN get a HECK of a lot closer). > Since this is false, it follows that PA+[~(Ax)R(x, p)] has no model and > is, therefore, inconsistent. PA+[~(Ax)R(x, p)] does indeed have models. In them, the x for which R(x,p) comes up false is not a natural number. For more than you ever wanted to know about these models, consult "Models of Peano Arithmetic" by R.W.Kaye (1991) (Oxford Logic Guides).
From: Chris Menzel on 27 Apr 2005 16:17
On Wed, 27 Apr 2005 19:15:44 +1200, Barb Knox <see(a)sig.below> said: > [Finalyson said]: >>d. An incomplete theory is inconsistent. > > No. For example PA is probably consistent, and if so is also (by Goedel) > incomplete. We scarcely need a counterexample here, as the consistency of an incomplete theory follows almost immediately from the definitions of "consistent" and "complete". But if Ross insists on a counterexample, we don't need anything so powerful as PA; plain old first-order logic (a.k.a. Ross's "No Axiom Theory") will do. (Note we're talking about *negation* completeness here.) Chris Menzel |