Fitch's paradox and OWA
in [Logic]
|
From: Marshall on 31 Dec 2009 16:53 On Dec 31, 11:22 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > Marshall says... > > > > >On Dec 31, 7:10=A0am, stevendaryl3...(a)yahoo.com (Daryl McCullough) > >wrote: > >> I don't see a rule saying f |- []f. Where did you see that? > > >He didn't say that there was an explicitly stated rule of > >that form. He said that in step 8 of the derivation, they > >use a rule that was explicitly stated as > > If |- f then |- []f > >but they use it *as if* the rule was > > f |- []f > > No, I don't think they did that. What they did was > to assume K(p & ~K(p)), and show that that leads to > a contradiction. That's a proof of ~K(p & ~K(p)). > So we have |- ~K(p & ~K(p)). Then we can apply the > rule "If |- f, then |- [] f" to conclude > []~K(p & ~K(p)) Certainly steps 4 - 9 constitute an RAA proof with the assumption being K(p & ~K(p)). However what I was referring to was specifically how they get from step 7 to step 8 within that RAA proof. Your response does not seem to address that particular issue. Are your comfortable with how step 8 is obtained from step 7 via Rule C as described on this page? http://plato.stanford.edu/entries/fitch-paradox/ It's entirely possible that I misunderstand Jan Hidder's point, or rule C, or something else entirely, however I would like to at least feel that we were discussing the same step in the proof. Marshall
From: Marshall on 31 Dec 2009 18:27 On Dec 31, 1:08 pm, Barb Knox <Barb...(a)LivingHistory.co.uk> wrote: > Marshall <marshall.spi...(a)gmail.com> wrote: > > On Dec 30, 8:16 pm, Barb Knox <s...(a)sig.below> wrote: > > > Marshall <marshall.spi...(a)gmail.com> wrote: > > > > By the nature of the construction of predicate logic, every arithmetic > > > formula must be either true or false in the standard model of the > > > natural numbers. > > > > But, we have no satisfactory way to fully characterise that standard > > > model! We all think we know what the natural numbers are, but Goedel > > > showed that there is no first-order way to define them, and I don't know > > > of *any* purely formal (i.e., syntactic) way to do do. > > > I was more under the impression that Goedel showed there > > was no complete finite theory of them, rather than no > > way to define them. Are you saying those are equivalent? > > Yes, in this context. Since we are finite beings we need to use finite > systems. I have no disagreement with the point about finiteness, but I don't see how that point leads to saying that a theory is the same thing as a definition. That is rather tantamount to saying that theories are all there are, and that's just not true. There are things such as computational models, for examples. It seems entirely appropriate to me to use a computational model as the definition of something, which is why I gave a computational model of the naturals as a definition. Perhaps worse, if it's not possible to have a definition of anything, then I don't see how you can have any theories, either. Theory of what? If you have no definition, I don't see how you can even claim to have an object under discussion. > > > (The usual ways > > > to define them are not fully syntactic, but rely on "the full semantics" > > > of 2nd-order logic, or "a standard model" of set theory, both of which > > > are more complicated than just relying on "the Standard Model" of > > > arithmetic in the first place.) > > > Here's a possible definition: > > > nat := 0 | succ nat > > > x + 0 = x > > x + succ y = succ x+y > > > x * 0 = 0 > > x * succ y = x + (x * y) > > > Is there some way this definition is not fully syntactic? > > It uses no quantifying over predicates, so it can't be > > using second order logic. > > It certainly seems to me that the above is fully syntactic, > > and is a complete definition of basic arithmetic. Are > > there statements that are true of this definition that > > can't be captured by any finite theory? Sure there > > are, but that has nothing to do with whether it's > > a proper syntactic definition. To say it's not a syntactic > > definition, you have to point out something about > > it that's not syntactic, or not correct as a model > > of the naturals. > > This is the usual first-order initial-algebra definition, and with the > addition of "succ x = succ y -> x=y" and an induction schema gives > first-order Peano Arithmetic. Small points: First of all, I claim "succ x = succ y -> x=y" is necessarily the case via the definition of =. Secondly, I claim we don't need to explicitly add any induction schema, because induction on the naturals in this case is merely a special case of structural induction, which is itself merely a special case of case analysis on the constructors for nat, and case analysis is always available, as it were. These are perhaps just quibbles. > First-order logic is indeed formal (i.e., > syntactic) in that all inferencing activities consist of finite > operations on finite strings. But, via Goedel and others, the Peano > axioms do NOT fully characterise the natural numbers N. N is indeed a > model (the Standard Model) which satisfies these axioms, but there are > also *non-standard models* which satisfy these axioms -- these models > contain infinite elements in addition to the usual naturals. > > You can get some of the flavour of non-standard models by considering > the following non-standard model for just succ, where every element has > a unique successor and predecessor: > > 0, 1, 2, ... ..., w-2, w-1, w, w+1, w+2, ... > > So, we can readily produce purely formal systems that are satisfied by > N, but all of them (as far as I know) are also satisfied by other, > non-standard, models. Try as we might, those pesky infinite > non-standard integers keep cropping up. That is the sense in which I > mean that we apparently can not formally fully characterise N. I can see how your above set could be a model for PA, but I don't see how it's supposed to be something that conforms to the definition I gave. For one thing, addition on the naturals is supposed to be total. What is the result of "2 + w" under my definition of +? It does not terminate, because you have introduced elements with infinite descending deconstruction. That my addition operator is total over (nat, nat) is provable; if there is some value for which it is not total that value must therefor not belong to nat. For another thing, my definition doesn't have any "w" in it, so you don't get to insert them in to the process. We are supposed to be being syntactical here; recall that you wanted to keep out second order logic and set theory, so no "w". Perhaps most importantly, I defined "nat" as those things that are constructed via one of the two specified constructors. Your w-elements are not so constructed, so they cannot meet the definition I gave. I have noticed in the past that logicians and set theorists don't necessarily buy the idea that the universe consists only of those objects that can be constructed using explicitly defined construction rules. I am rather inclined to say "tough," but perhaps I'll get better results if I just say that's fine, but anything that isn't so constructed isn't a natural, by definition. > (Note that we similarly cannot formally define "finite", so the dodge of > saying something like "the naturals are defined by the Peano axioms plus > the restriction that everything is finite" can not be expressed purely > formally.) It seems to me that syntax is necessarily finite, but again this is perhaps just a quibble. > > > > If it's actually the case (that every statement of basic arithmetic > > > > is either true or false) then it's not a shortcoming to say so. > > > > On the contrary, that would be a virtue. > > > > Speaking philosophically (since I'm posting from sci.philoisophy.tech), > > > entities which in some sense exist but are thoroughly inaccessible seem > > > to be of little value. This applies to the truth values of any > > > statements which can never be known to be true or false. > > > While I have sympathy for that position, I don't think it's > > tenable in the long run. Or anyway, it's not tenable to go > > from "of little value" to suggesting that we should, say, > > not attend to the real numbers because of the existence > > of uncomputable numbers, > > I am not an expert in that field, but I believe that almost all of real > analysis can be reconstructed using just computable numbers, e.g. the > work of Bishop. I'd accept "almost all" but note that "almost all" isn't the same as "all". For example, the order relation on computable numbers is not itself computable, sadly. Also isn't it the case that the least-upper-bound property is lost if we limit ourselves to computables? Regardless, the bigger issue, it seems to me, is that any such system is going be be distinctly more complex than the reals, and that complexity has a nontrivial cost. > > or suggest that statements > > that are undecidable one way or the other are somehow > > neither true nor false. What they are is undecidable. > > They are true or false in any *particular* model. Since we apparently > cannot formally pin down arithmetic to have just one particular model > (the Standard one) then there will always be some arithmetic statements, > the undecidable ones, which are true in some models and false in others. Even if we can pin it down, we still have statements that we don't know if they are true or false. It might require an infinite amount of computation to decide. Or just more than we will ever have. > Thus it is unreasonable to say that an undecidable statement is simply > "true" or "false" -- we need to specify a particular model, almost > always the Standard one, which we can not fully characterise formally. Sure, but whatever those statements do evaluate to, we can narrow it down to one of two possibilities, even if we can't narrow it any further. > This doesn't prevent doing interesting number theory, but it is at least > somewhat bothersome from a foundational perspective. I agree that it is bothersome! Marshall
From: Nam Nguyen on 31 Dec 2009 18:40 Barb Knox wrote: > In article > <a3f061ed-3838-4be9-b73a-836141dc640f(a)u7g2000yqm.googlegroups.com>, > Marshall <marshall.spight(a)gmail.com> wrote: > >> On Dec 30, 8:16 pm, Barb Knox <s...(a)sig.below> wrote: >>> Marshall <marshall.spi...(a)gmail.com> wrote: >>> >>> By the nature of the construction of predicate logic, every arithmetic >>> formula must be either true or false in the standard model of the >>> natural numbers. >>> >>> But, we have no satisfactory way to fully characterise that standard >>> model! We all think we know what the natural numbers are, but Goedel >>> showed that there is no first-order way to define them, and I don't know >>> of *any* purely formal (i.e., syntactic) way to do do. >> I was more under the impression that Goedel showed there >> was no complete finite theory of them, rather than no >> way to define them. Are you saying those are equivalent? > > Yes, in this context. Since we are finite beings we need to use finite > systems. > > >>> (The usual ways >>> to define them are not fully syntactic, but rely on "the full semantics" >>> of 2nd-order logic, or "a standard model" of set theory, both of which >>> are more complicated than just relying on "the Standard Model" of >>> arithmetic in the first place.) >> Here's a possible definition: >> >> nat := 0 | succ nat >> >> x + 0 = x >> x + succ y = succ x+y >> >> x * 0 = 0 >> x * succ y = x + (x * y) >> >> Is there some way this definition is not fully syntactic? >> It uses no quantifying over predicates, so it can't be >> using second order logic. > >> It certainly seems to me that the above is fully syntactic, >> and is a complete definition of basic arithmetic. Are >> there statements that are true of this definition that >> can't be captured by any finite theory? Sure there >> are, but that has nothing to do with whether it's >> a proper syntactic definition. To say it's not a syntactic >> definition, you have to point out something about >> it that's not syntactic, or not correct as a model >> of the naturals. > > This is the usual first-order initial-algebra definition, and with the > addition of "succ x = succ y -> x=y" and an induction schema gives > first-order Peano Arithmetic. First-order logic is indeed formal (i.e., > syntactic) in that all inferencing activities consist of finite > operations on finite strings. But, via Goedel and others, the Peano > axioms do NOT fully characterise the natural numbers N. N is indeed a > model (the Standard Model) which satisfies these axioms, but there are > also *non-standard models* which satisfy these axioms -- these models > contain infinite elements in addition to the usual naturals. > > You can get some of the flavour of non-standard models by considering > the following non-standard model for just succ, where every element has > a unique successor and predecessor: > > 0, 1, 2, ... ..., w-2, w-1, w, w+1, w+2, ... > > > So, we can readily produce purely formal systems that are satisfied by > N, but all of them (as far as I know) are also satisfied by other, > non-standard, models. Try as we might, those pesky infinite > non-standard integers keep cropping up. That is the sense in which I > mean that we apparently can not formally fully characterise N. > > (Note that we similarly cannot formally define "finite", so the dodge of > saying something like "the naturals are defined by the Peano axioms plus > the restriction that everything is finite" can not be expressed purely > formally.) > > >>>> If it's actually the case (that every statement of basic arithmetic >>>> is either true or false) then it's not a shortcoming to say so. >>>> On the contrary, that would be a virtue. >>> Speaking philosophically (since I'm posting from sci.philoisophy.tech), >>> entities which in some sense exist but are thoroughly inaccessible seem >>> to be of little value. This applies to the truth values of any >>> statements which can never be known to be true or false. >> While I have sympathy for that position, I don't think it's >> tenable in the long run. Or anyway, it's not tenable to go >> from "of little value" to suggesting that we should, say, >> not attend to the real numbers because of the existence >> of uncomputable numbers, > > I am not an expert in that field, but I believe that almost all of real > analysis can be reconstructed using just computable numbers, e.g. the > work of Bishop. > >> or suggest that statements >> that are undecidable one way or the other are somehow >> neither true nor false. What they are is undecidable. > > They are true or false in any *particular* model. Since we apparently > cannot formally pin down arithmetic to have just one particular model > (the Standard one) then there will always be some arithmetic statements, > the undecidable ones, which are true in some models and false in others. Agree. The question - and the heart of my argument - is whether or not there exists a formula F such that it's impossible to know/assert a truth value in the collection K of _all_ arithmetic models: K = {the standard one, the non-standard ones}? I've argued that there exist such statements. > Thus it is unreasonable to say that an undecidable statement is simply > "true" or "false" -- we need to specify a particular model, almost > always the Standard one, which we can not fully characterise formally. > > This doesn't prevent doing interesting number theory, but it is at least > somewhat bothersome from a foundational perspective. Arguably, FOL isn't just for number theories and so there's always a possibility the existences of such formulas might shed some light about FOL systems that we've largely ignored: e.g. systems that have infinite number of logical symbols, some of which might represent isomorphic - but different - operations.
From: Marshall on 31 Dec 2009 18:52 On Dec 31, 12:29 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > Marshall wrote: > > On Dec 30, 8:16 pm, Barb Knox <s...(a)sig.below> wrote: > >> Marshall <marshall.spi...(a)gmail.com> wrote: > > >> By the nature of the construction of predicate logic, every arithmetic > >> formula must be either true or false in the standard model of the > >> natural numbers. > > >> But, we have no satisfactory way to fully characterise that standard > >> model! We all think we know what the natural numbers are, but Goedel > >> showed that there is no first-order way to define them, and I don't know > >> of *any* purely formal (i.e., syntactic) way to do do. > > > I was more under the impression that Goedel showed there > > was no complete finite theory of them, rather than no > > way to define them. > > Godel didn't show any of the 2 you've mentioned. "Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable in the theory." So there cannot be a complete finite theory of basic arithmetic. > > Are you saying those are equivalent? > > If I'm the one answering this question then "No": defining a model of a formal > system is not the same as demonstrating anything about a formal system that's > supposed to be about the model. Naturally. Well we agree on one thing. That's unusual. > > It certainly seems to me that the above is fully syntactic, > > and is a complete definition of basic arithmetic. > > That's *not* the canonical knowledge of arithmetic: what happens to the usual > syntactical symbol '<', in your "complete definition"? It's easy to extend this with <. > > Are > > there statements that are true of this definition that > > can't be captured by any finite theory? Sure there > > are, but that has nothing to do with whether it's > > a proper syntactic definition. To say it's not a syntactic > > definition, you have to point out something about > > it that's not syntactic, or not correct as a model > > of the naturals. > > Setting aside the missing "<", what you've defined up there is > *in no way* conforming with the _FOL definition of a model_ which > the naturals is supposed to be collectively. For example, what's > the set of 2-tuples that would correspond to your '+'? The goal was to provide a syntactic definition of the naturals, which I did. The goal was not to provide a FOL model. Nonetheless it's pretty easy to get there from here. For example: {((x, y), z) | x+y=z} > >>> If it's actually the case (that every statement of basic arithmetic > >>> is either true or false) then it's not a shortcoming to say so. > >>> On the contrary, that would be a virtue. > >> Speaking philosophically (since I'm posting from sci.philoisophy.tech), > >> entities which in some sense exist but are thoroughly inaccessible seem > >> to be of little value. This applies to the truth values of any > >> statements which can never be known to be true or false. > > > While I have sympathy for that position, I don't think it's > > tenable in the long run. Or anyway, it's not tenable to go > > from "of little value" to suggesting that we should, say, > > not attend to the real numbers because of the existence > > of uncomputable numbers, or suggest that statements > > that are undecidable one way or the other are somehow > > neither true nor false. What they are is undecidable. > > First order undecidable formulas are in a different class than those > that aren't model-able, aren't truth assigned-able. > > I asked you before: > > "(1) There are infinite counter examples of GC. > > Tell me what you'd even suspect as a road-map to assign true or > false to (1)?" You keep assuming that the mere fact that a sentence is undecidable means that it has some definite truth value that is not one of {true, false}. Apparently you just take this as a given. I, however, regard it as a false statement. > Now if you let (1') be defined as: > > (1') df= (1) /\ A1 /\ A2 /\ ... A9 > > where A1 - A9 are Q's axioms (a la Shoenfield). Tell us, Marshall, what models or > what kinds of models that you think you could assign 'true' or 'false' to > (1')? If you really can't - which I don't think you can - then don't you at > least think of the possibility that there are arithmetic statements that can't > be true or false? I suppose anything is possible, in some vague, New-Age sort of way. I suppose if someone were to supply some convincing argument as to why there must be some third possibility, I would at least consider it. However, I have yet to hear any convincing argument in favor of there being a third possibility. The mere fact of a decision being hard, even infinitely hard, does not suggest to me the existence of some third truth value for a sentence to have. > Why is it that a statement has to be true or false while _there's no way_ to > assign a truth value to it any way? Other than we might have grown up accustomed > to it, what kind of reasoning is that? > > Ok I might sound a bit rhetorical here. But can you technically answer my question > about (1')? It seems to me that the definitions of the various things we are talking about necessitate that a statement is either true or false. The definition does not admit to the existence of any third possibility. That some statements are undecidable does not alter the definition of the terms the statements were made with; the definitions remain as they were. Thus every statement must have one of the two truth values, by definition. Now, if you want to make some new system to evaluate statements in, that could certainly be defined with more than the usual two possibilities. But that wouldn't be the usual basic arithmetic; it'd be something new. Although I don't consider reasoning by analogy to the real world to be a great technique, it is at least suggestive that there are real-world statements that we can narrow down to few possibilities but cannot narrow down to one. For example, Mr. McCullough's coin-and- railroad story. We could even further say we were close enough to see the coin landed definitely on one side, but we weren't close enough to say which side it was. Marshall
From: Marshall on 31 Dec 2009 18:58
On Dec 31, 3:40 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > Barb Knox wrote: > > > They are true or false in any *particular* model. Since we apparently > > cannot formally pin down arithmetic to have just one particular model > > (the Standard one) then there will always be some arithmetic statements, > > the undecidable ones, which are true in some models and false in others.. > > Agree. The question - and the heart of my argument - is whether or not there > exists a formula F such that it's impossible to know/assert a truth value > in the collection K of _all_ arithmetic models: K = {the standard one, the > non-standard ones}? I've argued that there exist such statements. Why would the existence of such statements imply that there are truth values other than true or false? Marshall |