finite_family_one_point_factor_two_gluing
For two disjoint finite set families whose cross intersections lie in one point, factor-two packing-cover certificates for both families and their point-deleted families give such a certificate for their union.
Statement
theorem finite_family_one_point_factor_two_gluing {α : Type*} [DecidableEq α] (F₁ F₂ : Finset (Finset α)) (p : α) (hF : Disjoint F₁ F₂) (hcross : ∀ A ∈ F₁, ∀ B ∈ F₂, A ∩ B ⊆ {p}) (h₁ : ∃ P C, finite_family_packing_is_disjoint F₁ P ∧ finite_family_point_cover F₁ C ∧ C.card ≤ 2 * P.card) (h₂ : ∃ P C, finite_family_packing_is_disjoint F₂ P ∧ finite_family_point_cover F₂ C ∧ C.card ≤ 2 * P.card) (h₁del : ∃ P C, finite_family_packing_is_disjoint (F₁.filter (fun A => p ∉ A)) P ∧ finite_family_point_cover (F₁.filter (fun A => p ∉ A)) C ∧ C.card ≤ 2 * P.card) (h₂del : ∃ P C, finite_family_packing_is_disjoint (F₂.filter (fun A => p ∉ A)) P ∧ finite_family_point_cover (F₂.filter (fun A => p ∉ A)) C ∧ C.card ≤ 2 * P.card) : ∃ P C, finite_family_packing_is_disjoint (F₁ ∪ F₂) P ∧ finite_family_point_cover (F₁ ∪ F₂) C ∧ C.card ≤ 2 * P.card
- Source
- Published one-point separator reduction, https://www.cs.tau.ac.il/~krivelev/2.pdf, Lemma 5; finite-family formulation used in the triangle packing campaign.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- finite_family_packing_is_disjointA subfamily is a packing when its distinct members are disjoint.
- finite_family_point_coverA set of points meets every member of a finite family.
The proof, explained
To construct a factor-two packing-cover certificate for F₁ ∪ F₂, we case split on the relative sizes of the packings for each family versus their subfamilies avoiding the intersection point p. If either family's full packing is no larger than its p-avoiding packing (|P₁| ≤ |Q₁| or |P₂| ≤ |Q₂|), we combine the p-avoiding packing with the other family's full packing; the union of the two covers remains a factor-two certificate. When both full packings are strictly larger than their p-avoiding counterparts (|P₁| > |Q₁| and |P₂| > |Q₂|), we filter P₂ to its p-avoiding elements R, losing at most one element, and take cover {p} ∪ D₁ ∪ D₂. The resulting packing P₁ ∪ R and cover satisfy the factor-two bound by linear arithmetic, as the +1 from {p} is absorbed by the strict size gap |P₁| ≥ |Q₁| + 1.
In a pairwise disjoint family P, at most one set contains a given point p, so the number of sets in P avoiding p is at least |P| - 1. automation
Since the sets in P are pairwise disjoint, no two distinct sets in P can both contain p; thus the subfamily of sets containing p has cardinality at most 1. The total size |P| is the sum of the sizes of sets containing p and sets avoiding p, so |P| ≤ |{A ∈ P | p ∉ A}| + 1.
uses
Finset.card_le_one.mpr,Finset.mem_filter.mp,Finset.disjoint_left.mp,Finset.card_filter_add_card_filter_notclassical have hsmall : (P.filter (fun A => p ∈ A)).card ≤ 1 := by apply Finset.card_le_one.mpr intro A hA B hB have hA' := Finset.mem_filter.mp hA have hB' := Finset.mem_filter.mp hB by_contra hne exact Finset.disjoint_left.mp (hP hA'.1 hB'.1 hne) hA'.2 hB'.2 have hparts := Finset.card_filter_add_card_filter_not (s := P) (fun A => p ∈ A) omega
If cross-intersections between F₁ and F₂ are contained in {p}, then any A ∈ F₁ and B ∈ F₂ such that p ∉ A or p ∉ B are disjoint.
Any shared element x ∈ A ∩ B must belong to {p} by the intersection condition, forcing x = p. Since by hypothesis p ∉ A or p ∉ B, p cannot belong to both sets, a contradiction showing A ∩ B = ∅.
uses
Finset.disjoint_left.mpr,Finset.mem_inter.mpr,Finset.mem_singleton.mpapply Finset.disjoint_left.mpr intro x hxA hxB have hx := hcross A hA B hB (Finset.mem_inter.mpr ⟨hxA,hxB⟩) have hxp : x = p := Finset.mem_singleton.mp hx subst x exact havoid.elim (fun h => h hxA) (fun h => h hxB)
For packings P₁ ⊆ F₁ and P₂ ⊆ F₂, if either all sets in P₁ avoid p or all sets in P₂ avoid p, then P₁ ∪ P₂ is a packing in F₁ ∪ F₂ and |P₁ ∪ P₂| = |P₁| + |P₂|.
Since F₁ and F₂ are disjoint, P₁ and P₂ are disjoint finsets, making |P₁ ∪ P₂| = |P₁| + |P₂|. Pairwise disjointness holds within P₁ and P₂ by assumption, while any cross-pair A ∈ P₁, B ∈ P₂ is disjoint by in519_cross_disjoint because at least one of the two sets avoids p.
uses
Disjoint.mono,Finset.union_subset_union,Finset.card_union_of_disjoint,Finset.coe_union,Set.pairwise_union_of_symm,in519_cross_disjoint,Or.inl,Or.inrhave hdisj : Disjoint P₁ P₂ := Disjoint.mono hsub₁ hsub₂ hF refine ⟨Finset.union_subset_union hsub₁ hsub₂, ?_, Finset.card_union_of_disjoint hdisj⟩ rw [Finset.coe_union, Set.pairwise_union_of_symm] refine ⟨hpack₁, hpack₂, ?_⟩ intro A hA B hB _ apply in519_cross_disjoint F₁ F₂ p hcross (hsub₁ hA) (hsub₂ hB) exact havoid.elim (fun h => Or.inl (h A hA)) (fun h => Or.inr (h B hB))
The union of point covers C₁ for F₁ and C₂ for F₂ covers the union F₁ ∪ F₂.
Every set A ∈ F₁ ∪ F₂ belongs to F₁ or F₂. If A ∈ F₁, it intersects C₁, hence intersects C₁ ∪ C₂; similarly, if A ∈ F₂, it intersects C₂ ⊆ C₁ ∪ C₂.
uses
Finset.mem_union.mp,Finset.not_disjoint_iff.mp,Finset.not_disjoint_iff.mpr,Finset.mem_union_left,Finset.mem_union_rightintro A hA rcases Finset.mem_union.mp hA with hA | hA · obtain ⟨x, hxA, hxC⟩ := Finset.not_disjoint_iff.mp (h₁ A hA) exact Finset.not_disjoint_iff.mpr ⟨x, hxA, Finset.mem_union_left _ hxC⟩ · obtain ⟨x, hxA, hxC⟩ := Finset.not_disjoint_iff.mp (h₂ A hA) exact Finset.not_disjoint_iff.mpr ⟨x, hxA, Finset.mem_union_right _ hxC⟩
If D₁ and D₂ cover the subfamilies of F₁ and F₂ avoiding p, then {p} ∪ D₁ ∪ D₂ covers F₁ ∪ F₂.
Given A ∈ F₁ ∪ F₂, if p ∈ A, then A intersects {p} ⊆ {p} ∪ D₁ ∪ D₂. If p ∉ A, then A belongs to the p-avoiding subfamily of either F₁ or F₂, so by in519_cover_union, A intersects D₁ ∪ D₂ ⊆ {p} ∪ D₁ ∪ D₂.
uses
Finset.not_disjoint_iff.mpr,Finset.mem_insert_self,in519_cover_union,Finset.mem_union.mp,Finset.mem_union_left,Finset.mem_filter.mpr,Finset.mem_union_right,Finset.not_disjoint_iff.mp,Finset.mem_insert_of_memintro A hA by_cases hp : p ∈ A · exact Finset.not_disjoint_iff.mpr ⟨p, hp, Finset.mem_insert_self _ _⟩ · have hd : ¬ Disjoint A (D₁ ∪ D₂) := by apply in519_cover_union _ _ _ _ h₁ h₂ A rcases Finset.mem_union.mp hA with hA | hA · exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hA,hp⟩) · exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨hA,hp⟩) obtain ⟨x, hxA, hxD⟩ := Finset.not_disjoint_iff.mp hd exact Finset.not_disjoint_iff.mpr ⟨x,hxA,Finset.mem_insert_of_mem hxD⟩
Extract factor-two certificates (P₁, C₁), (P₂, C₂), (Q₁, D₁), and (Q₂, D₂), and establish that Q₁ ⊆ F₁ and Q₂ ⊆ F₂ with all their sets avoiding p.
We unpack the existential hypotheses to obtain packings and covers satisfying |C₁| ≤ 2|P₁|, |C₂| ≤ 2|P₂|, |D₁| ≤ 2|Q₁|, and |D₂| ≤ 2|Q₂|. Because Q₁ and Q₂ are packings in the filtered subfamilies, they are subsets of F₁ and F₂ respectively, and every set in Q₁ and Q₂ avoids p.
uses
Finset.filter_subset,Finset.mem_filter.mpclassical obtain ⟨P₁,C₁,⟨hP₁,hpack₁⟩,hc₁,hbound₁⟩ := h₁ obtain ⟨P₂,C₂,⟨hP₂,hpack₂⟩,hc₂,hbound₂⟩ := h₂ obtain ⟨Q₁,D₁,⟨hQ₁,hqpack₁⟩,hd₁,hdbound₁⟩ := h₁del obtain ⟨Q₂,D₂,⟨hQ₂,hqpack₂⟩,hd₂,hdbound₂⟩ := h₂del have hQ₁sub : Q₁ ⊆ F₁ := (hQ₁.trans (Finset.filter_subset _ _)) have hQ₂sub : Q₂ ⊆ F₂ := (hQ₂.trans (Finset.filter_subset _ _)) have hQ₁avoid : ∀ A ∈ Q₁, p ∉ A := by intro A hA exact (Finset.mem_filter.mp (hQ₁ hA)).2 have hQ₂avoid : ∀ A ∈ Q₂, p ∉ A := by intro A hA exact (Finset.mem_filter.mp (hQ₂ hA)).2
If |P₁| ≤ |Q₁|, the packing Q₁ ∪ P₂ and cover C₁ ∪ C₂ form a factor-two certificate for F₁ ∪ F₂. automation
Since every set in Q₁ avoids p, in519_union_packing shows that Q₁ ∪ P₂ is a valid packing in F₁ ∪ F₂ with size |Q₁| + |P₂|. The set C₁ ∪ C₂ covers F₁ ∪ F₂ by in519_cover_union. Its size satisfies |C₁ ∪ C₂| ≤ |C₁| + |C₂| ≤ 2|P₁| + 2|P₂| ≤ 2|Q₁| + 2|P₂| = 2|Q₁ ∪ P₂|, which is verified by linear arithmetic.
uses
in519_union_packing,Or.inl,in519_cover_union,Finset.card_union_leby_cases hlarge₁ : P₁.card ≤ Q₁.card · have hp := in519_union_packing F₁ F₂ Q₁ P₂ p hF hcross hQ₁sub hP₂ hqpack₁ hpack₂ (Or.inl hQ₁avoid) refine ⟨Q₁ ∪ P₂, C₁ ∪ C₂, ⟨hp.1,hp.2.1⟩, in519_cover_union _ _ _ _ hc₁ hc₂, ?_⟩ have hc := Finset.card_union_le C₁ C₂ rw [hp.2.2] omega
If |P₂| ≤ |Q₂|, the packing P₁ ∪ Q₂ and cover C₁ ∪ C₂ form a factor-two certificate for F₁ ∪ F₂. automation
Symmetrically, since every set in Q₂ avoids p, in519_union_packing shows that P₁ ∪ Q₂ is a valid packing of size |P₁| + |Q₂|. The cover C₁ ∪ C₂ covers F₁ ∪ F₂, and |C₁ ∪ C₂| ≤ |C₁| + |C₂| ≤ 2|P₁| + 2|P₂| ≤ 2|P₁| + 2|Q₂| = 2|P₁ ∪ Q₂| by linear arithmetic.
uses
in519_union_packing,Or.inr,in519_cover_union,Finset.card_union_leby_cases hlarge₂ : P₂.card ≤ Q₂.card · have hp := in519_union_packing F₁ F₂ P₁ Q₂ p hF hcross hP₁ hQ₂sub hpack₁ hqpack₂ (Or.inr hQ₂avoid) refine ⟨P₁ ∪ Q₂, C₁ ∪ C₂, ⟨hp.1,hp.2.1⟩, in519_cover_union _ _ _ _ hc₁ hc₂, ?_⟩ have hc := Finset.card_union_le C₁ C₂ rw [hp.2.2] omega
When |P₁| > |Q₁| and |P₂| > |Q₂|, the packing P₁ ∪ R (where R = {A ∈ P₂ | p ∉ A}) and cover {p} ∪ D₁ ∪ D₂ form a factor-two certificate for F₁ ∪ F₂. automation
We define R as the subfamily of sets in P₂ avoiding p; it is a pairwise disjoint subset of F₂, and by in519_drop_point_packing, |P₂| ≤ |R| + 1. Since R avoids p, P₁ ∪ R is a packing in F₁ ∪ F₂ of cardinality |P₁| + |R|. By in519_cover_insert_from_deleted, {p} ∪ D₁ ∪ D₂ covers F₁ ∪ F₂. Its size is at most 1 + |D₁| + |D₂| ≤ 1 + 2|Q₁| + 2|Q₂|. Since |Q₁| ≤ |P₁| - 1 and |Q₂| ≤ |P₂| - 1 ≤ |R|, we have 1 + 2|Q₁| + 2|Q₂| ≤ 1 + 2(|P₁| - 1) + 2|R| = 2(|P₁| + |R|) - 1 ≤ 2|P₁ ∪ R|, which closes by linear arithmetic.
uses
Finset.filter_subset,Finset.mem_filter.mp,in519_drop_point_packing,in519_union_packing,Or.inr,in519_cover_insert_from_deleted,Finset.card_union_le,Finset.card_insert_lelet R := P₂.filter (fun A => p ∉ A) have hRsub : R ⊆ F₂ := (Finset.filter_subset _ _).trans hP₂ have hRpack : (R : Set (Finset α)).Pairwise Disjoint := by apply hpack₂.mono intro A hA exact (Finset.mem_filter.mp hA).1 have hRavoid : ∀ A ∈ R, p ∉ A := by intro A hA exact (Finset.mem_filter.mp hA).2 have hRcard : P₂.card ≤ R.card + 1 := in519_drop_point_packing P₂ p hpack₂ have hp := in519_union_packing F₁ F₂ P₁ R p hF hcross hP₁ hRsub hpack₁ hRpack (Or.inr hRavoid) refine ⟨P₁ ∪ R, insert p (D₁ ∪ D₂), ⟨hp.1,hp.2.1⟩, in519_cover_insert_from_deleted _ _ _ _ _ hd₁ hd₂, ?_⟩ have hc := Finset.card_union_le D₁ D₂ have hi := Finset.card_insert_le p (D₁ ∪ D₂) rw [hp.2.2] omega
Finset.card_le_one.mpr- A finite set has cardinality at most 1 if any two of its elements are equal.
Finset.mem_filter.mp- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.disjoint_left.mp- If two finite sets are disjoint, any element of the first does not belong to the second.
Finset.card_filter_add_card_filter_not- The cardinality of a finite set is the sum of the cardinalities of the elements satisfying a predicate and those that do not.
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first belongs to the second.
Finset.mem_inter.mpr- An element belongs to the intersection of two finite sets if it belongs to both sets.
Finset.mem_singleton.mp- If an element belongs to a singleton set {p}, it is equal to p.
Disjoint.mono- Disjointness is monotonic with respect to subset inclusion: if a ⊆ b, c ⊆ d, and b is disjoint from d, then a is disjoint from c.
Finset.union_subset_union- If s ⊆ u and t ⊆ v, then s ∪ t ⊆ u ∪ v.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.coe_union- The set coercion of the union of two finsets is the union of their coercions.
Set.pairwise_union_of_symm- The union of two sets is pairwise disjoint if each set is pairwise disjoint and every element of the first is disjoint from every distinct element of the second.
in519_cross_disjoint- If cross-intersections between F₁ and F₂ are contained in {p}, then any A ∈ F₁ and B ∈ F₂ with p ∉ A or p ∉ B are disjoint.
Or.inl- From a proof of P, infer the disjunction P ∨ Q.
Or.inr- From a proof of Q, infer the disjunction P ∨ Q.
Finset.mem_union.mp- If an element belongs to the union of two sets, it belongs to the first or the second.
Finset.not_disjoint_iff.mp- If two finite sets are not disjoint, there exists an element common to both.
Finset.not_disjoint_iff.mpr- If two finite sets share an element, they are not disjoint.
Finset.mem_union_left- If an element belongs to s, it belongs to s ∪ t.
Finset.mem_union_right- If an element belongs to t, it belongs to s ∪ t.
Finset.mem_insert_self- An element a belongs to insert(a, s).
in519_cover_union- The union of point covers for two families covers the union of the two families.
Finset.mem_filter.mpr- If an element belongs to a finset and satisfies a predicate, it belongs to the filtered finset.
Finset.mem_insert_of_mem- If an element belongs to s, it belongs to insert(b, s) for any b.
Finset.filter_subset- Filtering a finite set by a predicate yields a subset of the original set.
in519_union_packing- The union of packings from two disjoint families with cross-intersections in {p} is a packing of their union, with size equal to the sum of their sizes, provided at least one packing avoids p.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities.
in519_drop_point_packing- For any pairwise disjoint packing, the number of sets avoiding a given point p is at least the size of the packing minus 1.
in519_cover_insert_from_deleted- If D₁ and D₂ cover the p-avoiding subfamilies of F₁ and F₂, then {p} ∪ D₁ ∪ D₂ covers F₁ ∪ F₂.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
- The arithmetic inequalities in the three case splits are solved automatically by `omega`, notably in the final case where the strict bounds |Q₁| < |P₁| and |Q₂| < |P₂| absorb the +1 from the inserted point p.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
private theorem in519_drop_point_packing {α : Type*} [DecidableEq α] (P : Finset (Finset α)) (p : α) (hP : (P : Set (Finset α)).Pairwise Disjoint) : P.card ≤ (P.filter (fun A => p ∉ A)).card + 1 := by classical have hsmall : (P.filter (fun A => p ∈ A)).card ≤ 1 := by apply Finset.card_le_one.mpr intro A hA B hB have hA' := Finset.mem_filter.mp hA have hB' := Finset.mem_filter.mp hB by_contra hne exact Finset.disjoint_left.mp (hP hA'.1 hB'.1 hne) hA'.2 hB'.2 have hparts := Finset.card_filter_add_card_filter_not (s := P) (fun A => p ∈ A) omegaprivate theorem in519_cross_disjoint {α : Type*} [DecidableEq α] (F₁ F₂ : Finset (Finset α)) (p : α) (hcross : ∀ A ∈ F₁, ∀ B ∈ F₂, A ∩ B ⊆ {p}) {A B : Finset α} (hA : A ∈ F₁) (hB : B ∈ F₂) (havoid : p ∉ A ∨ p ∉ B) : Disjoint A B := by apply Finset.disjoint_left.mpr intro x hxA hxB have hx := hcross A hA B hB (Finset.mem_inter.mpr ⟨hxA,hxB⟩) have hxp : x = p := Finset.mem_singleton.mp hx subst x exact havoid.elim (fun h => h hxA) (fun h => h hxB)private theorem in519_union_packing {α : Type*} [DecidableEq α] (F₁ F₂ P₁ P₂ : Finset (Finset α)) (p : α) (hF : Disjoint F₁ F₂) (hcross : ∀ A ∈ F₁, ∀ B ∈ F₂, A ∩ B ⊆ {p}) (hsub₁ : P₁ ⊆ F₁) (hsub₂ : P₂ ⊆ F₂) (hpack₁ : (P₁ : Set (Finset α)).Pairwise Disjoint) (hpack₂ : (P₂ : Set (Finset α)).Pairwise Disjoint) (havoid : (∀ A ∈ P₁, p ∉ A) ∨ ∀ B ∈ P₂, p ∉ B) : (P₁ ∪ P₂ ⊆ F₁ ∪ F₂) ∧ ((P₁ ∪ P₂ : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint ∧ (P₁ ∪ P₂).card = P₁.card + P₂.card := by have hdisj : Disjoint P₁ P₂ := Disjoint.mono hsub₁ hsub₂ hF refine ⟨Finset.union_subset_union hsub₁ hsub₂, ?_, Finset.card_union_of_disjoint hdisj⟩ rw [Finset.coe_union, Set.pairwise_union_of_symm] refine ⟨hpack₁, hpack₂, ?_⟩ intro A hA B hB _ apply in519_cross_disjoint F₁ F₂ p hcross (hsub₁ hA) (hsub₂ hB) exact havoid.elim (fun h => Or.inl (h A hA)) (fun h => Or.inr (h B hB))private theorem in519_cover_union {α : Type*} [DecidableEq α] (F₁ F₂ : Finset (Finset α)) (C₁ C₂ : Finset α) (h₁ : finite_family_point_cover F₁ C₁) (h₂ : finite_family_point_cover F₂ C₂) : finite_family_point_cover (F₁ ∪ F₂) (C₁ ∪ C₂) := by intro A hA rcases Finset.mem_union.mp hA with hA | hA · obtain ⟨x, hxA, hxC⟩ := Finset.not_disjoint_iff.mp (h₁ A hA) exact Finset.not_disjoint_iff.mpr ⟨x, hxA, Finset.mem_union_left _ hxC⟩ · obtain ⟨x, hxA, hxC⟩ := Finset.not_disjoint_iff.mp (h₂ A hA) exact Finset.not_disjoint_iff.mpr ⟨x, hxA, Finset.mem_union_right _ hxC⟩private theorem in519_cover_insert_from_deleted {α : Type*} [DecidableEq α] (F₁ F₂ : Finset (Finset α)) (p : α) (D₁ D₂ : Finset α) (h₁ : finite_family_point_cover (F₁.filter (fun A => p ∉ A)) D₁) (h₂ : finite_family_point_cover (F₂.filter (fun A => p ∉ A)) D₂) : finite_family_point_cover (F₁ ∪ F₂) (insert p (D₁ ∪ D₂)) := by intro A hA by_cases hp : p ∈ A · exact Finset.not_disjoint_iff.mpr ⟨p, hp, Finset.mem_insert_self _ _⟩ · have hd : ¬ Disjoint A (D₁ ∪ D₂) := by apply in519_cover_union _ _ _ _ h₁ h₂ A rcases Finset.mem_union.mp hA with hA | hA · exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hA,hp⟩) · exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨hA,hp⟩) obtain ⟨x, hxA, hxD⟩ := Finset.not_disjoint_iff.mp hd exact Finset.not_disjoint_iff.mpr ⟨x,hxA,Finset.mem_insert_of_mem hxD⟩theorem finite_family_one_point_factor_two_gluing {α : Type*} [DecidableEq α] (F₁ F₂ : Finset (Finset α)) (p : α) (hF : Disjoint F₁ F₂) (hcross : ∀ A ∈ F₁, ∀ B ∈ F₂, A ∩ B ⊆ {p}) (h₁ : ∃ P C, finite_family_packing_is_disjoint F₁ P ∧ finite_family_point_cover F₁ C ∧ C.card ≤ 2 * P.card) (h₂ : ∃ P C, finite_family_packing_is_disjoint F₂ P ∧ finite_family_point_cover F₂ C ∧ C.card ≤ 2 * P.card) (h₁del : ∃ P C, finite_family_packing_is_disjoint (F₁.filter (fun A => p ∉ A)) P ∧ finite_family_point_cover (F₁.filter (fun A => p ∉ A)) C ∧ C.card ≤ 2 * P.card) (h₂del : ∃ P C, finite_family_packing_is_disjoint (F₂.filter (fun A => p ∉ A)) P ∧ finite_family_point_cover (F₂.filter (fun A => p ∉ A)) C ∧ C.card ≤ 2 * P.card) : ∃ P C, finite_family_packing_is_disjoint (F₁ ∪ F₂) P ∧ finite_family_point_cover (F₁ ∪ F₂) C ∧ C.card ≤ 2 * P.card := by classical obtain ⟨P₁,C₁,⟨hP₁,hpack₁⟩,hc₁,hbound₁⟩ := h₁ obtain ⟨P₂,C₂,⟨hP₂,hpack₂⟩,hc₂,hbound₂⟩ := h₂ obtain ⟨Q₁,D₁,⟨hQ₁,hqpack₁⟩,hd₁,hdbound₁⟩ := h₁del obtain ⟨Q₂,D₂,⟨hQ₂,hqpack₂⟩,hd₂,hdbound₂⟩ := h₂del have hQ₁sub : Q₁ ⊆ F₁ := (hQ₁.trans (Finset.filter_subset _ _)) have hQ₂sub : Q₂ ⊆ F₂ := (hQ₂.trans (Finset.filter_subset _ _)) have hQ₁avoid : ∀ A ∈ Q₁, p ∉ A := by intro A hA exact (Finset.mem_filter.mp (hQ₁ hA)).2 have hQ₂avoid : ∀ A ∈ Q₂, p ∉ A := by intro A hA exact (Finset.mem_filter.mp (hQ₂ hA)).2 by_cases hlarge₁ : P₁.card ≤ Q₁.card · have hp := in519_union_packing F₁ F₂ Q₁ P₂ p hF hcross hQ₁sub hP₂ hqpack₁ hpack₂ (Or.inl hQ₁avoid) refine ⟨Q₁ ∪ P₂, C₁ ∪ C₂, ⟨hp.1,hp.2.1⟩, in519_cover_union _ _ _ _ hc₁ hc₂, ?_⟩ have hc := Finset.card_union_le C₁ C₂ rw [hp.2.2] omega by_cases hlarge₂ : P₂.card ≤ Q₂.card · have hp := in519_union_packing F₁ F₂ P₁ Q₂ p hF hcross hP₁ hQ₂sub hpack₁ hqpack₂ (Or.inr hQ₂avoid) refine ⟨P₁ ∪ Q₂, C₁ ∪ C₂, ⟨hp.1,hp.2.1⟩, in519_cover_union _ _ _ _ hc₁ hc₂, ?_⟩ have hc := Finset.card_union_le C₁ C₂ rw [hp.2.2] omega let R := P₂.filter (fun A => p ∉ A) have hRsub : R ⊆ F₂ := (Finset.filter_subset _ _).trans hP₂ have hRpack : (R : Set (Finset α)).Pairwise Disjoint := by apply hpack₂.mono intro A hA exact (Finset.mem_filter.mp hA).1 have hRavoid : ∀ A ∈ R, p ∉ A := by intro A hA exact (Finset.mem_filter.mp hA).2 have hRcard : P₂.card ≤ R.card + 1 := in519_drop_point_packing P₂ p hpack₂ have hp := in519_union_packing F₁ F₂ P₁ R p hF hcross hP₁ hRsub hpack₁ hRpack (Or.inr hRavoid) refine ⟨P₁ ∪ R, insert p (D₁ ∪ D₂), ⟨hp.1,hp.2.1⟩, in519_cover_insert_from_deleted _ _ _ _ _ hd₁ hd₂, ?_⟩ have hc := Finset.card_union_le D₁ D₂ have hi := Finset.card_insert_le p (D₁ ∪ D₂) rw [hp.2.2] omega