[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
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
More information about the FOM
mailing list