[FOM] None [Arithmetic with the biggest number]]

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