[FOM] Concerning Ancestral Logic

[Richard Heck]

The question was mainly for Arnon, but let me add a bit.

Shapiro does discuss AL in his book, around p. 227. The characterization
he gives there is purely semantical. Here's one way to do it. Introduce
a new symbol *. Given a formula \phi, *xy(\phi(x,y))(a,b) is a formula,
where x and y are variables and a and b are terms. It is true iff there
is a finite sequence x_1, ..., x_n such that \phi(x_i,x_{i+1}). (Of
course, satisfaction is what we really need.) Note that this is Frege's
`strong' ancestral: We do not, in general, have *xy(\phi(x,y))(a,a).

Since the ancestral is definable by a \Pi^1_1 formula, AL is a
sub-system of \Pi^1_1 second-order logic. I believe it's a proper
sub-system but I'm not sure I'm remembering that corrrectly. In any
event, it follows that AL is both incomplete and non-compact, since
arithmetic therefore has a categorical formulation in AL. Define the
`weak' ancestral thus:
*=xy(\phi(x,y))(a,b) iff *xy(\phi(x,y))(a,b) \vel a = b
Then induction takes the form:
\forall n[*=xy(y=Sx)(0,n)]
Just as Dedekind and Frege taught.

That AL is incomplete does not, of course, imply that there are not nice
partial axiomatizations of it, just as there are nice partial
axiomatizations of second-order logic. I discuss the question how to
axiomatize it in my paper "The Logic of Frege's Theorem", available from
my web site.

Richard Heck

Bill Taylor wrote:
> This query is mainly directed to Arnon Avron, but no doubt others
> may feel like joining in.
>
> Arnon - you have been extolling the virtues of AL as an alternative,
> (an extension?), of FOL.  It sounds good, but I don't yet know what it is.
> You mention it was given a treatment in Shapiro's F-without-F, but I don't
> recall noticing it from when I read that.
>
> So I wonder if you could give us all a brief rundown on it.
> Nothing too massively technical, but just enough to get the flavour
> and main ideas.  I was thinking of, say, 2 or 3 standard paragraphs.
>
> Could you do that please?   Thanks muchly,
>
> Bill Taylor
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>   


-- 
==================================================================
Richard G Heck, Jr
Professor of Philosophy
Brown University
http://bobjweil.com/heck/
==================================================================
Get my public key from http://sks.keyserver.penguin.de
Hash: 0x1DE91F1E66FFBDEC
Learn how to sign your email using Thunderbird and GnuPG at:
http://dudu.dyn.2-h.org/nist/gpg-enigmail-howto