src/HOL/GCD.thy
changeset 44845 5e51075cbd97
parent 44821 a92f65e174cf
child 44890 22f665a2e91c
equal deleted inserted replaced
44844:f74a4175a3a8 44845:5e51075cbd97
  1461 
  1461 
  1462 
  1462 
  1463 subsubsection {* The complete divisibility lattice *}
  1463 subsubsection {* The complete divisibility lattice *}
  1464 
  1464 
  1465 
  1465 
  1466 interpretation gcd_semilattice_nat: semilattice_inf "op dvd" "(%m n::nat. m dvd n & ~ n dvd m)" gcd
  1466 interpretation gcd_semilattice_nat: semilattice_inf gcd "op dvd" "(%m n::nat. m dvd n & ~ n dvd m)"
  1467 proof
  1467 proof
  1468   case goal3 thus ?case by(metis gcd_unique_nat)
  1468   case goal3 thus ?case by(metis gcd_unique_nat)
  1469 qed auto
  1469 qed auto
  1470 
  1470 
  1471 interpretation lcm_semilattice_nat: semilattice_sup "op dvd" "(%m n::nat. m dvd n & ~ n dvd m)" lcm
  1471 interpretation lcm_semilattice_nat: semilattice_sup lcm "op dvd" "(%m n::nat. m dvd n & ~ n dvd m)"
  1472 proof
  1472 proof
  1473   case goal3 thus ?case by(metis lcm_unique_nat)
  1473   case goal3 thus ?case by(metis lcm_unique_nat)
  1474 qed auto
  1474 qed auto
  1475 
  1475 
  1476 interpretation gcd_lcm_lattice_nat: lattice "op dvd" "(%m n::nat. m dvd n & ~ n dvd m)" gcd lcm ..
  1476 interpretation gcd_lcm_lattice_nat: lattice gcd "op dvd" "(%m n::nat. m dvd n & ~ n dvd m)" lcm ..
  1477 
  1477 
  1478 text{* Lifting gcd and lcm to finite (Gcd/Lcm) and infinite sets (GCD/LCM).
  1478 text{* Lifting gcd and lcm to finite (Gcd/Lcm) and infinite sets (GCD/LCM).
  1479 GCD is defined via LCM to facilitate the proof that we have a complete lattice.
  1479 GCD is defined via LCM to facilitate the proof that we have a complete lattice.
  1480 Later on we show that GCD and Gcd coincide on finite sets.
  1480 Later on we show that GCD and Gcd coincide on finite sets.
  1481 *}
  1481 *}
  1577 proof -
  1577 proof -
  1578   show ?thesis using lcm_semilattice_nat.fold_sup_le_sup[OF assms, of 1] by (simp add: Lcm_def)
  1578   show ?thesis using lcm_semilattice_nat.fold_sup_le_sup[OF assms, of 1] by (simp add: Lcm_def)
  1579 qed
  1579 qed
  1580 
  1580 
  1581 interpretation gcd_lcm_complete_lattice_nat:
  1581 interpretation gcd_lcm_complete_lattice_nat:
  1582   complete_lattice GCD LCM "op dvd" "%m n::nat. m dvd n & ~ n dvd m" gcd lcm 1 0
  1582   complete_lattice GCD LCM gcd "op dvd" "%m n::nat. m dvd n & ~ n dvd m" lcm 1 0
  1583 proof
  1583 proof
  1584   case goal1 show ?case by simp
  1584   case goal1 show ?case by simp
  1585 next
  1585 next
  1586   case goal2 show ?case by simp
  1586   case goal2 show ?case by simp
  1587 next
  1587 next