Theory Intersection_Calculus
section ‹Calculi Based on the Intersection of Redundancy Criteria›
text ‹In this section, section 2.3 of the report is covered, on calculi
equipped with a family of redundancy criteria.›
theory Intersection_Calculus
imports
Calculus
Ordered_Resolution_Prover.Lazy_List_Liminf
Ordered_Resolution_Prover.Lazy_List_Chain
begin
subsection ‹Calculi with a Family of Redundancy Criteria›
locale intersection_calculus =
inference_system Inf + consequence_relation_family Bot Q entails_q
for
Bot :: "'f set" and
Inf :: ‹'f inference set› and
Q :: "'q set" and
entails_q :: "'q ⇒ 'f set ⇒ 'f set ⇒ bool"
+ fixes
Red_I_q :: "'q ⇒ 'f set ⇒ 'f inference set" and
Red_F_q :: "'q ⇒ 'f set ⇒ 'f set"
assumes
Q_nonempty: "Q ≠ {}" and
all_red_crit: "∀q ∈ Q. calculus Bot Inf (entails_q q) (Red_I_q q) (Red_F_q q)"
begin
definition Red_I :: "'f set ⇒ 'f inference set" where
"Red_I N = (⋂q ∈ Q. Red_I_q q N)"
definition Red_F :: "'f set ⇒ 'f set" where
"Red_F N = (⋂q ∈ Q. Red_F_q q N)"
sublocale calculus Bot Inf entails Red_I Red_F
unfolding calculus_def calculus_axioms_def
proof (intro conjI)
show "consequence_relation Bot entails"
using intersect_cons_rel_family .
next
show "∀N. Red_I N ⊆ Inf"
unfolding Red_I_def
proof
fix N
show "(⋂q ∈ Q. Red_I_q q N) ⊆ Inf"
proof (intro Inter_subset)
fix Red_Is
assume one_red_inf: "Red_Is ∈ (λq. Red_I_q q N) ` Q"
show "Red_Is ⊆ Inf"
using one_red_inf all_red_crit calculus.Red_I_to_Inf by blast
next
show "(λq. Red_I_q q N) ` Q ≠ {}"
using Q_nonempty by blast
qed
qed
next
show "∀B N. B ∈ Bot ⟶ N ⊨Q {B} ⟶ N - Red_F N ⊨Q {B}"
proof (intro allI impI)
fix B N
assume
B_in: "B ∈ Bot" and
N_unsat: "N ⊨Q {B}"
show "N - Red_F N ⊨Q {B}" unfolding entails_def Red_F_def
proof
fix qi
assume qi_in: "qi ∈ Q"
define entails_qi (infix ‹⊨qi› 50) where "entails_qi = entails_q qi"
have cons_rel_qi: "consequence_relation Bot entails_qi"
unfolding entails_qi_def using qi_in all_red_crit calculus.axioms(1) by blast
define Red_F_qi where "Red_F_qi = Red_F_q qi"
have red_qi_in: "Red_F N ⊆ Red_F_qi N"
unfolding Red_F_def Red_F_qi_def using qi_in image_iff by blast
then have "N - Red_F_qi N ⊆ N - Red_F N" by blast
then have entails_1: "N - Red_F N ⊨qi N - Red_F_qi N"
using qi_in all_red_crit
unfolding calculus_def consequence_relation_def entails_qi_def by metis
have N_unsat_qi: "N ⊨qi {B}" using qi_in N_unsat unfolding entails_qi_def entails_def
by simp
then have N_unsat_qi: "N - Red_F_qi N ⊨qi {B}"
using qi_in all_red_crit Red_F_qi_def calculus.Red_F_Bot[OF _ B_in] entails_qi_def
by fastforce
show "N - (⋂q ∈ Q. Red_F_q q N) ⊨qi {B}"
using consequence_relation.entails_trans[OF cons_rel_qi entails_1 N_unsat_qi]
unfolding Red_F_def .
qed
qed
next
show "∀N1 N2. N1 ⊆ N2 ⟶ Red_F N1 ⊆ Red_F N2"
proof (intro allI impI)
fix N1 :: "'f set"
and N2 :: "'f set"
assume
N1_in_N2: "N1 ⊆ N2"
show "Red_F N1 ⊆ Red_F N2"
proof
fix C
assume "C ∈ Red_F N1"
then have "∀qi ∈ Q. C ∈ Red_F_q qi N1" unfolding Red_F_def by blast
then have "∀qi ∈ Q. C ∈ Red_F_q qi N2"
using N1_in_N2 all_red_crit calculus.axioms(2) calculus.Red_F_of_subset by blast
then show "C ∈ Red_F N2" unfolding Red_F_def by blast
qed
qed
next
show "∀N1 N2. N1 ⊆ N2 ⟶ Red_I N1 ⊆ Red_I N2"
proof (intro allI impI)
fix N1 :: "'f set"
and N2 :: "'f set"
assume
N1_in_N2: "N1 ⊆ N2"
show "Red_I N1 ⊆ Red_I N2"
proof
fix ι
assume "ι ∈ Red_I N1"
then have "∀qi ∈ Q. ι ∈ Red_I_q qi N1" unfolding Red_I_def by blast
then have "∀qi ∈ Q. ι ∈ Red_I_q qi N2"
using N1_in_N2 all_red_crit calculus.axioms(2) calculus.Red_I_of_subset by blast
then show "ι ∈ Red_I N2" unfolding Red_I_def by blast
qed
qed
next
show "∀N2 N1. N2 ⊆ Red_F N1 ⟶ Red_F N1 ⊆ Red_F (N1 - N2)"
proof (intro allI impI)
fix N2 N1
assume N2_in_Red_N1: "N2 ⊆ Red_F N1"
show "Red_F N1 ⊆ Red_F (N1 - N2)"
proof
fix C
assume "C ∈ Red_F N1"
then have "∀qi ∈ Q. C ∈ Red_F_q qi N1" unfolding Red_F_def by blast
moreover have "∀qi ∈ Q. N2 ⊆ Red_F_q qi N1" using N2_in_Red_N1 unfolding Red_F_def by blast
ultimately have "∀qi ∈ Q. C ∈ Red_F_q qi (N1 - N2)"
using all_red_crit calculus.axioms(2) calculus.Red_F_of_Red_F_subset
by blast
then show "C ∈ Red_F (N1 - N2)" unfolding Red_F_def by blast
qed
qed
next
show "∀N2 N1. N2 ⊆ Red_F N1 ⟶ Red_I N1 ⊆ Red_I (N1 - N2)"
proof (intro allI impI)
fix N2 N1
assume N2_in_Red_N1: "N2 ⊆ Red_F N1"
show "Red_I N1 ⊆ Red_I (N1 - N2)"
proof
fix ι
assume "ι ∈ Red_I N1"
then have "∀qi ∈ Q. ι ∈ Red_I_q qi N1" unfolding Red_I_def by blast
moreover have "∀qi ∈ Q. N2 ⊆ Red_F_q qi N1" using N2_in_Red_N1 unfolding Red_F_def by blast
ultimately have "∀qi ∈ Q. ι ∈ Red_I_q qi (N1 - N2)"
using all_red_crit calculus.axioms(2) calculus.Red_I_of_Red_F_subset by blast
then show "ι ∈ Red_I (N1 - N2)" unfolding Red_I_def by blast
qed
qed
next
show "∀ι N. ι ∈ Inf ⟶ concl_of ι ∈ N ⟶ ι ∈ Red_I N"
proof (intro allI impI)
fix ι N
assume
i_in: "ι ∈ Inf" and
concl_in: "concl_of ι ∈ N"
then have "∀qi ∈ Q. ι ∈ Red_I_q qi N"
using all_red_crit calculus.axioms(2) calculus.Red_I_of_Inf_to_N by blast
then show "ι ∈ Red_I N" unfolding Red_I_def by blast
qed
qed
lemma sat_int_to_sat_q: "calculus.saturated Inf Red_I N ⟷
(∀qi ∈ Q. calculus.saturated Inf (Red_I_q qi) N)" for N
proof
fix N
assume inter_sat: "calculus.saturated Inf Red_I N"
show "∀qi ∈ Q. calculus.saturated Inf (Red_I_q qi) N"
proof
fix qi
assume qi_in: "qi ∈ Q"
then interpret one: calculus Bot Inf "entails_q qi" "Red_I_q qi" "Red_F_q qi"
by (metis all_red_crit)
show "one.saturated N"
using qi_in inter_sat
unfolding one.saturated_def saturated_def Red_I_def by blast
qed
next
fix N
assume all_sat: "∀qi ∈ Q. calculus.saturated Inf (Red_I_q qi) N"
show "saturated N"
unfolding saturated_def Red_I_def
proof
fix ι
assume ι_in: "ι ∈ Inf_from N"
have "∀Red_I_qi ∈ Red_I_q ` Q. ι ∈ Red_I_qi N"
proof
fix Red_I_qi
assume red_inf_in: "Red_I_qi ∈ Red_I_q ` Q"
then obtain qi where
qi_in: "qi ∈ Q" and
red_inf_qi_def: "Red_I_qi = Red_I_q qi" by blast
then interpret one: calculus Bot Inf "entails_q qi" "Red_I_q qi" "Red_F_q qi"
by (metis all_red_crit)
have "one.saturated N" using qi_in all_sat red_inf_qi_def by blast
then show "ι ∈ Red_I_qi N" unfolding one.saturated_def using ι_in red_inf_qi_def by blast
qed
then show "ι ∈ (⋂q ∈ Q. Red_I_q q N)" by blast
qed
qed
lemma stat_ref_comp_from_bot_in_sat:
"(∀N. calculus.saturated Inf Red_I N ∧ (∀B ∈ Bot. B ∉ N) ⟶
(∃B ∈ Bot. ∃qi ∈ Q. ¬ entails_q qi N {B})) ⟹
statically_complete_calculus Bot Inf entails Red_I Red_F"
proof (rule ccontr)
assume
N_saturated: "∀N. (calculus.saturated Inf Red_I N ∧ (∀B ∈ Bot. B ∉ N)) ⟶
(∃B ∈ Bot. ∃qi ∈ Q. ¬ entails_q qi N {B})" and
no_stat_ref_comp: "¬ statically_complete_calculus Bot Inf (⊨Q) Red_I Red_F"
obtain N1 B1 where B1_in:
"B1 ∈ Bot" and N1_saturated: "calculus.saturated Inf Red_I N1" and
N1_unsat: "N1 ⊨Q {B1}" and no_B_in_N1: "∀B ∈ Bot. B ∉ N1"
using no_stat_ref_comp by (metis calculus_axioms statically_complete_calculus.intro
statically_complete_calculus_axioms.intro)
obtain B2 qi where
qi_in: "qi ∈ Q" and
no_qi: "¬ entails_q qi N1 {B2}"
using N_saturated N1_saturated no_B_in_N1 by auto
have "N1 ⊨Q {B2}" using N1_unsat B1_in intersect_cons_rel_family
unfolding consequence_relation_def by metis
then have "entails_q qi N1 {B2}" unfolding entails_def using qi_in by blast
then show False using no_qi by simp
qed
end
end