?FOL Transitive Closures

dennis.hamilton at acm.org dennis.hamilton at acm.org
Tue Mar 14 20:23:32 EDT 2023

My apologies.  The list doesn't pass UTF-8 symbols. Corrected in place,

-----Original Message-----
From: dennis.hamilton at acm.org
Sent: Tuesday, March 14, 2023 14:45
Subject: RE: FOL Transitive Closures

I'm missing something.  Given N as the domain of discourse, and having 0 and
successor and the minimum axioms for Peano Arithmetic, I don't understand

	a < S(a)
	a < b & b < c -> a < c
doesn't establish a transitive closure using FOL (ok, with induction
schema), and to even emphasize the potential infinity (although I think
that's already established via S(x)),
	(a)(exists b[orcmid] ) [ a < b ].

So is the claim more about set-theoretic relations in FOL and an inability
to achieve something similar given a (suitable?) relation, R ?

From: Vaughan Pratt
Sent: Saturday, March 11, 2023 23:15
Subject: Re: ?Finitism / potential infinity requires the paraconsistent

 [ . ]

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.

 [ . ]

Vaughan Pratt

More information about the FOM mailing list