[math-fun] Election manipulation and/or fraud in USA 2014 revealed by statistical tests
Mike Stay: If you could get a celebrity statistician like Nate Silver to confirm it, then sure.
-- http://rangevoting.org/USA2014.html now contains a note at the end indicating Nate Silver agrees with it. Unless he doesn't. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Well, he agrees that the polls didn't match the voting, but that's hardly news: his article is about how that happens all the time. On Sun, Nov 9, 2014 at 9:54 AM, Warren D Smith <warren.wds@gmail.com> wrote:
Mike Stay: If you could get a celebrity statistician like Nate Silver to confirm it, then sure.
-- http://rangevoting.org/USA2014.html now contains a note at the end indicating Nate Silver agrees with it. Unless he doesn't.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Goedel's original undecidable statement, as described in the article by Nagel & Newman about it in the 4-volume set The World of Mathematics, or in the more detailed book by Goedel's Proof by the same authors, is a statement that can be interpreted as saying "There is no proof of me." So as you may have seen, if it's false then there *is* a proof of it, so it's true. So, if number theory is consistent, then it can't be false since that leads to a contradiction. So it must be true (in a cosmic sense). Therefore there really is no proof of it. QUESTIONS: ---------- Are there relatively simple propositions in number theory that are known to be undecidable? What about undecidable in the sense that we have no way of knowing whether the proposition is true or false. (Potentially, like the Twin Prime Conjecture.) Is it plausible that every such undecidable proposition is that way because (maybe like the TWP) it is true -- or false -- only because of probabilistic accident? It seems to me that if we used a number system with infinitesimals (like the Surreals) to record probabilities, then most or all of the propositions like TWP that [appear to have probability 1 of being true] would have probability 1-eps of being true, where eps is the reciprocal of an uncountable number. If this is always the case, then the probability that ALL such propositions are true without exception is also 1. (For, the countable product of numbers of form 1-eps where eps is the reciprocal of an uncountable number would still be of the same form.) Are there some propositions whose probability of being true at least heuristically can be calculated as a number strictly between 0 and 1 ??? --Dan
At 03:02 PM 11/9/2014, Dan Asimov wrote:
Goedel's original undecidable statement, as described in the article by Nagel & Newman about it in the 4-volume set The World of Mathematics, or in the more detailed book by Goedel's Proof by the same authors, is a statement that can be interpreted as saying "There is no proof of me."
So as you may have seen, if it's false then there *is* a proof of it, so it's true. So, if number theory is consistent, then it can't be false since that leads to a contradiction. So it must be true (in a cosmic sense). Therefore there really is no proof of it.
QUESTIONS: ----------
Are there relatively simple propositions in number theory that are known to be undecidable?
Hilbert's Tenth Problem is about as simple as you can get.
What about undecidable in the sense that we have no way of knowing whether the proposition is true or false. (Potentially, like the Twin Prime Conjecture.)
Undecidable in this sense usually means that the new statement can be added as a new axiom without rendering the system inconsistent. Alternatively, the negative of the new statement can be added as a new axiom without rendering the system inconsistent. So you get two new non-trivial theories: one in which the previously undecidable statement is true, and one in which the previously undecidable statement is false.
Is it plausible that every such undecidable proposition is that way because (maybe like the TWP) it is true -- or false -- only because of probabilistic accident?
???
It seems to me that if we used a number system with infinitesimals (like the Surreals) to record probabilities, then most or all of the propositions like TWP that [appear to have probability 1 of being true] would have probability 1-eps of being true, where eps is the reciprocal of an uncountable number.
If this is always the case, then the probability that ALL such propositions are true without exception is also 1. (For, the countable product of numbers of form 1-eps where eps is the reciprocal of an uncountable number would still be of the same form.)
Are there some propositions whose probability of being true at least heuristically can be calculated as a number strictly between 0 and 1 ???
There has been a huge amount of work on "probabilistic logics", both classical & quantum. There are also so-called "modal logics" which define quantifiers "necessary" and "possible", and there is some intersection with probabilistic logics & quantum logics. There may be some versions of these logics that deal with uncountable universes, but I'd have to do some searching to find out. Countably infinite universes -- e.g., the integers -- have also been studied to some extent via theories such as "S1S", "S2", "real closed fields", "Presburger Arithmetic", etc.
On Sun, Nov 9, 2014 at 6:30 PM, Henry Baker <hbaker1@pipeline.com> wrote:
At 03:02 PM 11/9/2014, Dan Asimov wrote:
Goedel's original undecidable statement, as described in the article by Nagel & Newman about it in the 4-volume set The World of Mathematics, or in the more detailed book by Goedel's Proof by the same authors, is a statement that can be interpreted as saying "There is no proof of me."
So as you may have seen, if it's false then there *is* a proof of it, so it's true. So, if number theory is consistent, then it can't be false since that leads to a contradiction. So it must be true (in a cosmic sense). Therefore there really is no proof of it.
QUESTIONS: ----------
Are there relatively simple propositions in number theory that are known to be undecidable?
Hilbert's Tenth Problem is about as simple as you can get.
What undecidable *proposition* is associated with Hilbert's 10th problem? There is no *algorithm* for deciding whether a given Diophantine equation has a solution, but the proposition "for any Turing machine M, M does not compute, given a (suitably encoded) Diophantine equation as input, whether that equation has a solution" is not undecideable; it's true and provable. A strengthened version of the finite Ramsey theorem is the simplest "natural" statement proven to be undecideable in formal number theory. The result that this is undecideable is called the Paris Harrington theorem. See http://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem for details. Andy
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
On Sun, Nov 9, 2014 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Goedel's original undecidable statement, as described in the article by Nagel & Newman about it in the 4-volume set The World of Mathematics, or in the more detailed book by Goedel's Proof by the same authors, is a statement that can be interpreted as saying "There is no proof of me."
So as you may have seen, if it's false then there *is* a proof of it, so it's true. So, if number theory is consistent, then it can't be false since that leads to a contradiction. So it must be true (in a cosmic sense).
I'm not sure what "true in a cosmic sense" means. The Goedel sentence for formal number theory is provable in ZF, so it's true if you believe in set theory. Also, the theory where you assume it's true is omega-consistent, while the theory where you assume it's false is omega-inconsistent, so that's a reason to prefer it (although I think proving this, or even stating it, requires set theory, rather than formal number theory). A theory is Omega-inconsistent if there is a formula P(X) such that all of P(0), P(1), P(2), P(3).... are provable, but so is "There exists an X such that not P(X)"
Is it plausible that every such undecidable proposition is that way because (maybe like the TWP) it is true -- or false -- only because of probabilistic accident?
Only if you can define "probabilistic accident" precisely. I don't think it's plausible that this can be done.
It seems to me that if we used a number system with infinitesimals (like the Surreals) to record probabilities, then most or all of the propositions like TWP that [appear to have probability 1 of being true] would have probability 1-eps of being true, where eps is the reciprocal of an uncountable number.
Two years ago, wouldn't you have put the proposition "there are infinitely many pairs of primes that differ by 1000 or less" to be in the same category of "statements with probability 1-eps of being true" as TWP? But it's not in any such mysterious category; it's just true. I see no reason not to think that TWP has the same status, and it will get proved in a year or a century.
If this is always the case, then the probability that ALL such propositions are true without exception is also 1. (For, the countable product of numbers of form 1-eps where eps is the reciprocal of an uncountable number would still be of the same form.)
Are there some propositions whose probability of being true at least heuristically can be calculated as a number strictly between 0 and 1 ???
The leap from "systems with infinitesimals exist" to "intuitive conclusions reached from intuitions about infinitesimals" is a large one. It's easy to reach contradictions by reasoning loosely about infinitesimals, so unless you define your terms very precisely, I find it hard to make any sense of statements like this. There's a heuristic principle that the primes behave like a randomly selected set of numbers, where the probability that n is selected is 1/ln(n), except when they don't. Formulating a precise version of this statement, proving such a statement, developing a theory of probability where probabilities are surreal numbers, and proving that the TWP has a meaningful probability in such a system, all seem to me much more difficult problems than TWP. Andy -- Andy.Latto@pobox.com
participants (6)
-
Adam P. Goucher -
Andy Latto -
Dan Asimov -
Henry Baker -
Mike Stay -
Warren D Smith