Re: Why an inconsistent ZF may be desirable, and should be welcome.

From: Bhupinder Singh Anand (re_at_alixcomsi.com)
Date: 03/24/05 

Date: 24 Mar 2005 06:17:11 -0800

On Mar 19, 1:04 pm, george wrote:

G>> The prior question is, are you going to define it in formal
language? If so, can you avoid defining it circularly? Whether you can
define it COHERENTLY is a much harder question, and you have to answer
it BEFORE whether you have it done it "verifiably" can become relevant.
<<G

George
====
You have raised some very interesting issues - particularly regarding
the possibility of formally, coherently, and without circularity,
defining mathematical truth verifiably (and mathematical objects
constructively) - that, I feel, deserve to be addressed seriously.

Now, classically:

TARSKI'S DEFINITION : A well-formed formula [(Ax)F(x)] of a language L
is true under an interpretation M of L if, and only if, the interpreted
relation, F(x), is satisfied by every x in M.

Although this appears to be a fairly innocent formalisation of
intuitive truth, note, first, that it is silent on the question of how,
for any interpretation M, we can effectively determine whether the
relation F(x) is, indeed, satisfied by every x in M.

Second, it does not distinguish between languages of expression, which
are intended to capture elements, of the mental gestalt of an
individual, within a symbolic language (reasonably, these would include
our spoken and written languages, as also sign languages, painting,
sculpture, music, etc.), and languages of communication, which are
intended to distinguish - and effectively communicate - those of such
individual concepts that are accepted as lying within what may be
accepted, and termed, as a common collective of gestalts.

This lack of distinction is reflected in the oft encountered - and, as
I argue, unnecessary - controversy between those who believe that
whatever can be conceived must exist in a Platonic world, and those who
believe that only that which can be communicated effectively can be
claimed to exist.

Moreover, a significant consequence - of the failure to distinguish
between Platonic conception and effective communication - is that
Tarski's definition implicitly commits us to admitting, in a formal
language, such as, say, PA, implicit reference to Platonic elements, in
the domain of an interpretation M of PA, that are, clearly,
non-intuitive, and conceivable only subjectively in individual
gestalts.

Thus, the definition (implicitly) implies that we may (explicitly)
assert the closure of a formal relation under the universal quantifier
as satisfied in M if, and only if, the relation is individually, and
collectively - in the sense of algorithmically - satisfied by all the
elements in the ontology of M, even if some elements of this ontology
are not interpretations of any mathematical objects that are
representable in PA!

Now, I argue that a constructive view of Goedel's reasoning is that
such a broad, and implicit (hence ambiguous), commitment is
unnecessary, even if it is not formally invalid. It should, then,
follow that, by the principle of Occam's razor, we ought not to
unrestrictedly assert [R(x)] as collectively (i.e., algorithmically)
satisfied by all x in the standard interpretation M of PA, although we
may assert that [R(x)] is satisfied individually by any given x in M.

The significance of this, last, distinction is that the totality of
values for which [R(x)] is satisfied in M may not, then, be
constructively definable as a formal mathematical object in PA. In
other words, the classical assumption that such values always define a
'set' in any Axiomatic Set Theory such as ZF may, when interpreted
constructively, introduce an anomaly, if not an inconsistency, either
in PA or in M. If so, we may not be able to make any constructively
meaningful assertion about the totality of values that satisfy [R(x)]
in M.

This is, in fact, the basis for my formal argument for the
inconsistency of ZF - that every recursive number-theoretic relation
does not well-define a (recursively enumerable) sub-set of the natural
numbers in any Axiomatic Set Theory that is a consistent extension of
PA, if we define a mathematical object and a set constructively as
follows:

DEFINITION (i): A primitive mathematical object, of a formal
mathematical language, L, is any symbol for an individual constant,
predicate letter, or a function letter, which is defined as a primitive
symbol of L.

DEFINITION (ii): A formal mathematical object, of a formal mathematical
language, L, is any symbol for an individual constant, predicate
letter, or a function letter that is either a primitive mathematical
object of L, or one that can be introduced through definition into L
without inviting inconsistency.

DEFINITION (iii): A mathematical object, of a formal mathematical
language, L, is any symbol that is either a primitive, or a formal,
mathematical object of L.

DEFINITION (iv): A set, in the domain of any interpretation, M, of a
formal mathematical language, L, is the range of any function in M that
is an interpretation of a function letter that is a mathematical object
of L.

It follows that, under such definitions, expressions such as
'(Ax)F(x)', and '(Ex)F(x)' - in an interpretation M of a formal theory
P - may be taken to mean 'F(x) is true for all x in M', and 'F(x) is
true for some x in M', respectively, if, and only if, the predicate
letter 'F' is a formal mathematical object in P.

In the absence of a meta-proof that 'F' is, indeed, such a mathematical
object, the expressions '(Ax)F(x)' and '(Ex)F(x)' ought,
constructively, only be taken to mean that 'F(x) is true for any given
x in M', and 'It is not true that F(x) is false for any given x in M',
indicating that even if the predicate 'F(x)' is well-defined, and
decidable, in M for any given value of x, there yet may not be any
uniformly effective (algorithmic) method for such decidability.

The question arises: What exactly does this mean, and why is the
distinction important?

Taking the latter part of the question first, the distinction is
important because we do not, then, need to accept absolute limits on
our ability to adequately formalise, and effectively communicate,
mathematical concepts that are accepted as being common to a collective
of gestalts.

Now, a central issue in the development of any significant Artificial
Intelligence is that of understanding, and finding, effective methods
of duplicating the cognitive and expressive processes of the human
mind. This issue is being increasingly brought into sharper focus by
the rapid advances in the experimental, behavioural, and computer
sciences.

Penrose's "The Emperor's New Mind" and "Shadows of the
Mind" highlight what is striking about the attempts, and struggles,
of current work in these areas to express their observations adequately
- necessarily in a predictable way - within the standard
interpretations of formal propositions as offered by classical theory.

So, the question arises: Are formal classical theories essentially
unable to adequately express the extent and range of human cognition,
or does the problem lie in the way formal theories are classically
interpreted at the moment?

The former addresses the question of whether there are absolute limits
on our capacity to express human cognition unambiguously; the latter,
whether there are only temporal limits - not necessarily absolute - to
the capacity of classical interpretations to communicate unambiguously
that which we intended to capture within our formal expression.

Now, my thesis is that we may comfortably reject the first, by
recognising that we can, indeed, constructively extend Tarski's
definitions, of the 'satisfiability' and 'truth' of formal relations
and propositions, respectively, under a given interpretation,
verifiably.

So, we return to the first part of the earlier question: What exactly
does this mean?

Well, it means that we can, for instance, replace the strong,
classical, implicit interpretation of Tarski's non-constructive
definition, which, in the case of a formula with a single variable
letter, is essentially the assertion:

(i) CLASSICAL SATISFIABILITY: The well-formed formula [F(x)] of a
formal system P is satisfied classically under an interpretation M of P
if, and only if, the interpreted predicate F(x) is satisfied
collectively (i.e., algorithmically), and individually, by the elements
in the domain of M;

by the weaker, explicit assertion:

(i_a) WEAK SATISFIABILITY: The well-formed formula [F(x)] of a formal
system P is satisfied constructively under an interpretation M of P if,
and only if, the interpreted predicate F(x) is satisfied either
collectively (i.e., algorithmically), or individually, by the elements
in the domain of M.

We can, further, eliminate any implicit commitment to a Platonic
ontology by making this definition constructive - in the sense of being
effectively verifiable, as follows:

(ii) INDIVIDUAL SATISFIABILITY: The well-formed formula [F(x)] of a
formal system P is individually satisfied under an interpretation M of
P if, and only if, given any value k in M, there is an individually
effective method (which may depend on the value k) to determine that
the interpreted proposition F(k) is satisfied in M.

(iii) UNIFORM (ALGORITHMIC) SATISFIABILITY: The well-formed formula
[F(x)] of a formal system P is uniformly (algorithmically) satisfied
under an interpretation M of P if, and only if, there is a uniformly
effective method (necessarily independent of x) such that, given any
value k in M, it can determine that the interpreted proposition F(k) is
satisfied in M.

(iv) CONSTRUCTIVE SATISFIABILITY: The well-formed formula [F(x)] of a
formal system P is constructively satisfied under an interpretation M
of P if, and only if, it is either uniformly satisfied in M, or it is
individually satisfied in M.

Clearly, if [F(x)] is uniformly satisfied in M, then it is, obviously,
individually satisfied in M. However, does the converse hold?

More to the point, could Goedel's PA-undecidable proposition, say
[(Ax)R(x)], be an instance of a formula [R(x)] that is individually
satisfied in the standard interpretation M (since Goedel's reasoning
shows that [R(k)] is provable in PA for any numeral [k]), but not
uniformly (i.e., algorithmically) satisfied in M?

An interesting consequence of an affirmative answer to this question
would be that the interpreted arithmetical predicate R(x) - which is
instantiationally equivalent to a primitive recursive relation -
becomes Turing-undecidable!

Prima facie, this would appear to conflict with the classical
postulation that a number-theoretic function is Turing-computable if,
and only if, it is partial recursive. However, the conflict may be
illusory: the proof of equivalence seems to presume that there is
always a uniformly effective method for computing any given partial
recursive function . This proof would be invalid if we held,
constructively, that Goedel has shown there are total arithmetical
functions, and relations, that may not be computable, or decidable,
respectively, by any uniformly effective method .

A key question, of course, is: do we benefit significantly from a
constructive definition of Tarskian satisfiability?

An immediate, and striking, benefit is that of verifiability. We are
now able to define effective computability constructively, i.e., in a
verifiable manner, by addressing the questions:

(v) INDIVIDUALLY EFFECTIVE METHOD: When may we constructively assume
that, given any sequence s of an interpretation M of P, there is an
individually effective method to determine that s satisfies a given
P-formula in M?

(vi) UNIFORMLY (ALGORITHMICALLY) EFFECTIVE METHOD: When may we
constructively assume that there is a uniformly (algorithmically)
effective method such that, given any sequence s of an interpretation
M, s satisfies a given P-formula in M?

If the domain D of M can be assumed representable in P (which may,
ultimately, reduce to a philosophically arguable issue), then (v) can,
indeed, be answered constructively; we simply extend the classical
Church Thesis as follows:

(vii) INDIVIDUAL CHURCH THESIS: If, for a given relation R(x), and any
value a in some interpretation M of P, there is an individually
effective method such that it will determine whether R(a) holds in M or
not, then every element of the domain D of M is the interpretation of
some term of P, and there is some P-formula [R'(x)] such that:

  R(a) holds in M if, and only if, [R'(a)] is P-provable.

(In other words, the Individual Church Thesis postulates that the
domain of a relation R that is effectively decidable individually in an
interpretation M of some formal system P can only consist of
mathematical objects of P, even if R is not, itself, a mathematical
object in P.)

Moreover, (vi), too, can be answered constructively for any
interpretation M of P, if we postulate:

(viii) UNIFORM CHURCH THESIS: If, in some interpretation M of P, there
is a uniformly effective method such that, for a given relation R(x),
and any value a in M, it will determine whether R(a) holds in M or not,
then R(x) is the interpretation in M of a P-formula [R(x)], and:

  R(a) holds in M if, and only if, [R(a)] is P-provable.

(Thus, the Uniform Church Thesis postulates, first, that the domain of
a relation R that is effectively decidable uniformly - i.e.,
algorithmically - in an interpretation M of a formal system P can only
consist of mathematical objects of P; and, second, that R, too, is
necessarily a mathematical object in P.)

G>> Whatever "constructively" means. <<G

I use the term 'constructive' both in its familiar, linguistic, sense,
and in a mathematically precise sense. Mathematically, I consider a
concept as 'constructive' if, and only if, it can be defined in terms
of pre-existing concepts without inviting inconsistency. Otherwise, I
understand it in an intuitive sense to mean unambiguously verifiable,
by some 'effective method', within some finite, well-defined, language
or meta-language. Generally, it may be taken to correspond, broadly, to
Goedel's concept of 'intuitionistically unobjectionable', which,
itself, was perhaps based on Hilbert's pre-1934 notion of 'finitary'.

The concept of 'effective method' (as well of its synonym, 'mechanical
procedure') are, of course, not at all precise in classical theory, and
are intuitively taken to mean "... a process which requires no
ingenuity for its performance".

Nevertheless, I consider some consequences of defining these critical
concepts precisely in appropriate contexts as detailed above.

G>> Not so much as you might think. Feferman has already had a go at
it, arguably. See math.stanford.edu/~feferman/pa­pers/predarith.pdf
("Predicative Foundations of Arithmetic"). What he means by
"predicative" and what you mean by "constructive" are not THAT far
apart. <<G

Many thanks for the link.

Note that Feferman's Elementary theory of Finite Sets and Classes,
(EFSC), and its extensions, all contain a weak comprehension axiom
(WS-CA), and an axiom of separation (Sep).

Now, a closer look at my argument for the inconsistency of ZF will show
that, under its explicit premises, the inconsistency is derivable in
any language in which both PA, and any finite segment of PRA, can be
interpreted, and which contains any of the usual forms of the axiom of
separation or of comprehension.

My personal impression is that the perceived, post-1934, dilution of
Hilbert's finitary point of view was, perhaps, a tacit acceptance, by
him, of ZF as an intuitively consistent theory that could interpret
both PA and any finite segment of PRA (which he had shown to be
consistent).

It seems to me that such acceptance, even if tacit, could - in view of
the enormous influence of Hilbert's finitism - account for the
subsequent (and continuing) focus on interpreting all mathematical
languages within ZF, or in its co-consistent extensions, and the
striving for relative consistency with ZF, rather than for finitary
accountability outside of it, since the standard interpretation of ZF
is the (strongly counter-intuitive?) hyper-arithmetical cumulative
hierarchy (Feferman's HYP).

However, my argument is that there is also an implicit acceptance of an
implied limitation in such a point of view: if every
Tarskian-satisfiable formula of a formal language L, under an
interpretation in another formal language M, is, implicitly, assumed
provable in M, then it follows that, in actual mathematical practice,
Tarskian-satisfiability is tacitly accepted as being necessarily
algorithmic - provability in any formal language, such as M, being
independent of the substitution of any values in M for the free
variables of the formula.

This is a point of ambiguity on which I find that standard
interpretations of classical theory are silent.

Now, my thesis is that the ambiguity is removable if we interpret
Goedel's reasoning constructively. Such interpretations indicate that
an implicit acceptance of mathematical truth as necessarily algorithmic
(based on standard interpretations of Tarski's Theorem, to the effect
that the truth of the formulas of any Peano Arithmetic is not
expressible within the arithmetic) is not necessary and, by the
principle of Occam's razor, should yield precedence to a more natural
acceptance of the conclusion that there may be L-formulas that are not
algorithmically true - i.e., provable independent of any particular
substitution of values for the free variables - under the
interpretation M, but which can be shown to be individually true -
i.e., provable for each substitution of values for the free variables,
where the proof may depend on the particular values substituted - under
the interpretation M.

To get a wider perspective on this, one could consider the case of
Penrose tiles, where (apparently similar to Goedel's argument) it seems
that there is a finitary meta-proof, but no possible proof in the
formal geometry of a plane, that it can be entirely covered with a
certain shape of tile.

G>> Wrong. <<G

It would, indeed, be a pity - albeit understandable - if you were to
allow the striking contrast between your extensive scholarship, and my
limited one, to prevent you from taking a closer look at my arguments,
particularly the explicit premises on which they are based, and their
conditional conclusions. Of course that still does not guarantee that
you will feel the required time and trouble to have been justified -
although I believe that you will not find the exercise to have been
entirely futile.

G>> People have already started looking at broader (yet weaker)
paradigms. The point is that weak machinery is sufficient to do a lot
of stuff, if you go to second order. <<G

This sounds interesting. Could you be more explicit about the work to
which you are referring.

G>> The basic textbook sense. <<G

I'd be grateful if you could you give some references on textbooks that
deal formally with PRA.

G>> PA *is not* a language. PA is an axiom-set, or the formal theory
that is the closure thereof (under logical consequence). There are a
great many other theories, INCLUDING PRA, over the SAME language. <<G

This is another very interesting point, and raises the question:

What is mathematics?

Personally - without attempting to address the issue in its broader
dimensions, and without any loss of generality - I consider mathematics
simply as a set of precise, symbolic, languages.

Now, one can, of course, define a mathematical language broadly as
containing all the primitive symbols of PA, PRA and ZF, and a
collective grammar that determines the formation of well-formed
formulas, plus a set of common logical axioms etc. One could then treat
particular sub-sets of this as individual formal systems with their own
sets of deduction rules and non-logical axioms etc., that are defined
over a common, base, language.

However - in a Wittgensteinian attempt to preserve, and highlight,
their separate evolutionary origins - I prefer to treat, say, Peano
Arithmetic PA (or Russell and Whitehead's Principia Mathematica, PM,
or ZF), as a distinct language that is intended to express - in a
finite, unambiguous, and communicable manner - relations between
concepts that are external to the language PA (or to PM, or to ZF).
Each such language is, thus, in a Platonic sense, two-valued, if we
assume that a relation either holds or does not hold externally
(relative to the language).

A selected, finite, number of primitive formal assertions about a
finite set of selected primitive relations of, say, a language L are,
then, defined as axiomatically L-provable; all other assertions about
relations that can be effectively defined in terms of the primitive
relations are termed as L-provable if, and only if, there is a finite
sequence of assertions of L, each of which is either a primitive
assertion, or which can effectively be determined in a finite number of
steps as an immediate consequence of any two assertions preceding it in
the sequence by a finite set of rules of consequence.

An effective interpretation of a language L into another language, say
PM (or PA, or ZFC, or English, etc.), is essentially, then, the
specification of an effective method by which any assertion of L is
translated unambiguously into a unique assertion of PM (or PA, or ZFC,
or English, etc.). Clearly, if a relation is provable in L, then it
should be effectively decidable in any interpretation of L that shares
a common logic - since a finite proof sequence of L would, prima facie,
translate as a finite proof sequence in the interpretation. Thus,
clearly, formal provability implies algorithmic truth under any
interpretation.

I find that such a view makes it somewhat easier for me to address more
general questions such as:

Is the converse true? In other words, if an assertion is decidable in
an interpretation M of L, then does such decidability translate into an
effective method of decidability in L?

Obviously, such a question can only be addressed unambiguously if there
is an effective method for determining whether an assertion is
decidable in M. If there is no such effective method, then we are faced
with the following thesis:

THESIS: If there is no effective method for the unambiguous
decidability of the assertions of a mathematical language L under an
interpretation M, then L can only be considered a mathematical language
of intuitive expression, but not a mathematical language of effective,
and unambiguous, communication.

What this means is that, in the absence of an effective method of
decidability in a mathematical language M that is a model of, say, a
mathematical language such as PA, any correlation of soundness between
a PA-assertion and an assertion in M is essentially arguable; so it is
meaningless to ask whether, in general, an assertion of PA is decidable
under interpretation in M or not (the question of whether the assertion
is decidable in PA or not is, then, an issue of secondary consequence).

To digress a bit, such a view also makes it easier for me to address
inter-disciplinary questions, such as::

Can the Mind be considered as the standard - albeit intuitive - model M
of PA, with the brain as its domain, and can PA be considered a
formalisation of the Mind?

Note that the first part of the question can, of course, be easily
answered affirmatively, since every proof sequence of PA can,
intuitively, be recognised by, and thus be seen as an effective method
of decidability in, M.

The second part, on the other hand, can be answered negatively just as
easily, if we accept that the Mind can be seen to experience
hallucinations (reflecting synaptic patterns that, by definition, we
assume correspond to some aspects of the physical state of the brain)
that cannot conceivably be effectively verified in any consistent
formal language.

However, if we adopt the Individual and Uniform Church Theses,
(vii)-(viii) above, then every individually effective method, and every
uniformly effective method of decidability, or computability, in the
Mind should correspond to some effective method of decidability, or
computability, in any language that is used to describe the Mind.

It follows that, if, as I also argue, any two interpretations of such a
language are isomorphic, then the language can, in a sense, be taken as
adequately formalising that part of the activity of the brain that
lends itself to mathematical representation.

This was the reasoning that led me to consider whether an inconsistent
ZF could, in a sense, be welcome as such a language.

Thanks, once again, for your stimulating comments, and my apologies for
such a lengthy - and, occasionally, only obliquely relevant - response.

Regards,

Bhup

Relevant Pages

  • Re: Skolems Paradox
    ... My crude understanding is that an interpretation of a language is all ... So an uncountable set does not exist. ... But in recent times I have seen to my surprise that so many mathematicians think that these axioms of set theory provide the ideal foundation for mathematics; therefore it seemed to me that the time had come for a critique. ...
    (sci.logic)
  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... PA, however, is the de facto language of arithmetic, ... > of mathematics they regard as meaningful without resorting ... > nonstandard interpretation of someone's utterances surely ... Mathematical discourse is clearly not meaningless. ...
    (comp.theory)
  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... PA, however, is the de facto language of arithmetic, ... > of mathematics they regard as meaningful without resorting ... > nonstandard interpretation of someone's utterances surely ... Mathematical discourse is clearly not meaningless. ...
    (sci.math)
  • Re: THIS STATEMENT HAS NO PROOF IN ANY SYSTEM = true or false?
    ... PA, however, is the de facto language of arithmetic, ... > of mathematics they regard as meaningful without resorting ... > nonstandard interpretation of someone's utterances surely ... Mathematical discourse is clearly not meaningless. ...
    (sci.logic)
  • Re: Enderton problem
    ... So A appears to have a descending chain. ... It's also not elementarily equivalent to N, ... have language with usual truths about N expressible in this ... It depends on the interpretation of "<". ...
    (sci.logic)