src/HOL/Library/Countable.thy
author nipkow
Wed Jan 10 15:25:09 2018 +0100 (19 months ago)
changeset 67399 eab6ce8368fa
parent 66453 cc19f7ca2ed6
child 67405 e9ab4ad7bd15
permissions -rw-r--r--
ran isabelle update_op on all sources
haftmann@26169
     1
(*  Title:      HOL/Library/Countable.thy
haftmann@26350
     2
    Author:     Alexander Krauss, TU Muenchen
huffman@43534
     3
    Author:     Brian Huffman, Portland State University
blanchet@58160
     4
    Author:     Jasmin Blanchette, TU Muenchen
haftmann@26169
     5
*)
haftmann@26169
     6
wenzelm@60500
     7
section \<open>Encoding (almost) everything into natural numbers\<close>
haftmann@26169
     8
haftmann@26169
     9
theory Countable
wenzelm@66453
    10
imports Old_Datatype HOL.Rat Nat_Bijection
haftmann@26169
    11
begin
haftmann@26169
    12
wenzelm@60500
    13
subsection \<open>The class of countable types\<close>
haftmann@26169
    14
haftmann@29797
    15
class countable =
wenzelm@61076
    16
  assumes ex_inj: "\<exists>to_nat :: 'a \<Rightarrow> nat. inj to_nat"
haftmann@26169
    17
haftmann@26169
    18
lemma countable_classI:
haftmann@26169
    19
  fixes f :: "'a \<Rightarrow> nat"
haftmann@26169
    20
  assumes "\<And>x y. f x = f y \<Longrightarrow> x = y"
haftmann@26169
    21
  shows "OFCLASS('a, countable_class)"
haftmann@26169
    22
proof (intro_classes, rule exI)
haftmann@26169
    23
  show "inj f"
haftmann@26169
    24
    by (rule injI [OF assms]) assumption
haftmann@26169
    25
qed
haftmann@26169
    26
haftmann@26169
    27
wenzelm@60500
    28
subsection \<open>Conversion functions\<close>
haftmann@26169
    29
wenzelm@61076
    30
definition to_nat :: "'a::countable \<Rightarrow> nat" where
haftmann@26169
    31
  "to_nat = (SOME f. inj f)"
haftmann@26169
    32
wenzelm@61076
    33
definition from_nat :: "nat \<Rightarrow> 'a::countable" where
wenzelm@61076
    34
  "from_nat = inv (to_nat :: 'a \<Rightarrow> nat)"
haftmann@26169
    35
haftmann@26169
    36
lemma inj_to_nat [simp]: "inj to_nat"
haftmann@26169
    37
  by (rule exE_some [OF ex_inj]) (simp add: to_nat_def)
haftmann@26169
    38
hoelzl@43992
    39
lemma inj_on_to_nat[simp, intro]: "inj_on to_nat S"
hoelzl@43992
    40
  using inj_to_nat by (auto simp: inj_on_def)
hoelzl@43992
    41
huffman@29910
    42
lemma surj_from_nat [simp]: "surj from_nat"
huffman@29910
    43
  unfolding from_nat_def by (simp add: inj_imp_surj_inv)
huffman@29910
    44
haftmann@26169
    45
lemma to_nat_split [simp]: "to_nat x = to_nat y \<longleftrightarrow> x = y"
haftmann@26169
    46
  using injD [OF inj_to_nat] by auto
haftmann@26169
    47
haftmann@26169
    48
lemma from_nat_to_nat [simp]:
haftmann@26169
    49
  "from_nat (to_nat x) = x"
haftmann@26169
    50
  by (simp add: from_nat_def)
haftmann@26169
    51
haftmann@26169
    52
wenzelm@60500
    53
subsection \<open>Finite types are countable\<close>
haftmann@26169
    54
haftmann@26169
    55
subclass (in finite) countable
haftmann@28823
    56
proof
wenzelm@61076
    57
  have "finite (UNIV::'a set)" by (rule finite_UNIV)
nipkow@31992
    58
  with finite_conv_nat_seg_image [of "UNIV::'a set"]
haftmann@26169
    59
  obtain n and f :: "nat \<Rightarrow> 'a" 
haftmann@26169
    60
    where "UNIV = f ` {i. i < n}" by auto
haftmann@26169
    61
  then have "surj f" unfolding surj_def by auto
haftmann@26169
    62
  then have "inj (inv f)" by (rule surj_imp_inj_inv)
wenzelm@61076
    63
  then show "\<exists>to_nat :: 'a \<Rightarrow> nat. inj to_nat" by (rule exI[of inj])
haftmann@26169
    64
qed
haftmann@26169
    65
haftmann@26169
    66
wenzelm@60500
    67
subsection \<open>Automatically proving countability of old-style datatypes\<close>
huffman@43534
    68
wenzelm@61115
    69
context
wenzelm@61115
    70
begin
wenzelm@61115
    71
wenzelm@61115
    72
qualified inductive finite_item :: "'a Old_Datatype.item \<Rightarrow> bool" where
huffman@43534
    73
  undefined: "finite_item undefined"
blanchet@58112
    74
| In0: "finite_item x \<Longrightarrow> finite_item (Old_Datatype.In0 x)"
blanchet@58112
    75
| In1: "finite_item x \<Longrightarrow> finite_item (Old_Datatype.In1 x)"
blanchet@58112
    76
| Leaf: "finite_item (Old_Datatype.Leaf a)"
blanchet@58112
    77
| Scons: "\<lbrakk>finite_item x; finite_item y\<rbrakk> \<Longrightarrow> finite_item (Old_Datatype.Scons x y)"
huffman@43534
    78
wenzelm@61115
    79
qualified function nth_item :: "nat \<Rightarrow> ('a::countable) Old_Datatype.item"
huffman@43534
    80
where
huffman@43534
    81
  "nth_item 0 = undefined"
huffman@43534
    82
| "nth_item (Suc n) =
huffman@43534
    83
  (case sum_decode n of
huffman@43534
    84
    Inl i \<Rightarrow>
huffman@43534
    85
    (case sum_decode i of
blanchet@58112
    86
      Inl j \<Rightarrow> Old_Datatype.In0 (nth_item j)
blanchet@58112
    87
    | Inr j \<Rightarrow> Old_Datatype.In1 (nth_item j))
huffman@43534
    88
  | Inr i \<Rightarrow>
huffman@43534
    89
    (case sum_decode i of
blanchet@58112
    90
      Inl j \<Rightarrow> Old_Datatype.Leaf (from_nat j)
huffman@43534
    91
    | Inr j \<Rightarrow>
huffman@43534
    92
      (case prod_decode j of
blanchet@58112
    93
        (a, b) \<Rightarrow> Old_Datatype.Scons (nth_item a) (nth_item b))))"
huffman@43534
    94
by pat_completeness auto
huffman@43534
    95
huffman@43534
    96
lemma le_sum_encode_Inl: "x \<le> y \<Longrightarrow> x \<le> sum_encode (Inl y)"
huffman@43534
    97
unfolding sum_encode_def by simp
huffman@43534
    98
huffman@43534
    99
lemma le_sum_encode_Inr: "x \<le> y \<Longrightarrow> x \<le> sum_encode (Inr y)"
huffman@43534
   100
unfolding sum_encode_def by simp
huffman@43534
   101
wenzelm@61115
   102
qualified termination
huffman@43534
   103
by (relation "measure id")
huffman@43534
   104
  (auto simp add: sum_encode_eq [symmetric] prod_encode_eq [symmetric]
huffman@43534
   105
    le_imp_less_Suc le_sum_encode_Inl le_sum_encode_Inr
huffman@43534
   106
    le_prod_encode_1 le_prod_encode_2)
huffman@43534
   107
huffman@43534
   108
lemma nth_item_covers: "finite_item x \<Longrightarrow> \<exists>n. nth_item n = x"
huffman@43534
   109
proof (induct set: finite_item)
huffman@43534
   110
  case undefined
huffman@43534
   111
  have "nth_item 0 = undefined" by simp
huffman@43534
   112
  thus ?case ..
huffman@43534
   113
next
huffman@43534
   114
  case (In0 x)
huffman@43534
   115
  then obtain n where "nth_item n = x" by fast
blanchet@58112
   116
  hence "nth_item (Suc (sum_encode (Inl (sum_encode (Inl n))))) = Old_Datatype.In0 x" by simp
huffman@43534
   117
  thus ?case ..
huffman@43534
   118
next
huffman@43534
   119
  case (In1 x)
huffman@43534
   120
  then obtain n where "nth_item n = x" by fast
blanchet@58112
   121
  hence "nth_item (Suc (sum_encode (Inl (sum_encode (Inr n))))) = Old_Datatype.In1 x" by simp
huffman@43534
   122
  thus ?case ..
huffman@43534
   123
next
huffman@43534
   124
  case (Leaf a)
blanchet@58112
   125
  have "nth_item (Suc (sum_encode (Inr (sum_encode (Inl (to_nat a)))))) = Old_Datatype.Leaf a"
blanchet@58112
   126
    by simp
huffman@43534
   127
  thus ?case ..
huffman@43534
   128
next
huffman@43534
   129
  case (Scons x y)
huffman@43534
   130
  then obtain i j where "nth_item i = x" and "nth_item j = y" by fast
huffman@43534
   131
  hence "nth_item
blanchet@58112
   132
    (Suc (sum_encode (Inr (sum_encode (Inr (prod_encode (i, j))))))) = Old_Datatype.Scons x y"
blanchet@58112
   133
    by simp
huffman@43534
   134
  thus ?case ..
huffman@43534
   135
qed
huffman@43534
   136
huffman@43534
   137
theorem countable_datatype:
blanchet@58112
   138
  fixes Rep :: "'b \<Rightarrow> ('a::countable) Old_Datatype.item"
blanchet@58112
   139
  fixes Abs :: "('a::countable) Old_Datatype.item \<Rightarrow> 'b"
blanchet@58112
   140
  fixes rep_set :: "('a::countable) Old_Datatype.item \<Rightarrow> bool"
huffman@43534
   141
  assumes type: "type_definition Rep Abs (Collect rep_set)"
huffman@43534
   142
  assumes finite_item: "\<And>x. rep_set x \<Longrightarrow> finite_item x"
huffman@43534
   143
  shows "OFCLASS('b, countable_class)"
huffman@43534
   144
proof
wenzelm@63040
   145
  define f where "f y = (LEAST n. nth_item n = Rep y)" for y
huffman@43534
   146
  {
huffman@43534
   147
    fix y :: 'b
huffman@43534
   148
    have "rep_set (Rep y)"
huffman@43534
   149
      using type_definition.Rep [OF type] by simp
huffman@43534
   150
    hence "finite_item (Rep y)"
huffman@43534
   151
      by (rule finite_item)
huffman@43534
   152
    hence "\<exists>n. nth_item n = Rep y"
huffman@43534
   153
      by (rule nth_item_covers)
huffman@43534
   154
    hence "nth_item (f y) = Rep y"
huffman@43534
   155
      unfolding f_def by (rule LeastI_ex)
huffman@43534
   156
    hence "Abs (nth_item (f y)) = y"
huffman@43534
   157
      using type_definition.Rep_inverse [OF type] by simp
huffman@43534
   158
  }
huffman@43534
   159
  hence "inj f"
huffman@43534
   160
    by (rule inj_on_inverseI)
huffman@43534
   161
  thus "\<exists>f::'b \<Rightarrow> nat. inj f"
huffman@43534
   162
    by - (rule exI)
huffman@43534
   163
qed
huffman@43534
   164
wenzelm@60500
   165
ML \<open>
blanchet@58161
   166
  fun old_countable_datatype_tac ctxt =
blanchet@58160
   167
    SUBGOAL (fn (goal, _) =>
huffman@43534
   168
      let
huffman@43534
   169
        val ty_name =
huffman@43534
   170
          (case goal of
wenzelm@56243
   171
            (_ $ Const (@{const_name Pure.type}, Type (@{type_name itself}, [Type (n, _)]))) => n
huffman@43534
   172
          | _ => raise Match)
huffman@43534
   173
        val typedef_info = hd (Typedef.get_info ctxt ty_name)
huffman@43534
   174
        val typedef_thm = #type_definition (snd typedef_info)
huffman@43534
   175
        val pred_name =
wenzelm@59582
   176
          (case HOLogic.dest_Trueprop (Thm.concl_of typedef_thm) of
blanchet@58160
   177
            (_ $ _ $ _ $ (_ $ Const (n, _))) => n
huffman@43534
   178
          | _ => raise Match)
lars@65411
   179
        val induct_info = Inductive.the_inductive_global ctxt pred_name
huffman@43534
   180
        val pred_names = #names (fst induct_info)
huffman@43534
   181
        val induct_thms = #inducts (snd induct_info)
huffman@43534
   182
        val alist = pred_names ~~ induct_thms
nipkow@67399
   183
        val induct_thm = the (AList.lookup (=) alist pred_name)
huffman@49187
   184
        val vars = rev (Term.add_vars (Thm.prop_of induct_thm) [])
wenzelm@59643
   185
        val insts = vars |> map (fn (_, T) => try (Thm.cterm_of ctxt)
huffman@49187
   186
          (Const (@{const_name Countable.finite_item}, T)))
wenzelm@60801
   187
        val induct_thm' = Thm.instantiate' [] insts induct_thm
huffman@43534
   188
        val rules = @{thms finite_item.intros}
huffman@43534
   189
      in
huffman@43534
   190
        SOLVED' (fn i => EVERY
wenzelm@60752
   191
          [resolve_tac ctxt @{thms countable_datatype} i,
wenzelm@60752
   192
           resolve_tac ctxt [typedef_thm] i,
wenzelm@60752
   193
           eresolve_tac ctxt [induct_thm'] i,
wenzelm@60752
   194
           REPEAT (resolve_tac ctxt rules i ORELSE assume_tac ctxt i)]) 1
huffman@43534
   195
      end)
wenzelm@60500
   196
\<close>
wenzelm@47432
   197
wenzelm@61115
   198
end
huffman@43534
   199
huffman@43534
   200
wenzelm@60500
   201
subsection \<open>Automatically proving countability of datatypes\<close>
blanchet@58160
   202
blanchet@62691
   203
ML_file "../Tools/BNF/bnf_lfp_countable.ML"
blanchet@58160
   204
wenzelm@60500
   205
ML \<open>
blanchet@58161
   206
fun countable_datatype_tac ctxt st =
wenzelm@60029
   207
  (case try (fn () => HEADGOAL (old_countable_datatype_tac ctxt) st) () of
wenzelm@60029
   208
    SOME res => res
wenzelm@60029
   209
  | NONE => BNF_LFP_Countable.countable_datatype_tac ctxt st);
blanchet@58161
   210
blanchet@58161
   211
(* compatibility *)
blanchet@58161
   212
fun countable_tac ctxt =
blanchet@58161
   213
  SELECT_GOAL (countable_datatype_tac ctxt);
wenzelm@60500
   214
\<close>
blanchet@58161
   215
wenzelm@60500
   216
method_setup countable_datatype = \<open>
blanchet@58161
   217
  Scan.succeed (SIMPLE_METHOD o countable_datatype_tac)
wenzelm@60500
   218
\<close> "prove countable class instances for datatypes"
blanchet@58160
   219
blanchet@58160
   220
wenzelm@60500
   221
subsection \<open>More Countable types\<close>
blanchet@58160
   222
wenzelm@60500
   223
text \<open>Naturals\<close>
huffman@43534
   224
blanchet@58160
   225
instance nat :: countable
blanchet@58160
   226
  by (rule countable_classI [of "id"]) simp
blanchet@58160
   227
wenzelm@60500
   228
text \<open>Pairs\<close>
blanchet@58160
   229
blanchet@58160
   230
instance prod :: (countable, countable) countable
blanchet@58160
   231
  by (rule countable_classI [of "\<lambda>(x, y). prod_encode (to_nat x, to_nat y)"])
blanchet@58160
   232
    (auto simp add: prod_encode_eq)
blanchet@58158
   233
wenzelm@60500
   234
text \<open>Sums\<close>
blanchet@58160
   235
blanchet@58160
   236
instance sum :: (countable, countable) countable
blanchet@58160
   237
  by (rule countable_classI [of "(\<lambda>x. case x of Inl a \<Rightarrow> to_nat (False, to_nat a)
blanchet@58160
   238
                                     | Inr b \<Rightarrow> to_nat (True, to_nat b))"])
blanchet@58160
   239
    (simp split: sum.split_asm)
blanchet@58160
   240
wenzelm@60500
   241
text \<open>Integers\<close>
blanchet@58158
   242
blanchet@58160
   243
instance int :: countable
blanchet@58160
   244
  by (rule countable_classI [of int_encode]) (simp add: int_encode_eq)
blanchet@58160
   245
wenzelm@60500
   246
text \<open>Options\<close>
blanchet@58160
   247
blanchet@58160
   248
instance option :: (countable) countable
blanchet@58160
   249
  by countable_datatype
blanchet@58160
   250
wenzelm@60500
   251
text \<open>Lists\<close>
blanchet@58160
   252
blanchet@58160
   253
instance list :: (countable) countable
blanchet@58160
   254
  by countable_datatype
blanchet@58160
   255
wenzelm@60500
   256
text \<open>String literals\<close>
blanchet@58160
   257
blanchet@58160
   258
instance String.literal :: countable
blanchet@58221
   259
  by (rule countable_classI [of "to_nat \<circ> String.explode"]) (auto simp add: explode_inject)
blanchet@58160
   260
wenzelm@60500
   261
text \<open>Functions\<close>
blanchet@58160
   262
blanchet@58160
   263
instance "fun" :: (finite, countable) countable
blanchet@58160
   264
proof
blanchet@58160
   265
  obtain xs :: "'a list" where xs: "set xs = UNIV"
blanchet@58160
   266
    using finite_list [OF finite_UNIV] ..
blanchet@58160
   267
  show "\<exists>to_nat::('a \<Rightarrow> 'b) \<Rightarrow> nat. inj to_nat"
blanchet@58160
   268
  proof
blanchet@58160
   269
    show "inj (\<lambda>f. to_nat (map f xs))"
blanchet@58160
   270
      by (rule injI, simp add: xs fun_eq_iff)
blanchet@58160
   271
  qed
blanchet@58160
   272
qed
blanchet@58160
   273
wenzelm@60500
   274
text \<open>Typereps\<close>
blanchet@58158
   275
huffman@43534
   276
instance typerep :: countable
blanchet@58160
   277
  by countable_datatype
blanchet@58160
   278
blanchet@58160
   279
wenzelm@60500
   280
subsection \<open>The rationals are countably infinite\<close>
blanchet@58160
   281
blanchet@58160
   282
definition nat_to_rat_surj :: "nat \<Rightarrow> rat" where
blanchet@58160
   283
  "nat_to_rat_surj n = (let (a, b) = prod_decode n in Fract (int_decode a) (int_decode b))"
blanchet@58160
   284
blanchet@58160
   285
lemma surj_nat_to_rat_surj: "surj nat_to_rat_surj"
blanchet@58160
   286
unfolding surj_def
blanchet@58160
   287
proof
blanchet@58160
   288
  fix r::rat
blanchet@58160
   289
  show "\<exists>n. r = nat_to_rat_surj n"
blanchet@58160
   290
  proof (cases r)
blanchet@58160
   291
    fix i j assume [simp]: "r = Fract i j" and "j > 0"
blanchet@58161
   292
    have "r = (let m = int_encode i; n = int_encode j in nat_to_rat_surj (prod_encode (m, n)))"
blanchet@58160
   293
      by (simp add: Let_def nat_to_rat_surj_def)
blanchet@58161
   294
    thus "\<exists>n. r = nat_to_rat_surj n" by(auto simp: Let_def)
blanchet@58160
   295
  qed
blanchet@58160
   296
qed
blanchet@58160
   297
blanchet@58160
   298
lemma Rats_eq_range_nat_to_rat_surj: "\<rat> = range nat_to_rat_surj"
blanchet@58160
   299
  by (simp add: Rats_def surj_nat_to_rat_surj)
blanchet@58160
   300
blanchet@58160
   301
context field_char_0
blanchet@58160
   302
begin
blanchet@58160
   303
blanchet@58160
   304
lemma Rats_eq_range_of_rat_o_nat_to_rat_surj:
blanchet@58221
   305
  "\<rat> = range (of_rat \<circ> nat_to_rat_surj)"
blanchet@58160
   306
  using surj_nat_to_rat_surj
blanchet@58160
   307
  by (auto simp: Rats_def image_def surj_def) (blast intro: arg_cong[where f = of_rat])
blanchet@58160
   308
blanchet@58160
   309
lemma surj_of_rat_nat_to_rat_surj:
blanchet@58221
   310
  "r \<in> \<rat> \<Longrightarrow> \<exists>n. r = of_rat (nat_to_rat_surj n)"
blanchet@58160
   311
  by (simp add: Rats_eq_range_of_rat_o_nat_to_rat_surj image_def)
huffman@43534
   312
huffman@43534
   313
end
blanchet@58160
   314
blanchet@58160
   315
instance rat :: countable
blanchet@58160
   316
proof
blanchet@58160
   317
  show "\<exists>to_nat::rat \<Rightarrow> nat. inj to_nat"
blanchet@58160
   318
  proof
blanchet@58160
   319
    have "surj nat_to_rat_surj"
blanchet@58160
   320
      by (rule surj_nat_to_rat_surj)
blanchet@58160
   321
    then show "inj (inv nat_to_rat_surj)"
blanchet@58160
   322
      by (rule surj_imp_inj_inv)
blanchet@58160
   323
  qed
blanchet@58160
   324
qed
blanchet@58160
   325
blanchet@58160
   326
end