Re: Continuum hypothesis

On Sep 14, 4:06 pm, djr...@xxxxxxxxxx wrote:
On Sep 14, 1:30 am, "R. Srinivasan" <sradh...@xxxxxxxxxx> wrote:


On Sep 14, 2:29 am, djr...@xxxxxxxxxx wrote:

On Sep 13, 4:30 pm, george <gree...@xxxxxxxxxx> wrote:

On Sep 13, 6:48 am, djr...@xxxxxxxxxx wrote:

When you say Godelian incompleteness represents reasoning that is not
finitary,

Well, it is reasoning about an infinite domain.
It is confirming the truth of a Pi-1 sentence, which has
infinitely many instances as truths.

I don't understand what you are saying. It's just a theorem.

It's a theorem about an infinite number of things and about an
infinite
realm.

Incompleteness is a natural phenomenon.

And also an infinitary one. There is no incompleteness over finite
domains.

There simply is no algorithm
for determining whether an arbitrary diophantine equation has any
solutions.

And the reason WHY that is is that an ARBITRARY Diophantine
equation can have INFINITELY many different possible coefficients.
As soon as you restrict the space of possible coefficients to
something
finite, you can use an algorithm of exhaustion.

Okay, so let's say he (RS) meant that Godel's theorem was a theorem
about formal systems with an infinite domain of discourse (e.g. the
natural numbers). My question: so what?

My definition of infinitary reasoning is that it necessarily involves
*quantification* over infinite entities, i.e., at some point you are
referrring to infinitely many inifnite entities. We are still within
finitary reasoning even if the domain is infinite, as long as the
objects quantified over are all finite (as George pointed out).

The dispute between me and those like AK taking the classical line is
the very definition of "finite" and hence "infinite". Let us consider
the fact that Godel's incompleteness theorems require the existence of
nonstandard models of PA. By my yardstick these nonstandard models are
infinitary objects because you need to quantify over (infinitely many)
nonstandard integers to define them. Although these nonstandard
integers are *formally* classified as "finite", the fact is that each
nonstandard (positive) integer rho is greater than every standard
integer, i.e.

rho > 1, 2, 3, .....

This fact makes rho an "actually" infinite entity in my view because
you need this result to even define nonstandard integers, it is a
fundamental requirement. To call these integers "finite" is not
acceptable in NAFL, which will not ;permit them.

So Godel's theorem has infinitary consequences by the NAFL yardstick.
There must be something in Godel's proof that is not acceptable in
NAFL. The attempt to formalize the notion of a formal system, such as
PA, within arithmetic itself (i.e., the arithmetization of syntax)
must be unacceptable because it is self-referential. The
quantiification over the symbols representiing infinite entities, such
as, functions may be classified as "finitary" by those taking the
classical line, but it cannot be permitted in NAFL. Once you have
defined these functions within a theory, they are infinite entities,
period; that is one of the reasons why you cannot quantify over these
in NAFL.

Note that the arithmetization of syntax enables the formalization of
Godel's reasoning in theories weaker than PA, such as Primitive
recursive arithmetic (PRA) and it is this fact which is cited to
support the claim that Godel's reasoning is finitary.

Again I am not sure I understand. I could repeat my earlier question.
Maybe our regular integer meaning for 2 could have its place taken by
some infinite set of whatever cardinality. So what? We interpret 2 as
the integer that we know and love. That's what matters. It's not clear
to me what is meant by "rejecting" nonstandard models.

I will explain NAFL in detail in a separate thread. For now, I just
observe the following. If there exists a model for NPA (the NAFL
version of Peano Arithmetic) in which "finite" means "standard
finite", then there cannot exist another model for NPA in which
"finite" means "nonstandard finite". For if both models were to be
permitted, then NAFL principles (the Main Postulate) will demand that
there must also exist a model for NPA in which "finite" means neither
"standard finite" nor "nonstandard finite" and that is not possible.

Essentially, the meaning of "finite" must be unique with respect to
NAFL theories, rather than just with respect to models for theories as
in classical logic. This is so because NAFL truths are with respect
to theories. Thus if a NAFL theory T proves that "There exists a
unique (finite) set X such that......", then T must provide a unique
construction for X and the meanings of "unique" and "finite" get fixed
with respect to T rather then just with respect to models for T.
Whereas classically, the uniqueness is enforced in models of T, but
not with respect to T itself, in the sense that different models for T
can have different constructions for X with possibly different
meanings for finite.

Note also that the NAFL model is a completely different beast from the
classical model; the NAFL model, unlike the classical one, gets
generated by a NAFL theory T* (which I call the "interpretation" of
T); only propositions provable/refutable in T* are assigned the value
"True". This is also vital to understanding why nonstandard models are
not permitted for NAFL theories.

As for Godel, what exactly is it you object to, his method of proof,
or the result, or both? Suppose it's the result (or both). Do you
believe that Godel's theorem is false? Do you believe that the Halting
problem can be solved? Do you believe that there *is* an algorithm
that, given an arbitrary diophantine equation, will tell you whether
it has any solutions or not? One can hardly call these problems
"meaningless" or "ill-defined", so it seems to me one must consider
them as true or false (or remain agnostic).

Let me start with the Halting problem. NAFL has a different model of
computation and a different theory of computability as compared to
classical logic. The classical Turing Machine (TM) does have an
infinite tape and at least the non-halting TM's must be considered as
infinite entities. So one cannot map "all" TM's to the natural numbers
in NAFL because that would amount to quantification over infinite
entities. So Turing's proof will not go through in NAFL.

When one does manage to capture the notion of "all" TM's in NAFL
without any direct quantification, it will turn out that the such a
notion of "all" TM's must necessarily include non-classical TM"s which
use NAFL logical principles (similar to quantum computation). So to
answer your question, the halting problem is solvable in NAFL, but the
TM that solves it may not be a classical one. Here is my paper on "The
foundations of real analysis and computability theory in NAFL" that
makes a beginning on how to formulate computability theory in NAFL:

http://arxiv.org/abs/math.LO/0506475

What about Godel's theorems? Again consistency of the NAFL theory NPA
demands its completeness, so there cannot be any undecidable
propositions in NPA and Godel's theorems fail. Why does this happen?
For starters, the assumptions made in deriving Godel's incompleteness
theorems will fail in NAFL. For example, there is no list of "all
proofs" of NPA in NAFL. Because NAFL requires that whenever NPA proves
the existence of inifnitely many natural numbers that satisfy some
property (in the language of NPA), then NPA must also prove the
existence of the corresponding infinite class of natural numbers. It
follows that these "non-classical" proofs cannot be separated out from
the classical ones in a purported list of "all" proofs of NPA. So the
proofs in NPA cannot even be mapped to the natural numbers, as assumed
by Godel for classical PA.

Another reason is what I mentioned earlier. The functions or
predicates in NAFL already have arguments that can take on arbitrary,
and hence, infinitely many values. In NAFL, one must necessarily treat
these as infinite entities and cannot separate out the meanings
already given to them and just treat these as "symbols", devoid of any
meaning. E.g. when we know that some variable can take on infinitely
many values (natural numbers), then a particular value gets assigned
if and only if the human mind assigns that value; when no value is
assigned by the human mind, the variable is in a superposed state of
having all the possible values. So it is not possible to divest the
meaning assigned to such a variable and treat it as a mere (finite)
symbol that can be quantified over. In fact it cannot be quantified
over in NAFL, because it must be treated as an inifnite entity.

This is also why an "aribtrary diophantine equation" is not a
legitimate entity in NAFL. Because that entity can only be created by
quantification over infinite entities; we are talking of infinitely
many possible diophantine equations, each with possibly infinitely
many solutions, etc.

Suppose it's the method of proof (or both). The way you say there
"must be" something unacceptable about Godel's reasoning makes me
think that you do not have any particular objection to the proof, and
are really objecting to the result. But then you say his reasoning
uses "self-reference". So? It just so happens that this can be done in
any reasonable fragment of arithmetic. Maybe someone like Peter Smith
can explain why there is nothing wrong with Godel's proof.

If one accepts classical logic, then I will concede that there is
probably nothing wrong with Godel's proof. But here I am arguing from
a new logic NAFL.

I was not under the impression that Godel's proof required
quantification over all functions. My understanding is that Godel's
proof goes through in any formal system with sufficient arithmetical
apparatus to carry it out. This means, containing minimal arithmetic
or Q. Q does not have the notion of arbitrary function.

One could formalize Godel's incompleteness theorems in Q, but only via
arithmetization of syntax. For example, Godel's theorems, as applied
to PA ,may be encoded and proven in Q. The quantification over the
function symbols,etc. occurs prior to the coding, according to my
understanding. Basically NAFL will not permit such an coding, wherein
an infinite entity is encoded by a finite natural number; that can
only be done by quantification which is illegal in NAFL. And as I
explained in the previous paragraph, one cannot justify such
quantification by asserting that only (finite) symbols are being
quantified over.

Regards, RS

.

Relevant Pages

  • Re: Continuum hypothesis
    ... That makes infinite sets impredicative ... It is the NAFL truth ... You say the syntax is that of classical first order logic. ... Kronecker had to say about this. ...
    (sci.logic)
  • Re: "Godel got it all wrong"
    ... For a logic (NAFL) in which Godel's theorems do not go through see ... There is no such thing as an arbitrary infinite object ... Every formal proposition of NPA is either provable or refutable in NPA ... notion of provability itself is not formalizable in NAFL theories, ...
    (sci.logic)
  • Re: The Modified Halting Problem, Take ??? .
    ... Turing tapes" will not be a set or even a proper class in NAFL, ... each tape itself is an infinite entity. ... They're usually described as potentially infinite or finitely unbounded. ... and there is no last digit of Pi ever computed which one would think ...
    (sci.logic)
  • Re: infinitely many nns = infinite nns?
    ... I have already explained in sci.logic threads as to how NAFL deals ... quantification over infinite classes is banned. ... sequence of closed real intervals: ... can only be possible if open intervals of reals ...
    (sci.logic)
  • Re: A Possible "solution" to the Halting Problem
    ... Pi is an infinite abstract object. ... NAFL and it is very restricted as compared to classical logic. ... TMs served as protypical ... this is what I mean by saying that quantification over infinite objects ...
    (sci.logic)