Re[2]: ​Re: Mathematics with the potential infinite

[Matthias]

I have questions/comments concerning the discussion between Haim Gaifman 
and Vaughan Pratt.

To me, there are two approaches. I want to know whether you have a 
different understanding on that.

(i) There is Hilbert's program, where one accepts (some or all) infinite 
totalities and tries to secure their use by "finitary reasoning", using 
metamathematical arguments.

(ii) There is the approach to use the potential infinite, i.e. one 
accepts only finite sets, but allow them to increase without any bound. 
The restrictions in what is meaningful is the result of its concrete 
formalization.

It is often said that Tait made finitism concrete by restricting 
arithmetic to PRA. His paper is related to Hilbert's program, although 
he tries to avoid infinite totalites of numbers. But there is also some 
critique by Schirn and Niebergall on Tait's task.

The second approach was developed e.g. by Marcin Mostowski and Jan 
Mycielski. Since Mostowski uses fixed domains of quantification and 
Mycielski variable ones, there are restrictions in Mostowski's approach, 
but not in Mycielski's (at least not for first-order logic). These are 
basically semantical ways, but there are other approaches to translate 
the formulas, e.g. in a modal logic (see Øystein Linnebo and Stewart 
Shapiro).

Another point: I think that it is possible to show that R or P(N) are 
uncountable (non-enumerable), using the potential infinite. Cantor's 
diagonal argument does not require completed infinites. Assume e : N -> 
P(N) is surjective, then consider d := { n \in N | n \not\in e(n) }. At 
each stage of the set d, one needs the enumeration e up to the same 
stage, not the complete function.

Regards,
Matthias


------ Originalnachricht ------
Von "Vaughan Pratt" <pratt at cs.stanford.edu>
An "Haim Gaifman" <hg17 at columbia.edu>
Cc fom at cs.nyu.edu
Datum 30.01.2023 07:06:44
Betreff Re: ​Re: Mathematics with the potential infinite

>Meanwhile I realized I was too focused on the uniqueness part in the 
>antecedent of my axiom.  If phrased as "given any two distinct reals, 
>one of them must be either below some element of L or above some 
>element of U" then I don't see any quantification over an infinite set. 
>  It is the existence part in the consequent that has to quantify over 
>all elements of type L and all elements of type U.  So if the 
>definition of "potentially infinite" disallows quantifying over all the 
>elements of a nonempty linear order having no upper bound (because one 
>can prove that it must be infinite) then I now understand how my 
>definition of a dyadic irrational violates the requirement of being 
>only potentially infinite.
>
>Although that uniqueness part appears in the antecedent of my axiom, a 
>negative appearance, and I don't know the rules governing "only 
>potentially infinite" in antecedents.
>
>Vaughan
>
>On Sun, Jan 29, 2023 at 9:27 PM Vaughan Pratt <pratt at cs.stanford.edu> 
>wrote:
>>"But, in general, to say that between an ascending sequence
>>and a descending sequence there is a gap which can be filled exactly 
>>by one sequence, you must at least quantify  over all natural 
>>numbers."
>>
>>How so?  I have a type L with no greatest element and a type U with no 
>>least element, such that there can be at most one element that is both 
>>greater than any element of type L and less than any element of type 
>>U.  Where am I quantifying over all natural numbers?
>>
>>If your objection is that it can be proved that there must be 
>>infinitely many elements of type L, then that objection can also be 
>>raised about elements of type integer.  I'm not seeing the difference.
>>
>>Vaughan
>>
>>
>>On Sun, Jan 29, 2023 at 8:42 PM Haim Gaifman <hg17 at columbia.edu> 
>>wrote:
>>>You can certainly say if you assume potential infinity that there is 
>>>no  greatest integer (because n+1 > n).
>>>
>>>Certain infinite sequences of natural numbers can be justified on the 
>>>basis of potential infinity.  Roughly speaking, as long as you can 
>>>define them without using quantification over  all natural numbers, 
>>>but only over “sufficiently large but finite initial segments of the 
>>>natural numbers”, you are OK. For example, the iterations of the 
>>>exponential function: 1, 2, 4, 16, 2^(16), 2^((2^16)),… is 
>>>legitiemate on the basis of potential infinity.
>>>
>>>Thus, you can handle  dyadic rationals.
>>>
>>>But, in general, to say that between an ascending sequence
>>>and a descending sequence there is a gap which can be filled exactly 
>>>by one sequence, you must at least quantify  over all natural 
>>>numbers. This is what one does in analysis when one defines the least 
>>>upper bound and the greatest lower bound, and other standard notions. 
>>>In "For every delta there is an epsilon” you can choose delta and 
>>>epsilon to be of the form 1/m and 1/n, and in general this would 
>>>involve quantification over all natural numbers.
>>>
>>>Best, Haim Gaifman
>>>
>>>>On Jan 29, 2023, at 12:05 AM, Vaughan Pratt <pratt at cs.stanford.edu> 
>>>>wrote:
>>>>
>>>>Thanks, Haim, good to hear from you, and good to know you're 
>>>>watching FOM.
>>>>
>>>>You seem to be answering my second question, "Can R be shown to be 
>>>>uncountable using only potential infinities" in the negative.  That 
>>>>was my intuition, as I can't imagine how Cantor's proof that R is 
>>>>uncountable could be carried out using only potential infinities, 
>>>>which was why I asked it.
>>>>
>>>>But what about my first question?  If one can talk about integers as 
>>>>involving only potential infinities, surely one can do that with 
>>>>dyadic rationals (or general rationals for that matter, although the 
>>>>dyadic kind suffice her.0e).
>>>>
>>>>Can one say that there is no greatest integer without going beyond 
>>>>potential infinities?  If so, why can't one speak of an ascending 
>>>>chain of dyadic rationales below a descending chain of dyadic 
>>>>rationals such that neither has a greatest (resp. least) element?  
>>>>And the extra condition of at most one element between those two 
>>>>chains is surely finitary.
>>>>
>>>>If the concept of "only potential infinities" is sufficiently well 
>>>>defined, it should be possible to see (i) precisely which condition 
>>>>has been violated in the above definition of a real, and (ii) 
>>>>whether some slight adjustment to that condition would overcome the 
>>>>violation.
>>>>
>>>>Defining a real to be either a dyadic rational or the unique dyadic 
>>>>irrational filling a gap in my sense has elements in common with 
>>>>both Cantor's Cauchy sequences and Dedekind's cuts, but 
>>>>(potentially) without involving the actual infinities of either.
>>>>
>>>>Moreover the language is that of Presburger arithmetic 
>>>>(multiplication does not enter into the above definition of a real) 
>>>>and therefore the sorts of undecidable questions that prompted 
>>>>Brouwer to introduce his notion of apartness should not plague this 
>>>>naive definition of a real number.
>>>>
>>>>Vaughan Pratt
>>>>
>>>>On Sat, Jan 28, 2023 at 7:03 PM Haim Gaifman <hg17 at columbia.edu> 
>>>>wrote:
>>>>>Dear Vaughan,
>>>>>Long time no hear no see, and it is very nice to hear from you.
>>>>>The restriction of subscribing only to potential infinities (which 
>>>>>can be traced back to Aristoteles) is Hilbert’s so called finitist 
>>>>>position; Abraham Robinson agrees with him. Only structures based 
>>>>>on proper initial segments of the natural numbers: {0, 1, 2,…, m} 
>>>>>are accepted as legitimate, but for every m, if n > m, one accepts 
>>>>>also the extension based on {0, 1, …., m, m+1,…., n}. The functions 
>>>>>and/or relations that come with these structures are the usual 
>>>>>functions and/or relations of PA (Peano Arithmetic). Of course, the 
>>>>>functions are partial functions  , given the restrictions on the 
>>>>>domain.
>>>>>
>>>>>PA, which is based on the standard model N of natural numbers, is 
>>>>>much much… stronger than the theories
>>>>>that arise within the framework of potential infinity.
>>>>>One such interesting theory has been proposed by Skolem
>>>>>and is known as PRA for Primitive Recursive Arithmetic.
>>>>>
>>>>>Now your question, if I understand you correctly, asks for a way of 
>>>>>describing an uncountable structure using only potential 
>>>>>infinities.This would be impossible, unless you allow countable 
>>>>>non-standard model for the theory linearly ordered groups.
>>>>>
>>>>>Best, Haim Gaifman
>>>>>
>>>>>>On Jan 28, 2023, at 3:13 AM, Vaughan Pratt <pratt at cs.stanford.edu> 
>>>>>>wrote:
>>>>>>
>>>>>>My apologies for not having previously followed threads on this 
>>>>>>topic.  However after seeing Stephen Simpson's message just now 
>>>>>>(Friday) it occurred to me to ask whether an uncountable set could 
>>>>>>be described using only potential infinities, for example the real 
>>>>>>numbers (R, *, 0, <=) as a linearly ordered group under addition, 
>>>>>>compatibly ordered in the sense that each of the group 
>>>>>>multiplication's two arguments is monotone: if x <= y then x*z <= 
>>>>>>y*z, and likewise for the right argument.  (* = +.)
>>>>>>
>>>>>>Define a *geodesic* to be a nondegenerate linearly ordered group 
>>>>>>(G, *, 0, <=).  (Although G is not assumed abelian, the linear 
>>>>>>order makes it abelian.)  Examples include the integers, the 
>>>>>>dyadic rationals, every field between the rationals and the reals, 
>>>>>>and many non-Archimedean extensions thereof.
>>>>>>
>>>>>>Call a geodesic G *gapless* when (i) it is dense, and (ii) for 
>>>>>>every nonempty suborder (U, <=) of (G, <=) having no least 
>>>>>>element, and every nonempty suborder (L, <=) of (G, <=) with L < U 
>>>>>>and having no greatest element, such that there is at most one 
>>>>>>element of G between L and U; then there exists an element of G 
>>>>>>between L and U.
>>>>>>
>>>>>>I claim that every gapless geodesic is isomorphic to R with the 
>>>>>>above structure.
>>>>>>
>>>>>>(Proof outline: Take any element x of G with 0 < x and pair 0 and 
>>>>>>x with 0 and 1 in R.  Pair the integers in R with the subgroup of 
>>>>>>G generated by x, cyclic and therefore abelian.  Repeatedly divide 
>>>>>>the intervals in (n, n+1) in G into two equal parts and pair the 
>>>>>>results with the dyadic rationals in (0,1), a dense set.  Pair 
>>>>>>each dyadic irrational q in R with the unique x given by the 
>>>>>>gaplessness condition for any L and U in G whose counterpart in R 
>>>>>>converges to q from each side.  Lastly, G must be Archimedean or 
>>>>>>there would be an empty gap between the finite and infinite 
>>>>>>elements of G.)
>>>>>>
>>>>>>1.  Do these definitions, claims, and constructions meet the 
>>>>>>criteria for only potential infinities?
>>>>>>
>>>>>>2.  Can R be shown to be uncountable using only potential 
>>>>>>infinities?
>>>>>>
>>>>>>(Those familiar with Otto Hoelder's 1901 paper showing that every 
>>>>>>Archimedean linearly ordered group is isomorphic to some subgroup 
>>>>>>of R under addition, which may be anywhere between Z and R, may 
>>>>>>see some similarity of ideas in the above.)
>>>>>>
>>>>>>Vaughan Pratt
>>>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20230131/3060502b/attachment-0001.html>