[FOM] Some observations on infinity

[Andrew Boucher]

  This is a follow-up to the postings of Alexander Zenkin and Dean 
Buckner on infinity.

I am partisan for distinguishing *three* different concepts of infinity, 
which despite the riskiness of using terms with a history, I would call 
potential infinity, actual infinity, and ad infinitum.  To delineate 
these concepts, consider second-order logic with arithmetical 
comprehension and with a (third-order) number relationship Mn,P, which 
says "P has the number n" (like the "#P = n" of Frege Arithmetic, only 
totality is not assumed), and a number predicate Nn, which says "n is a 
finite number".  

Let
! = not,
[..] = there exists ..

Use "potential" infinity (POTINF) to label
    (n) (Nn => [P][a] ( !Pa & Mn,P )),
that is for every finite number n, there exist things numbering n and 
one more thing.  

Use "actual" infinity (ACTINF) to label
    [P](n) ! ( Nn & Mn,P ),
that is there are things which are not numbered by any natural number.

And use "ad infinitum" (ADINF) to label
    (n)(P)(a)(Nn & Mn,P & !Pa => [m](Nm & Mm,{x : Px V x = a}))
that is whenever there are a finite number of things and one other 
thing, there exists a finite number numbering all these things.

Of the eight possibilities, only two (I hope I have this right) cannot hold:
1)  POTINF & ACTINF & ADINF.
Univ = {0,1}.  ! N0 & N1.  M0,P <=> ! [x] Px.  M1,P <=> [x] Px.  (Note 
that the empty set is actually infinite.)
2)  POTINF & ACTINF & ! ADINF.
Univ = {0}.  N0.  M0,P <=> ! [x] Px.  (Note that {0} is actually infinite.)
3)  POTINF & ! ACTINF & ADINF.
Univ = {0}.  N0.  M0,P for all P.  
4)  POTINF & ! ACTINF & ! ADINF.
Not possible, since ! ADINF => ACTINF.  Pf:  Because ! ADINF, for some 
n,P,a we have that Nn & Mn,P & !Pa but ![m](Nm & Mm,{x : Px V x = a}). 
 But then {x : Px V x = a} is actually infinite, i.e. ACTINF.
5)  ! POTINF & ACTINF & ADINF.
Univ = {0,2}.  !N0 & N2.  M0,P <=> ! [x] Px. M2,P <=> [a][b](Pa & Pb & 
(c)(Pc => c = a & c = b)).  (Note that {0} is actually infinite.)
6)  ! POTINF & ACTINF & ! ADINF.
Univ = {0,2}.  N0 & N2.  M0,P <=> ! [x] Px. M2,P <=> [a][b](Pa & Pb & 
(c)(Pc => c = a & c = b)).  (Note that {0} is actually infinite.)
7)  ! POTINF & ! ACTINF & ADINF.
Univ = {0,1}.  N0 & N1.  M0,P for all P.  M1,P for no P.  
8)  ! POTINF & ! ACTINF & ! ADINF.
Not possible, since ! ADINF => ACTINF.


Because of the model presented for 1), there exists a finite model in 
which all three are true.  Of course, this is less interesting than it 
seems (if it seems interesting at all!), because no assumptions have 
been made about N or M which make them correspond to their intended 
meaning.  What would, I hope, be interesting is if one could present 
axioms which determine N and M to have their "true" meaning, but still 
allow one or more of these three infinities to hold in a finite model.

This is not the case for ADINF.  To see this, use "P ~ Q" to abbreviate:
    "[R] ( R is a one-to-one function from P onto Q)

Then there is no finite model in which all these three are true:
1) N0 & (P)(M0,P <=> (x) ! Px)
2) Finite Hume's Principle (without assetions of uniqueness or 
existence), i.e.
    (P)(Q)(n)(Nn & Mn,P => (Mn,Q <=> P ~ Q))
3) ADINF.
Pf:  By 1), N0  & M0,{} & !{}0, where we use {} for the empty predicate. 
 By ADINF there exists 1 s.t. N1 & M1,{0}.  If 1 = 0, then {} ~ {0} by 
FHP, a contradiction.  So !{0}1.  By ADINF, there exists 2 s.t. N2 & 
M2,{0,1}.  Again  by FHP, if 2 = 0, then {} ~ {0,1}.  And if 2 = 1, then 
by FHP {0,1} ~ {0}.  Both are contradictions, so !{0,1}2.  And so on.

However, there is a system, which seems to set N and M their "usual" 
meaning (minus of course that N continues ad infinitum), which can prove 
POTINF and ACTINF, and which *does* have a finite model. Use
    Sn,m to mean "m follows n (in the natural number sequence)",
a relationship which is not assumed to be total on N.

Consider the following axioms:
(F1) Uniquesness of numbering
(n)(m)(P)(Mn,P & Mm,P => n = m)
(F2) Zero
(P)(M0,P <=> (x) ! Px)
(F3) Successoring
(P)(Q)(a)(n)(m)(Nn & Sn,m & !Pa & (x)(Qx <=> Px V x = a) => (Mm,Q <=> Mn,P))
(F4)  Full Induction.  From phi(0) and (n)(m)(Nn & Sn,m & phi(n) => 
phi(m)), infer (n)(Nn => phi(n)).
(F5)  N0
(F6) ADINF

Set F = {F1,F2,F3,F4}.  Then F and indeed F + {F5} is evidently 
satisfied by a finite model, indeed one with a singleton domain, {0}. 
 It turns out that F (with only arithmetic comprehension) can prove both 
POTINF and ACTINF.  The proof of POTINF follows the Fregean technique: 
 n numbers {0,...,n-1}, to which n does not belong.  ACTINF follows as a 
straightfoward consequence.  F captures a fair amount of our intuitive 
notion of N and M, because e.g. it can prove FHP (as stated above), the 
Pigeon Hole Principle, etc.

Let me linger on this for a moment, to emphasize the Skolemish nature. 
 A model of F can be finite - indeed it can be any initial segment of 
the naturals, including the singleton {0} -, but it can prove assertions 
which seem fairly to transcribe the notion of potential and actual 
infinity.  The set of all finite numbers is infinite even if it looks 
finite from the outside, because even if it is finite - say {0,...,n} - 
on the outside, there would not exist a finite number big enough (n + 1) 
on the inside to number all of them.  

Although I cannot speak definitively in anyone else's name, it would 
seem that ultrafinitists are on safe ground only denying ADINF, less 
safe ground denying either POTINF or ACTINF.

PS.  Remark that F + {F5,F6} suffice to prove the Peano Axioms.  By 
itself, F is an extremely strong system - I would conjecture it could 
prove Fermat's Last Theorem.

           
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/fom/attachments/20030103/e3e36ec4/attachment.html