From: [email protected]
To: [email protected]
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_1ExAyP(x,y) Sigma_2AxEyP(x,y) Pi_2etc.
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/[email protected]/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 [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
