src/HOL/Library/Nat_Infinity.thy
author nipkow
Sat Feb 26 17:44:42 2011 +0100 (2011-02-26)
changeset 41853 258a489c24b2
parent 38621 d6cb7e625d75
child 41855 c3b6e69da386
permissions -rw-r--r--
Added material by David Trachtenherz
wenzelm@11355
     1
(*  Title:      HOL/Library/Nat_Infinity.thy
haftmann@27110
     2
    Author:     David von Oheimb, TU Muenchen;  Florian Haftmann, TU Muenchen
nipkow@41853
     3
    Contributions: David Trachtenherz, TU Muenchen
oheimb@11351
     4
*)
oheimb@11351
     5
wenzelm@14706
     6
header {* Natural numbers with infinity *}
oheimb@11351
     7
nipkow@15131
     8
theory Nat_Infinity
haftmann@30663
     9
imports Main
nipkow@15131
    10
begin
oheimb@11351
    11
haftmann@27110
    12
subsection {* Type definition *}
oheimb@11351
    13
oheimb@11351
    14
text {*
wenzelm@11355
    15
  We extend the standard natural numbers by a special value indicating
haftmann@27110
    16
  infinity.
oheimb@11351
    17
*}
oheimb@11351
    18
oheimb@11351
    19
datatype inat = Fin nat | Infty
oheimb@11351
    20
wenzelm@21210
    21
notation (xsymbols)
wenzelm@19736
    22
  Infty  ("\<infinity>")
wenzelm@19736
    23
wenzelm@21210
    24
notation (HTML output)
wenzelm@19736
    25
  Infty  ("\<infinity>")
wenzelm@19736
    26
oheimb@11351
    27
nipkow@31084
    28
lemma not_Infty_eq[iff]: "(x ~= Infty) = (EX i. x = Fin i)"
nipkow@31084
    29
by (cases x) auto
nipkow@31084
    30
nipkow@31084
    31
lemma not_Fin_eq [iff]: "(ALL y. x ~= Fin y) = (x = Infty)"
nipkow@31077
    32
by (cases x) auto
nipkow@31077
    33
nipkow@31077
    34
haftmann@27110
    35
subsection {* Constructors and numbers *}
haftmann@27110
    36
haftmann@27110
    37
instantiation inat :: "{zero, one, number}"
haftmann@25594
    38
begin
haftmann@25594
    39
haftmann@25594
    40
definition
haftmann@27110
    41
  "0 = Fin 0"
haftmann@25594
    42
haftmann@25594
    43
definition
haftmann@32069
    44
  [code_unfold]: "1 = Fin 1"
haftmann@25594
    45
haftmann@25594
    46
definition
haftmann@32069
    47
  [code_unfold, code del]: "number_of k = Fin (number_of k)"
oheimb@11351
    48
haftmann@25594
    49
instance ..
haftmann@25594
    50
haftmann@25594
    51
end
haftmann@25594
    52
haftmann@27110
    53
definition iSuc :: "inat \<Rightarrow> inat" where
haftmann@27110
    54
  "iSuc i = (case i of Fin n \<Rightarrow> Fin (Suc n) | \<infinity> \<Rightarrow> \<infinity>)"
oheimb@11351
    55
oheimb@11351
    56
lemma Fin_0: "Fin 0 = 0"
haftmann@27110
    57
  by (simp add: zero_inat_def)
haftmann@27110
    58
haftmann@27110
    59
lemma Fin_1: "Fin 1 = 1"
haftmann@27110
    60
  by (simp add: one_inat_def)
haftmann@27110
    61
haftmann@27110
    62
lemma Fin_number: "Fin (number_of k) = number_of k"
haftmann@27110
    63
  by (simp add: number_of_inat_def)
haftmann@27110
    64
haftmann@27110
    65
lemma one_iSuc: "1 = iSuc 0"
haftmann@27110
    66
  by (simp add: zero_inat_def one_inat_def iSuc_def)
oheimb@11351
    67
oheimb@11351
    68
lemma Infty_ne_i0 [simp]: "\<infinity> \<noteq> 0"
haftmann@27110
    69
  by (simp add: zero_inat_def)
oheimb@11351
    70
oheimb@11351
    71
lemma i0_ne_Infty [simp]: "0 \<noteq> \<infinity>"
haftmann@27110
    72
  by (simp add: zero_inat_def)
haftmann@27110
    73
haftmann@27110
    74
lemma zero_inat_eq [simp]:
haftmann@27110
    75
  "number_of k = (0\<Colon>inat) \<longleftrightarrow> number_of k = (0\<Colon>nat)"
haftmann@27110
    76
  "(0\<Colon>inat) = number_of k \<longleftrightarrow> number_of k = (0\<Colon>nat)"
haftmann@27110
    77
  unfolding zero_inat_def number_of_inat_def by simp_all
haftmann@27110
    78
haftmann@27110
    79
lemma one_inat_eq [simp]:
haftmann@27110
    80
  "number_of k = (1\<Colon>inat) \<longleftrightarrow> number_of k = (1\<Colon>nat)"
haftmann@27110
    81
  "(1\<Colon>inat) = number_of k \<longleftrightarrow> number_of k = (1\<Colon>nat)"
haftmann@27110
    82
  unfolding one_inat_def number_of_inat_def by simp_all
haftmann@27110
    83
haftmann@27110
    84
lemma zero_one_inat_neq [simp]:
haftmann@27110
    85
  "\<not> 0 = (1\<Colon>inat)"
haftmann@27110
    86
  "\<not> 1 = (0\<Colon>inat)"
haftmann@27110
    87
  unfolding zero_inat_def one_inat_def by simp_all
oheimb@11351
    88
haftmann@27110
    89
lemma Infty_ne_i1 [simp]: "\<infinity> \<noteq> 1"
haftmann@27110
    90
  by (simp add: one_inat_def)
haftmann@27110
    91
haftmann@27110
    92
lemma i1_ne_Infty [simp]: "1 \<noteq> \<infinity>"
haftmann@27110
    93
  by (simp add: one_inat_def)
haftmann@27110
    94
haftmann@27110
    95
lemma Infty_ne_number [simp]: "\<infinity> \<noteq> number_of k"
haftmann@27110
    96
  by (simp add: number_of_inat_def)
haftmann@27110
    97
haftmann@27110
    98
lemma number_ne_Infty [simp]: "number_of k \<noteq> \<infinity>"
haftmann@27110
    99
  by (simp add: number_of_inat_def)
haftmann@27110
   100
haftmann@27110
   101
lemma iSuc_Fin: "iSuc (Fin n) = Fin (Suc n)"
haftmann@27110
   102
  by (simp add: iSuc_def)
haftmann@27110
   103
haftmann@27110
   104
lemma iSuc_number_of: "iSuc (number_of k) = Fin (Suc (number_of k))"
haftmann@27110
   105
  by (simp add: iSuc_Fin number_of_inat_def)
oheimb@11351
   106
oheimb@11351
   107
lemma iSuc_Infty [simp]: "iSuc \<infinity> = \<infinity>"
haftmann@27110
   108
  by (simp add: iSuc_def)
oheimb@11351
   109
oheimb@11351
   110
lemma iSuc_ne_0 [simp]: "iSuc n \<noteq> 0"
haftmann@27110
   111
  by (simp add: iSuc_def zero_inat_def split: inat.splits)
haftmann@27110
   112
haftmann@27110
   113
lemma zero_ne_iSuc [simp]: "0 \<noteq> iSuc n"
haftmann@27110
   114
  by (rule iSuc_ne_0 [symmetric])
oheimb@11351
   115
haftmann@27110
   116
lemma iSuc_inject [simp]: "iSuc m = iSuc n \<longleftrightarrow> m = n"
haftmann@27110
   117
  by (simp add: iSuc_def split: inat.splits)
haftmann@27110
   118
haftmann@27110
   119
lemma number_of_inat_inject [simp]:
haftmann@27110
   120
  "(number_of k \<Colon> inat) = number_of l \<longleftrightarrow> (number_of k \<Colon> nat) = number_of l"
haftmann@27110
   121
  by (simp add: number_of_inat_def)
oheimb@11351
   122
oheimb@11351
   123
haftmann@27110
   124
subsection {* Addition *}
haftmann@27110
   125
haftmann@27110
   126
instantiation inat :: comm_monoid_add
haftmann@27110
   127
begin
haftmann@27110
   128
blanchet@38167
   129
definition [nitpick_simp]:
haftmann@37765
   130
  "m + n = (case m of \<infinity> \<Rightarrow> \<infinity> | Fin m \<Rightarrow> (case n of \<infinity> \<Rightarrow> \<infinity> | Fin n \<Rightarrow> Fin (m + n)))"
oheimb@11351
   131
haftmann@27110
   132
lemma plus_inat_simps [simp, code]:
haftmann@27110
   133
  "Fin m + Fin n = Fin (m + n)"
haftmann@27110
   134
  "\<infinity> + q = \<infinity>"
haftmann@27110
   135
  "q + \<infinity> = \<infinity>"
haftmann@27110
   136
  by (simp_all add: plus_inat_def split: inat.splits)
haftmann@27110
   137
haftmann@27110
   138
instance proof
haftmann@27110
   139
  fix n m q :: inat
haftmann@27110
   140
  show "n + m + q = n + (m + q)"
haftmann@27110
   141
    by (cases n, auto, cases m, auto, cases q, auto)
haftmann@27110
   142
  show "n + m = m + n"
haftmann@27110
   143
    by (cases n, auto, cases m, auto)
haftmann@27110
   144
  show "0 + n = n"
haftmann@27110
   145
    by (cases n) (simp_all add: zero_inat_def)
huffman@26089
   146
qed
huffman@26089
   147
haftmann@27110
   148
end
oheimb@11351
   149
haftmann@27110
   150
lemma plus_inat_0 [simp]:
haftmann@27110
   151
  "0 + (q\<Colon>inat) = q"
haftmann@27110
   152
  "(q\<Colon>inat) + 0 = q"
haftmann@27110
   153
  by (simp_all add: plus_inat_def zero_inat_def split: inat.splits)
oheimb@11351
   154
haftmann@27110
   155
lemma plus_inat_number [simp]:
huffman@29012
   156
  "(number_of k \<Colon> inat) + number_of l = (if k < Int.Pls then number_of l
huffman@29012
   157
    else if l < Int.Pls then number_of k else number_of (k + l))"
haftmann@27110
   158
  unfolding number_of_inat_def plus_inat_simps nat_arith(1) if_distrib [symmetric, of _ Fin] ..
oheimb@11351
   159
haftmann@27110
   160
lemma iSuc_number [simp]:
haftmann@27110
   161
  "iSuc (number_of k) = (if neg (number_of k \<Colon> int) then 1 else number_of (Int.succ k))"
haftmann@27110
   162
  unfolding iSuc_number_of
haftmann@27110
   163
  unfolding one_inat_def number_of_inat_def Suc_nat_number_of if_distrib [symmetric] ..
oheimb@11351
   164
haftmann@27110
   165
lemma iSuc_plus_1:
haftmann@27110
   166
  "iSuc n = n + 1"
haftmann@27110
   167
  by (cases n) (simp_all add: iSuc_Fin one_inat_def)
haftmann@27110
   168
  
haftmann@27110
   169
lemma plus_1_iSuc:
haftmann@27110
   170
  "1 + q = iSuc q"
haftmann@27110
   171
  "q + 1 = iSuc q"
nipkow@41853
   172
by (simp_all add: iSuc_plus_1 add_ac)
nipkow@41853
   173
nipkow@41853
   174
lemma iadd_Suc: "iSuc m + n = iSuc (m + n)"
nipkow@41853
   175
by (simp_all add: iSuc_plus_1 add_ac)
oheimb@11351
   176
nipkow@41853
   177
lemma iadd_Suc_right: "m + iSuc n = iSuc (m + n)"
nipkow@41853
   178
by (simp only: add_commute[of m] iadd_Suc)
nipkow@41853
   179
nipkow@41853
   180
lemma iadd_is_0: "(m + n = (0::inat)) = (m = 0 \<and> n = 0)"
nipkow@41853
   181
by (cases m, cases n, simp_all add: zero_inat_def)
oheimb@11351
   182
huffman@29014
   183
subsection {* Multiplication *}
huffman@29014
   184
huffman@29014
   185
instantiation inat :: comm_semiring_1
huffman@29014
   186
begin
huffman@29014
   187
blanchet@38167
   188
definition times_inat_def [nitpick_simp]:
huffman@29014
   189
  "m * n = (case m of \<infinity> \<Rightarrow> if n = 0 then 0 else \<infinity> | Fin m \<Rightarrow>
huffman@29014
   190
    (case n of \<infinity> \<Rightarrow> if m = 0 then 0 else \<infinity> | Fin n \<Rightarrow> Fin (m * n)))"
huffman@29014
   191
huffman@29014
   192
lemma times_inat_simps [simp, code]:
huffman@29014
   193
  "Fin m * Fin n = Fin (m * n)"
huffman@29014
   194
  "\<infinity> * \<infinity> = \<infinity>"
huffman@29014
   195
  "\<infinity> * Fin n = (if n = 0 then 0 else \<infinity>)"
huffman@29014
   196
  "Fin m * \<infinity> = (if m = 0 then 0 else \<infinity>)"
huffman@29014
   197
  unfolding times_inat_def zero_inat_def
huffman@29014
   198
  by (simp_all split: inat.split)
huffman@29014
   199
huffman@29014
   200
instance proof
huffman@29014
   201
  fix a b c :: inat
huffman@29014
   202
  show "(a * b) * c = a * (b * c)"
huffman@29014
   203
    unfolding times_inat_def zero_inat_def
huffman@29014
   204
    by (simp split: inat.split)
huffman@29014
   205
  show "a * b = b * a"
huffman@29014
   206
    unfolding times_inat_def zero_inat_def
huffman@29014
   207
    by (simp split: inat.split)
huffman@29014
   208
  show "1 * a = a"
huffman@29014
   209
    unfolding times_inat_def zero_inat_def one_inat_def
huffman@29014
   210
    by (simp split: inat.split)
huffman@29014
   211
  show "(a + b) * c = a * c + b * c"
huffman@29014
   212
    unfolding times_inat_def zero_inat_def
huffman@29014
   213
    by (simp split: inat.split add: left_distrib)
huffman@29014
   214
  show "0 * a = 0"
huffman@29014
   215
    unfolding times_inat_def zero_inat_def
huffman@29014
   216
    by (simp split: inat.split)
huffman@29014
   217
  show "a * 0 = 0"
huffman@29014
   218
    unfolding times_inat_def zero_inat_def
huffman@29014
   219
    by (simp split: inat.split)
huffman@29014
   220
  show "(0::inat) \<noteq> 1"
huffman@29014
   221
    unfolding zero_inat_def one_inat_def
huffman@29014
   222
    by simp
huffman@29014
   223
qed
huffman@29014
   224
huffman@29014
   225
end
huffman@29014
   226
huffman@29014
   227
lemma mult_iSuc: "iSuc m * n = n + m * n"
nipkow@29667
   228
  unfolding iSuc_plus_1 by (simp add: algebra_simps)
huffman@29014
   229
huffman@29014
   230
lemma mult_iSuc_right: "m * iSuc n = m + m * n"
nipkow@29667
   231
  unfolding iSuc_plus_1 by (simp add: algebra_simps)
huffman@29014
   232
huffman@29023
   233
lemma of_nat_eq_Fin: "of_nat n = Fin n"
huffman@29023
   234
  apply (induct n)
huffman@29023
   235
  apply (simp add: Fin_0)
huffman@29023
   236
  apply (simp add: plus_1_iSuc iSuc_Fin)
huffman@29023
   237
  done
huffman@29023
   238
haftmann@38621
   239
instance inat :: semiring_char_0 proof
haftmann@38621
   240
  have "inj Fin" by (rule injI) simp
haftmann@38621
   241
  then show "inj (\<lambda>n. of_nat n :: inat)" by (simp add: of_nat_eq_Fin)
haftmann@38621
   242
qed
huffman@29023
   243
nipkow@41853
   244
lemma imult_is_0[simp]: "((m::inat) * n = 0) = (m = 0 \<or> n = 0)"
nipkow@41853
   245
by(auto simp add: times_inat_def zero_inat_def split: inat.split)
nipkow@41853
   246
nipkow@41853
   247
lemma imult_is_Infty: "((a::inat) * b = \<infinity>) = (a = \<infinity> \<and> b \<noteq> 0 \<or> b = \<infinity> \<and> a \<noteq> 0)"
nipkow@41853
   248
by(auto simp add: times_inat_def zero_inat_def split: inat.split)
nipkow@41853
   249
nipkow@41853
   250
nipkow@41853
   251
subsection {* Subtraction *}
nipkow@41853
   252
nipkow@41853
   253
instantiation inat :: minus
nipkow@41853
   254
begin
nipkow@41853
   255
nipkow@41853
   256
definition diff_inat_def:
nipkow@41853
   257
"a - b = (case a of (Fin x) \<Rightarrow> (case b of (Fin y) \<Rightarrow> Fin (x - y) | \<infinity> \<Rightarrow> 0)
nipkow@41853
   258
          | \<infinity> \<Rightarrow> \<infinity>)"
nipkow@41853
   259
nipkow@41853
   260
instance ..
nipkow@41853
   261
nipkow@41853
   262
end
nipkow@41853
   263
nipkow@41853
   264
lemma idiff_Fin_Fin[simp,code]: "Fin a - Fin b = Fin (a - b)"
nipkow@41853
   265
by(simp add: diff_inat_def)
nipkow@41853
   266
nipkow@41853
   267
lemma idiff_Infty[simp,code]: "\<infinity> - n = \<infinity>"
nipkow@41853
   268
by(simp add: diff_inat_def)
nipkow@41853
   269
nipkow@41853
   270
lemma idiff_Infty_right[simp,code]: "Fin a - \<infinity> = 0"
nipkow@41853
   271
by(simp add: diff_inat_def)
nipkow@41853
   272
nipkow@41853
   273
lemma idiff_0[simp]: "(0::inat) - n = 0"
nipkow@41853
   274
by (cases n, simp_all add: zero_inat_def)
nipkow@41853
   275
nipkow@41853
   276
lemmas idiff_Fin_0[simp] = idiff_0[unfolded zero_inat_def]
nipkow@41853
   277
nipkow@41853
   278
lemma idiff_0_right[simp]: "(n::inat) - 0 = n"
nipkow@41853
   279
by (cases n) (simp_all add: zero_inat_def)
nipkow@41853
   280
nipkow@41853
   281
lemmas idiff_Fin_0_right[simp] = idiff_0_right[unfolded zero_inat_def]
nipkow@41853
   282
nipkow@41853
   283
lemma idiff_self[simp]: "n \<noteq> \<infinity> \<Longrightarrow> (n::inat) - n = 0"
nipkow@41853
   284
by(auto simp: zero_inat_def)
nipkow@41853
   285
nipkow@41853
   286
(*lemmas idiff_self_eq_0_Fin = idiff_self_eq_0[unfolded zero_inat_def]*)
nipkow@41853
   287
huffman@29014
   288
haftmann@27110
   289
subsection {* Ordering *}
haftmann@27110
   290
haftmann@35028
   291
instantiation inat :: linordered_ab_semigroup_add
haftmann@27110
   292
begin
oheimb@11351
   293
blanchet@38167
   294
definition [nitpick_simp]:
haftmann@37765
   295
  "m \<le> n = (case n of Fin n1 \<Rightarrow> (case m of Fin m1 \<Rightarrow> m1 \<le> n1 | \<infinity> \<Rightarrow> False)
haftmann@27110
   296
    | \<infinity> \<Rightarrow> True)"
oheimb@11351
   297
blanchet@38167
   298
definition [nitpick_simp]:
haftmann@37765
   299
  "m < n = (case m of Fin m1 \<Rightarrow> (case n of Fin n1 \<Rightarrow> m1 < n1 | \<infinity> \<Rightarrow> True)
haftmann@27110
   300
    | \<infinity> \<Rightarrow> False)"
oheimb@11351
   301
haftmann@27110
   302
lemma inat_ord_simps [simp]:
haftmann@27110
   303
  "Fin m \<le> Fin n \<longleftrightarrow> m \<le> n"
haftmann@27110
   304
  "Fin m < Fin n \<longleftrightarrow> m < n"
haftmann@27110
   305
  "q \<le> \<infinity>"
haftmann@27110
   306
  "q < \<infinity> \<longleftrightarrow> q \<noteq> \<infinity>"
haftmann@27110
   307
  "\<infinity> \<le> q \<longleftrightarrow> q = \<infinity>"
haftmann@27110
   308
  "\<infinity> < q \<longleftrightarrow> False"
haftmann@27110
   309
  by (simp_all add: less_eq_inat_def less_inat_def split: inat.splits)
oheimb@11351
   310
haftmann@27110
   311
lemma inat_ord_code [code]:
haftmann@27110
   312
  "Fin m \<le> Fin n \<longleftrightarrow> m \<le> n"
haftmann@27110
   313
  "Fin m < Fin n \<longleftrightarrow> m < n"
haftmann@27110
   314
  "q \<le> \<infinity> \<longleftrightarrow> True"
haftmann@27110
   315
  "Fin m < \<infinity> \<longleftrightarrow> True"
haftmann@27110
   316
  "\<infinity> \<le> Fin n \<longleftrightarrow> False"
haftmann@27110
   317
  "\<infinity> < q \<longleftrightarrow> False"
haftmann@27110
   318
  by simp_all
oheimb@11351
   319
haftmann@27110
   320
instance by default
haftmann@27110
   321
  (auto simp add: less_eq_inat_def less_inat_def plus_inat_def split: inat.splits)
oheimb@11351
   322
haftmann@27110
   323
end
haftmann@27110
   324
haftmann@35028
   325
instance inat :: ordered_comm_semiring
huffman@29014
   326
proof
huffman@29014
   327
  fix a b c :: inat
huffman@29014
   328
  assume "a \<le> b" and "0 \<le> c"
huffman@29014
   329
  thus "c * a \<le> c * b"
huffman@29014
   330
    unfolding times_inat_def less_eq_inat_def zero_inat_def
huffman@29014
   331
    by (simp split: inat.splits)
huffman@29014
   332
qed
huffman@29014
   333
haftmann@27110
   334
lemma inat_ord_number [simp]:
haftmann@27110
   335
  "(number_of m \<Colon> inat) \<le> number_of n \<longleftrightarrow> (number_of m \<Colon> nat) \<le> number_of n"
haftmann@27110
   336
  "(number_of m \<Colon> inat) < number_of n \<longleftrightarrow> (number_of m \<Colon> nat) < number_of n"
haftmann@27110
   337
  by (simp_all add: number_of_inat_def)
oheimb@11351
   338
haftmann@27110
   339
lemma i0_lb [simp]: "(0\<Colon>inat) \<le> n"
haftmann@27110
   340
  by (simp add: zero_inat_def less_eq_inat_def split: inat.splits)
oheimb@11351
   341
nipkow@41853
   342
lemma ile0_eq [simp]: "n \<le> (0\<Colon>inat) \<longleftrightarrow> n = 0"
nipkow@41853
   343
by (simp add: zero_inat_def less_eq_inat_def split: inat.splits)
haftmann@27110
   344
haftmann@27110
   345
lemma Infty_ileE [elim!]: "\<infinity> \<le> Fin m \<Longrightarrow> R"
haftmann@27110
   346
  by (simp add: zero_inat_def less_eq_inat_def split: inat.splits)
oheimb@11351
   347
haftmann@27110
   348
lemma Infty_ilessE [elim!]: "\<infinity> < Fin m \<Longrightarrow> R"
haftmann@27110
   349
  by simp
oheimb@11351
   350
nipkow@41853
   351
lemma not_iless0 [simp]: "\<not> n < (0\<Colon>inat)"
haftmann@27110
   352
  by (simp add: zero_inat_def less_inat_def split: inat.splits)
haftmann@27110
   353
nipkow@41853
   354
lemma i0_less [simp]: "(0\<Colon>inat) < n \<longleftrightarrow> n \<noteq> 0"
nipkow@41853
   355
by (simp add: zero_inat_def less_inat_def split: inat.splits)
oheimb@11351
   356
haftmann@27110
   357
lemma iSuc_ile_mono [simp]: "iSuc n \<le> iSuc m \<longleftrightarrow> n \<le> m"
haftmann@27110
   358
  by (simp add: iSuc_def less_eq_inat_def split: inat.splits)
haftmann@27110
   359
 
haftmann@27110
   360
lemma iSuc_mono [simp]: "iSuc n < iSuc m \<longleftrightarrow> n < m"
haftmann@27110
   361
  by (simp add: iSuc_def less_inat_def split: inat.splits)
oheimb@11351
   362
haftmann@27110
   363
lemma ile_iSuc [simp]: "n \<le> iSuc n"
haftmann@27110
   364
  by (simp add: iSuc_def less_eq_inat_def split: inat.splits)
oheimb@11351
   365
wenzelm@11355
   366
lemma not_iSuc_ilei0 [simp]: "\<not> iSuc n \<le> 0"
haftmann@27110
   367
  by (simp add: zero_inat_def iSuc_def less_eq_inat_def split: inat.splits)
haftmann@27110
   368
haftmann@27110
   369
lemma i0_iless_iSuc [simp]: "0 < iSuc n"
haftmann@27110
   370
  by (simp add: zero_inat_def iSuc_def less_inat_def split: inat.splits)
haftmann@27110
   371
nipkow@41853
   372
lemma iless_iSuc0[simp]: "(n < iSuc 0) = (n = 0)"
nipkow@41853
   373
by (simp add: zero_inat_def iSuc_def less_inat_def split: inat.split)
nipkow@41853
   374
haftmann@27110
   375
lemma ileI1: "m < n \<Longrightarrow> iSuc m \<le> n"
haftmann@27110
   376
  by (simp add: iSuc_def less_eq_inat_def less_inat_def split: inat.splits)
haftmann@27110
   377
haftmann@27110
   378
lemma Suc_ile_eq: "Fin (Suc m) \<le> n \<longleftrightarrow> Fin m < n"
haftmann@27110
   379
  by (cases n) auto
haftmann@27110
   380
haftmann@27110
   381
lemma iless_Suc_eq [simp]: "Fin m < iSuc n \<longleftrightarrow> Fin m \<le> n"
haftmann@27110
   382
  by (auto simp add: iSuc_def less_inat_def split: inat.splits)
oheimb@11351
   383
nipkow@41853
   384
lemma imult_Infty: "(0::inat) < n \<Longrightarrow> \<infinity> * n = \<infinity>"
nipkow@41853
   385
by (simp add: zero_inat_def less_inat_def split: inat.splits)
nipkow@41853
   386
nipkow@41853
   387
lemma imult_Infty_right: "(0::inat) < n \<Longrightarrow> n * \<infinity> = \<infinity>"
nipkow@41853
   388
by (simp add: zero_inat_def less_inat_def split: inat.splits)
nipkow@41853
   389
nipkow@41853
   390
lemma inat_0_less_mult_iff: "(0 < (m::inat) * n) = (0 < m \<and> 0 < n)"
nipkow@41853
   391
by (simp only: i0_less imult_is_0, simp)
nipkow@41853
   392
nipkow@41853
   393
lemma mono_iSuc: "mono iSuc"
nipkow@41853
   394
by(simp add: mono_def)
nipkow@41853
   395
nipkow@41853
   396
haftmann@27110
   397
lemma min_inat_simps [simp]:
haftmann@27110
   398
  "min (Fin m) (Fin n) = Fin (min m n)"
haftmann@27110
   399
  "min q 0 = 0"
haftmann@27110
   400
  "min 0 q = 0"
haftmann@27110
   401
  "min q \<infinity> = q"
haftmann@27110
   402
  "min \<infinity> q = q"
haftmann@27110
   403
  by (auto simp add: min_def)
oheimb@11351
   404
haftmann@27110
   405
lemma max_inat_simps [simp]:
haftmann@27110
   406
  "max (Fin m) (Fin n) = Fin (max m n)"
haftmann@27110
   407
  "max q 0 = q"
haftmann@27110
   408
  "max 0 q = q"
haftmann@27110
   409
  "max q \<infinity> = \<infinity>"
haftmann@27110
   410
  "max \<infinity> q = \<infinity>"
haftmann@27110
   411
  by (simp_all add: max_def)
haftmann@27110
   412
haftmann@27110
   413
lemma Fin_ile: "n \<le> Fin m \<Longrightarrow> \<exists>k. n = Fin k"
haftmann@27110
   414
  by (cases n) simp_all
haftmann@27110
   415
haftmann@27110
   416
lemma Fin_iless: "n < Fin m \<Longrightarrow> \<exists>k. n = Fin k"
haftmann@27110
   417
  by (cases n) simp_all
oheimb@11351
   418
oheimb@11351
   419
lemma chain_incr: "\<forall>i. \<exists>j. Y i < Y j ==> \<exists>j. Fin k < Y j"
nipkow@25134
   420
apply (induct_tac k)
nipkow@25134
   421
 apply (simp (no_asm) only: Fin_0)
haftmann@27110
   422
 apply (fast intro: le_less_trans [OF i0_lb])
nipkow@25134
   423
apply (erule exE)
nipkow@25134
   424
apply (drule spec)
nipkow@25134
   425
apply (erule exE)
nipkow@25134
   426
apply (drule ileI1)
nipkow@25134
   427
apply (rule iSuc_Fin [THEN subst])
nipkow@25134
   428
apply (rule exI)
haftmann@27110
   429
apply (erule (1) le_less_trans)
nipkow@25134
   430
done
oheimb@11351
   431
haftmann@29337
   432
instantiation inat :: "{bot, top}"
haftmann@29337
   433
begin
haftmann@29337
   434
haftmann@29337
   435
definition bot_inat :: inat where
haftmann@29337
   436
  "bot_inat = 0"
haftmann@29337
   437
haftmann@29337
   438
definition top_inat :: inat where
haftmann@29337
   439
  "top_inat = \<infinity>"
haftmann@29337
   440
haftmann@29337
   441
instance proof
haftmann@29337
   442
qed (simp_all add: bot_inat_def top_inat_def)
haftmann@29337
   443
haftmann@29337
   444
end
haftmann@29337
   445
huffman@26089
   446
haftmann@27110
   447
subsection {* Well-ordering *}
huffman@26089
   448
huffman@26089
   449
lemma less_FinE:
huffman@26089
   450
  "[| n < Fin m; !!k. n = Fin k ==> k < m ==> P |] ==> P"
huffman@26089
   451
by (induct n) auto
huffman@26089
   452
huffman@26089
   453
lemma less_InftyE:
huffman@26089
   454
  "[| n < Infty; !!k. n = Fin k ==> P |] ==> P"
huffman@26089
   455
by (induct n) auto
huffman@26089
   456
huffman@26089
   457
lemma inat_less_induct:
huffman@26089
   458
  assumes prem: "!!n. \<forall>m::inat. m < n --> P m ==> P n" shows "P n"
huffman@26089
   459
proof -
huffman@26089
   460
  have P_Fin: "!!k. P (Fin k)"
huffman@26089
   461
    apply (rule nat_less_induct)
huffman@26089
   462
    apply (rule prem, clarify)
huffman@26089
   463
    apply (erule less_FinE, simp)
huffman@26089
   464
    done
huffman@26089
   465
  show ?thesis
huffman@26089
   466
  proof (induct n)
huffman@26089
   467
    fix nat
huffman@26089
   468
    show "P (Fin nat)" by (rule P_Fin)
huffman@26089
   469
  next
huffman@26089
   470
    show "P Infty"
huffman@26089
   471
      apply (rule prem, clarify)
huffman@26089
   472
      apply (erule less_InftyE)
huffman@26089
   473
      apply (simp add: P_Fin)
huffman@26089
   474
      done
huffman@26089
   475
  qed
huffman@26089
   476
qed
huffman@26089
   477
huffman@26089
   478
instance inat :: wellorder
huffman@26089
   479
proof
haftmann@27823
   480
  fix P and n
haftmann@27823
   481
  assume hyp: "(\<And>n\<Colon>inat. (\<And>m\<Colon>inat. m < n \<Longrightarrow> P m) \<Longrightarrow> P n)"
haftmann@27823
   482
  show "P n" by (blast intro: inat_less_induct hyp)
huffman@26089
   483
qed
huffman@26089
   484
haftmann@27110
   485
haftmann@27110
   486
subsection {* Traditional theorem names *}
haftmann@27110
   487
haftmann@27110
   488
lemmas inat_defs = zero_inat_def one_inat_def number_of_inat_def iSuc_def
haftmann@27110
   489
  plus_inat_def less_eq_inat_def less_inat_def
haftmann@27110
   490
haftmann@27110
   491
lemmas inat_splits = inat.splits
haftmann@27110
   492
oheimb@11351
   493
end