Comments (by well-wishers)
01
& Notes (by B. S. Anand)
(Random
thoughts and extracts from on-going correspondence on issues of current
interest in mathematics, mathematical logic, philosophy and related subjects)
14 April
2001
Comment : The meta-expression ~(x)├S R(x) appears to blur the distinction between our being able to say for any x that we do not have a proof of R(x), and our having a
proof-sequence in S showing
that the formula is unprovable in S. The subtlety of Gφdel 's argument is that he can distinguish these, and prove
informally and meta-logically that the Gφdelian formula is unprovable-in-S, without
this being itself a formal proof-in-S, which of course would lead to a straight contradiction.
Note : On a distinction between informal,
meta-logical truth and logical provability
1 For any x we do not have a proof of R(x) in S
Assuming S to be a valid formalisation of Peanos Arithmetic A, we note that the following meta-statements, in a constructive meta-theory M of S, are meta-logically equivalent forms of the meta-expression For any x we do not have a proof of R(x) in S:
Ψ R(x) is not provable in S for any x
Ψ (x) ~├S R(x)
Ψ ~├S R(1) & ~├S R(2) & ~├S R(3) & ...
Ψ (x) ~R(x) is provable in S
Ψ ~R(1) is provable in S & ~R(2) is provable in S & ~R(3) is provable in S & ...
Ψ (x)R(x) is not provable in S
Ψ R(1) is not provable in S & R(2) is not provable in S &R(3) is not provable in S & ...
where we use the symbolism x in the meta-theory M to emphasise that compound meta-statements in M validly permit only constructive values for x.
In addition, if the Gφdel-number of R(x) is r, and the Gφdel-number of the variable x is 17, then the above are meta-logically equivalent, in Gφdels notation, to the arithmetical sentence Q :
(x) ~ Bew [ Sb (r : (17, z(x))) ].
This means that, for instance :
R(x) is not provable in S for any x holds in M if and only if the arithmetical sentence Q holds in A.
2 There is a proof-sequence in S showing that the formula R(x) is unprovable in S
In contrast, the meta-logically equivalent form, in the meta-theory M of S, of the meta-expression There is a proof-sequence in S showing that the formula R(x) is unprovable in S is the following meta-statement in M :
├S ~ Bew (r)
If the Gφdel-number of R(x) is r, then ~ Bew (r) also has some Gφdel-number r', and the above is meta-logically equivalent to the arithmetical sentence Q' :
Bew (r').
This now means that, for instance :
There is a proof-sequence in S showing that the formula R(x) is unprovable in S holds in M if and only if the arithmetical sentence Q' holds in A.
3 The two are distinctly different propositions
Clearly, the arithmetical sentences (x) ~ Bew [ Sb (r : (17, z(x))) ] and Bew (r') bring out the distinction in A between For any x we do not have a proof of R(x) in S and There is a proof-sequence in S showing that the formula R(x) is unprovable in S.
4 R(x) is not provable in S for all x
Similarly, we note that the following meta-statements, in the meta-theory M of S, are meta-logically equivalent forms of the meta-expression R(x) is not provable in S for all x :
Ψ ~(x)├S R(x) :
Ψ
(x)R(x) is not provable in S
Ψ
~(x)R(x) is provable in S
In addition, if the Gφdel-number of R(x) is r, and the Gφdel-number of the variable x is 17, then the above are meta-logically equivalent, in Gφdels notation, to the arithmetical sentence Q'' :
~(x) Bew [ Sb (r : (17, z(x))) ].
This means that, for instance :
R(x) is not provable in S for all x holds in M if and only if the arithmetical sentence Q'' holds in A.
The distinction between the two Arithmetical sentences of A, ~(x) Bew [ Sb (r : (17, z(x))) ] and (x) ~ Bew [ Sb (r : (17, z(x))) ], is of course obvious.
5 Gφdels implicit intuitionistic thesis
In Re-visiting Gφdels proof of undecidability we propose a formalisation of the concept of constructive and intuitionistically unobjectionable reasoning, reflected in our use of the notation x above, through appropriate meta-postulation.
Accordingly, we consider there the consequences of explicitly meta-postulating that, for instance, the meta statement R(x) is provable in S for all x of M, corresponding to the arithmetical sentence (x) Bew [ Sb (r : (17, z(x))) ] of A, and the meta-statement R(x) is provable in S of M, corresponding to the arithmetical sentence Bew (r) of A, are meta-logically equivalent.
(4/19/01 7:09:40 PM)
13 April 2001
Comment : The
interplay between logic and meta-logic, and between open formulae with a free
variable, and closed formulae with the variables universally quantified, is
extremely tricky.
Note
: On implicit meta-postulations underlying Gφdels reasoning
Re-visiting Gφdels proof of undecidability considers the consequences of explicitly meta-postulating that which we intuitively intend by the notation 'R(x)'.
It addresses the question : Does 'R(x)' represent a denumerable number of functions, or can it represent a transfinite number of functions?
This is the same as asking whether Peano's axiom schemas are denumerable or transfinite.
More precisely, the question, expressed meta-mathematically, is :
In a formalisation S of Peanos Arithmetic, is [I : R(x) is provable in S] meta-equivalent to [II : R(x) is provable in S for all x] or to [III : (x)R(x) is provable in S]?
Formal Number Theory implicitly meta-postulates the meta-equivalence of I and III, i.e. of R(x) is provable in S and (x)R(x) is provable in S.
This means that both R(x) is provable in S and (x)R(x) is provable in S translate in any interpretation A of S as (x)R(x) is provable in A, from which we can only conclude the infinite set of statements R(x) holds in A where the range of x can be denumerable or transfinite.
Clearly, this does not capture the essence of the meta-statement R(x) is provable in S, since, under interpretation, this meta-statement actually establishes that R(x) is provable in A for all values of x, which is meaningless if the range of x is transfinite.
We thus address the question of whether R(x) is provable in S can be meta-postulated as meta-equivalent to R(x) is provable in S for all x, which latter can be expressed more specifically as the meta-statement (x)R(x) is provable in S, where we use the notation x to emphasise that the range of the variable x in meta-statements in M need not be the range of x under any interpretation of S involved in the meta-statement.
Now it does appear that, if we are to adopt a constructive and intuitionistically unobjectionable approach, we must then accept that the range of x in meta-statements such as this can only be denumerable.
In this case, we should be at liberty to meta-postulate the meta-equivalence of I and II, i.e. of R(x) is provable in S and R(x) is provable in S for all x without fear of contradiction.
The question arises : What does the absence of such a meta-postulate indicate?
Clearly, if we permit a transfinite range for x, then we need to either provide some meaningful interpretations to the transfinite number of provable statements R(x) is provable in S, or take the stand that R(x) is provable in S for all x is not a meaningful meta-statement.
However, the latter option is not available if we accept that every recursive function and relation can be expressed in S, since, if R(x) is a recursive relation, then each of the above meta-statements I, II and III can be expressed within S.
Thus the absence of a meta-equivalence between I and II is essentially a tacit acceptance that the range of x may be transfinite in meta-statements, if we can provide suitable interpretations to the concept of provability of a transfinite set of statements. I do not touch upon this issue here.
What I do show in my papers, however, is that if we restrict ourselves to a constructive and intuitionistically unobjectionable approach in our meta-reasoning when meta-postulating I as meta-equivalent to II, then we arrive at a contradiction if we accept that every recursive function and relation can be expressed in S.
I take this to mean, firstly, that we cannot have a standard (denumerable) model of a formal system S in which every recursive function and relation is expressible within S in a constructive and intuitionistically unobjectionable way.
Since this apparently contradicts the Skolem-Lφwenheim theorem, I conclude the existing proofs establishing that every recursive function and relation is expressible within S may be fundamentally flawed.
A possible flaw is an invalid use of the Gφdel β-function, which validly permits sequences of determinate, if undetermined, length to be represented by formulas of a formal system S.
This only establishes that every recursive function can be represented in S for any given set of values of the variables contained in it.
However the Gφdel β-function cannot be used to validly construct a formula strongly representing a primitive recursive function, which is essentially an infinite sequence of indeterminate length.
This means the standard proofs may not unequivocally establish that every recursive function can itself be represented in S.
13 April 2001
Comment : [Harry Fisher
<harry@harrylfisher.fsnet.co.uk>] We can, in principle, write out
any finite sequence of digits, say for e, but this must of course be only an
approximation to the true value. This argument insists that e has a
non-terminating sequence of digits, not a string of length Aleph zero; and that
the writing out of e is a non-terminating process, impossible of completion.
Note
: A perspective on creation through definition the Cantor way
1. Consider the transcendental numbers e and π.
2. Consider the decimal representations :
e' = e - [e] = 0. e1 e2 e3
π' = π - [π] = 0. π1 π2 π3
where ei and π i are the ith digits in the decimal representations of e' and π' respectively.
3. We define the number n such that :
n = 0. n1 n2 n3
where :
ni = 0 if ei ≠ π i
and :
ni = 1 if ei = π i
4. Clearly n looks like a number, just as the Liar construction looks like a sentence, and the Russell construction looks like a set.
5. In each case the form of the constructed element does not violate the rules of the grammar determining the form of the accepted, meaningfully constructed and well-defined elements of the language.
6. The question arises, however : Is the construction valid and intuitionistically unobjectionable?
7. Is there a guarantee that no proof will later emerge (as in the case of the Russell set, or Gφdels undecidable sentence) that will lead to an inconsistency?
13 April 2001
Comment : [Harry Fisher
<harry@harrylfisher.fsnet.co.uk>] Yes, but . . . This is an
interesting case, surely. We can exploit the superb symmetry in other ways,
too. Suppose we list on the RHS only irrationals, and only a finite number of
them; then by reflection we have, on the LHS, the same strings of digits,
inverted left to right.
Would you not accept that these numbers
exist to the left of the radix point, and that therefore "infinite
integers" have been generated, and written out in full precision? It is of
course to be noted that "infinite integers" are claimed to exist in
the theory named "non-standard analysis", for which Abraham Robinson
is largely responsible.
If you answer
NO then I completely agree! I
immediately offer my next inference:
that the non-existence of these "infinite integers" to the
left of the radix point precludes existence for their mirror images to the
right of the radix point. In other words we cannot write out in full the
decimal expansion for any irrational.
Note
: On Harry Fishers remark regarding Jailtons reasoning
It certainly
conveys more, with greater accuracy and completion, to say that 'e' has a
non-terminating sequence of digits, rather than to say that it is a string of
length Aleph zero; thus emphasising that the writing out of e is a
non-terminating process, impossible of completion
Clearly, instead
of focusing on the postulated abstract existence of finite, infinite
and transfinite mathematical elements, which immediately involves some form of
static Platonism (whether overt or covert), we should really be focusing
on dynamic finite, infinite and transfinite processes.
Thus we should
be talking only of dynamically generating finite, infinite and
transfinite numbers. The cardinality of a particular type of number is then a
property not of the set of all numbers of that particular type
- and of postulating a possibly inconsistent abstract existence to such an entity
- but a property of the nature of the dynamic generating process involved in
the construction..
Currently
mathematics equates the two, which is reflected most vividly in the accepted
definition of a function as a mapping (which implicitly postulates
that a function is determined by the totality of its values), and in the
theorem on the completeness of metric spaces (which also implicitly
postulates that equivalent Cauchy sequences have the same limit - implying that
their generating processes must yield identical results).
If there are
recursive functions that cannot be represented formally, I take it to mean that
the Platonist doctrine for capturing the essence of such functions through the
postulated existence of abstract entities such as their defining sets,
is of limited value.
Similarly if, as
I show in papers that are still only in handwritten form, we can construct two
identical - not merely equivalent - Cauchy sequences that correspond, however,
to two dynamic processes that yield different limits, then the theorem on the
completeness of metric spaces collapses, along with the absoluteness of the
Platonist doctrine.
The views expressed
here are not necessarily those of Harry Fisher harry@harrylfisher.fsnet.co.uk
13 April 2001
Comment : [Anthony P. Stone
<stone_catend@compuserve.com>] I have to make the following comment on Jailton
Ferreira's paper <http://arXiv.org/abs/math/0103124>, and I understand that Harry
agrees. In section 2, there are the correspondences:
...f6 f5 f4 f3 f2 f1 ↔ 0. f1 f2 f3 f4 f5 f6 ...
In order to
include all the real numbers from 0 to 1 on the right hand side, some of them are
non-terminating decimals. In those cases the left hand side is
not finite, and is therefore, unfortunately, not a natural number.
Note
: On Jailtons objection to Cantors argument (as I understand it)
1. Assume that we can constructively set up a 1-1 correspondence (in an intuitionistically unobjectionable manner) :
n ↔ rn ↔ 0. rn,1 rn,2 rn,3
between the integers n, and the real numbers rn between 0 and 1, where 0. rn,1 rn,2 rn,3 is the binary representation of rn, so that rn,i = either 0 or 1.
2. The question arises : can we define a real number :
s ↔ 0. s1 s2 s3
such that si ≠ ri,i for all i?
3. If so, then the real number s lies between 0 and 1, and so must correspond to some integer k in the above 1-1 correspondence. We then have that :
k ↔ rk ↔ 0. rk,1 rk,2 rk,3
and
k ↔ s ↔ 0. s1 s2 s3
4. We thus have the contradiction :
si = rk,i for all i, and
sk ≠ rk,k.
5. The question arises : even assuming the above 1-1 correspondence n ↔ rn can be constructively established, is the above definition of s constructive and intuitionistically unobjectionable?
6. Prima facie, Cantors reasoning appears to be that of Platonistic creation through definition, similar to the definition of the Liar sentence as The Liar sentence is a lie, or that of the Russell set as The set of all sets that are not members of themselves, or Gφdels postulation that his primitive recursive sentence ~ [ xB [ Sb ( y : (19, z(y) ) ) ] ] can be represented in his formalisation of Peanos Arithmetic.
7. Thus Cantors reasoning can only be taken to reasonably conclude that there is no constructive and intuitionistically unobjectionable way of constructing s even if there is some constructive and intuitionistically unobjectionable way of setting up the 1-1 correspondence n ↔ rn.
8. We cannot, however, conclude from this reasoning that there is no way of setting up the 1-1 correspondence n ↔ rn in a constructive and intuitionistically unobjectionable way.
The views expressed here are not necessarily those of Jailton C. Ferreira <jailton@cnen.gov.br>
(Updated : 5/31/01 2:16:24 AM by re@alixcomsi.com)