2
$\begingroup$
  • Concerning the undecidability of an assertion ( a theorem ) in mathematics, can somebody give an example and thus prove that a theorem is undecidable ? I will then higly appreciate showing the procedure of using the axiom of choice to prove that only by using the axiom of choice the theorem in question could be proven. Can somebody also give the example of an undecidable theorem which is proven to be so but for which there is still no axiom of choice which could prove the theorem ?
  • I was reading recently in a book that every undecidable question creates a bifurcation and imposes a choice. It then gives the example of P. Cohens theorem on the continuum hypotheses which, according to the book, leads to a bifurcation: we have to choose either there are no cardinals between the countable and the continuum or that there are 36 of them. The first choise is then made because of simplicity (according to the book). What i dont understand here is: how one proceeds from the simple definition of the choice function and axiom of choice in the set-theoretical context to the assertion of such choices as mentioned above for which you would hardly see the intervention of the axiom of choice as we define it usually ?

Many thanks for your comments.

$\endgroup$
  • 1
    $\begingroup$ What's with the downvotes here? The question does seem to be based in confusion, but it's the kind of confusion that one ought to be able to write an answer to help dispelling, and the OP has made a reasonable effort to make his confusion clear enough to be answerable. $\endgroup$ – Henning Makholm Sep 26 '16 at 9:55
  • 2
    $\begingroup$ The Axiom of Choice is itself an example of a theorem (of ZFC set theory) that is undecidable without the Axiom of Choice and can be proved only using the Axiom of Choice. The Continuum Hypothesis is an example of an undecidable statement (of ZFC) which cannot be proved even with the Axiom of Choice. The question of how many cardinals there are between the countable and the continuum has nothing to do with the Axiom of Choice; not every mathematical use of the word "choose" is related to the Axiom of Choice. $\endgroup$ – Gerry Myerson Sep 26 '16 at 10:00
4
$\begingroup$

A theorem cannot be "undecidable" on its own; undecidability is a relationship between a theorem and a particular set of axioms. So asking for an "undecidable theorem" is like hearing about an equivalence relation and asking for an example of an "equivalent element".

Once we pick a particular set of axioms, then we can ask what theorems are undecidable from those axioms. For example,

  • The axiom of choice is undecidable from the axioms of Zermelo-Fraenkel set theory.

  • The continuum hypothesis is undecidable from the axioms of Zermelo-Franekel set theory with the axiom of choice (ZFC).

  • Similarly, the existence of an inaccessible cardinal number is undecidable from the axioms of ZFC set theory (including the axiom of choice).

  • The Paris-Harrington principle is undecidable from the axioms of Peano Arithmetic

There is a general result, Gödel's incompleteness theorem, which shows that all sufficiently strong systems of true axioms will have undecidable theorems. The examples above, though, are not the ones that are produced from the incompleteness theorems (not directly, at least).

The notion of "choice" in your book is not related to the sense of "choice" in the axiom of choice. The book is just saying that, if a theorem is undecidable from a set of axioms, we can decide whether we would like to add the theorem as an axiom, or whether we prefer to add its negation, and either will leave us with a consistent set of axioms.

This does not mean, though, that both the theorem and its negation are always equally acceptable. For example, many of our standard axioms are undecidable from the other axioms, but that does not suggest we should add the negations of these axioms instead (e.g. the negation of the axiom of choice is not a particularly useful axiom to add to ZF).

So the question becomes: what evidence or argument is there for accepting a new axiom, or for rejecting it?

For example, although the axiom of choice is undecidable in ZF set theory, it it standard to use it as an axiom in undergraduate mathematics. On the other hand, the continuum hypothesis is also undecidable in ZF set theory, but we don't usually take it as an axiom. This is because the argument for taking the axiom of choice as an axiom, historically, has been broadly accepted by the mathematics community (although not universally), while the argument for taking CH as an axiom has not been accepted to nearly the same extent.

$\endgroup$
  • $\begingroup$ I am concerned about your use of the word undecidable. In your answer the word unprovable is used where you have said undecidable. Undecidable refers to sets (ie the set of all theorems of ZFC). $\endgroup$ – Rene Schipperus Sep 26 '16 at 17:03
  • 2
    $\begingroup$ Unfortunately, "undecidable" is used in the literature both to refer to independent theorems for some set of axioms (as in this question) and to refer to algorithmically undecidable sets in the sense of computability theory. It took some force of will for me to avoid the word "independent" in the answer and math the terminology from the question. $\endgroup$ – Carl Mummert Sep 26 '16 at 17:25
  • $\begingroup$ What literature ? I have never seen this. $\endgroup$ – Rene Schipperus Sep 26 '16 at 17:27
  • 1
    $\begingroup$ There are many uses. Gödel's paper on the incompleteness theorems is entitled "Over formally undecidable propositions of Principia Mathematica and related systems I" and Gödel routinely used the term "undecidable". The source book edited by Martin Davis is entitled "The Undecidable: Basic papers on undecidable propositions, unsolvable problems, and computable functions" . In philosophy, they talk about "absolutely undecidable propositions", but never absolutely independent propositions. There are many other examples. It may date back to Hilbert's use of the word "Entscheidungsproblem". $\endgroup$ – Carl Mummert Sep 26 '16 at 17:32
  • $\begingroup$ Ok I dont like any of your examples (sorry) Godels papers and Davis book are old, and philosophy is irrelevant. What are the trends in modern textbooks and papers ? $\endgroup$ – Rene Schipperus Sep 26 '16 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.