The End of an Era - That of The Natural Numbers
in [Math]
|
From: MoeBlee on 3 May 2010 11:08 On May 1, 1:28 pm, Alan Smaill <sma...(a)SPAM.inf.ed.ac.uk> wrote: > MoeBlee <jazzm...(a)hotmail.com> writes: 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.) In both senses: (1) We have various theorem schemata (that don't need the axiom of of infinity) that provide for proving, by induction, that a ceratin property holds for all finite sets. (2) The axiom of infinity is not needed to use induction to prove that some given property holds for all members of a given finite set. MoeBlee
From: Alan Smaill on 3 May 2010 12:51 MoeBlee <jazzmobe(a)hotmail.com> writes: > On May 1, 1:28�pm, Alan Smaill <sma...(a)SPAM.inf.ed.ac.uk> wrote: >> MoeBlee <jazzm...(a)hotmail.com> writes: > 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.) thanks for the reply > In both senses: > > (1) We have various theorem schemata (that don't need the axiom of of > infinity) that provide for proving, by induction, that a ceratin > property holds for all finite sets. OK -- but proofs of the schemata are not strictly within set theory, I take it, but with meta-theoretic characterisation of these schemata. And then what is the notion of "all finite sets" here? Part of the schemata? > (2) The axiom of infinity is not needed to use induction to prove that > some given property holds for all members of a given finite set. Agreed if that set is given by explicit enumeration of the elements -- is that what you mean? > MoeBlee -- Alan Smaill email: A.Smaill at ed.ac.uk School of Informatics tel: 44-131-650-2710 University of Edinburgh
From: MoeBlee on 3 May 2010 13:42 On May 3, 11:51 am, Alan Smaill <sma...(a)SPAM.inf.ed.ac.uk> wrote: > MoeBlee <jazzm...(a)hotmail.com> writes: > > In both senses: > > > (1) We have various theorem schemata (that don't need the axiom of of > > infinity) that provide for proving, by induction, that a ceratin > > property holds for all finite sets. > > OK -- but proofs of the schemata are not strictly within set theory, I take it, > but with meta-theoretic characterisation of these schemata. Sure, in the sense that every axiom or theorem schema is stated in the metalanguage. But then each schema defines an infinite set of axioms or theorems. Various such schemata are shown in Suppes's 'Axiomatic Set Theory'. > And then what > is the notion of "all finite sets" here? Just any of the ordinary equivalents of Tarski's definition. For example, a set S is finite iff there is an R such that R that well orders S and the converse of R well orders S. > > (2) The axiom of infinity is not needed to use induction to prove that > > some given property holds for all members of a given finite set. > > Agreed if that set is given by explicit enumeration of the elements -- > is that what you mean? I mean that any finite set is 1-1 with some finite ordinal (we don't need the axiom of infinity for this). Then it's easy to see that we can use induction to prove that, for some given property (in which this holds, of course) that all members of a given finite set have said property. Or we could establish this even without going through the notion of ordinals, but just from the fact that every finite set has a well ordering. MoeBlee
From: Nam Nguyen on 4 May 2010 01:21 William Hughes wrote: > On May 2, 6:46 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > >> What I'm >> really ... really .. after is _formalizing_ what is impossible to >> know or infer. Would that be too much to ask for, > > My guess is yes, but what do I know? > Certainly a good start would > be to find a class of unknowable statements. That's what I've been doing (or at least trying to do). > > A good start is not proclaiming the end of natural numbers > and posting an "observation" that twists the phrase > "any intuition" past the breaking point. Any intuition _about the natural numbers_, NOT just any-whatsoever- intuition, remember? > > It is interesting to note that while you have been presented with > many putative "intuitions" given which the truth or falsehood > of (1) is knowable (you have accepted none and explicitly rejected > one), you have not presented a single "intuition" under which the > truth or falsehood of (1) is not knowable. That's correct: I have not - yet. That doesn't mean I'm not going to. > Given that the truth or falsehood of (1) is knowable, iff the truth > or falsehood of cGC is knowable, I think that finding an > interesting example will be hard. "interesting example" of what, while my intention is to demonstrate it's impossible to know the truth value of (1)? > > <snip> > >> I mean, even though we can't answer all the mathematical questions >> about arithmetic, wouldn't it be in our own reasoning interest to >> _formally_ categorize them in to which one we'd know and which one we'd >> NOT know? > > > It would also be in our own reasoning interest to divide the > questions into those which have a proof that can be written down > in a century, and those which do not. I don't see any > hope here either. > > Given an unsolved mathematical question Q, there are three > possibilities > > -there is a solution to Q that is reasonably short > (reasonably short may be many volumes) > -there is a solution to Q but the shortest solution > is too long to write down > -there is no solution to Q > > Except for contrived examples, I cannot see > how to distinguish among the three. It's up to you but I think it'd serve no interesting purpose in trying to formalize different kinds of theorems, especially by proof-length. The reason being is contingent and non-logical formulas exist for the purpose of richly describing non-logical concepts, because logical tautologies or contradictions are not adequate for the descriptions. And given there's no limit how many different contingent or non-logical concepts there could exist, it's virtually pointless to try to categorize them. For example, while the proof of say FLT might be extremely long in PA, its proof in an inconsistent T1, or in the T2 = {FLT} would be very short! Otoh, the 3rd case of "there is no solution to [a question] Q" or of "don't know the truth value or decidability of an F w.r.t a T" is actually categorize-able - at least in general. Let's elaborate on this a little more. Let T = {Ax[~(Sx=0)] \/ ~Ax[~(Sx=0)]} Model theoretically, T is consistent because we can have a model M where its universe Um is a singleton. Yet, let F = Ax[~(Sx=0)] then it's IMPOSSIBLE to know the answer to the question Q of F's decidability in T! In addition, if, for some reason, we only describe model M' where the universe M'u is incompletely described as M'u = {e1, ...} where "..." means there might be more or none elements besides e1, then M' is an _intuitive_ model of T in which it's impossible to know the truth value of F, or of ~F! So, _far from being a philosophical talk_, this example of T above has demonstrated that within FOL reasoning, there's a case of impossibility of knowing of the decidability or the truth value of a formula in a formal system T! Of course this T is not in the same category of "as strong as arithmetic" system such as Q (Robinson Arithmetic) or PA. But the example above means we can no longer simply dismiss at least the possibility that it's impossible to know the decidability or truth value of (1) in an arithmetic formal system. [To be continued...]
From: Nam Nguyen on 4 May 2010 02:04
Alan Smaill wrote: > Nam Nguyen <namducnguyen(a)shaw.ca> writes: > >> Also, I suppose many decades ago truth-equals-provability mathematics >> was the "actual mathematics" of the time. A kind of >> "soup-du-jour mathematics" isn't it? >> [Actually Shoenfield gave a hint this was (and is) the case!] > > Given his acceptance of G�del's incompleteness theorem, > your claim is implausible. > > Which "hint" of his do you have in mind? First, he said of his version of Robinson Arithmetic system (he denoted by N) as "[a formal] system for the natural numbers." (pg. 22). But then in a subsequent chapter he had: "The theory N is not a satisfactory axiom system for studying natural numbers" (pg. 204). |