src/HOL/Library/Formal_Power_Series.thy
changeset 62390 842917225d56
parent 62343 24106dc44def
child 62422 4aa35fd6c152
equal deleted inserted replaced
62380:29800666e526 62390:842917225d56
   470 lemma X_pow_eq_X_pow_iff [simp]:
   470 lemma X_pow_eq_X_pow_iff [simp]:
   471   "(X :: ('a :: {comm_ring_1}) fps) ^ m = X ^ n \<longleftrightarrow> m = n"
   471   "(X :: ('a :: {comm_ring_1}) fps) ^ m = X ^ n \<longleftrightarrow> m = n"
   472 proof
   472 proof
   473   assume "(X :: 'a fps) ^ m = X ^ n"
   473   assume "(X :: 'a fps) ^ m = X ^ n"
   474   hence "(X :: 'a fps) ^ m $ m = X ^ n $ m" by (simp only:)
   474   hence "(X :: 'a fps) ^ m $ m = X ^ n $ m" by (simp only:)
   475   thus "m = n" by (simp split: split_if_asm)
   475   thus "m = n" by (simp split: if_split_asm)
   476 qed simp_all
   476 qed simp_all
   477 
   477 
   478 
   478 
   479 subsection \<open>Subdegrees\<close>
   479 subsection \<open>Subdegrees\<close>
   480 
   480 
   765   assume A: "fps_cutoff n f = 0"
   765   assume A: "fps_cutoff n f = 0"
   766   thus "f = 0 \<or> n \<le> subdegree f"
   766   thus "f = 0 \<or> n \<le> subdegree f"
   767   proof (cases "f = 0")
   767   proof (cases "f = 0")
   768     assume "f \<noteq> 0"
   768     assume "f \<noteq> 0"
   769     with A have "n \<le> subdegree f"
   769     with A have "n \<le> subdegree f"
   770       by (intro subdegree_geI) (auto simp: fps_eq_iff split: split_if_asm)
   770       by (intro subdegree_geI) (auto simp: fps_eq_iff split: if_split_asm)
   771     thus ?thesis ..
   771     thus ?thesis ..
   772   qed simp
   772   qed simp
   773 qed (auto simp: fps_eq_iff intro: nth_less_subdegree_zero)
   773 qed (auto simp: fps_eq_iff intro: nth_less_subdegree_zero)
   774 
   774 
   775 lemma fps_cutoff_0 [simp]: "fps_cutoff 0 f = 0"
   775 lemma fps_cutoff_0 [simp]: "fps_cutoff 0 f = 0"
   822   "open (U :: 'a fps set) \<longleftrightarrow> (\<forall>x\<in>U. eventually (\<lambda>(x', y). x' = x \<longrightarrow> y \<in> U) uniformity)"
   822   "open (U :: 'a fps set) \<longleftrightarrow> (\<forall>x\<in>U. eventually (\<lambda>(x', y). x' = x \<longrightarrow> y \<in> U) uniformity)"
   823 
   823 
   824 instance
   824 instance
   825 proof
   825 proof
   826   show th: "dist a b = 0 \<longleftrightarrow> a = b" for a b :: "'a fps"
   826   show th: "dist a b = 0 \<longleftrightarrow> a = b" for a b :: "'a fps"
   827     by (simp add: dist_fps_def split: split_if_asm)
   827     by (simp add: dist_fps_def split: if_split_asm)
   828   then have th'[simp]: "dist a a = 0" for a :: "'a fps" by simp
   828   then have th'[simp]: "dist a a = 0" for a :: "'a fps" by simp
   829 
   829 
   830   fix a b c :: "'a fps"
   830   fix a b c :: "'a fps"
   831   consider "a = b" | "c = a \<or> c = b" | "a \<noteq> b" "a \<noteq> c" "b \<noteq> c" by blast
   831   consider "a = b" | "c = a \<or> c = b" | "a \<noteq> b" "a \<noteq> c" "b \<noteq> c" by blast
   832   then show "dist a b \<le> dist a c + dist b c"
   832   then show "dist a b \<le> dist a c + dist b c"
  4374   shows "f $ j = g $ j"
  4374   shows "f $ j = g $ j"
  4375 proof (rule ccontr)
  4375 proof (rule ccontr)
  4376   assume "f $ j \<noteq> g $ j"
  4376   assume "f $ j \<noteq> g $ j"
  4377   hence "f \<noteq> g" by auto
  4377   hence "f \<noteq> g" by auto
  4378   with assms have "i < subdegree (f - g)"
  4378   with assms have "i < subdegree (f - g)"
  4379     by (simp add: split_if_asm dist_fps_def)
  4379     by (simp add: if_split_asm dist_fps_def)
  4380   also have "\<dots> \<le> j"
  4380   also have "\<dots> \<le> j"
  4381     using \<open>f $ j \<noteq> g $ j\<close> by (intro subdegree_leI) simp_all
  4381     using \<open>f $ j \<noteq> g $ j\<close> by (intro subdegree_leI) simp_all
  4382   finally show False using \<open>j \<le> i\<close> by simp
  4382   finally show False using \<open>j \<le> i\<close> by simp
  4383 qed
  4383 qed
  4384 
  4384 
  4389   case True
  4389   case True
  4390   then show ?thesis by simp
  4390   then show ?thesis by simp
  4391 next
  4391 next
  4392   case False
  4392   case False
  4393   with assms have "dist f g = inverse (2 ^ subdegree (f - g))"
  4393   with assms have "dist f g = inverse (2 ^ subdegree (f - g))"
  4394     by (simp add: split_if_asm dist_fps_def)
  4394     by (simp add: if_split_asm dist_fps_def)
  4395   moreover
  4395   moreover
  4396   from assms and False have "i < subdegree (f - g)"
  4396   from assms and False have "i < subdegree (f - g)"
  4397     by (intro subdegree_greaterI) simp_all
  4397     by (intro subdegree_greaterI) simp_all
  4398   ultimately show ?thesis by simp
  4398   ultimately show ?thesis by simp
  4399 qed
  4399 qed