[FOM] 303: PA Completeness (restatement)

[Andrej Bauer]

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

http://math.andrej.com/2006/11/04/are-small-sentences-of-peano-arithmetic-decidable/

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 
notebook.

I hope other FOM readers find this interesting, too.

Andrej Bauer