In a Consistent System, Can a True Sentence Imply a False One?
in [Logic]
|
Prev: when math defines the boundary between finite versus infinite at 10^500 #696 Correcting Math
Next: FLT like 4Color Mapping, Poincare C. and Kepler Packing #697 Correcting Math
From: Nam Nguyen on 10 Aug 2010 13:05 Aatu Koskensilta wrote: > Nam Nguyen <namducnguyen(a)shaw.ca> writes: > >> Well, it doesn't seem to be false to me according to Godel's own >> remark on his paper (though I have only a translated version). > > What remark is that? The incompleteness theorems certainly apply to > e.g. primitive recursive arithmetic, which has infinitely many > non-logical symbols. [For example, did you mean beside addition (+) and multiplication (*) we would have infinitely many binary operation symbols?] Godel wrote in the introduction: "It is shown below that this is not the case, and that in both the systems mentioned there are in fact relatively simple problems in the theory of ordinary whole numbers [4] which cannot be decided from the axioms." where: [4] "I.e., more precisely, there are undecidable propositions in which besides the logical constants ~ (not), v (or), (x) (for all) and = (identical with), *there are no other concepts beyond* + (addition) and . (multiplication), both referred to the natural numbers, and where the prefix (x) can also refer only to the natural numbers." [Emphasis is mine]. I take it that "there are no other concepts beyond ..." is a clear indication the number of arithmetic operations have to be finite, for his proof to work in _all cases_. If we allow the number to be infinite, two problems seem arise: - An infinite set could have an infinite proper subset. If all the primes are used up for "half" of these non-logical symbols, how do we encode formulas with symbols from the other half? - What would guarantee that _any_ formal system sufficiently expressing the arithmetic of the natural numbers with infinitely many non-logical (operation) symbols would NOT be inconsistent? -- ----------------------------------------------------------- Normally, we do not so much look at things as overlook them. Zen Quotes by Alan Watt -----------------------------------------------------------
From: Aatu Koskensilta on 10 Aug 2010 13:43 Nam Nguyen <namducnguyen(a)shaw.ca> writes: > [For example, did you mean beside addition (+) and multiplication (*) > we would have infinitely many binary operation symbols?] In PRA there are for any n infinitely many n-ary function symbols. Each function symbol corresponds to a primitive recursive definition of a function. > I take it that "there are no other concepts beyond ..." is a clear > indication the number of arithmetic operations have to be finite, for > his proof to work in _all cases_. Why? G�del is in "I.e., more precisely, there are undecidable propositions in which besides the logical constants ~ (not), v (or), (x) (for all) and = (identical with), *there are no other concepts beyond* + (addition) and . (multiplication), both referred to the natural numbers, and where the prefix (x) can also refer only to the natural numbers." effectively observing that the undecidable proposition we get by applying the first incompleteness theorem to a particular theory can be expressed in the first-order language of arithmetic. > - An infinite set could have an infinite proper subset. If all the primes > are used up for "half" of these non-logical symbols, how do we encode > formulas with symbols from the other half? If all numbers are used up as codes for variables, how do we encode more complex terms? As long as the number of symbols is countable devising a suitable coding is not at all problematic. > - What would guarantee that _any_ formal system sufficiently expressing > the arithmetic of the natural numbers with infinitely many non-logical > (operation) symbols would NOT be inconsistent? Take any consistent theory. Add infinitely many function symbols. The result is again a consistent theory. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechen kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Nam Nguyen on 10 Aug 2010 16:08 Aatu Koskensilta wrote: > Nam Nguyen <namducnguyen(a)shaw.ca> writes: > >> [For example, did you mean beside addition (+) and multiplication (*) >> we would have infinitely many binary operation symbols?] > > In PRA there are for any n infinitely many n-ary function symbols. Each > function symbol corresponds to a primitive recursive definition of a > function. > >> I take it that "there are no other concepts beyond ..." is a clear >> indication the number of arithmetic operations have to be finite, for >> his proof to work in _all cases_. > > Why? G�del is in > > "I.e., more precisely, there are undecidable propositions in which > besides the logical constants ~ (not), v (or), (x) (for all) and = > (identical with), *there are no other concepts beyond* + (addition) > and . (multiplication), both referred to the natural numbers, and > where the prefix (x) can also refer only to the natural numbers." > > effectively observing that the undecidable proposition we get by > applying the first incompleteness theorem to a particular theory can be > expressed in the first-order language of arithmetic. > >> - An infinite set could have an infinite proper subset. If all the primes >> are used up for "half" of these non-logical symbols, how do we encode >> formulas with symbols from the other half? > > If all numbers are used up as codes for variables, how do we encode > more complex terms? As long as the number of symbols is countable > devising a suitable coding is not at all problematic. > >> - What would guarantee that _any_ formal system sufficiently expressing >> the arithmetic of the natural numbers with infinitely many non-logical >> (operation) symbols would NOT be inconsistent? > > Take any consistent theory. Add infinitely many function symbols. The > result is again a consistent theory. OK. Fwiw, I believe in 2 things in reasoning: a) technical correctness and b) the essence of the issue. For a) I'll concede my asserting that Godel's work requires only finitely many non logical symbols for the underlying T is too strong to be correct (and adequately portraying what I'd like to say). But for b) there's still an essence in what I tried to say about finitely-many-non-logical-symbol requirement. Let me elaborate. Certainly we could extend L = L(PA) to L' with additional non-logical (individual constant) symbols 0', 0'', 0''', etc... with the axioms that: 0' = S(0), 0'' = S(0'), 0''' = S(0''), etc... Now let's define PA' a system which is PA + {those axioms above} then w.r.t. PA' has infinitely many non-logical symbols but if Godel's work applies to PA, it'd also apply to PA'. _Note_ though: in all axioms defining 0', 0'', 0''', _the non-logical symbol 0 must necessarily be present_ ! That fact is trivial given L' is an extension of L; and so is that 0 can't be defined in term of the other "zeros" (0', 0'', 0''', ...) given that L is NOT an extension of any of it's non-trivial extension. In effect, 0 has the "parental" relationship with the other "zeros", and L is also "parental" to L', as far as inheritance/extension hierarchy is concerned. Now, let's consider L'' as an extension of L that has an additional symbol S'. The set of axioms of say PA'' is identical to that of PA, with one new one: S'S'S'(0) = SSSSSSS(0). The long and short of it is while L is still parental to L'', S is no longer parental to S': both each would depend on the other for the overall axiomatization of the underlying system (PA''). The long and short of it is there's a language: rL = (0, S', +', *', <', S'', +'', *'', <'', S''', +''', *''', <''', ...) where we'd have infinitely many sub-languages each of all of which is syntactically and semantically isomorphic to L(PA). And yet in the meta level we could stipulate the axioms rPA written in rL as the following grouping: Group A: The familiar PA axioms for each sub-language that's isomorphic to L(PA). Group B: For each pair of distinct sub-languages, e.g. and without loss of generality, L1 = (0, S', +', *', <') and L2 = (0, S'', +'', *'', <''), there be this axiom: S'S'S'S'...SS(0) = S''S''S''S''S''...S''S''S''(0) where the numeral on the left of = is of different length (in term of FOL language symbols) than the one on the right. Note that all the sub-languages mentioned above are of "sibling" level with each other: hence all the (successor function) symbols and, given group B axioms, all corresponding terms involving successor functions symbols In summary, that's what I meant to say when saying that Godel's work doesn't apply to this kind of systems that would have this kind of infinite non-logical but _sibling_ symbols. If that's not so, perhaps an explanation could be offered? Thanks. -- ----------------------------------------------------------- Normally, we do not so much look at things as overlook them. Zen Quotes by Alan Watt -----------------------------------------------------------
From: Nam Nguyen on 10 Aug 2010 16:35 Nam Nguyen wrote: > and so is that 0 can't > be defined in term of the other "zeros" (0', 0'', 0''', ...) given > that L is NOT an extension of any of it's non-trivial extension. There was a bit "glossing" here and the statement wouldn't be correct in general. But it was meant to be in the familiar context of Peano arithmetic as expressed in the familiar L(PA). -- ----------------------------------------------------------- Normally, we do not so much look at things as overlook them. Zen Quotes by Alan Watt -----------------------------------------------------------
From: Nam Nguyen on 10 Aug 2010 16:54
Nam Nguyen wrote: > Aatu Koskensilta wrote: >> Nam Nguyen <namducnguyen(a)shaw.ca> writes: >> >>> [For example, did you mean beside addition (+) and multiplication (*) >>> we would have infinitely many binary operation symbols?] >> >> In PRA there are for any n infinitely many n-ary function symbols. Each >> function symbol corresponds to a primitive recursive definition of a >> function. >> >>> I take it that "there are no other concepts beyond ..." is a clear >>> indication the number of arithmetic operations have to be finite, for >>> his proof to work in _all cases_. >> >> Why? G�del is in >> >> "I.e., more precisely, there are undecidable propositions in which >> besides the logical constants ~ (not), v (or), (x) (for all) and = >> (identical with), *there are no other concepts beyond* + (addition) >> and . (multiplication), both referred to the natural numbers, and >> where the prefix (x) can also refer only to the natural numbers." >> >> effectively observing that the undecidable proposition we get by >> applying the first incompleteness theorem to a particular theory can be >> expressed in the first-order language of arithmetic. >> >>> - An infinite set could have an infinite proper subset. If all the >>> primes >>> are used up for "half" of these non-logical symbols, how do we encode >>> formulas with symbols from the other half? >> >> If all numbers are used up as codes for variables, how do we encode >> more complex terms? As long as the number of symbols is countable >> devising a suitable coding is not at all problematic. >> >>> - What would guarantee that _any_ formal system sufficiently expressing >>> the arithmetic of the natural numbers with infinitely many >>> non-logical >>> (operation) symbols would NOT be inconsistent? >> >> Take any consistent theory. Add infinitely many function symbols. The >> result is again a consistent theory. > > OK. Fwiw, I believe in 2 things in reasoning: a) technical correctness > and b) the essence of the issue. For a) I'll concede my asserting that > Godel's work requires only finitely many non logical symbols for the > underlying T is too strong to be correct (and adequately portraying what > I'd like to say). But for b) there's still an essence in what I tried > to say about finitely-many-non-logical-symbol requirement. > > Let me elaborate. > > Certainly we could extend L = L(PA) to L' with additional non-logical > (individual constant) symbols 0', 0'', 0''', etc... with the axioms > that: 0' = S(0), 0'' = S(0'), 0''' = S(0''), etc... Now let's define > PA' a system which is PA + {those axioms above} then w.r.t. PA' has > infinitely many non-logical symbols but if Godel's work applies to PA, > it'd also apply to PA'. _Note_ though: in all axioms defining 0', 0'', > 0''', _the non-logical symbol 0 must necessarily be present_ ! That > fact is trivial given L' is an extension of L; and so is that 0 can't > be defined in term of the other "zeros" (0', 0'', 0''', ...) given > that L is NOT an extension of any of it's non-trivial extension. > > In effect, 0 has the "parental" relationship with the other "zeros", > and L is also "parental" to L', as far as inheritance/extension > hierarchy is concerned. > > Now, let's consider L'' as an extension of L that has an additional > symbol S'. The set of axioms of say PA'' is identical to that of > PA, with one new one: S'S'S'(0) = SSSSSSS(0). The long and short of > it is while L is still parental to L'', S is no longer parental to S': > both each would depend on the other for the overall axiomatization > of the underlying system (PA''). > > The long and short of it is there's a language: > > rL = (0, S', +', *', <', S'', +'', *'', <'', > S''', +''', *''', <''', ...) > > where we'd have infinitely many sub-languages each of all of which is > syntactically and semantically isomorphic to L(PA). And yet in the > meta level we could stipulate the axioms rPA written in rL as the > following grouping: > > Group A: The familiar PA axioms for each sub-language that's > isomorphic to L(PA). > > Group B: For each pair of distinct sub-languages, e.g. and without loss > of generality, L1 = (0, S', +', *', <') and L2 = (0, S'', +'', > *'', <''), there be this axiom: > > S'S'S'S'...SS(0) = S''S''S''S''S''...S''S''S''(0) It was meant to be: S'S'S'S'...S'S'(0) = S''S''S''S''S''...S''S''S''(0) > > where the numeral on the left of = is of different length > (in term of FOL language symbols) than the one on the right. > > Note that all the sub-languages mentioned above are of "sibling" > level with each other: hence all the (successor function) symbols > and, given group B axioms, all corresponding terms involving successor > functions symbols > > In summary, that's what I meant to say when saying that Godel's work > doesn't apply to this kind of systems that would have this kind of > infinite non-logical but _sibling_ symbols. If that's not so, perhaps > an explanation could be offered? Thanks. -- ----------------------------------------------------------- Normally, we do not so much look at things as overlook them. Zen Quotes by Alan Watt ----------------------------------------------------------- |