Re: ​Re: Mathematics with the potential infinite

Vaughan Pratt pratt at cs.stanford.edu
Sun Jan 29 14:21:04 EST 2023


And to make things more concrete, consider the dyadic irrational 1/3.
Writing in binary, let L be the type of dyadic rationals of the form 0.,
0.0, 0.01, 0.010, 0.0101, 0.01010, ... and let U be the type of  those of
the form 0.J, 0.0J, 0.01J, 0.010J, 0.0101J, 0.01010J, ... where J denotes
an infinite string of 1's (so 0.J is the dyadic rational 1, 0.0J is 1/2,
etc.).   Evidently there can be no greatest dyadic rational of type L, and
no least of type U.  Moreover there cannot be two reals both of which are
above every dyadic rational of type L and below every one of type U,
because if there were we would only need finitely many dyadic rationals to
witness the failure of at least one of them to meet that condition.  The
conditions of the axiom regarding existence of a dyadic irrational having
been met, we infer the existence of 0.010101010... = 1/3.

More generally. for any given real written in binary, define the type L for
that real to consist of its prefixes, and the type U to consist of the same
prefixes with J appended (equivalently with 1 added to the last bit of the
corresponding prefix in L).

Surely "potentially infinite" can be defined in a way that makes all the
infinities in the above only potentially infinite.

One might complain that writing a real in binary is an actual infinity.  To
get around this, allow L and U to each be arbitrary finite sequences of
bits, with U differing from L by adding 1 to the last bit of each element
of U and doing the usual carry propagation in the finitely many bits of
that element.

Vaughan

On Sat, Jan 28, 2023 at 9:05 PM 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 here).
>
> 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/20230129/c92b9c90/attachment-0001.html>


More information about the FOM mailing list