Quelle  Basic.thy

theory Basic imports Main begin

lemma conj_rule: "[ P; Q ] ==> P ∧ (Q ∧ P)"
apply (rule conjI)
 apply assumption
apply (rule conjI)
 apply assumption
apply assumption
done
    

lemma disj_swap: "P | Q ==> Q | P"
apply (erule disjE)
 apply (rule disjI2)
 apply assumption
apply (rule disjI1)
apply assumption
done

lemma conj_swap: "P ∧ Q ==> Q ∧ P"
apply (rule conjI)
 apply (drule conjunct2)
 apply assumption
apply (drule conjunct1)
apply assumption
done

lemma imp_uncurry: "P ⟶ Q ⟶ R ==> P ∧ Q ⟶ R"
apply (rule impI)
apply (erule conjE)
apply (drule mp)
 apply assumption
apply (drule mp)
  apply assumption
 apply assumption
done

text ‹
 by eliminates uses of assumption and done
 ›

lemma imp_uncurry': "P ⟶ Q ⟶ R ==> P ∧ Q ⟶ R"
apply (rule impI)
apply (erule conjE)
apply (drule mp)
 apply assumption
by (drule mp)


text ‹
 substitution
 
 @{thm[display] ssubst}
 \rulename{ssubst}
 ›

lemma "[ x = f x; P(f x) ] ==> P x"
by (erule ssubst)

text ‹
 also provable by simp (re-orients)
 ›

text ‹
 the subst method
 
 @{thm[display] mult.commute}
 \rulename{mult.commute}
 
 this would fail:
 apply (simp add: mult.commute)
 ›


lemma "[P x y z; Suc x < y] ==> f z = x*y"
txt‹
 @{subgoals[display,indent=0,margin=65]}
 ›
apply (subst mult.commute) 
txt‹
 @{subgoals[display,indent=0,margin=65]}
 ›
oops

(*exercise involving THEN*)
lemma "[P x y z; Suc x < y] ==> f z = x*y"
apply (rule mult.commute [THEN ssubst]) 
oops


lemma "[x = f x; triple (f x) (f x) x] ==> triple x x x"
apply (erule ssubst) 
  🍋 ‹@{subgoals[display,indent=0,margin=65]}›
back 🍋 ‹@{subgoals[display,indent=0,margin=65]}›
back 🍋 ‹@{subgoals[display,indent=0,margin=65]}›
back 🍋 ‹@{subgoals[display,indent=0,margin=65]}›
back 🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply assumption
done

lemma "[ x = f x; triple (f x) (f x) x ] ==> triple x x x"
apply (erule ssubst, assumption)
done

text‹
 or better still
 ›

lemma "[ x = f x; triple (f x) (f x) x ] ==> triple x x x"
by (erule ssubst)


lemma "[ x = f x; triple (f x) (f x) x ] ==> triple x x x"
apply (erule_tac P="λu. triple u u x" in ssubst)
apply (assumption)
done


lemma "[ x = f x; triple (f x) (f x) x ] ==> triple x x x"
by (erule_tac P="λu. triple u u x" in ssubst)


text ‹
 negation
 
 @{thm[display] notI}
 \rulename{notI}
 
 @{thm[display] notE}
 \rulename{notE}
 
 @{thm[display] classical}
 \rulename{classical}
 
 @{thm[display] contrapos_pp}
 \rulename{contrapos_pp}
 
 @{thm[display] contrapos_pn}
 \rulename{contrapos_pn}
 
 @{thm[display] contrapos_np}
 \rulename{contrapos_np}
 
 @{thm[display] contrapos_nn}
 \rulename{contrapos_nn}
 ›


lemma "[¬(P⟶Q); ¬(R⟶Q)] ==> R"
apply (erule_tac Q="R⟶Q" in contrapos_np)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply (intro impI)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
by (erule notE)

text ‹
 @{thm[display] disjCI}
 \rulename{disjCI}
 ›

lemma "(P ∨ Q) ∧ R ==> P ∨ Q ∧ R"
apply (intro disjCI conjI)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›

apply (elim conjE disjE)
 apply assumption
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›

by (erule contrapos_np, rule conjI)
text‹
 proof\ {\isacharparenleft}prove{\isacharparenright}{\isacharcolon}\ step\ {\isadigit{6}}\isanewline
 \isanewline
 goal\ {\isacharparenleft}lemma{\isacharparenright}{\isacharcolon}\isanewline
 {\isacharparenleft}P\ {\isasymor}\ Q{\isacharparenright}\ {\isasymand}\ R\ {\isasymLongrightarrow}\ P\ {\isasymor}\ Q\ {\isasymand}\ R\isanewline
 \ {\isadigit{1}}{\isachardot}\ {\isasymlbrakk}R{\isacharsemicolon}\ Q{\isacharsemicolon}\ {\isasymnot}\ P{\isasymrbrakk}\ {\isasymLongrightarrow}\ Q\isanewline
 \ {\isadigit{2}}{\isachardot}\ {\isasymlbrakk}R{\isacharsemicolon}\ Q{\isacharsemicolon}\ {\isasymnot}\ P{\isasymrbrakk}\ {\isasymLongrightarrow}\ R
 ›


text‹rule_tac, etc.›


lemma "P&Q"
apply (rule_tac P=P and Q=Q in conjI)
oops


text‹unification failure trace›

declare [[unify_trace_failure = true]]

lemma "P(a, f(b, g(e,a), b), a) ==> P(a, f(b, g(c,a), b), a)"
txt‹
 @{subgoals[display,indent=0,margin=65]}
 apply assumption
 Clash: e =/= c
 
 Clash: == =/= Trueprop
 ›
oops

lemma "∀x y. P(x,y) --> P(y,x)"
apply auto
txt‹
 @{subgoals[display,indent=0,margin=65]}
 apply assumption
 
 Clash: bound variable x (depth 1) =/= bound variable y (depth 0)
 
 Clash: == =/= Trueprop
 Clash: == =/= Trueprop
 ›
oops

declare [[unify_trace_failure = false]]


text‹Quantifiers›

text ‹
 @{thm[display] allI}
 \rulename{allI}
 
 @{thm[display] allE}
 \rulename{allE}
 
 @{thm[display] spec}
 \rulename{spec}
 ›

lemma "∀x. P x ⟶ P x"
apply (rule allI)
by (rule impI)

lemma "(∀x. P ⟶ Q x) ==> P ⟶ (∀x. Q x)"
apply (rule impI, rule allI)
apply (drule spec)
by (drule mp)

text‹rename_tac›
lemma "x < y ==> ∀x y. P x (f y)"
apply (intro allI)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply (rename_tac v w)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
oops


lemma "[∀x. P x ⟶ P (h x); P a] ==> P(h (h a))"
apply (frule spec)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply (drule mp, assumption)
apply (drule spec)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
by (drule mp)

lemma "[∀x. P x ⟶ P (f x); P a] ==> P(f (f a))"
by blast


text‹
 the existential quantifier›

text ‹
 @{thm[display]"exI"}
 \rulename{exI}
 
 @{thm[display]"exE"}
 \rulename{exE}
 ›


text‹
 instantiating quantifiers explicitly by rule_tac and erule_tac›

lemma "[∀x. P x ⟶ P (h x); P a] ==> P(h (h a))"
apply (frule spec)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply (drule mp, assumption)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply (drule_tac x = "h a" in spec)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
by (drule mp)

text ‹
 @{thm[display]"dvd_def"}
 \rulename{dvd_def}
 ›

lemma mult_dvd_mono: "[i dvd m; j dvd n] ==> i*j dvd (m*n :: nat)"
apply (simp add: dvd_def)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply (erule exE) 
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply (erule exE) 
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply (rename_tac l)
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply (rule_tac x="k*l" in exI) 
        🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply simp
done

text‹
 Hilbert-epsilon theorems›

text‹
 @{thm[display] the_equality[no_vars]}
 \rulename{the_equality}
 
 @{thm[display] some_equality[no_vars]}
 \rulename{some_equality}
 
 @{thm[display] someI[no_vars]}
 \rulename{someI}
 
 @{thm[display] someI2[no_vars]}
 \rulename{someI2}
 
 @{thm[display] someI_ex[no_vars]}
 \rulename{someI_ex}
 
 needed for examples
 
 @{thm[display] inv_def[no_vars]}
 \rulename{inv_def}
 
 @{thm[display] Least_def[no_vars]}
 \rulename{Least_def}
 
 @{thm[display] order_antisym[no_vars]}
 \rulename{order_antisym}
 ›


lemma "inv Suc (Suc n) = n"
by (simp add: inv_def)

text‹but we know nothing about inv Suc 0›

theorem Least_equality:
     "[ P (k::nat); ∀x. P x ⟶ k ≤ x ] ==> (LEAST x. P(x)) = k"
apply (simp add: Least_def)
 
txt‹
 @{subgoals[display,indent=0,margin=65]}
 ›
   
apply (rule the_equality)

txt‹
 @{subgoals[display,indent=0,margin=65]}
 
 first subgoal is existence; second is uniqueness
 ›
by (auto intro: order_antisym)


theorem axiom_of_choice:
     "(∀x. ∃y. P x y) ==> ∃f. ∀x. P x (f x)"
apply (rule exI, rule allI)

txt‹
 @{subgoals[display,indent=0,margin=65]}
 
 state after intro rules
 ›
apply (drule spec, erule exE)

txt‹
 @{subgoals[display,indent=0,margin=65]}
 
 applying @text{someI} automatically instantiates
 🍋‹f› t
›

by (rule someI)

(*both can be done by blast, which however hasn't been introduced yet*)
lemma "[| P (k::nat); ∀x. P x ⟶ k ≤ x |] ==> (LEAST x. P(x)) = k"
apply (simp add: Least_def)
by (blast intro: order_antisym)

theorem axiom_of_choice': "(∀x. ∃y. P x y) ==> ∃f. ∀x. P x (f x)"
apply (rule exI [of _  "λx. SOME y. P x y"])
by (blast intro: someI)

text‹end of Epsilon section›


lemma "(∃x. P x) ∨ (∃x. Q x) ==> ∃x. P x ∨ Q x"
apply (elim exE disjE)
 apply (intro exI disjI1)
 apply assumption
apply (intro exI disjI2)
apply assumption
done

lemma "(P⟶Q) ∨ (Q⟶P)"
apply (intro disjCI impI)
apply (elim notE)
apply (intro impI)
apply assumption
done

lemma "(P∨Q)∧(P∨R) ==> P ∨ (Q∧R)"
apply (intro disjCI conjI)
apply (elim conjE disjE)
apply blast
apply blast
apply blast
apply blast
(*apply elim*)
done

lemma "(∃x. P ∧ Q x) ==> P ∧ (∃x. Q x)"
apply (erule exE)
apply (erule conjE)
apply (rule conjI)
 apply assumption
apply (rule exI)
 apply assumption
done

lemma "(∃x. P x) ∧ (∃x. Q x) ==> ∃x. P x ∧ Q x"
apply (erule conjE)
apply (erule exE)
apply (erule exE)
apply (rule exI)
apply (rule conjI)
 apply assumption
oops

lemma "∀y. R y y ==> ∃x. ∀y. R x y"
apply (rule exI) 
  🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply (rule allI) 
  🍋 ‹@{subgoals[display,indent=0,margin=65]}›
apply (drule spec) 
  🍋 ‹@{subgoals[display,indent=0,margin=65]}›
oops

lemma "∀x. ∃y. x=y"
apply (rule allI)
apply (rule exI)
apply (rule refl)
done

lemma "∃x. ∀y. x=y"
apply (rule exI)
apply (rule allI)
oops

end