QUESTIONS: ----------
Are there relatively simple propositions in number theory that are known to be undecidable?
Note that a single proposition cannot be `undecidable' in the usual sense; it makes sense only to speak of the undecidability of a class of propositions. So, the Halting Problem is undecidable, but whether any particular Turing machine halts is decidable (the answer is either `yes' or `no'). There are, however, propositions which are *unprovable* in your favourite deductive system. So, in Peano arithmetic, the following statement is unprovable: "For every positive integer M and integer k >= 2, there exists N such that if the edges of the complete graph K_N (with vertices labelled {1, 2, ..., N}) are k-coloured, there exists m >= M such that there is a monochromatic K_m, one of whose vertices has a label smaller than m." (This can be converted into a first-order statement in arithmetic.) Now, I can prove that this statement is true, but only by reasoning about infinite objects (which is not allowed within Peano arithmetic) and applying to compactness. Moreover, there is no proof in Peano arithmetic that this is true, so by the Completeness Theorem there exist nonstandard models of Peano arithmetic in which [the encoding of] this statement is false! A similar situation exists for stronger deductive systems. For example, finite forms of the Robertson-Seymour theorem are beyond the second-order theory Pi11-CA0+BI, and Harvey Friedman exhibits certain combinatorial games whose proof requires the existence of Mahlo cardinals! And the only known proof of the unboundedness of the period of Laver tables (again, a very finite problem expressible as a statement in arithmetic) assumes the existence of a rank-into-rank cardinal (which is basically one of the boldest things one can assume). Of course, it's entirely plausible that there are proofs within ZFC alone.
It seems to me that if we used a number system with infinitesimals (like the Surreals) to record probabilities,
I don't think that there is any reasonable way to do so. Measure theory relies on the fact that we can take the sum of a countable series, which is in turn equivalent to being able to take the supremum of a countable set. But the Surreals lack the supremum property, so we can't build a measure theory using the surreals as an alternative to R.
Are there some propositions whose probability of being true at least heuristically can be calculated as a number strictly between 0 and 1 ???
Does this answer your question? http://en.wikipedia.org/wiki/Kolmogorov%27s_zero%E2%80%93one_law The question of the existence of infinitely many ménage primes is quite interesting, since the relevant series diverges, but particularly slowly. In particular, the nth ménage prime is expected to asymptotically exceed exp(exp(exp(n))), which may be why we've only found five so far. Sincerely, Adam P. Goucher