The End of an Era - That of The Natural Numbers
in [Math]
|
From: Alan Smaill on 1 May 2010 14:28 MoeBlee <jazzmobe(a)hotmail.com> writes: > On Apr 30, 6:24�pm, Transfer Principle <lwal...(a)lausd.net> wrote: > >> set theory also gives a >> definition of the multiplication of finite ordinals in terms >> of addition > > In set theory we could also define multiplication of finite ordinals > by Cartesian product. > >> although finite induction/recursion in ZF, >> ironically, requires the Axiom of Infinity) > > I don't know what you mean by 'finite induction/recursion', but in set > theory we don't need the axiom of infinity to prove that we can do > induction on finite sets. What statement of set theory are you thinking of here? (Not sure if you mean induction for a set given via an explicit finite enumeration, or some principle of induction that lets us proves something about all finite sets.) > MoeBlee > -- Alan Smaill
From: William Hughes on 1 May 2010 14:47 On May 1, 3:15 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > William Hughes wrote: > > On May 1, 2:21 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > > <snip> > > >> The definition of pGC was given before, in a high level as: > > >> pGC <-> "There are infinitely many examples of GC" > > >> From "there are infinitely many primes", how do you conclude > >> pGC is true? > > > Clearly. I do not understand what is meant by > > > "There are infinitely many examples of GC" > > > I take it to mean there are infinitely many even > > integers greater than 4 that are the sum of two primes. > > This follows immediately from the fact that there are > > an infinite number of primes (just add 3 to every prime, > > if the prime is not 2 you get an x for which GC(x) is true). > > Ah, yes. It's trivial indeed as you said. (As long long as we don't > in meta level conclude from "there are infinitely many primes" as > a 1st order theorem to "pGC is true" as a [meta] true statement. > We were talking about "decidable" which is of syntactical notion. > I forgot that I had asked you about being "_true_ in the naturals". > My bad!). > > OK then, let's get back to my question before this issue: > > NN asked: > > So, for example, suppose cGC is provable, how would you demonstrate > > (1) is decidable? > > to which WH responded: > > pGC is provably true. > > My question is based entirely on syntactical notion, free of notion > of truth of the naturals. Why does your answer have the word "true"? > Iow, why does your answer have something to do with my question? O.k, we lose true entirely, and take P is provable iff there is a derivation whose last line is P. And P is decidable iff P is provable or ~P is provable We start with "there are an infinite number of primes" is provable, (This is certainly a reasonable assumption) from which it follows that pGC is provable. If cGC is provable then ~(1) is provable and (1) is decidable.
From: Nam Nguyen on 1 May 2010 16:12 William Hughes wrote: > On May 1, 3:15 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: >> William Hughes wrote: >>> On May 1, 2:21 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: >>> <snip> >>>> The definition of pGC was given before, in a high level as: >>>> pGC <-> "There are infinitely many examples of GC" >>>> From "there are infinitely many primes", how do you conclude >>>> pGC is true? >>> Clearly. I do not understand what is meant by >>> "There are infinitely many examples of GC" >>> I take it to mean there are infinitely many even >>> integers greater than 4 that are the sum of two primes. >>> This follows immediately from the fact that there are >>> an infinite number of primes (just add 3 to every prime, >>> if the prime is not 2 you get an x for which GC(x) is true). >> Ah, yes. It's trivial indeed as you said. (As long long as we don't >> in meta level conclude from "there are infinitely many primes" as >> a 1st order theorem to "pGC is true" as a [meta] true statement. >> We were talking about "decidable" which is of syntactical notion. >> I forgot that I had asked you about being "_true_ in the naturals". >> My bad!). >> >> OK then, let's get back to my question before this issue: >> >> NN asked: >> > So, for example, suppose cGC is provable, how would you demonstrate >> > (1) is decidable? >> >> to which WH responded: >> > pGC is provably true. >> >> My question is based entirely on syntactical notion, free of notion >> of truth of the naturals. Why does your answer have the word "true"? >> Iow, why does your answer have something to do with my question? > > O.k, we lose true entirely, and take P is provable iff there > is a derivation whose last line is P. And P is decidable > iff P is provable or ~P is provable Ok. Let's loose "true", here. (My line of questions - here - was a bit sidetracked with your cross-path truth and provability). I think though you'd agreed with me that "provable" always means provable in a formal system T and that in this context T is supposed to be "as strong as arithmetic", which is an intuitive notion. (If you don't please let me know). > > We start with "there are an infinite number of primes" > is provable, (This is certainly a reasonable assumption) from which it > follows that pGC is provable. > If cGC is provable then ~(1) is provable and (1) is decidable. Now then going back further to our original argument: NN [originally] stated: > if we have any intuition about the naturals then we'd also > have the intuition that we can't know the arithmetic truth > or falsehood of (1) WH later responed: > However, I cannot see why you should think the fact that you > have "any intuition about the naturals" means that cGC is > undecidable. which NN asked: > but where did I say that? which WH answer: > Now apply the fact that (1) is decidable iff cGC > is decidable So, what does the fact that in T "If cGC is provable then ... (1) is decidable" have anything to do with what I originally stated as the first observation [above]? Can you elaborate on how that fact would relate to my observation, especially, e.g., when being provable or decidable doesn't necessarily mean being true?
From: Nam Nguyen on 1 May 2010 18:48 Nam Nguyen wrote: > William Elliot wrote: >> On Mon, 26 Apr 2010, Nam Nguyen wrote: >>>>> >>> The correct versions are: >>> >>> GC(x) <-> (x is even >=4) -> Ep1p2[(p1, p2 are primes) /\ (x=p1+p2)] >> >> By that definition, GC(pi) is true. The correct definition is: >> >> GC(x) <-> >> (x is even integer) & (x >= 4 -> Ep1p2[(p1, p2 are primes) /\ (x=p1+p2)]) > > Thanks for the correction. In fact cGC(x) should be similarly corrected: > > cGC(x) <-> > (x is even integer) & (x >= 4 -> ~Ep1p2[(p1, p2 are primes) /\ > (x=p1+p2)]) > >> >>> (*)P <-> Ex[P(x)] /\ AxEy[P(x) -> (P(y) /\ (x < y))] >>> >>>>>> First observation: if we have any intuition about the naturals >>>>>> then we'd also have the intuition that we can't know the >>>>>> arithmetic truth or falsehood of (1). >>> >> Based upon that intuition, I'll concur that we don't know >> the truth or falsehood of (1). > > "Don't know" is actually not a precise notion in reasoning. Today we > might be in a "don't know" state of something that's still possible > to know, but tomorrow we might know it. Otoh, "never know", "can't > know", "impossible" is a precise notion: it means it's not possible > to know within the reasoning framework. For example, it's impossible > to know through syntactical proof the syntactical consistency of a > consistent formal system. > >> Based upon that intuition, you claim we'll never know >> the truth or falsehood of (1). >> >> That's an unsubstatiated claim. >> Give some insights why I should accept it. As previously mentioned, this might be a long response, spreading into multiple posts, and this post would be just an "introduction" where I'd share some high level "insights" about why it's impossible to know the truth value of (1), given our intuitive knowledge of the arithmetic of the natural numbers. I think one would agree with me _precision_ in mathematical reasoning is of paramount importance to consistent reasoning, making deductions, or making logical arguments. If we don't have a precise definition of something, how could we _always_ argue for or against predicates about that something? If we don't precisely follow what we've defined as a rigid framework of inference, how worthwhile would logical conclusions be? In a high level then my claim begins with the notion that our knowledge of arithmetic of the natural numbers is intuitive and is NOT precise, because there are only a finite number of ways we could define such knowledge and none is actually precise or free of being circular. A) If such knowledge is "precisely" embedded in formal systems "as strong as arithmetic" then there's no guarantee _any of such a system_ be consistent, which is something we'd need for the knowledge. B) If such knowledge is that of a model of a formal system, such as Q, then the knowledge can't be precise, for we don't have a precise knowledge of all the required n-ary relations: we don't know _all_ the required n-tuples that would have exist in those relations. C) If an arithmetic truth is just a mental (hence subjective) mapping between a formula and the word "true", or "false", then it's too relative or subjective to be agreed by all human beings as "precise". It's not true such imprecise knowledge of the naturals would mean we know nothing about them: we do know know some formula being true. It's just that we wouldn't be able know the truth status of all formulas! The difficulty though is how we could discern gold from bronze, so to speak, and separate the formulas that are _impossible to know_ the truth value from those that are _only difficult to know_ . Iow, _if_ the naturals collectively be _precisely_ a model of Q, then for any formula F, (F xor ~F) would be true. But we only have a incomplete (hence imprecise) knowledge of the naturals, then of course we can't assert (F xor ~F) is true - for ANY F. [Next post: why (1) or similar formula would be in the category we can't assert its truth or falsehood.]
From: William Hughes on 1 May 2010 19:33
On May 1, 5:12 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > William Hughes wrote: > > On May 1, 3:15 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > >> William Hughes wrote: > >>> On May 1, 2:21 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > >>> <snip> > >>>> The definition of pGC was given before, in a high level as: > >>>> pGC <-> "There are infinitely many examples of GC" > >>>> From "there are infinitely many primes", how do you conclude > >>>> pGC is true? > >>> Clearly. I do not understand what is meant by > >>> "There are infinitely many examples of GC" > >>> I take it to mean there are infinitely many even > >>> integers greater than 4 that are the sum of two primes. > >>> This follows immediately from the fact that there are > >>> an infinite number of primes (just add 3 to every prime, > >>> if the prime is not 2 you get an x for which GC(x) is true). > >> Ah, yes. It's trivial indeed as you said. (As long long as we don't > >> in meta level conclude from "there are infinitely many primes" as > >> a 1st order theorem to "pGC is true" as a [meta] true statement. > >> We were talking about "decidable" which is of syntactical notion. > >> I forgot that I had asked you about being "_true_ in the naturals". > >> My bad!). > > >> OK then, let's get back to my question before this issue: > > >> NN asked: > >> > So, for example, suppose cGC is provable, how would you demonstrate > >> > (1) is decidable? > > >> to which WH responded: > >> > pGC is provably true. > > >> My question is based entirely on syntactical notion, free of notion > >> of truth of the naturals. Why does your answer have the word "true"? > >> Iow, why does your answer have something to do with my question? > > > O.k, we lose true entirely, and take P is provable iff there > > is a derivation whose last line is P. And P is decidable > > iff P is provable or ~P is provable > > Ok. Let's loose "true", here. (My line of questions - here - was a bit > sidetracked with your cross-path truth and provability). I think though > you'd agreed with me that "provable" always means provable in a formal > system T and that in this context T is supposed to be "as strong as > arithmetic", which is an intuitive notion. (If you don't please let me > know). > > > > > We start with "there are an infinite number of primes" > > is provable, (This is certainly a reasonable assumption) from which it > > follows that pGC is provable. > > If cGC is provable then ~(1) is provable and (1) is decidable. > > Now then going back further to our original argument: > > NN [originally] stated: > > > if we have any intuition about the naturals then we'd also > > have the intuition that we can't know the arithmetic truth > > or falsehood of (1) > > WH later responed: > > However, I cannot see why you should think the fact that you > > have "any intuition about the naturals" means that cGC is > > undecidable. > > which NN asked: > > but where did I say that? a rather important snip here You said "if we have any intuition about the naturals then we'd also have the intuition that we can't know the arithmetic truth or falsehood of (1)" > > which WH answer: > > Now apply the fact that (1) is decidable iff cGC > > is decidable > > So, what does the fact that in T "If cGC is provable then ... (1) > is decidable" have anything to do with what I originally stated as > the first observation [above]? Can you elaborate on how that fact > would relate to my observation, We now have (1) is decidable iff cGC is decidable. pGC is true pGC is provable We will assume that T is sound (another reasonable and common assumption). Consider your statement "we can't know the arithmetic truth or falsehood of (1)" However, if (1) is decidable we can know the arithmetic truth or falsehood of (1). So if cGC is decidable then (1) is decidable and we can know the arithmetic truth or falsehood of (1). [If cGC not decidable, then (1) is not decidable. It may still be possible to know the arithmetic truth or falsehood of (1) but this seems unlikely.] Now, "cGC is decidable" is a perfectly reasonable intuition, so if we assume T is sound, observation 1 is false. > especially, e.g., when being provable > or decidable doesn't necessarily mean being true? If we do not assume T is sound, then there is no connection between provable and true. Now we have to phrase things: (1) is true iff cGC is false. However, "cGC is false" is a perfectly reasonable intuition, so even if we don't assume T is sound, observation 1 is false. - William Hughes |