section ‹Independence systems›
theory Indep_System
imports Main
begin
lemma finite_psubset_inc_induct:
assumes "finite A" "X ⊆ A"
assumes "⋀X. (⋀Y. X ⊂ Y ⟹ Y ⊆ A ⟹ P Y) ⟹ P X"
shows "P X"
proof -
have wf: "wf {(X,Y). Y ⊂ X ∧ X ⊆ A}"
by (rule wf_bounded_set[where ub = "λ_. A" and f = id]) (auto simp add: ‹finite A›)
show ?thesis
proof (induction X rule: wf_induct[OF wf, case_names step])
case (step X)
then show ?case using assms(3)[of X] by blast
qed
qed
text ‹
An \emph{independence system} consists of a finite ground set together with an independence
predicate over the sets of this ground set. At least one set of the carrier is independent and
subsets of independent sets are also independent.
›
locale indep_system =
fixes carrier :: "'a set"
fixes indep :: "'a set ⇒ bool"
assumes carrier_finite: "finite carrier"
assumes indep_subset_carrier: "indep X ⟹ X ⊆ carrier"
assumes indep_ex: "∃X. indep X"
assumes indep_subset: "indep X ⟹ Y ⊆ X ⟹ indep Y"
begin
lemmas psubset_inc_induct [case_names carrier step] = finite_psubset_inc_induct[OF carrier_finite]
lemmas indep_finite [simp] = finite_subset[OF indep_subset_carrier carrier_finite]
text ‹
The empty set is independent.
›
lemma indep_empty [simp]: "indep {}"
using indep_ex indep_subset by auto
subsection ‹Sub-independence systems›
text ‹
A subset of the ground set induces an independence system.
›
definition indep_in where "indep_in ℰ X ⟷ X ⊆ ℰ ∧ indep X"
lemma indep_inI:
assumes "X ⊆ ℰ"
assumes "indep X"
shows "indep_in ℰ X"
using assms unfolding indep_in_def by auto
lemma indep_in_subI: "indep_in ℰ X ⟹ indep_in ℰ' (X ∩ ℰ')"
using indep_subset unfolding indep_in_def by auto
lemma dep_in_subI:
assumes "X ⊆ ℰ'"
shows "¬ indep_in ℰ' X ⟹ ¬ indep_in ℰ X"
using assms unfolding indep_in_def by auto
lemma indep_in_subset_carrier: "indep_in ℰ X ⟹ X ⊆ ℰ"
unfolding indep_in_def by auto
lemma indep_in_subI_subset:
assumes "ℰ' ⊆ ℰ"
assumes "indep_in ℰ' X"
shows "indep_in ℰ X"
proof -
have "indep_in ℰ (X ∩ ℰ)" using assms indep_in_subI by auto
moreover have "X ∩ ℰ = X" using assms indep_in_subset_carrier by auto
ultimately show ?thesis by auto
qed
lemma indep_in_supI:
assumes "X ⊆ ℰ'" "ℰ' ⊆ ℰ"
assumes "indep_in ℰ X"
shows "indep_in ℰ' X"
proof -
have "X ∩ ℰ' = X" using assms by auto
then show ?thesis using assms indep_in_subI[where ℰ = ℰ and ℰ' = ℰ' and X = X] by auto
qed
lemma indep_in_indep: "indep_in ℰ X ⟹ indep X"
unfolding indep_in_def by auto
lemmas indep_inD = indep_in_subset_carrier indep_in_indep
lemma indep_system_subset [simp, intro]:
assumes "ℰ ⊆ carrier"
shows "indep_system ℰ (indep_in ℰ)"
unfolding indep_system_def indep_in_def
using finite_subset[OF assms carrier_finite] indep_subset by auto
text ‹
We will work a lot with different sub structures. Therefore, every definition `foo' will have
a counterpart `foo\_in' which has the ground set as an additional parameter. Furthermore, every
result about `foo' will have another result about `foo\_in'. With this, we usually don't have to
work with @{command interpretation} in proofs.
›
context
fixes ℰ
assumes "ℰ ⊆ carrier"
begin
interpretation ℰ: indep_system ℰ "indep_in ℰ"
using ‹ℰ ⊆ carrier› by auto
lemma indep_in_sub_cong:
assumes "ℰ' ⊆ ℰ"
shows "ℰ.indep_in ℰ' X ⟷ indep_in ℰ' X"
unfolding ℰ.indep_in_def indep_in_def using assms by auto
lemmas indep_in_ex = ℰ.indep_ex
lemmas indep_in_subset = ℰ.indep_subset
lemmas indep_in_empty = ℰ.indep_empty
end
subsection ‹Bases›
text ‹
A \emph{basis} is a maximal independent set, i.\,e.\ an independent set which becomes dependent on
inserting any element of the ground set.
›
definition basis where "basis X ⟷ indep X ∧ (∀x ∈ carrier - X. ¬ indep (insert x X))"
lemma basisI:
assumes "indep X"
assumes "⋀x. x ∈ carrier - X ⟹ ¬ indep (insert x X)"
shows "basis X"
using assms unfolding basis_def by auto
lemma basis_indep: "basis X ⟹ indep X"
unfolding basis_def by auto
lemma basis_max_indep: "basis X ⟹ x ∈ carrier - X ⟹ ¬ indep (insert x X)"
unfolding basis_def by auto
lemmas basisD = basis_indep basis_max_indep
lemmas basis_subset_carrier = indep_subset_carrier[OF basis_indep]
lemmas basis_finite [simp] = indep_finite[OF basis_indep]
lemma indep_not_basis:
assumes "indep X"
assumes "¬ basis X"
shows "∃x ∈ carrier - X. indep (insert x X)"
using assms basisI by auto
lemma basis_subset_eq:
assumes "basis B⇩1"
assumes "basis B⇩2"
assumes "B⇩1 ⊆ B⇩2"
shows "B⇩1 = B⇩2"
proof (rule ccontr)
assume "B⇩1 ≠ B⇩2"
then obtain x where x: "x ∈ B⇩2 - B⇩1" using assms by auto
then have "insert x B⇩1 ⊆ B⇩2" using assms by auto
then have "indep (insert x B⇩1)" using assms basis_indep[of B⇩2] indep_subset by auto
moreover have "x ∈ carrier - B⇩1" using assms x basis_subset_carrier by auto
ultimately show False using assms basisD by auto
qed
definition basis_in where
"basis_in ℰ X ⟷ indep_system.basis ℰ (indep_in ℰ) X"
lemma basis_iff_basis_in: "basis B ⟷ basis_in carrier B"
proof -
interpret ℰ: indep_system carrier "indep_in carrier"
by auto
show "basis B ⟷ basis_in carrier B"
unfolding basis_in_def
proof (standard, goal_cases LTR RTL)
case LTR
show ?case
proof (rule ℰ.basisI)
show "indep_in carrier B" using LTR basisD indep_subset_carrier indep_inI by auto
next
fix x
assume "x ∈ carrier - B"
then have "¬ indep (insert x B)" using LTR basisD by auto
then show "¬ indep_in carrier (insert x B)" using indep_inD by auto
qed
next
case RTL
show ?case
proof (rule basisI)
show "indep B" using RTL ℰ.basis_indep indep_inD by blast
next
fix x
assume "x ∈ carrier - B"
then have "¬ indep_in carrier (insert x B)" using RTL ℰ.basisD by auto
then show "¬ indep (insert x B)" using indep_subset_carrier indep_inI by blast
qed
qed
qed
context
fixes ℰ
assumes "ℰ ⊆ carrier"
begin
interpretation ℰ: indep_system ℰ "indep_in ℰ"
using ‹ℰ ⊆ carrier› by auto
lemma basis_inI_aux: "ℰ.basis X ⟹ basis_in ℰ X"
unfolding basis_in_def by auto
lemma basis_inD_aux: "basis_in ℰ X ⟹ ℰ.basis X"
unfolding basis_in_def by auto
lemma not_basis_inD_aux: "¬ basis_in ℰ X ⟹ ¬ ℰ.basis X"
using basis_inI_aux by auto
lemmas basis_inI = basis_inI_aux[OF ℰ.basisI]
lemmas basis_in_indep_in = ℰ.basis_indep[OF basis_inD_aux]
lemmas basis_in_max_indep_in = ℰ.basis_max_indep[OF basis_inD_aux]
lemmas basis_inD = ℰ.basisD[OF basis_inD_aux]
lemmas basis_in_subset_carrier = ℰ.basis_subset_carrier[OF basis_inD_aux]
lemmas basis_in_finite = ℰ.basis_finite[OF basis_inD_aux]
lemmas indep_in_not_basis_in = ℰ.indep_not_basis[OF _ not_basis_inD_aux]
lemmas basis_in_subset_eq = ℰ.basis_subset_eq[OF basis_inD_aux basis_inD_aux]
end
context
fixes ℰ
assumes *: "ℰ ⊆ carrier"
begin
interpretation ℰ: indep_system ℰ "indep_in ℰ"
using * by auto
lemma basis_in_sub_cong:
assumes "ℰ' ⊆ ℰ"
shows "ℰ.basis_in ℰ' B ⟷ basis_in ℰ' B"
proof (safe, goal_cases LTR RTL)
case LTR
show ?case
proof (rule basis_inI)
show "ℰ' ⊆ carrier" using assms * by auto
next
show "indep_in ℰ' B"
using * assms LTR ℰ.basis_in_subset_carrier ℰ.basis_in_indep_in indep_in_sub_cong by auto
next
fix x
assume "x ∈ ℰ' - B"
then show "¬ indep_in ℰ' (insert x B)"
using * assms LTR ℰ.basis_in_max_indep_in ℰ.basis_in_subset_carrier indep_in_sub_cong by auto
qed
next
case RTL
show ?case
proof (rule ℰ.basis_inI)
show "ℰ' ⊆ ℰ" using assms by auto
next
show "ℰ.indep_in ℰ' B"
using * assms RTL basis_in_subset_carrier basis_in_indep_in indep_in_sub_cong by auto
next
fix x
assume "x ∈ ℰ' - B"
then show "¬ ℰ.indep_in ℰ' (insert x B)"
using * assms RTL basis_in_max_indep_in basis_in_subset_carrier indep_in_sub_cong by auto
qed
qed
end
subsection ‹Circuits›
text ‹
A \emph{circuit} is a minimal dependent set, i.\,e.\ a set which becomes independent on removing
any element of the ground set.
›
definition circuit where "circuit X ⟷ X ⊆ carrier ∧ ¬ indep X ∧ (∀x ∈ X. indep (X - {x}))"
lemma circuitI:
assumes "X ⊆ carrier"
assumes "¬ indep X"
assumes "⋀x. x ∈ X ⟹ indep (X - {x})"
shows "circuit X"
using assms unfolding circuit_def by auto
lemma circuit_subset_carrier: "circuit X ⟹ X ⊆ carrier"
unfolding circuit_def by auto
lemmas circuit_finite [simp] = finite_subset[OF circuit_subset_carrier carrier_finite]
lemma circuit_dep: "circuit X ⟹ ¬ indep X"
unfolding circuit_def by auto
lemma circuit_min_dep: "circuit X ⟹ x ∈ X ⟹ indep (X - {x})"
unfolding circuit_def by auto
lemmas circuitD = circuit_subset_carrier circuit_dep circuit_min_dep
lemma circuit_nonempty: "circuit X ⟹ X ≠ {}"
using circuit_dep indep_empty by blast
lemma dep_not_circuit:
assumes "X ⊆ carrier"
assumes "¬ indep X"
assumes "¬ circuit X"
shows "∃x ∈ X. ¬ indep (X - {x})"
using assms circuitI by auto
lemma circuit_subset_eq:
assumes "circuit C⇩1"
assumes "circuit C⇩2"
assumes "C⇩1 ⊆ C⇩2"
shows "C⇩1 = C⇩2"
proof (rule ccontr)
assume "C⇩1 ≠ C⇩2"
then obtain x where "x ∉ C⇩1" "x ∈ C⇩2" using assms by auto
then have "indep C⇩1" using indep_subset ‹C⇩1 ⊆ C⇩2› circuit_min_dep[OF ‹circuit C⇩2›, of x] by auto
then show False using assms circuitD by auto
qed
definition circuit_in where
"circuit_in ℰ X ⟷ indep_system.circuit ℰ (indep_in ℰ) X"
context
fixes ℰ
assumes "ℰ ⊆ carrier"
begin
interpretation ℰ: indep_system ℰ "indep_in ℰ"
using ‹ℰ ⊆ carrier› by auto
lemma circuit_inI_aux: "ℰ.circuit X ⟹ circuit_in ℰ X"
unfolding circuit_in_def by auto
lemma circuit_inD_aux: "circuit_in ℰ X ⟹ ℰ.circuit X"
unfolding circuit_in_def by auto
lemma not_circuit_inD_aux: "¬ circuit_in ℰ X ⟹ ¬ ℰ.circuit X"
using circuit_inI_aux by auto
lemmas circuit_inI = circuit_inI_aux[OF ℰ.circuitI]
lemmas circuit_in_subset_carrier = ℰ.circuit_subset_carrier[OF circuit_inD_aux]
lemmas circuit_in_finite = ℰ.circuit_finite[OF circuit_inD_aux]
lemmas circuit_in_dep_in = ℰ.circuit_dep[OF circuit_inD_aux]
lemmas circuit_in_min_dep_in = ℰ.circuit_min_dep[OF circuit_inD_aux]
lemmas circuit_inD = ℰ.circuitD[OF circuit_inD_aux]
lemmas circuit_in_nonempty = ℰ.circuit_nonempty[OF circuit_inD_aux]
lemmas dep_in_not_circuit_in = ℰ.dep_not_circuit[OF _ _ not_circuit_inD_aux]
lemmas circuit_in_subset_eq = ℰ.circuit_subset_eq[OF circuit_inD_aux circuit_inD_aux]
end
lemma circuit_in_subI:
assumes "ℰ' ⊆ ℰ" "ℰ ⊆ carrier"
assumes "circuit_in ℰ' C"
shows "circuit_in ℰ C"
proof (rule circuit_inI)
show "ℰ ⊆ carrier" using assms by auto
next
show "C ⊆ ℰ" using assms circuit_in_subset_carrier[of ℰ' C] by auto
next
show "¬ indep_in ℰ C"
using assms
circuit_in_dep_in[where ℰ = ℰ' and X = C]
circuit_in_subset_carrier dep_in_subI[where ℰ' = ℰ' and ℰ = ℰ]
by auto
next
fix x
assume "x ∈ C"
then show "indep_in ℰ (C - {x})"
using assms circuit_in_min_dep_in indep_in_subI_subset by auto
qed
lemma circuit_in_supI:
assumes "ℰ' ⊆ ℰ" "ℰ ⊆ carrier" "C ⊆ ℰ'"
assumes "circuit_in ℰ C"
shows "circuit_in ℰ' C"
proof (rule circuit_inI)
show "ℰ' ⊆ carrier" using assms by auto
next
show "C ⊆ ℰ'" using assms by auto
next
have "¬ indep_in ℰ C" using assms circuit_in_dep_in by auto
then show "¬ indep_in ℰ' C" using assms dep_in_subI[of C ℰ] by auto
next
fix x
assume "x ∈ C"
then have "indep_in ℰ (C - {x})" using assms circuit_in_min_dep_in by auto
then have "indep_in ℰ' ((C - {x}) ∩ ℰ')" using indep_in_subI by auto
moreover have "(C - {x}) ∩ ℰ' = C - {x}" using assms circuit_in_subset_carrier by auto
ultimately show "indep_in ℰ' (C - {x})" by auto
qed
context
fixes ℰ
assumes *: "ℰ ⊆ carrier"
begin
interpretation ℰ: indep_system ℰ "indep_in ℰ"
using * by auto
lemma circuit_in_sub_cong:
assumes "ℰ' ⊆ ℰ"
shows "ℰ.circuit_in ℰ' C ⟷ circuit_in ℰ' C"
proof (safe, goal_cases LTR RTL)
case LTR
show ?case
proof (rule circuit_inI)
show "ℰ' ⊆ carrier" using assms * by auto
next
show "C ⊆ ℰ'"
using assms LTR ℰ.circuit_in_subset_carrier by auto
next
show "¬ indep_in ℰ' C"
using assms LTR ℰ.circuit_in_dep_in indep_in_sub_cong[OF *] by auto
next
fix x
assume "x ∈ C"
then show "indep_in ℰ' (C - {x})"
using assms LTR ℰ.circuit_in_min_dep_in indep_in_sub_cong[OF *] by auto
qed
next
case RTL
show ?case
proof (rule ℰ.circuit_inI)
show "ℰ' ⊆ ℰ" using assms * by auto
next
show "C ⊆ ℰ'"
using assms * RTL circuit_in_subset_carrier by auto
next
show "¬ ℰ.indep_in ℰ' C"
using assms * RTL circuit_in_dep_in indep_in_sub_cong[OF *] by auto
next
fix x
assume "x ∈ C"
then show "ℰ.indep_in ℰ' (C - {x})"
using assms * RTL circuit_in_min_dep_in indep_in_sub_cong[OF *] by auto
qed
qed
end
lemma circuit_imp_circuit_in:
assumes "circuit C"
shows "circuit_in carrier C"
proof (rule circuit_inI)
show "C ⊆ carrier" using circuit_subset_carrier[OF assms] .
next
show "¬ indep_in carrier C" using circuit_dep[OF assms] indep_in_indep by auto
next
fix x
assume "x ∈ C"
then have "indep (C - {x})" using circuit_min_dep[OF assms] by auto
then show "indep_in carrier (C - {x})" using circuit_subset_carrier[OF assms] by (auto intro: indep_inI)
qed auto
subsection ‹Relation between independence and bases›
text ‹
A set is independent iff it is a subset of a basis.
›
lemma indep_imp_subset_basis:
assumes "indep X"
shows "∃B. basis B ∧ X ⊆ B"
using assms
proof (induction X rule: psubset_inc_induct)
case carrier
show ?case using indep_subset_carrier[OF assms] .
next
case (step X)
{
assume "¬ basis X"
then obtain x where "x ∈ carrier" "x ∉ X" "indep (insert x X)"
using step.prems indep_not_basis by auto
then have ?case using step.IH[of "insert x X"] indep_subset_carrier by auto
}
then show ?case by auto
qed
lemmas subset_basis_imp_indep = indep_subset[OF basis_indep]
lemma indep_iff_subset_basis: "indep X ⟷ (∃B. basis B ∧ X ⊆ B)"
using indep_imp_subset_basis subset_basis_imp_indep by auto
lemma basis_ex: "∃B. basis B"
using indep_imp_subset_basis[OF indep_empty] by auto
context
fixes ℰ
assumes *: "ℰ ⊆ carrier"
begin
interpretation ℰ: indep_system ℰ "indep_in ℰ"
using * by auto
lemma indep_in_imp_subset_basis_in:
assumes "indep_in ℰ X"
shows "∃B. basis_in ℰ B ∧ X ⊆ B"
unfolding basis_in_def using ℰ.indep_imp_subset_basis[OF assms] .
lemmas subset_basis_in_imp_indep_in = indep_in_subset[OF * basis_in_indep_in[OF *]]
lemma indep_in_iff_subset_basis_in: "indep_in ℰ X ⟷ (∃B. basis_in ℰ B ∧ X ⊆ B)"
using indep_in_imp_subset_basis_in subset_basis_in_imp_indep_in by auto
lemma basis_in_ex: "∃B. basis_in ℰ B"
unfolding basis_in_def using ℰ.basis_ex .
lemma basis_in_subI:
assumes "ℰ' ⊆ ℰ" "ℰ ⊆ carrier"
assumes "basis_in ℰ' B"
shows "∃B' ⊆ ℰ - ℰ'. basis_in ℰ (B ∪ B')"
proof -
have "indep_in ℰ B" using assms basis_in_indep_in indep_in_subI_subset by auto
then obtain B' where B': "basis_in ℰ B'" "B ⊆ B'"
using assms indep_in_imp_subset_basis_in[of B] by auto
show ?thesis
proof (rule exI)
have "B' - B ⊆ ℰ - ℰ'"
proof
fix x
assume *: "x ∈ B' - B"
then have "x ∈ ℰ" "x ∉ B"
using assms ‹basis_in ℰ B'› basis_in_subset_carrier[of ℰ] by auto
moreover {
assume "x ∈ ℰ'"
moreover have "indep_in ℰ (insert x B)"
using * assms indep_in_subset[OF _ basis_in_indep_in] B' by auto
ultimately have "indep_in ℰ' (insert x B)"
using assms basis_in_subset_carrier unfolding indep_in_def by auto
then have False using assms * ‹x ∈ ℰ'› basis_in_max_indep_in by auto
}
ultimately show "x ∈ ℰ - ℰ'" by auto
qed
moreover have "B ∪ (B' - B) = B'" using ‹B ⊆ B'› by auto
ultimately show "B' - B ⊆ ℰ - ℰ' ∧ basis_in ℰ (B ∪ (B' - B))"
using ‹basis_in ℰ B'› by auto
qed
qed
lemma basis_in_supI:
assumes "B ⊆ ℰ'" "ℰ' ⊆ ℰ" "ℰ ⊆ carrier"
assumes "basis_in ℰ B"
shows "basis_in ℰ' B"
proof (rule basis_inI)
show "ℰ' ⊆ carrier" using assms by auto
next
show "indep_in ℰ' B"
proof -
have "indep_in ℰ' (B ∩ ℰ')"
using assms basis_in_indep_in[of ℰ B] indep_in_subI by auto
moreover have "B ∩ ℰ' = B" using assms by auto
ultimately show ?thesis by auto
qed
next
show "⋀x. x ∈ ℰ' - B ⟹ ¬ indep_in ℰ' (insert x B)"
using assms basis_in_subset_carrier basis_in_max_indep_in dep_in_subI[of _ ℰ ℰ'] by auto
qed
end
subsection ‹Relation between dependence and circuits›
text ‹
A set is dependent iff it contains a circuit.
›
lemma dep_imp_supset_circuit:
assumes "X ⊆ carrier"
assumes "¬ indep X"
shows "∃C. circuit C ∧ C ⊆ X"
using assms
proof (induction X rule: remove_induct)
case (remove X)
{
assume "¬ circuit X"
then obtain x where "x ∈ X" "¬ indep (X - {x})"
using remove.prems dep_not_circuit by auto
then obtain C where "circuit C" "C ⊆ X - {x}"
using remove.prems remove.IH[of x] by auto
then have ?case by auto
}
then show ?case using remove.prems by auto
qed (auto simp add: carrier_finite finite_subset)
lemma supset_circuit_imp_dep:
assumes "circuit C ∧ C ⊆ X"
shows "¬ indep X"
using assms indep_subset circuit_dep by auto
lemma dep_iff_supset_circuit:
assumes "X ⊆ carrier"
shows "¬ indep X ⟷ (∃C. circuit C ∧ C ⊆ X)"
using assms dep_imp_supset_circuit supset_circuit_imp_dep by auto
context
fixes ℰ
assumes "ℰ ⊆ carrier"
begin
interpretation ℰ: indep_system ℰ "indep_in ℰ"
using ‹ℰ ⊆ carrier› by auto
lemma dep_in_imp_supset_circuit_in:
assumes "X ⊆ ℰ"
assumes "¬ indep_in ℰ X"
shows "∃C. circuit_in ℰ C ∧ C ⊆ X"
unfolding circuit_in_def using ℰ.dep_imp_supset_circuit[OF assms] .
lemma supset_circuit_in_imp_dep_in:
assumes "circuit_in ℰ C ∧ C ⊆ X"
shows "¬ indep_in ℰ X"
using assms ℰ.supset_circuit_imp_dep unfolding circuit_in_def by auto
lemma dep_in_iff_supset_circuit_in:
assumes "X ⊆ ℰ"
shows "¬ indep_in ℰ X ⟷ (∃C. circuit_in ℰ C ∧ C ⊆ X)"
using assms dep_in_imp_supset_circuit_in supset_circuit_in_imp_dep_in by auto
end
subsection ‹Ranks›
definition lower_rank_of :: "'a set ⇒ nat" where
"lower_rank_of carrier' ≡ Min {card B | B. basis_in carrier' B}"
definition upper_rank_of :: "'a set ⇒ nat" where
"upper_rank_of carrier' ≡ Max {card B | B. basis_in carrier' B}"
lemma collect_basis_finite: "finite (Collect basis)"
proof -
have "Collect basis ⊆ {X. X ⊆ carrier}"
using basis_subset_carrier by auto
moreover have "finite …"
using carrier_finite by auto
ultimately show ?thesis using finite_subset by auto
qed
context
fixes ℰ
assumes *: "ℰ ⊆ carrier"
begin
interpretation ℰ: indep_system ℰ "indep_in ℰ"
using * by auto
lemma collect_basis_in_finite: "finite (Collect (basis_in ℰ))"
unfolding basis_in_def using ℰ.collect_basis_finite .
lemma lower_rank_of_le: "lower_rank_of ℰ ≤ card ℰ"
proof -
have "∃n ∈ {card B | B. basis_in ℰ B}. n ≤ card ℰ"
using card_mono[OF ℰ.carrier_finite basis_in_subset_carrier[OF *]] basis_in_ex[OF *] by auto
moreover have "finite {card B | B. basis_in ℰ B}"
using collect_basis_in_finite by auto
ultimately show ?thesis
unfolding lower_rank_of_def using basis_ex Min_le_iff by auto
qed
lemma upper_rank_of_le: "upper_rank_of ℰ ≤ card ℰ"
proof -
have "∀n ∈ {card B | B. basis_in ℰ B}. n ≤ card ℰ"
using card_mono[OF ℰ.carrier_finite basis_in_subset_carrier[OF *]] by auto
then show ?thesis
unfolding upper_rank_of_def using basis_in_ex[OF *] collect_basis_in_finite by auto
qed
context
fixes ℰ'
assumes **: "ℰ' ⊆ ℰ"
begin
interpretation ℰ'⇩1: indep_system ℰ' "indep_in ℰ'"
using * ** by auto
interpretation ℰ'⇩2: indep_system ℰ' "ℰ.indep_in ℰ'"
using * ** by auto
lemma lower_rank_of_sub_cong:
shows "ℰ.lower_rank_of ℰ' = lower_rank_of ℰ'"
proof -
have "⋀B. ℰ'⇩1.basis B ⟷ ℰ'⇩2.basis B"
using ** basis_in_sub_cong[OF *, of ℰ']
unfolding basis_in_def ℰ.basis_in_def by auto
then show ?thesis
unfolding lower_rank_of_def ℰ.lower_rank_of_def
using basis_in_sub_cong[OF * **]
by auto
qed
lemma upper_rank_of_sub_cong:
shows "ℰ.upper_rank_of ℰ' = upper_rank_of ℰ'"
proof -
have "⋀B. ℰ'⇩1.basis B ⟷ ℰ'⇩2.basis B"
using ** basis_in_sub_cong[OF *, of ℰ']
unfolding basis_in_def ℰ.basis_in_def by auto
then show ?thesis
unfolding upper_rank_of_def ℰ.upper_rank_of_def
using basis_in_sub_cong[OF * **]
by auto
qed
end
end
end
end