|
Re: The seven step-Mathematical preliminaries
Bruno Marchal wrote:
>
> On 10 Jun 2009, at 02:20, Brent Meeker wrote:
>
>
>
>> I think Godel's imcompleteness theorem already implies that there must
>> be non-unique extensions, (e.g. maybe you can add an axiom either that
>> there are infinitely many pairs of primes differing by two or the
>> negative of that). That would seem to be a reductio against the
>> existence of a hypercomputer that could decide these propositions by
>> inspection.
>
>
> Not at all. Gödel's theorem implies that there must be non-unique
> *consistent* extensions. But there is only one sound extension. The
> unsound consistent extensions, somehow, does no more talk about
> natural numbers.
OK. But ISTM that statement implies that we are relying on an intuitive notion
as our conception of natural numbers, rather than a formal definition. I guess I
don't understand "unsound" in this context.
>
> Typical example: take the proposition that PA is inconsistant. By
> Gödel's second incompletenss theorem, we have that PA+"PA is
> inconsistent" is a consistent extension of PA. But it is not a sound
> one. It affirms the existence of a number which is a Gödel number of a
> proof of 0=1. But such a number is not a usual number at all.
Suppose, for example, that the twin primes conjecture is undecidable in PA. Are
you saying that either PA+TP or PA+~TP must be unsound? And what exactly does
"unsound" mean? Does it have a formal definition or does it just mean
"violating our intuition about numbers?"
Brent
>
> An oracle for the whole arithmetical truth is well defined in set
> theory, even if it is a non effective object.
>
> Bruno
>
> http://iridia.ulb.ac.be/~marchal/>
>
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
RE: The seven step-Mathematical preliminaries
Some parts of this message have been removed.
Learn more about Nabble's security policy.
> Date: Wed, 10 Jun 2009 09:18:10 +0200 > From: torgny@...> To: everything-list@...> Subject: Re: The seven step-Mathematical preliminaries > > > Jesse Mazer skrev: >> >> >>> Date: Tue, 9 Jun 2009 18:38:23 +0200 >>> From: torgny@...>>> To: everything-list@...>>> Subject: Re: The seven step-Mathematical preliminaries >>> >>> For you to be able to use the word "all", you must define the "domain" >>> of that word. If you do not define the domain, then it will be >>> impossible for me and all other humans to understand what you are >>> talking about. >> >> OK, so how do you say I should define this type of "universe"? Unless >> you are demanding that I actually give you a list which spells out >> every symbol-string that qualifies as a member, can't I simply provide >> an abstract *rule* that would allow someone to determine in principle >> if a particular symbol-string they are given qualifies? Or do you have >> a third alternative besides spelling out every member or giving an >> abstract rule? > > You have to spell out every member.
Where does this "have to" come from? Again, is it something you have a philosophical or logical definition for, or is it just your aesthetic preference?
Because in a *rule* you are
> (implicitely) using this type of "universe", and you will then get a > circular definition.
A good rule (as opposed to a 'bad' rule like 'the set of all sets that do not contain themselves') gives a perfectly well-defined criteria for what is contained in the universe, such that no one will ever have cause to be unsure about whether some particular symbol-string they're given at belongs in this universe. It's only "circular" if you say in advance that there is something problematic about rules which define infinite universes, but again this just seems like your aesthetic preference and not something you have given any philosophical/logical justification for.
Jesse
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@... To unsubscribe from this group, send email to everything-list+unsubscribe@... For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
|
|
RE: The seven step-Mathematical preliminaries
Some parts of this message have been removed.
Learn more about Nabble's security policy.
From: marchal@...To: everything-list@...Subject: Re: The seven step-Mathematical preliminaries Date: Wed, 10 Jun 2009 18:03:26 +0200 On 10 Jun 2009, at 01:50, Jesse Mazer wrote:
Isn't this based on the idea that there should be an objective truth about every well-formed proposition about the natural numbers even if the Peano axioms cannot decide the truth about all propositions? I think that the statements that cannot be proved are disproved would all be ones of the type "for all numbers with property X, Y is true" or "there exists a number (or some finite group of numbers) with property X" (i.e. propositions using either the 'for all' or 'there exists' universal quantifiers in logic, with variables representing specific numbers or groups of numbers). So to believe these statements are objectively true basically means there would be a unique way to "extend" our judgment of the truth-values of propositions from the judgments already given by the Peano axioms, in such a way that if we could flip through all the infinite propositions judged true by the Peano axioms, we would *not* find an example of a proposition like "for this specific number N with property X, Y is false" (which would disprove the 'for all' proposition above), and likewise we would not find that for every possible number (or group of numbers) N, the Peano axioms proved a proposition like "number N does not have property X" (which would disprove the 'there exists' proposition above).
We can't actual flip through an infinite number of propositions in a finite time of course, but if we had a "hypercomputer" that could do so (which is equivalent to the notion of a hypercomputer that can decide in finite time if any given Turing program halts or not),
>Such an hypercomputer is just what Turing called an "oracle". And the haslting oracle is very low in the hierarchy of possible oracles. And Turing results is that even a transfinite ladder of more and more powerful oracles that you can add on Peano Arithmetic, will not give you a complete theory. Hypercomputing by constructive extension of PA, with more and more powerful oracles does not help to overcome incompleteness, unless you add non constructive ordinal extension of "hypercomputation". This is the obeject of the study of the degrees of unsolvability, originated by Emil Post.
Interesting, thanks. But I find it hard to imagine what kind of finite proposition about natural numbers could not be checked simply by plugging in every possible value for whatever variables appear in the proposition...certainly as long as the number of variables appearing in the proposition is finite, the number of possible ways of substituting specific values for those variables is countably infinite and a hypercomputer should be able to check every case in a finite time. Does what you're saying imply you can you have a proposition which somehow implicitly involves an infinite number of distinct variables even though it doesn't actually write them all out? Can all propositions about arbitrary *real* numbers (which are of course uncountably infinite) be translated into equivalent propositions about whole numbers in arithmetic? Or am I taking the wrong approach here, and the reason a hypercomputer can't decide every proposition about arithmetic unrelated to the issue of how many distinct variables can appear in a proposition?
Jesse
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@... To unsubscribe from this group, send email to everything-list+unsubscribe@... For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
Of course, Torgny stops, in the UD Argument, at step 0. He disbelieves
"classical computationalism".
The "yes doctor" is made senseless; because "he is a zombie", and
Church thesis becomes senseless, because he is ultrafinitist, and
Church thesis concerns functions from N to N, or from N to 2, and NXN
to N, ... It concerns those computable and non computable objects. N=
{0, 1, 2, 3, ...}.
But yes, we need N, and its structure (N,+,x). We cannot prove that N
exists. But we can postulate its existence, give it a recursive name,
and generate and develop more and more simple and powerful theories
about it and its structure. Usual math use N, and its images all the
times. Only a philosopher can be paid to doubt N. A good thing!
Without N, no universal machine, no universal person.
And no Mandelbrot Set M is available for an ultrafinitist, given the
bijection between N and the little Mandelbrots (those the M set is
made of!).
Here
http://www.youtube.com/watch?v=1l9N5a0nxuQ&feature=channelA beautiful illustration that the M set summarizes its "histories", 2
times, 4 times, 8 times 16 times, 32 times ... around its little
Mandelbrot sets, (or around its histories ...). In the zoom here, a
feature of the history is "going near the tail of a little Mandelbrot
set", and both the music and image coloring (different in the zoom in
and the zoom out) illustrates that "Hopf bifurcation" where the
neighborhoods are multiplied by two, iteratively, and with an
accelerating frequence, so that the limit (of 2^n) gives a little
mandelbrot set (or ...).
Bruno
On 10 Jun 2009, at 18:24, Bruno Marchal wrote:
>
>
> On 10 Jun 2009, at 02:20, Brent Meeker wrote:
>
>
>
>
>> So we believe in the consistency of Peano's arithmetic because we
>> have a
>> physical model.
>
> Why physical? And do we have a physical model? I would say we belive
> in the consistency (and soundness) of PA because we have a model of
> PA, the well known structure (N, 0, +, *).
>
> If comp is true, there is no physical model at all. (But this is not
> something on which I want to insist for now).
>
> Bruno
>
>
>
> http://iridia.ulb.ac.be/~marchal/>
>
>
>
> >
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
 RE: The seven step-Mathematical preliminaries
On 10 Jun 2009, at 20:00, Brent Meeker wrote:
>
> Bruno Marchal wrote:
>>
>> On 10 Jun 2009, at 02:20, Brent Meeker wrote:
>>
>>
>>
>>> I think Godel's imcompleteness theorem already implies that there
>>> must
>>> be non-unique extensions, (e.g. maybe you can add an axiom either
>>> that
>>> there are infinitely many pairs of primes differing by two or the
>>> negative of that). That would seem to be a reductio against the
>>> existence of a hypercomputer that could decide these propositions by
>>> inspection.
>>
>>
>> Not at all. Gödel's theorem implies that there must be non-unique
>> *consistent* extensions. But there is only one sound extension. The
>> unsound consistent extensions, somehow, does no more talk about
>> natural numbers.
>
> OK. But ISTM that statement implies that we are relying on an
> intuitive notion
> as our conception of natural numbers, rather than a formal definition.
You are right. We have to rely on our intuition. After Gödel we know
that even our use of formal system has to be based on our intuition of
the natural number, and we don't have any fixed and complete
formalization of the natural numbers.
> I guess I
> don't understand "unsound" in this context.
Unsound means false in the structure (N, +, *). We can define this
"formally" in a theory which is richer than PA, like ZF set theory. Of
course we can't define "sound" for ZF. Intuition just cannot be
avoided. Today we can understand how machine can develop intuition,
despite this cannot be formalized.
>
>
>>
>> Typical example: take the proposition that PA is inconsistant. By
>> Gödel's second incompletenss theorem, we have that PA+"PA is
>> inconsistent" is a consistent extension of PA. But it is not a sound
>> one. It affirms the existence of a number which is a Gödel number
>> of a
>> proof of 0=1. But such a number is not a usual number at all.
>
> Suppose, for example, that the twin primes conjecture is undecidable
> in PA. Are
> you saying that either PA+TP or PA+~TP must be unsound?
Yes. That is why, unlike in Set Theory, nobody seriously doubt about
the excluded middle principle in the structure (N,+,*).
> And what exactly does
> "unsound" mean?
It really means false in the structure (N,+,*).
> Does it have a formal definition or does it just mean
> "violating our intuition about numbers?"
As I said, you can formalize the notion of soundness in Set Theory.
But this adds nothing, except that it shows that the notion of
soundness has the same level of complexity that usual analytical or
topological set theoretical notions. So you can also say that
"unsound" means violation of our intuitive understanding of what the
structure (N,+,*) consists in. We cannot formalize in any "absolute
way" that understanding, but we can formalize it in richer theories
used everyday by mathematicians.
Bruno
http://iridia.ulb.ac.be/~marchal/--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
On 10 Jun 2009, at 20:17, Jesse Mazer wrote:
From: marchal@...To: everything-list@...Subject: Re: The seven step-Mathematical preliminaries Date: Wed, 10 Jun 2009 18:03:26 +0200 On 10 Jun 2009, at 01:50, Jesse Mazer wrote:
>Such an hypercomputer is just what Turing called an "oracle". And the haslting oracle is very low in the hierarchy of possible oracles. And Turing results is that even a transfinite ladder of more and more powerful oracles that you can add on Peano Arithmetic, will not give you a complete theory. Hypercomputing by constructive extension of PA, with more and more powerful oracles does not help to overcome incompleteness, unless you add non constructive ordinal extension of "hypercomputation". This is the obeject of the study of the degrees of unsolvability, originated by Emil Post.
Interesting, thanks. But I find it hard to imagine what kind of finite proposition about natural numbers could not be checked simply by plugging in every possible value for whatever variables appear in the proposition...certainly as long as the number of variables appearing in the proposition is finite, the number of possible ways of substituting specific values for those variables is countably infinite and a hypercomputer should be able to check every case in a finite time.
Countably infinite does not mean recursively countably infinite. This is something which I will explain in the "seventh step thread".
There is theorem by Kleene which links Post-Turing degrees of unsolvability with the shape of arithmetical formula. With "P" denoting decidable predicates (Sigma_0) we have
ExP(x) Sigma_1 (mechanical) AxP(x) Pi_1 ExAyP(x,y) Sigma_2 AxEyP(x,y) Pi_2 etc.
This will defined countably infinite set which are more and more complex, and which needs more and more non-mechanical procedures. You can intuitively understand, perhaps, that "to be the coded" of an halting procedure (Sigma_1) needs less "hypercomputation" than "to be the coded of an everywhere defined procedure, which is Sigma_2.
Does what you're saying imply you can you have a proposition which somehow implicitly involves an infinite number of distinct variables even though it doesn't actually write them all out?
The complexity grows up even when you restrict yourself to a finite number of variables. By the theorem of Kleene, the complexity comes from the alternation of the quantifiers.
Can all propositions about arbitrary *real* numbers (which are of course uncountably infinite) be translated into equivalent propositions about whole numbers in arithmetic?
Here you are jumping from arithmetical truth to analytical truth. In principle analytical truth extends the whole arithmetical hierarchy. So the correct answer is "no". But this is for "arbitrary analytical truth". By a sort of miracle, the analytical truth that we met in the everyday practice of analysis can be translated in arithmetical proposition. A well known example is the Riemann's hypothesis which is equivalent to a Pi_1 arithmetical proposition. I have personally stopped to believe in the relevance of analytical truth in the ontology. Epistemologically, it is not difficult to build arithmetical relation such that you need analytical devices to solve them. A bit like higher cardinal in set theory can provide light in combinatorial problems in braids and knots theory.
Or am I taking the wrong approach here, and the reason a hypercomputer can't decide every proposition about arithmetic unrelated to the issue of how many distinct variables can appear in a proposition?
It is related to the number of variables, but the hierarchy grows up without necessitating to go beyond finite number of variables. The interesting story about the degree of complexity of "hypermachines" happens between the recursively countable and the less and less recursively countable, and they are all captured by formula with finite number of variables.
I hope I will be able to put some light on this in the seventh step thread, or in some possible AUDA thread in the future. The quantified "guardian angel", that is the modal logic G* extended with the quantifier, is already "undecidable" even in the presence of an oracle for the whole arithmetical truth. Even a "GOD" or "hypermachine" capable of answering all Sigma_i and Pi_i questions can still not answer general provability question bearing on a machine. The arithmetical "second Plotinian God", that is Plato's NOUS, or intellect, is already beyond the reach of the first Plotinian God (the ONE, or arithmetical truth).
No machine can make a complete theory of what machine can and cannot do. When the complexity of machine go above the treshold of universality, they are faced with an intrinsically huge complexity. Machines can understand themselves only very partially. They can progress by transforming themselves in more powerful (with respect to provability) machines, but by doing so, they augment their complexity.
Bruno
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@... To unsubscribe from this group, send email to everything-list+unsubscribe@... For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
> As I said, you can formalize the notion of soundness in Set Theory. But
> this adds nothing, except that it shows that the notion of soundness has
> the same level of complexity that usual analytical or topological set
> theoretical notions. So you can also say that "unsound" means violation
> of our intuitive understanding of what the structure (N,+,*) consists in.
> We cannot formalize in any "absolute way" that understanding, but we can
> formalize it in richer theories used everyday by mathematicians.
You're using soundness in a different sense than I'm familiar with.
Soundness is a property of logical systems that states "in this proof
system, provable implies true". Godel's Completeness Theorem shows there
exists a system of logic (first-order logic, specifically) that has this
soundness property. In other words, nothing for which an exact and complete
proof in first-order logic exists, is false.
Soundness is particularly important to logicians because if a system is
unsound, any proofs made with that system are essentially meaningless.
There are limits to what you can do with higher-order logical systems
because of this.
I think what you're bickering over isn't the soundness of the system. I
think it's the selection of the label "natural number", which is a
completely arbitrary label. Any definition for "natural number" which is
finite in scope refers to a different concept than the one we mean when we
say "natural number". Any finite subset of N is less useful for
mathematical proofs (and in some cases, much harder to define--not all
subsets of N are definable in the structure {N: +, *}, after all) than the
whole shebang, which is why we immediately prefer the infinite definition.
Anna
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
On 11 Jun 2009, at 14:48, A. Wolf wrote:
>
>> As I said, you can formalize the notion of soundness in Set
>> Theory. But
>> this adds nothing, except that it shows that the notion of
>> soundness has
>> the same level of complexity that usual analytical or topological
>> set
>> theoretical notions. So you can also say that "unsound" means
>> violation
>> of our intuitive understanding of what the structure (N,+,*)
>> consists in.
>> We cannot formalize in any "absolute way" that understanding, but
>> we can
>> formalize it in richer theories used everyday by mathematicians.
>
> You're using soundness in a different sense than I'm familiar with.
I am indeed not using the term "soundness" like it is used in
"soundness and completeness" theorem, like for first order predicate
logic.
I use it, like many "provability logician" to mean "true in the
standard (usual) model of arithmetic.
See
http://en.wikipedia.org/wiki/SoundnessThere, they call arithmetic soundness what me (and many logician) call
"soundness", when they refer to theories about numbers.
Like Mendelson I prefer to use the term logically valid, to what you
call soundness.
Should not be a problem in this list, given that we don't use the
notion of models, nor of logical validity. I refer very rarely to
Gödel's completness, and when I do so, I do it in the form " a theory
has a model iff it is consistent" (this can be proved to be the case
for first order theory).
>
> Soundness is a property of logical systems that states "in this proof
> system, provable implies true". Godel's Completeness Theorem shows
> there
> exists a system of logic (first-order logic, specifically) that has
> this
> soundness property. In other words, nothing for which an exact and
> complete
> proof in first-order logic exists, is false.
>
> Soundness is particularly important to logicians because if a system
> is
> unsound, any proofs made with that system are essentially meaningless.
> There are limits to what you can do with higher-order logical systems
> because of this.
I am not sure I follow you. You mean by "true", I guess "true in, or
satisfied by, all models", or "false in any models". A theory is sound
if what is provable in the theory is satisfied by (true in) all models
of the theory.
A deduction A => B is sound, or logically valid, if all models which
satisfy A satisfy B.
The word "true" alone has no meaning. It refers always to a model, or
to a collection of models.
>
>
> I think what you're bickering over isn't the soundness of the system.
It is the arithmetical soundness.
> I
> think it's the selection of the label "natural number", which is a
> completely arbitrary label.
Nooo...., come on.
> Any definition for "natural number" which is
> finite in scope refers to a different concept than the one we mean
> when we
> say "natural number".
I don't see what you mean here. Robinson Arithmetic, which is a finite
theory, can be see as a definition of the usual natural numbers, but
like any definitions, finite or infinite (but then recursively
axiomatisable), it has non standard models satisfying the definition.
Oh, you mean a definition of natural number such that the model would
be finite in scope. This is non sense for me. Pace Torgny.
> Any finite subset of N is less useful for
> mathematical proofs (and in some cases, much harder to define--not all
> subsets of N are definable in the structure {N: +, *}, after all)
> than the
> whole shebang, which is why we immediately prefer the infinite
> definition.
Well, there is just no categorical first order definition of the
finite sets of natural numbers. And second order definition, assumes
the notion of infinite set.
Bruno
http://iridia.ulb.ac.be/~marchal/--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
A. Wolf wrote:
>> As I said, you can formalize the notion of soundness in Set Theory. But
>> this adds nothing, except that it shows that the notion of soundness has
>> the same level of complexity that usual analytical or topological set
>> theoretical notions. So you can also say that "unsound" means violation
>> of our intuitive understanding of what the structure (N,+,*) consists in.
>> We cannot formalize in any "absolute way" that understanding, but we can
>> formalize it in richer theories used everyday by mathematicians.
>
> You're using soundness in a different sense than I'm familiar with.
> Soundness is a property of logical systems that states "in this proof
> system, provable implies true". Godel's Completeness Theorem shows there
> exists a system of logic (first-order logic, specifically) that has this
> soundness property. In other words, nothing for which an exact and complete
> proof in first-order logic exists, is false.
I'm not sure I understand this. "True" and "false" are just arbitrary
attributes of propositions in logic. I read you last sentence above as saying:
Given premises, which I assume "true", then any inference from them using
first-order logic will be "true". But that just means I will not be able to
infer a contradiction (="false"). In other words, first-order logic is consistent.
Of course if I start with contradictory premises I will be able construct a
proof in first order logic that proves "X and not-X" which is "false".
Brent
>
> Soundness is particularly important to logicians because if a system is
> unsound, any proofs made with that system are essentially meaningless.
> There are limits to what you can do with higher-order logical systems
> because of this.
>
> I think what you're bickering over isn't the soundness of the system. I
> think it's the selection of the label "natural number", which is a
> completely arbitrary label. Any definition for "natural number" which is
> finite in scope refers to a different concept than the one we mean when we
> say "natural number". Any finite subset of N is less useful for
> mathematical proofs (and in some cases, much harder to define--not all
> subsets of N are definable in the structure {N: +, *}, after all) than the
> whole shebang, which is why we immediately prefer the infinite definition.
>
> Anna
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
RE: The seven step-Mathematical preliminaries
Some parts of this message have been removed.
Learn more about Nabble's security policy.
From: marchal@...To: everything-list@...Subject: Re: The seven step-Mathematical preliminaries Date: Thu, 11 Jun 2009 14:04:17 +0200 On 10 Jun 2009, at 20:17, Jesse Mazer wrote:
From: marchal@...To: everything-list@...Subject: Re: The seven step-Mathematical preliminaries Date: Wed, 10 Jun 2009 18:03:26 +0200 On 10 Jun 2009, at 01:50, Jesse Mazer wrote:
>Such an hypercomputer is just what Turing called an "oracle". And the haslting oracle is very low in the hierarchy of possible oracles. And Turing results is that even a transfinite ladder of more and more powerful oracles that you can add on Peano Arithmetic, will not give you a complete theory. Hypercomputing by constructive extension of PA, with more and more powerful oracles does not help to overcome incompleteness, unless you add non constructive ordinal extension of "hypercomputation". This is the obeject of the study of the degrees of unsolvability, originated by Emil Post.
Interesting, thanks. But I find it hard to imagine what kind of finite proposition about natural numbers could not be checked simply by plugging in every possible value for whatever variables appear in the proposition...certainly as long as the number of variables appearing in the proposition is finite, the number of possible ways of substituting specific values for those variables is countably infinite and a hypercomputer should be able to check every case in a finite time.
>Countably infinite does not mean recursively countably infinite. This is something which I will explain in the "seventh step thread".
There is theorem by Kleene which links Post-Turing degrees of unsolvability with the shape of arithmetical formula. With "P" denoting decidable predicates (Sigma_0) we have
ExP(x) Sigma_1 (mechanical) AxP(x) Pi_1 ExAyP(x,y) Sigma_2 AxEyP(x,y) Pi_2 etc.
Ah, that makes sense--I hadn't thought of combining multiple universal quantifiers in that way, but obviously you can do so and get a meaningful statement about arithmetic that for a mathematical realist should be either true or false.
OK, but this leads to a further question. I remember from Penrose's book that he talked about various levels of oracle machines (hypercomputers)--for example, a first order-oracle machine was like a Turing machine but with an added operation that could decide in one step whether any Turing program halts or not, a second-order oracle machine was like a Turing machine but with operations that could decide whether a Turing machine program *or* a first-order oracle machine program halts, and so forth. You can go even past finite-order oracle machines into oracle machines for higher ordinals too...for example, an omega-order oracle machine can tell you whether any finite-order oracle machine halts, an omega-plus-one-order oracle machine can tell you whether any finite-order oracle machine halts *or* whether an omega-order oracle machine halts, and so forth. So I assume from what you're saying above that even an omega-order oracle machine would not be able to decide the truth value of every proposition about arithmetic just by checking cases...if that's right, what would the propositions it can't decide look like? It can't just follow the pattern you showed above of adding more universal quantifiers, since it has to be a proposition of finite length.
I've also read that countable ordinals themselves can be classed as either "computable" or "noncomputable" (which makes sense since I'm pretty sure you can come up with a formalism where every possible countable ordinal is associated with a countable symbol-string, although the same ordinal might have multiple valid ways of expressing it as a symbol string since order doesn't matter in sets, so this doesn't help with the problem of whether the cardinality of the set of all distinct countable ordinals is the same as the cardinality of the set of all distinct real numbers, i.e. all distinct countable symbol-strings). So, there is a first countable-but-noncomputable ordinal, written as omega_1^CK (where _1 refers to a subscript and ^CK refers to a superscript), which means we should also have a notion of an omega_1^CK-order oracle machine. Would there be finite propositions about arithmetic that even this fantastical device could not decide?
Can all propositions about arbitrary *real* numbers (which are of course uncountably infinite) be translated into equivalent propositions about whole numbers in arithmetic?
>Here you are jumping from arithmetical truth to analytical truth. In principle analytical truth extends the whole arithmetical hierarchy. So the correct answer is "no". But this is for "arbitrary analytical truth". By a sort of miracle, the analytical truth that we met in the everyday practice of analysis can be translated in arithmetical proposition. A well known example is the Riemann's hypothesis which is equivalent to a Pi_1 arithmetical proposition. I have personally stopped to believe in the relevance of analytical truth in the ontology. Epistemologically, it is not difficult to build arithmetical relation such that you need analytical devices to solve them. A bit like higher cardinal in set theory can provide light in combinatorial problems in braids and knots theory.
What do you mean by "analytical devices" in this context? Something like a type of hypercomputer more powerful than any countable-ordinal-level hypercomputer?
Jesse
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@... To unsubscribe from this group, send email to everything-list+unsubscribe@... For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
> There, they call arithmetic soundness what me (and many logician) call
> "soundness", when they refer to theories about numbers. Like Mendelson I
> prefer to use the term logically valid, to what you call soundness.
I may have misstated myself, but the wiki article you pointed me to agrees
with what I tried to say: A logical system is sound if every provable
statement is valid. Validity is not the same as soundness. There are valid
arguments that are unsound. For example, if I say "x is not equal to x,
therefore there are no more than five natural numbers", this is a valid
(i.e., logically true) argument. But it's also an unsound argument, because
there is no interpretation where x is not equal to x.
What you're calling soundness I would call omega-consistent, but I see from
the article that this is sometimes called "arithmetical soundness".
> The word "true" alone has no meaning. It refers always to a model, or to a
> collection of models.
One could make the same argument about the symbol "=" not having any meaning
outside of a model, but "true" has a standard meaning in logic, one that is
often used interchangeably with "valid" (a stronger property). The general
"true" means "true under any interpretation".
> Oh, you mean a definition of natural number such that the model would be
> finite in scope. This is non sense for me. Pace Torgny.
Nonsense for me too, apart from the philisophical musings.
> Well, there is just no categorical first order definition of the finite
> sets of natural numbers. And second order definition, assumes the notion
> of infinite set.
I'm not sure what you mean here. Of course there is no categorical
first-order theory of N.
Anna
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
On 11 Jun 2009, at 21:43, Jesse Mazer wrote:
>Countably infinite does not mean recursively countably infinite. This is something which I will explain in the "seventh step thread".
There is theorem by Kleene which links Post-Turing degrees of unsolvability with the shape of arithmetical formula. With "P" denoting decidable predicates (Sigma_0) we have
ExP(x) Sigma_1 (mechanical) AxP(x) Pi_1 ExAyP(x,y) Sigma_2 AxEyP(x,y) Pi_2 etc.
Ah, that makes sense--I hadn't thought of combining multiple universal quantifiers in that way, but obviously you can do so and get a meaningful statement about arithmetic that for a mathematical realist should be either true or false.
Even for just an arithmetical realist. (All mathematicians are arithmetical realist, much less are mathematical realist. I am not an arithmetical realist). Of course some "exotic" philosopher could pretend they are not arithmetical realist, but this is near non sense for me.
OK, but this leads to a further question. I remember from Penrose's book that he talked about various levels of oracle machines (hypercomputers)--for example, a first order-oracle machine was like a Turing machine but with an added operation that could decide in one step whether any Turing program halts or not, a second-order oracle machine was like a Turing machine but with operations that could decide whether a Turing machine program *or* a first-order oracle machine program halts, and so forth.
Hmm... let us say "OK" (but this could be ambiguous). This gives mainly the arithmetical hierarchy when you start from the oracle for the halting problem. There are relativized hierarchy based on any oracle, and then starting from the halting problem in that oracle. The degrees are structured in a very complex way.
You can go even past finite-order oracle machines into oracle machines for higher ordinals too...
This leads to the hyperarithmetical hierarchy and/or analytical hierarchy, where you consider formula with variables for functions or sets. There are many non trivial theorems which relate those notions (and open problems, but I have not follow the recent developments). Imo, the best book on that subject is still the book by Rogers.
for example, an omega-order oracle machine can tell you whether any finite-order oracle machine halts, an omega-plus-one-order oracle machine can tell you whether any finite-order oracle machine halts *or* whether an omega-order oracle machine halts, and so forth. So I assume from what you're saying above that even an omega-order oracle machine would not be able to decide the truth value of every proposition about arithmetic just by checking cases...if that's right, what would the propositions it can't decide look like? It can't just follow the pattern you showed above of adding more universal quantifiers, since it has to be a proposition of finite length.
Indeed, but variable can represent infinite object, like in analysis. From the point of view of computability, infinite set of natural number, or functions from N to N, can play the role of the real numbers.
I've also read that countable ordinals themselves can be classed as either "computable" or "noncomputable" (which makes sense since I'm pretty sure you can come up with a formalism where every possible countable ordinal is associated with a countable symbol-string, although the same ordinal might have multiple valid ways of expressing it as a symbol string since order doesn't matter in sets, so this doesn't help with the problem of whether the cardinality of the set of all distinct countable ordinals is the same as the cardinality of the set of all distinct real numbers, i.e. all distinct countable symbol-strings). So, there is a first countable-but-noncomputable ordinal, written as omega_1^CK (where _1 refers to a subscript and ^CK refers to a superscript),
Yes. And CK is for "Church and Kleene. You can see omega_1^CK as the least non recursive ordinal. Omega_1 (aleph_1) is the least non countable ordinal. Of course omega_1^CK is much smaller than Omega_1. And with the continuum hypothesis Omega_1 is 2^aleph_0.
which means we should also have a notion of an omega_1^CK-order oracle machine.
You are quick here! There are more than one way to make this precise.
Would there be finite propositions about arithmetic that even this fantastical device could not decide?
This can depend of which "path" you will follow going through the constructive ordinals, and yes some path define "fantastical device" capable of answering all arithmetical questions. Obviously, this correspond to anything but machines! But yes, with comp those objects makes non sense form the third person point of view, but still are needed to figure out the first person points of view.
Can all propositions about arbitrary *real* numbers (which are of course uncountably infinite) be translated into equivalent propositions about whole numbers in arithmetic?
>Here you are jumping from arithmetical truth to analytical truth. In principle analytical truth extends the whole arithmetical hierarchy. So the correct answer is "no". But this is for "arbitrary analytical truth". By a sort of miracle, the analytical truth that we met in the everyday practice of analysis can be translated in arithmetical proposition. A well known example is the Riemann's hypothesis which is equivalent to a Pi_1 arithmetical proposition. I have personally stopped to believe in the relevance of analytical truth in the ontology. Epistemologically, it is not difficult to build arithmetical relation such that you need analytical devices to solve them. A bit like higher cardinal in set theory can provide light in combinatorial problems in braids and knots theory.
What do you mean by "analytical devices" in this context? Something like a type of hypercomputer more powerful than any countable-ordinal-level hypercomputer?
I don't think so. But such "hypercomputer" will make use of those countable but non recursive ordinal. With uncountable oracles everything becomes "trivially" computable. You can code in some arbitrary "real number" all solutions to any problem in math (not just in arithmetic). Analytical means that the variable can be real number (or arbitrary sets), but the oracles remain countable, but not necessarily recursive (or computable).
Very difficult question Jesse! Fortunately, we will not have to go through the analytical hierarchy, except perhaps to follow those who will succeed in solving the "measure problem", if that happens someday ...
Bruno
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@... To unsubscribe from this group, send email to everything-list+unsubscribe@... For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
Le 12-juin-09, à 09:31, Bruno Marchal a écrit :
>
> On 11 Jun 2009, at 21:43, Jesse Mazer wrote:
>
>>
>>
>> Ah, that makes sense--I hadn't thought of combining multiple
>> universal quantifiers in that way, but obviously you can do so and
>> get a meaningful statement about arithmetic that for a mathematical
>> realist should be either true or false.
>
>
> Even for just an arithmetical realist. (All mathematicians are
> arithmetical realist, much less are mathematical realist. I am not an
> arithmetical realist).
Raaah... Sorry. Of course I am an arithmetical realist. I am not a
*mathematical* realist (still less a physical realist).
With the month of June I have a lot of works to do, and I tend to do it
simultaneously. The result is an augmentation of mistakes! I hope you
have learned to automatically correct them. Sorry. Please, ask in case
of remaining doubt.
Bruno
http://iridia.ulb.ac.be/~marchal/--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
Le 12-juin-09, à 08:28, A. Wolf a écrit :
>
>> There, they call arithmetic soundness what me (and many logician)
>> call
>> "soundness", when they refer to theories about numbers. Like
>> Mendelson I
>> prefer to use the term logically valid, to what you call soundness.
>
> I may have misstated myself, but the wiki article you pointed me to
> agrees
> with what I tried to say:
That wiki article is not so good.
> A logical system is sound if every provable
> statement is valid.
... meaning "true in all models of the theory". OK.
Like a "tautology", for example "P OR NOT P" is true is all models
(those with P true, and those with P false).
A propositional calculus is sound if it proves only tautologies (true
in all models),
and complete if it proves all tautologies, that is: all the
propositions which are true in all models.
The intuitive idea is that a reasoning is valid if its truth status
does not depend on the way we interpret it.
> Validity is not the same as soundness.
Logicians from different fields use terms in different ways. In
provability logic and in recursion theory, soundness means often
"arithmetical soundness".
For example, in recursion theory, theory will be said Sigma_2 sound
when all Sigma_2 propositions proved in the theory are true ... in the
usual model (N,+,*).
> There are valid
> arguments that are unsound. For example, if I say "x is not equal
> to x,
> therefore there are no more than five natural numbers", this is a
> valid
> (i.e., logically true) argument. But it's also an unsound argument,
> because
> there is no interpretation where x is not equal to x.
Here most, if not all logicians, would disagree. Both in classical and
intuitionistic logic, To deduce any proposition from a falsity is
always a valid argument. Nobody will say that an argument is non valid
because its premise are absurd. Except in the "relevance logic" field.
Well, they will say that the reasoning is not ... relevant.
>
> What you're calling soundness I would call omega-consistent, but I
> see from
> the article that this is sometimes called "arithmetical soundness".
Soundness is a semantical notion. By the Tarski phenomenon such a
notion cannot be even just defined or expressed in the theory. That is
why Gödel makes the terrible effort for not using such a notion, which
was considered a bit controversial in those days.
Omega-consistency, like consistency, can be defined in a purely
syntactical way, and is much weaker than soundness.
>
>> The word "true" alone has no meaning. It refers always to a model,
>> or to a
>> collection of models.
>
> One could make the same argument about the symbol "=" not having any
> meaning
> outside of a model, but "true" has a standard meaning in logic, one
> that is
> often used interchangeably with "valid" (a stronger property). The
> general
> "true" means "true under any interpretation".
That is validity for me. But let us not debate on vocabulary,
especially before making a bit more logic.
>
>> Oh, you mean a definition of natural number such that the model
>> would be
>> finite in scope. This is non sense for me. Pace Torgny.
>
> Nonsense for me too, apart from the philisophical musings.
OK.
>
>> Well, there is just no categorical first order definition of the
>> finite
>> sets of natural numbers. And second order definition, assumes the
>> notion
>> of infinite set.
>
> I'm not sure what you mean here. Of course there is no categorical
> first-order theory of N.
>
We agree then. For the others, a theory is categorical if all its
model are isomorphic. In a sense, such a theory succeeds in capturing
completely its semantics. By well know theorems, such theories are
very rare, and in fact, when effective, very poor and very exceptional.
Bruno
http://iridia.ulb.ac.be/~marchal/--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
> Logicians from different fields use terms in different ways. In
> provability logic and in recursion theory, soundness means often
> "arithmetical soundness".
I understand.
Part of the reason for my particular viewpoint: there's a group of
professors at the college I work at who are working on bottom-up provability
of computer programs under specific constraints. "Soundness" for them means
the proof systems they use never prove a program is correct (meaning, it
meets formal, mathematically-written specifications) when it's actually
incorrect, provided the constraints are applied correctly. When the
constraints are not applied correctly, it's acceptable for the system to
prove things that aren't correct, and they still consider this sound for
their purposes.
> We agree then.
Yes, it's my fault for creating a semantics argument. I'm usually too busy
to even read the list...every once in a while something pops up and I feel
obliged to comment even when it's the middle of a conversation.
I actually have some questions for the list members that are relevant to the
list content, and this coming week is break. I may have a chance to post
them. They're much more on the philosophical side than the mathematical,
though.
Anna
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
Jesse Mazer skrev:
>
> > Date: Wed, 10 Jun 2009 09:18:10 +0200
> > From: torgny@...
> > To: everything-list@...
> > Subject: Re: The seven step-Mathematical preliminaries
> >
> > Jesse Mazer skrev:
> >>
> >>> Date: Tue, 9 Jun 2009 18:38:23 +0200
> >>> From: torgny@...
> >>> To: everything-list@...
> >>> Subject: Re: The seven step-Mathematical preliminaries
> >>>
> >>> For you to be able to use the word "all", you must define the "domain"
> >>> of that word. If you do not define the domain, then it will be
> >>> impossible for me and all other humans to understand what you are
> >>> talking about.
> >>
> >> OK, so how do you say I should define this type of "universe"? Unless
> >> you are demanding that I actually give you a list which spells out
> >> every symbol-string that qualifies as a member, can't I simply provide
> >> an abstract *rule* that would allow someone to determine in principle
> >> if a particular symbol-string they are given qualifies? Or do you have
> >> a third alternative besides spelling out every member or giving an
> >> abstract rule?
> >
> > You have to spell out every member.
>
> Where does this "have to" come from? Again, is it something you have a
> philosophical or logical definition for, or is it just your aesthetic
> preference?
It is, as I said above, for me and all other humans to understand what
you are talking about. It is also for to be able to decide what
deductions or conclusions or proofs that are legal or illegal. It has
nothing to do with my aesthetic preference.
>
> > Because in a *rule* you are
> > (implicitely) using this type of "universe", and you will then get a
> > circular definition.
>
> A good rule (as opposed to a 'bad' rule like 'the set of all sets that
> do not contain themselves') gives a perfectly well-defined criteria
> for what is contained in the universe, such that no one will ever have
> cause to be unsure about whether some particular symbol-string they're
> given at belongs in this universe. It's only "circular" if you say in
> advance that there is something problematic about rules which define
> infinite universes, but again this just seems like your aesthetic
> preference and not something you have given any philosophical/logical
> justification for.
What do you mean by "some particular symbol-string"?
I suppose that you mean by this is: If you take any particular
symbol-string from this universe, then no one will ever have cause to be
unsure about whether this symbol-string belongs in this universe. So
you are defining "this universe" by supposing that you have "this
universe" to start with. Is that not a typical circular definition?
--
Torgny Tholerus
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
RE: The seven step-Mathematical preliminaries
Some parts of this message have been removed.
Learn more about Nabble's security policy.
> Date: Fri, 12 Jun 2009 18:40:14 +0200 > From: torgny@...> To: everything-list@...> Subject: Re: The seven step-Mathematical preliminaries > > > Jesse Mazer skrev: > > > > > Date: Wed, 10 Jun 2009 09:18:10 +0200 > > > From: torgny@...> > > To: everything-list@...> > > Subject: Re: The seven step-Mathematical preliminaries > > > > > > Jesse Mazer skrev: > > >> > > >>> Date: Tue, 9 Jun 2009 18:38:23 +0200 > > >>> From: torgny@...> > >>> To: everything-list@...> > >>> Subject: Re: The seven step-Mathematical preliminaries > > >>> > > >>> For you to be able to use the word "all", you must define the "domain" > > >>> of that word. If you do not define the domain, then it will be > > >>> impossible for me and all other humans to understand what you are > > >>> talking about. > > >> > > >> OK, so how do you say I should define this type of "universe"? Unless > > >> you are demanding that I actually give you a list which spells out > > >> every symbol-string that qualifies as a member, can't I simply provide > > >> an abstract *rule* that would allow someone to determine in principle > > >> if a particular symbol-string they are given qualifies? Or do you have > > >> a third alternative besides spelling out every member or giving an > > >> abstract rule? > > > > > > You have to spell out every member. > > > > Where does this "have to" come from? Again, is it something you have a > > philosophical or logical definition for, or is it just your aesthetic > > preference? > > It is, as I said above, for me and all other humans to understand what > you are talking about. It is also for to be able to decide what > deductions or conclusions or proofs that are legal or illegal. It has > nothing to do with my aesthetic preference. Well, most humans who think about mathematics can understand rule-based definitions like "0 is a whole number, and N is a whole number if it's equal to some other whole number plus one"--you seem to be the lone exception. What's more, I kind of think you're "playing dumb" here, because I bet *you* would have little problem with a rule-based definition of a finite set that didn't actually spell out every member, like "0 is a member of the set, and N is in the set if it's equal to some other member of the set plus one, *unless* the 'other member of the set' is equal to 1,038,712 in which case no members of the set are larger than that." Here, can't you understand that the set includes every whole number from 0 to 1,038,712 without my having to write out every member? And the mental process that allows you to decide whether some string of symbols (say, 1692) would qualify as a member of that set is exactly the same as the mental process that would allow you to decide whether some string of symbols would qualify as a member of the "whole numbers" which have no upper limit.
As for being "able to decide what deductions or conclusions or proofs that are legal or illegal", how exactly would writing out all the members of the "universe" solve that? For example, I actually write out all the numbers from 0 to 1,038,712 and say that they are members of the "universe" I want to talk about. But if I write out some axioms used to prove various propositions about these numbers, they are still going to be in the form of general *rules* with abstract variables like x and y (where these variables stand for arbitrary numbers in the set), no? Or do you also insist that instead of writing axioms and making deductions, we also spell out in advance every proposition that shall be deemed true? In that case there is no room at all for mathematicians to make "deductions" or write "proofs", all of math would just consist of looking at the pre-established list of true propositions and checking if the proposition in question is on there.
> >
> > > Because in a *rule* you are
> > > (implicitely) using this type of "universe", and you will then get a
> > > circular definition.
> >
> > A good rule (as opposed to a 'bad' rule like 'the set of all sets that
> > do not contain themselves') gives a perfectly well-defined criteria
> > for what is contained in the universe, such that no one will ever have
> > cause to be unsure about whether some particular symbol-string they're
> > given at belongs in this universe. It's only "circular" if you say in
> > advance that there is something problematic about rules which define
> > infinite universes, but again this just seems like your aesthetic
> > preference and not something you have given any philosophical/logical
> > justification for.
>
> What do you mean by "some particular symbol-string"?
>
> I suppose that you mean by this is: If you take any particular
> symbol-string from this universe, then no one will ever have cause to be
> unsure about whether this symbol-string belongs in this universe. So
> you are defining "this universe" by supposing that you have "this
> universe" to start with. Is that not a typical circular definition?
No, I'm saying "take some particular collection of symbols like 0,1,2,3,4,5,6,7,8,9, then any finite ordered group of them like 21396 is a valid symbol string, and then you can use your rule to see if it qualifies as a member of the 'universe' defined by that rule" (for example, if the rule is one that gives us the set of all odd whole numbers, the symbol-string 21396 wouldn't qualify). Of course I have used the word "any" here, but the mental process that allows you to judge whether a *particular* symbol string qualifies is no different than the one that would be involved if I had said something like "take some particular collection of symbols like 0,1,2,3,4,5,6,7,8,9, then any ordered group of them *of length 10 or less* like 21396 is a valid symbol string". Somehow I doubt whether you would have any trouble judging whether a symbol string I gave you qualified as "valid" according to that criterion, even though I have not actually written out every valid symbol-string of length 10 or less.
Jesse
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@... To unsubscribe from this group, send email to everything-list+unsubscribe@... For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
|
|
RE: The seven step-Mathematical preliminaries
Some parts of this message have been removed.
Learn more about Nabble's security policy.
From: marchal@...To: everything-list@...Subject: Re: The seven step-Mathematical preliminaries Date: Fri, 12 Jun 2009 09:31:46 +0200 On 11 Jun 2009, at 21:43, Jesse Mazer wrote:
>Countably infinite does not mean recursively countably infinite. This is something which I will explain in the "seventh step thread".
There is theorem by Kleene which links Post-Turing degrees of unsolvability with the shape of arithmetical formula. With "P" denoting decidable predicates (Sigma_0) we have
ExP(x) Sigma_1 (mechanical) AxP(x) Pi_1 ExAyP(x,y) Sigma_2 AxEyP(x,y) Pi_2 etc.
Ah, that makes sense--I hadn't thought of combining multiple universal quantifiers in that way, but obviously you can do so and get a meaningful statement about arithmetic that for a mathematical realist should be either true or false.
>Even for just an arithmetical realist. (All mathematicians are arithmetical realist, much less are mathematical realist. I am not an arithmetical realist).
I assume you meant to write "I am not a mathematical realist"?
OK, but this leads to a further question. I remember from Penrose's book that he talked about various levels of oracle machines (hypercomputers)--for example, a first order-oracle machine was like a Turing machine but with an added operation that could decide in one step whether any Turing program halts or not, a second-order oracle machine was like a Turing machine but with operations that could decide whether a Turing machine program *or* a first-order oracle machine program halts, and so forth.
>Hmm... let us say "OK" (but this could be ambiguous). This gives mainly the arithmetical hierarchy when you start from the oracle for the halting problem. There are relativized hierarchy based on any oracle, and then starting from the halting problem in that oracle. The degrees are structured in a very complex way.
I don't know the meaning of the phrases "arithmetical hierarchy" or "relativized hierarchy", is there any simple way of explaining? In any case, the problem I am mainly concerned with is the set of all propositions that would be considered well-formed-formulas (WFFs) in the context of Peano arithmetic (so it would involve arithmetical symbols like + and x as well as logical symbols from first-order logic, and they'd be ordered in such a way that the symbol-string would express a coherent statement about arithmetic that could be either true or false). Is there some way to come up with a rule that would allow you to judge the true or falsity of *every* member of this set of propositions using some kind of sufficiently powerful hypercomputer (presumably a fairly powerful one like the 'omega-order oracle machine' or beyond), just by checking every possible value for the numbers that could be substituted in for variable symbols? That would allow us to make sense of the distinction between "truths about arithmetic" and "statements about arithmetic provable by some axiomatic system like the Peano axioms" (the issue Brent Meeker was talking about in the post at http:// www.mail-archive.com/everything-list@.../msg16562.html ), without having to worry about the "meaning" that we assign to arithmetical symbols like the number "2", or about philosophical questions about where our understanding of that meaning comes from. Instead we'd have a purely formal definition about how to judge the truth-value of WFFs beyond those the Peano axioms can judge, albeit one that cannot actually be put into practice for arbitrary propositions without actually having such a hypercomputer (but for some specific propositions like the Godel statement for the Peano axioms, I think we can come up with an argument for why the hypercomputer should judge this statement 'true' as long as we believe the Peano axioms are consistent, so in this sense defining arithmetical truth in terms of such a hypercomputer is *conceptually* useful).
You can go even past finite-order oracle machines into oracle machines for higher ordinals too...
>This leads to the hyperarithmetical hierarchy and/or analytical hierarchy, where you consider formula with variables for functions or sets. There are many non trivial theorems which relate those notions (and open problems, but I have not follow the recent developments). Imo, the best book on that subject is still the book by Rogers.
Again, I'm only interested here in the type of propositions that would be judged WFFs in the context of the Peano axioms, and I think in this case the variables only refer to particular numbers, right? Or is it possible to write a WFF in this context where the variables refer to "functions or sets"?
Like you I am an arithmetical realist but not necessarily a realist about arbitrary sets. I think it may be problematic to talk about sets that are so big that most of their numbers have no finite description, as must be true of any uncountable set. If there is no *rule* which maps countable ordinals to real numbers and which can be described in finite terms by a humanlike being, for example, then is it really meaningful to ask whether or not a completely incomprehensible mapping exists between these two sets? I'm not so sure, and thus I'm not sure whether I believe there is any "real truth" about the Continuum Hypothesis.
for example, an omega-order oracle machine can tell you whether any finite-order oracle machine halts, an omega-plus-one-order oracle machine can tell you whether any finite-order oracle machine halts *or* whether an omega-order oracle machine halts, and so forth. So I assume from what you're saying above that even an omega-order oracle machine would not be able to decide the truth value of every proposition about arithmetic just by checking cases...if that's right, what would the propositions it can't decide look like? It can't just follow the pattern you showed above of adding more universal quantifiers, since it has to be a proposition of finite length.
>Indeed, but variable can represent infinite object, like in analysis.
But can it do so in the context of propositions defined to be WFFs for the Peano axiomatic system?
which means we should also have a notion of an omega_1^CK-order oracle machine.
>You are quick here! There are more than one way to make this precise.
More than one non-equivalent way to make it precise, so that a number computable by one version of an "omega_1^CK-order oracle machine" might not be computable by another version? Of course even with ordinary Turing machines, there are multiple ways to design the internal state-changing rules for the machine, such that different Turing machines might respond to the same input string differently...still if a given output is computable by one universal Turing machine it should be computable by any other, so they are all "equivalent" in that sense. If we define the "order" of oracle machines in the sense I discussed (so that the third-order oracle machine can decide whether the first- or second-order oracle machines will halt given any input string of the type that could be given to a Turing machine, and so forth), then even if there could be different input-output relations for an oracle machine of a given "order", would the set of outputs "computable" by differently-designed oracle machines of that particular order not be "equivalent" in a similar sense?
Jesse
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@... To unsubscribe from this group, send email to everything-list+unsubscribe@... For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
Jesse Mazer skrev:
>
> > Date: Fri, 12 Jun 2009 18:40:14 +0200
> > From: torgny@...
> > To: everything-list@...
> > Subject: Re: The seven step-Mathematical preliminaries
> >
> > It is, as I said above, for me and all other humans to understand what
> > you are talking about. It is also for to be able to decide what
> > deductions or conclusions or proofs that are legal or illegal.
>
> Well, most humans who think about mathematics can understand
> rule-based definitions like "0 is a whole number, and N is a whole
> number if it's equal to some other whole number plus one"--you seem to
> be the lone exception.
>
> As for being "able to decide what deductions or conclusions or proofs
> that are legal or illegal", how exactly would writing out all the
> members of the "universe" solve that? For example, I actually write
> out all the numbers from 0 to 1,038,712 and say that they are members
> of the "universe" I want to talk about. But if I write out some axioms
> used to prove various propositions about these numbers, they are still
> going to be in the form of general *rules* with abstract variables
> like x and y (where these variables stand for arbitrary numbers in the
> set), no? Or do you also insist that instead of writing axioms and
> making deductions, we also spell out in advance every proposition that
> shall be deemed true? In that case there is no room at all for
> mathematicians to make "deductions" or write "proofs", all of math
> would just consist of looking at the pre-established list of true
> propositions and checking if the proposition in question is on there.
What do you think about the following deduction? Is it legal or illegal?
-------------------
Define the set A of all sets as:
For all x holds that x belongs to A if and only if x is a set.
This is an general rule saying that for some particular symbol-string x
you can always tell if x belongs to A or not. Most humans who think
about mathematics can understand this rule-based definition. This rule
holds for all and every object, without exceptions.
So this rule also holds for A itself. We can always substitute A for
x. Then we will get:
A belongs to A if and only if A is a set.
And we know that A is a set. So from this we can deduce:
A beongs to A.
-------------------
Quentin, what do you think? Is this deduction legal or illegal?
--
Torgny Tholerus
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
|
Re: The seven step-Mathematical preliminaries
2009/6/13 Torgny Tholerus < torgny@...>:
>
> Jesse Mazer skrev:
>>
>> > Date: Fri, 12 Jun 2009 18:40:14 +0200
>> > From: torgny@...
>> > To: everything-list@...
>> > Subject: Re: The seven step-Mathematical preliminaries
>> >
>> > It is, as I said above, for me and all other humans to understand what
>> > you are talking about. It is also for to be able to decide what
>> > deductions or conclusions or proofs that are legal or illegal.
>>
>> Well, most humans who think about mathematics can understand
>> rule-based definitions like "0 is a whole number, and N is a whole
>> number if it's equal to some other whole number plus one"--you seem to
>> be the lone exception.
>>
>> As for being "able to decide what deductions or conclusions or proofs
>> that are legal or illegal", how exactly would writing out all the
>> members of the "universe" solve that? For example, I actually write
>> out all the numbers from 0 to 1,038,712 and say that they are members
>> of the "universe" I want to talk about. But if I write out some axioms
>> used to prove various propositions about these numbers, they are still
>> going to be in the form of general *rules* with abstract variables
>> like x and y (where these variables stand for arbitrary numbers in the
>> set), no? Or do you also insist that instead of writing axioms and
>> making deductions, we also spell out in advance every proposition that
>> shall be deemed true? In that case there is no room at all for
>> mathematicians to make "deductions" or write "proofs", all of math
>> would just consist of looking at the pre-established list of true
>> propositions and checking if the proposition in question is on there.
>
> What do you think about the following deduction? Is it legal or illegal?
> -------------------
> Define the set A of all sets as:
>
> For all x holds that x belongs to A if and only if x is a set.
>
> This is an general rule saying that for some particular symbol-string x
> you can always tell if x belongs to A or not. Most humans who think
> about mathematics can understand this rule-based definition. This rule
> holds for all and every object, without exceptions.
>
> So this rule also holds for A itself. We can always substitute A for
> x. Then we will get:
>
> A belongs to A if and only if A is a set.
>
> And we know that A is a set. So from this we can deduce:
>
> A beongs to A.
> -------------------
> Quentin, what do you think? Is this deduction legal or illegal?
It depends if you allow a set to be part of itselft or not.
If you accept, that a set can be part of itself, it makes your
deduction legal regarding the rules. If you don't then the statement
is illegal regarding the rules (it violates the rule saying that a set
can't contains itself, which means that A in this system is not a set
thus all the reasoning in *that system* is false.
Choosing one rule or the other tells nothing about the rule itself
unless you can find a contradiction by choosing one or the other.
Regards,
Quentin
But I can't see why a set as I understand it cannot be part of
itself... {1,2,3} is included in {1,2,3} is true, what is the exact
problem with that statement ? (written differently all elements of the
set A are elements of the set B ===> A is included in B, here as A and
B are the same A is included in A.
> --
> Torgny Tholerus
>
> >
>
--
All those moments will be lost in time, like tears in rain.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en-~----------~----~----~----~------~----~------~--~---
|
