[FOM] 303: PA Completeness (restatement)

Andrej Bauer Andrej.Bauer at fmf.uni-lj.si
Sat Nov 4 16:58:34 EST 2006

Pietro Kreitlon Carolino wrote:
>    I would like to know the proportion of ExEy sentences that came up
> true in professor Bauer's Mathematica run.

I did not actually count how many were true and how many false. For 
example, we can throw out anything that has just one variable or is 
within Presburger arithmetic without deciding whether it's true or false.

So, I made another computation which does what you asked for. You can 
see the results in the Mathematica notebook (also available in PDF), 
which I published at


in order not do send attachments to FOM. I should point out that there 
are many different ways of counting here. For example, is "x + S 0" the 
same thing as "S x"? Should we put equations in canonical form before we 
start counting them? I indicate some possibilities in the Mathematica 

I hope other FOM readers find this interesting, too.

Andrej Bauer

More information about the FOM mailing list