mdfrbf_compress_subset_iff
The compression map is an order embedding: for all sets A, A' of points outside W, T A ⊆ T A' holds if and only if A ⊆ A'. Consequently T is injective, monotone, and reflects inclusions (hence strict inclusions), which is what lets an induced copy be pushed back from the compressed colouring to χ.
Statement
theorem mdfrbf_compress_subset_iff {d k : ℕ} (W : Finset (Fin d)) (χ : Finset (Fin d) → Fin k) (c : Fin k)
(A A' : Finset ↥(Finset.univ \ W)) :
mdfrbf_compress W χ c A ⊆ mdfrbf_compress W χ c A' ↔ A ⊆ A'- Source
- step towards mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- mdfrbf_compressThe compression map: given a block W ⊆ Fin d, a colouring χ and an excluded colour c, send a set A of points outside W to its image…
- Used by 1
- mixed_diamond_fan_ramsey_bound_all_singletons_fan_coloursCase b ≥ 2 with every singleton fan-coloured: if d ≥ j*a + (j-1)*b + 1 and the statement holds at (a, b-1) in dimension d-(j-1), then χ…
The proof, explained
The compression map embeds a set A outside W into the ambient space and optionally adjoins W whenever A contains a monochromatic witness of color c. Because embedded points never belong to W, removing W from the compressed set uniquely recovers the embedded image of A, which immediately gives the forward implication via injectivity of the embedding. The reverse implication follows because both the embedded image and the condition for adjoining W are monotonic with respect to inclusion.
The compression map can be written uniformly as the union of the embedded set with a conditional term that is either W or ∅.
By definition, mdfrbf_compress A is emb(A) ∪ W if A is nonempty and contains a nonempty monochromatic subset of color c, and emb(A) otherwise. Rewriting emb(A) as emb(A) ∪ ∅ in the negative case allows expressing both branches uniformly as emb(A) ∪ (if P(A) then W else ∅).
uses
Function.Embedding.subtype,if_pos,if_negclassical set emb : ↥(Finset.univ \ W) ↪ Fin d := Function.Embedding.subtype fun x => x ∈ Finset.univ \ W with hemb have hdef : ∀ A : Finset ↥(Finset.univ \ W), mdfrbf_compress W χ c A = A.map emb ∪ (if (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = c) then W else ∅) := by intro A unfold mdfrbf_compress simp only [← hemb] by_cases h : (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = c) · rw [if_pos h, if_pos h] · rw [if_neg h, if_neg h]; simp
The embedded set emb(A) is disjoint from W, and the conditional term is always a subset of W.
Every element x of the subtype Finset.univ \ W satisfies x ∉ W by definition of set difference. Consequently, emb(x) ∉ W for every point, so emb(A) and W are disjoint. Furthermore, whether the condition holds or not, the conditional set is either W or ∅, both of which are subsets of W.
uses
Finset.mem_sdiff,Finset.disjoint_left,Finset.mem_maphave hnotW : ∀ x : ↥(Finset.univ \ W), (emb x : Fin d) ∉ W := by intro x hx have hx2 : (x : Fin d) ∈ Finset.univ \ W := x.2 rw [Finset.mem_sdiff] at hx2 have hv : (emb x : Fin d) = (x : Fin d) := rfl rw [hv] at hx exact hx2.2 hx have hdisj : ∀ A : Finset ↥(Finset.univ \ W), Disjoint (A.map emb) W := by intro A rw [Finset.disjoint_left] intro y hy hyW rw [Finset.mem_map] at hy obtain ⟨x, -, rfl⟩ := hy exact hnotW x hyW have hWa : ∀ A : Finset ↥(Finset.univ \ W), (if (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = c) then W else ∅) ⊆ W := by intro A split_ifs <;> simp
Removing W from the compressed set of A recovers exactly the embedded set emb(A).
In the representation mdfrbf_compress A = emb(A) ∪ (if P(A) then W else ∅), the second term is contained in W while emb(A) is disjoint from W. Taking the set difference with W removes the conditional term completely and leaves emb(A) untouched, yielding (mdfrbf_compress A) \ W = emb(A).
uses
Finset.mem_sdiff,Finset.mem_union,Or.inl,Finset.disjoint_left.mphave hdiff : ∀ A : Finset ↥(Finset.univ \ W), mdfrbf_compress W χ c A \ W = A.map emb := by intro A rw [hdef A] ext y simp only [Finset.mem_sdiff, Finset.mem_union] constructor · rintro ⟨hy | hy, hyW⟩ · exact hy · exact absurd (hWa A hy) hyW · intro hy exact ⟨Or.inl hy, fun h => Finset.disjoint_left.mp (hdisj A) hy h⟩
Inclusion of compressed sets implies inclusion of the original sets: mdfrbf_compress A ⊆ mdfrbf_compress A' implies A ⊆ A'.
For any x ∈ A, its image emb(x) lies in emb(A) and thus in mdfrbf_compress A ⊆ mdfrbf_compress A'. Since emb(x) ∉ W, it belongs to (mdfrbf_compress A') \ W, which equals emb(A') by the previous identity. Because emb is an embedding (and hence injective), emb(x) ∈ emb(A') implies x ∈ A'.
uses
Finset.mem_map,Finset.mem_union_left,Finset.mem_sdiffconstructor · intro hsub x hx have h1 : emb x ∈ A.map emb := by rw [Finset.mem_map]; exact ⟨x, hx, rfl⟩ have h2 : emb x ∈ mdfrbf_compress W χ c A' := by apply hsub rw [hdef A] exact Finset.mem_union_left _ h1 have h4 : emb x ∈ A'.map emb := by rw [← hdiff A', Finset.mem_sdiff] exact ⟨h2, hnotW x⟩ rw [Finset.mem_map] at h4 obtain ⟨y, hy, hyx⟩ := h4 rw [emb.injective hyx] at hy exact hy
Inclusion of original sets implies inclusion of compressed sets: A ⊆ A' implies mdfrbf_compress A ⊆ mdfrbf_compress A'.
If A ⊆ A', then emb(A) ⊆ emb(A'). Furthermore, the condition that A contains a nonempty monochromatic subset of color c is monotonic: any witness B ⊆ A also satisfies B ⊆ A', so P(A) implies P(A'). Case analysis confirms that if P(A) holds, both compressed sets adjoin W and the inclusion holds; if P(A) does not hold, mdfrbf_compress A is just emb(A), which is already contained in emb(A') and therefore in mdfrbf_compress A'.
uses
Finset.map_subset_map.mpr,if_pos,Finset.union_subset_union,le_refl,if_neg,Finset.mem_union.mp,Finset.mem_union_left· intro hsub rw [hdef A, hdef A'] have hmap : A.map emb ⊆ A'.map emb := Finset.map_subset_map.mpr hsub have hHA : (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = c) → (A'.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A' ∧ χ (B.map emb) = c) := by rintro ⟨hne, B, hBne, hBsub, hBc⟩ exact ⟨hne.mono hsub, B, hBne, hBsub.trans hsub, hBc⟩ by_cases hA : (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = c) · rw [if_pos hA, if_pos (hHA hA)] exact Finset.union_subset_union hmap (le_refl W) · by_cases hA' : (A'.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A' ∧ χ (B.map emb) = c) · rw [if_neg hA, if_pos hA'] intro y hy rcases Finset.mem_union.mp hy with h | h · exact Finset.mem_union_left _ (hmap h) · exact absurd h (by simp) · rw [if_neg hA, if_neg hA'] intro y hy rcases Finset.mem_union.mp hy with h | h · exact Finset.mem_union_left _ (hmap h) · exact absurd h (by simp)
Function.Embedding.subtype- The canonical embedding of a subtype into its ambient type, mapping an element to its underlying value.
if_pos- If a condition is true, an if-then-else expression reduces to its 'then' branch.
if_neg- If a condition is false, an if-then-else expression reduces to its 'else' branch.
Finset.mem_sdiff- An element belongs to a set difference s \\ t if and only if it belongs to s and not to t.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first set belongs to the second.
Finset.disjoint_left.mp- If two sets are disjoint, any element in the first set does not belong to the second set.
Finset.mem_map- An element b belongs to the image Finset.map f s if and only if b = f a for some a in s.
Finset.mem_union- An element belongs to s ∪ t if and only if it belongs to s or to t.
Finset.mem_union.mp- If an element belongs to s ∪ t, then it belongs to s or to t.
Or.inl- Introduces a disjunction proof from a proof of its left disjunct.
Finset.mem_union_left- If an element belongs to s, it belongs to the union s ∪ t.
Finset.map_subset_map.mpr- If s ⊆ t, then the image of s under an embedding is a subset of the image of t.
Finset.union_subset_union- If s ⊆ u and t ⊆ v, then s ∪ t ⊆ u ∪ v.
le_refl- In any preorder, every element is less than or equal to itself (here, reflexivity of subset inclusion W ⊆ W).
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.
/-- The compression map is an order embedding of the subsets of the complement of W; it yields injectivity, monotonicity and reflection of inclusions at once. -/theorem mdfrbf_compress_subset_iff {d k : ℕ} (W : Finset (Fin d)) (χ : Finset (Fin d) → Fin k) (c : Fin k) (A A' : Finset ↥(Finset.univ \ W)) : mdfrbf_compress W χ c A ⊆ mdfrbf_compress W χ c A' ↔ A ⊆ A' := by classical set emb : ↥(Finset.univ \ W) ↪ Fin d := Function.Embedding.subtype fun x => x ∈ Finset.univ \ W with hemb have hdef : ∀ A : Finset ↥(Finset.univ \ W), mdfrbf_compress W χ c A = A.map emb ∪ (if (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = c) then W else ∅) := by intro A unfold mdfrbf_compress simp only [← hemb] by_cases h : (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = c) · rw [if_pos h, if_pos h] · rw [if_neg h, if_neg h]; simp have hnotW : ∀ x : ↥(Finset.univ \ W), (emb x : Fin d) ∉ W := by intro x hx have hx2 : (x : Fin d) ∈ Finset.univ \ W := x.2 rw [Finset.mem_sdiff] at hx2 have hv : (emb x : Fin d) = (x : Fin d) := rfl rw [hv] at hx exact hx2.2 hx have hdisj : ∀ A : Finset ↥(Finset.univ \ W), Disjoint (A.map emb) W := by intro A rw [Finset.disjoint_left] intro y hy hyW rw [Finset.mem_map] at hy obtain ⟨x, -, rfl⟩ := hy exact hnotW x hyW have hWa : ∀ A : Finset ↥(Finset.univ \ W), (if (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = c) then W else ∅) ⊆ W := by intro A split_ifs <;> simp have hdiff : ∀ A : Finset ↥(Finset.univ \ W), mdfrbf_compress W χ c A \ W = A.map emb := by intro A rw [hdef A] ext y simp only [Finset.mem_sdiff, Finset.mem_union] constructor · rintro ⟨hy | hy, hyW⟩ · exact hy · exact absurd (hWa A hy) hyW · intro hy exact ⟨Or.inl hy, fun h => Finset.disjoint_left.mp (hdisj A) hy h⟩ constructor · intro hsub x hx have h1 : emb x ∈ A.map emb := by rw [Finset.mem_map]; exact ⟨x, hx, rfl⟩ have h2 : emb x ∈ mdfrbf_compress W χ c A' := by apply hsub rw [hdef A] exact Finset.mem_union_left _ h1 have h4 : emb x ∈ A'.map emb := by rw [← hdiff A', Finset.mem_sdiff] exact ⟨h2, hnotW x⟩ rw [Finset.mem_map] at h4 obtain ⟨y, hy, hyx⟩ := h4 rw [emb.injective hyx] at hy exact hy · intro hsub rw [hdef A, hdef A'] have hmap : A.map emb ⊆ A'.map emb := Finset.map_subset_map.mpr hsub have hHA : (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = c) → (A'.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A' ∧ χ (B.map emb) = c) := by rintro ⟨hne, B, hBne, hBsub, hBc⟩ exact ⟨hne.mono hsub, B, hBne, hBsub.trans hsub, hBc⟩ by_cases hA : (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = c) · rw [if_pos hA, if_pos (hHA hA)] exact Finset.union_subset_union hmap (le_refl W) · by_cases hA' : (A'.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A' ∧ χ (B.map emb) = c) · rw [if_neg hA, if_pos hA'] intro y hy rcases Finset.mem_union.mp hy with h | h · exact Finset.mem_union_left _ (hmap h) · exact absurd h (by simp) · rw [if_neg hA, if_neg hA'] intro y hy rcases Finset.mem_union.mp hy with h | h · exact Finset.mem_union_left _ (hmap h) · exact absurd h (by simp)