Re: ​Finitism / potential infinity requires the paraconsistent logic NAFL

[Vaughan Pratt]

On Fri, 10 Mar 2023 01:03:26 +0000 (UTC), Radhakrishnan Srinivasan wrote,
"Within first-order logic (FOL), you certainly have the freedom to deny the
existence of infinite sets (in the classical sense) and replace them with
your potentially infinite sets."

I would be very interested to see how this is done within FOL.  I would
expect it to set Arnon Avron's mind at ease concerning the concept of a
potentially infinite set.

The limitation I see to FOL is that it can't express transitive closure of
a binary relation.  If it could, the following reasoning would permit
defining the notion of a potentially infinite set entirely within FOL.

Extensions of FOL can define transitive closure.  To the best of my
knowledge, the earliest such extension is first order dynamic logic, which
I developed in 1974 for a course at MIT and later published in FOCS'76 as
"Semantical Considerations on Floyd-Hoare Logic".  My first Ph.D. student
David Harel, currently the President of the Israel Academy of Sciences and
Humanities, published his thesis as a book titled First Order Dynamic Logic.

If we regard Tarski's cylindric algebras as the algebraic formulation of
FOL within the framework of RA, Relation Algebra, then the extension, by
Tarski and his student Judith Ng, of RA to RAT, namely RA plus transitive
closure, may be the second such extension.  This extension first appeared
as a couple of paragraphs in Math Abstracts in 1977, only a year after my
FOCS'76 paper, and seven years later as Ng's thesis in 1984 after Ralph
McKenzie took over her supervision from Tarski.

In 1980 Chandra and Harel added a fixpoint operator to FOL to a similar
effect, namely the ability to define transitive closure.  My JELIA'90 paper
on Action Logic conservatively extended the equational theory of regular
expressions, nowadays called Kleene algebras, with two implication
operations for past and future, a finitely axiomatizable theory that ruled
out John Horton Conway's "monster" models of that theory in the absence of
those two implications in his 1971 monograph Regular Algebra and Finite
Machines.

Thinking of FOL as a static logic, any extension of FOL to one that
accommodates ongoing behavior allows the set N of natural numbers to be
exhibited as taking infinite time to develop.  It is then possible to speak
of the velocity of growth of N, e.g. one number per second, a googol of
numbers per femtosecond, etc., as a finite quantity.  In the limit the
infinite set N is produced, taking infinite time.

With nothing but a compass, the transcendental quantity 2/pi can be
constructed in the limit of a process that keeps dividing an isosceles
triangle into two, starting from a right isosceles triangle with two of its
sides of unit length.

In short, putting time in the denominator allows the notion of a
potentially infinite set to be defined as one developable with finite
"velocity" in the infinite limit.  Without transitive closure, FOL cannot
express this notion.

Vaughan Pratt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20230311/7c29429b/attachment-0001.html>