src/HOL/Library/Continuum_Not_Denumerable.thy
changeset 63628 d02601840466
parent 63540 f8652d0534fa
child 63881 b746b19197bd
equal deleted inserted replaced
63625:1e7c5bbea36d 63628:d02601840466
    14 text \<open>
    14 text \<open>
    15   The following document presents a proof that the Continuum is uncountable.
    15   The following document presents a proof that the Continuum is uncountable.
    16   It is formalised in the Isabelle/Isar theorem proving system.
    16   It is formalised in the Isabelle/Isar theorem proving system.
    17 
    17 
    18   \<^bold>\<open>Theorem:\<close> The Continuum \<open>\<real>\<close> is not denumerable. In other words, there does
    18   \<^bold>\<open>Theorem:\<close> The Continuum \<open>\<real>\<close> is not denumerable. In other words, there does
    19   not exist a function \<open>f: \<nat> \<Rightarrow> \<real>\<close> such that f is surjective.
    19   not exist a function \<open>f: \<nat> \<Rightarrow> \<real>\<close> such that \<open>f\<close> is surjective.
    20 
    20 
    21   \<^bold>\<open>Outline:\<close> An elegant informal proof of this result uses Cantor's
    21   \<^bold>\<open>Outline:\<close> An elegant informal proof of this result uses Cantor's
    22   Diagonalisation argument. The proof presented here is not this one.
    22   Diagonalisation argument. The proof presented here is not this one.
    23 
    23 
    24   First we formalise some properties of closed intervals, then we prove the
    24   First we formalise some properties of closed intervals, then we prove the
    26   Real numbers and is the foundation for our argument. Informally it states
    26   Real numbers and is the foundation for our argument. Informally it states
    27   that an intersection of countable closed intervals (where each successive
    27   that an intersection of countable closed intervals (where each successive
    28   interval is a subset of the last) is non-empty. We then assume a surjective
    28   interval is a subset of the last) is non-empty. We then assume a surjective
    29   function \<open>f: \<nat> \<Rightarrow> \<real>\<close> exists and find a real \<open>x\<close> such that \<open>x\<close> is not in the
    29   function \<open>f: \<nat> \<Rightarrow> \<real>\<close> exists and find a real \<open>x\<close> such that \<open>x\<close> is not in the
    30   range of \<open>f\<close> by generating a sequence of closed intervals then using the
    30   range of \<open>f\<close> by generating a sequence of closed intervals then using the
    31   NIP.
    31   Nested Interval Property.
    32 \<close>
    32 \<close>
    33 
    33 
    34 theorem real_non_denum: "\<nexists>f :: nat \<Rightarrow> real. surj f"
    34 theorem real_non_denum: "\<nexists>f :: nat \<Rightarrow> real. surj f"
    35 proof
    35 proof
    36   assume "\<exists>f::nat \<Rightarrow> real. surj f"
    36   assume "\<exists>f::nat \<Rightarrow> real. surj f"