AFTD Auto-Formalizing Theoretical Domains

mdfrbf_compress_subset_iff

theoremverified

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

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.

  1. 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 ∅).

    lines 5–14

    uses Function.Embedding.subtype, if_pos, if_neg

      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
  2. 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.

    lines 15–32

    uses Finset.mem_sdiff, Finset.disjoint_left, Finset.mem_map

      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
  3. 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).

    lines 33–43

    uses Finset.mem_sdiff, Finset.mem_union, Or.inl, Finset.disjoint_left.mp

      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⟩
  4. 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'.

    lines 44–57

    uses Finset.mem_map, Finset.mem_union_left, Finset.mem_sdiff

      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
  5. 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'.

    lines 58–78

    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

/-- 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)
See it in the graphDiscuss this resultChallenge it