[FOM] None [Arithmetic with the biggest number]]
Vladimir Sazonov
V.Sazonov at csc.liv.ac.uk
Sat Feb 8 11:16:58 EST 2003
stevnewb at ix.netcom.com wrote:
>
> A question which has nothing to do with predicativity:
>
> Suppose we have a cwff ~B which has an infinite, but no finite models.
I am not sure what is cwff. But I guess that wff means
"well-formed formula".
[It
> can be the
> conjunction of the axioms for any theory that has no finite realizations.]
>
> Then B is n-valid [=df= valid on all and only finite domains.]
It must have an infinite model! Consider
B + exists x1,x2(x1\=x2) + exists x1,x2,x3(x1\=x2 & x1\=x3 & x2\=x3) +
...
This theory is consistent (because B is valid on all finite structures)
and, therefore, B has an infinite model (other one than ~B).
> If B is **valid** on all
> finite domains then B has models on all finite domains. The union of those
> models would have to be an infinite model. [I'm not invoking compactness
> here, merely the existence of unions.]
I am not sure what do you mean by union.
> That would entail that both B , ~B have infinite models.
Yes, but this seems to contradict to your above statement that
B is valid on all *and only* finite domains (if I understand you
correctly).
In all my reading
> in logic over the past forty years, I can't recall ever having come across
> anything that either asserted or denied the possibility of this "paradox".
Which paradox?
> Or even mentioned it.
>
> Suppose that the theory in question is the perennial favorite, Peano's
> Arithmetic. The axioms in the conjunction would be arranged so that
> the **last** axiom is
>
> "A:(n)[ n' /= 0] "
>
> [Read 'A:' and 'E:' as universal and existential quantifiers.]
>
> Then B replaces the last conjunction ' & ' with '=>' and negates the last
> axiom, so we have
>
> [&(first n-1 axioms)] => E:(n)[ n' = 0 ].
>
> In the finite models there is no problem, but how to interpret this
> distinguished n'? Perhaps as the smallest inaccessible cardinal?
It is unclear to me why =>, instead of &, is used here. Also, do you
take
into account that Peano Arithmetic PA in its contemporary formulation
has infinitely many axioms (due to the Induction *schema*)?
But, anyway, let us consider PA', a version of PA, containing
the ordinary axioms about successor operation n' (= n+1), except
that the axiom forall n (n' /= 0) is replaced by its negation
exists n (n' = 0)
Let also PA' contain all other usual axioms about addition,
multiplication, about any primitive recursive function,
and, moreover, about any (partial) recursive function.
(Let us omit here how to deal with partial functions
in these axioms; actually, in a sense partiality
may be avoided at all).
Finally, let PA' contain the Induction Schema where all
mentioned operations and the constant symbol 0 may participate.
This theory can be interpreted in any finite segment of natural
numbers {0,1,2,...,\Box}, where \Box denotes the last element
and is like to 0 (we have two zeros: the left 0 and the right \Box,
but \Box + 1 = 0; in principle, we can take \Box + 1 = \Box).
What is interesting about this arithmetic, as a language,
that all its recursive functions over finite segments
are exactly polynomial time computable (global) functions.
The induction axiom allows to prove more theorems on these
global functions. Thus, this may be considered as a
theory of polynomial time computability.
This is just to say that theories of the kind you are
interested in (as I understood you) may be quite reasonable.
This is another version of so called Bounded Arithmetic.
By the way, we may consider second order version of PA'
and discuss predicativity aspects here (analogous to
the usual predicativity, but with a specific feature
related with the problem "P=NP?"). Let me also mention
OPEN QUESTION 1:
Is second-order version of PA' stronger than PA'?
This can be read, e.g. in (some parts of) my paper
"On Bounded Set Theory" available via my home page
(cf. below).
Thus, there is nothing especially mysterious with this \Box.
However, we will see some really intriguing moments.
On the other hand, let us consider the theory
PA* = PA' + (0 /= \Box) + (0' /= \Box) + (0'' /= \Box) + etc.
Let me consider this "etc" in a less traditional way.
All these axioms are syntactical objects. Let us not mix
syntax with semantics (i.e. let us forget some aspects of
the ordinary metamathematical approach). This means that
all syntactically written axioms, formulas, definitions,
proofs, should be "feasible". We can imagine the term
0'''...' with many occurrences of "'", but this "many"
should be feasible, physically written, in principle.
Then PA* describes a theory of a finite segment of natural
numbers (due to Induction Schema which is essentially about
finiteness of the objects axiomatized) and about computability
(recursive functions) over the segment {0,1,2,...,\Box}.
But \Box represents just some non-feasible number
(as well as \Box-1, \Box-2,...). 0,1,2,... are feasible.
We can think that \Box = 2^1000 or the like, and even
postulate this (concrete; but is it essentially more
concrete than 2^{\aleph0}?) value of \Box in some way.
Call the resulting theory PA**.
OPEN (SEMI-FORMAL) QUESTION 2: Is second order version of PA*
(or of PA**) stronger than PA* (resp., PA**) under assumption
that all proofs should be feasible?
This is non-traditional consideration. Traditionally,
when the above "etc" and the syntax is understood
in the same way as natural numbers described by PA
(is not this a vicious circle?), the theory PA* has
an infinite "non-standard" model, like non-standard
models of PA.
In any case there is nothing mysterious here. Even
the vicious circle mentioned is avoided by reducing
everything, say to ZFC. But from the point of view
of foundations and corresponding philosophy,
I see this problem with the vicious circle.
Another OPEN FORMAL QUESTION 3:
Is there any model for PA* whose recursive
(polynomial time computable) functions
satisy also the second-order version of PA*?
Same (informally) for PA*- or PA**-like theories
under assumption that all (syntactic) definitions of
recursive functions should be feasible?
Note, that this model would consists only of
"constructive finite objects". Thus, very informally,
Should non-constructive(!) finite objects exist?
(There is a quite formal version of this question;
cf. my paper in MFCS'1980, LNCS 88, and corrections in
MFCS'1981, LNCS 118.)
This is also related in some way with Kolmogorov's
complexity of finite objects.
>
> This is not a put-on, I'm asking a serious question to which I do not know
> the answer.
>
> HEEELP!!!
Sorry, I am not sure if this really helps.
Vladimir Sazonov
--
Vladimir Sazonov V.Sazonov at csc.liv.ac.uk
Department of Computer Science tel: (+44) 0151 794-6792
University of Liverpool fax: (+44) 0151 794 3715
Liverpool L69 7ZF, U.K. http://www.csc.liv.ac.uk/~sazonov
>
> stevnewb
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
More information about the FOM
mailing list