AFTD Auto-Formalizing Theoretical Domains

op1370_block_forces_coordinate_pattern

theoremverified

For strongly incomparable families, if a two-element set {x,y} and its complement both occur outside the family of S, then x belongs to S exactly when y does not.

Statement

lemma op1370_block_forces_coordinate_pattern (n t : β„•)
    (π’œ : Fin t β†’ Finset (Finset (Fin n))) (hinc : strongly_incomparable π’œ)
    (i j k : Fin t) (hji : j β‰  i) (hki : k β‰  i) (x y : Fin n)
    (hw : ({x,y} : Finset (Fin n)) ∈ π’œ j)
    (hc : ({x,y} : Finset (Fin n))ᢜ ∈ π’œ k)
    (S : Finset (Fin n)) (hS : S ∈ π’œ i) : x ∈ S ↔ y βˆ‰ S
Source
Coordinate blocker implication for OP-1370.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • strongly_incomparableAn indexed family of finset families π’œ : ΞΉ β†’ Finset (Finset Ξ±) is strongly incomparable if for all i j : ΞΉ with i β‰  j, for all…
Used by 1

Lean source view module on GitHub

lemma op1370_block_forces_coordinate_pattern (n t : β„•)
    (π’œ : Fin t β†’ Finset (Finset (Fin n))) (hinc : strongly_incomparable π’œ)
    (i j k : Fin t) (hji : j β‰  i) (hki : k β‰  i) (x y : Fin n)
    (hw : ({x,y} : Finset (Fin n)) ∈ π’œ j)
    (hc : ({x,y} : Finset (Fin n))ᢜ ∈ π’œ k)
    (S : Finset (Fin n)) (hS : S ∈ π’œ i) : x ∈ S ↔ y βˆ‰ S := by
  open Finset in
  classical
  constructor
  Β· intro hx hy
    have hsub : ({x,y} : Finset (Fin n)) βŠ† S := by
      intro a ha
      simp only [mem_insert, mem_singleton] at ha
      rcases ha with rfl | rfl <;> assumption
    exact hinc j i hji {x,y} hw S hS hsub
  Β· intro hy
    by_contra hx
    have hsub : S βŠ† ({x,y} : Finset (Fin n))ᢜ := by
      intro a ha
      apply mem_compl.mpr
      simp only [mem_insert, mem_singleton, not_or]
      exact ⟨fun h => hx (h β–Έ ha), fun h => hy (h β–Έ ha)⟩
    exact hinc i k hki.symm S hS ({x,y} : Finset (Fin n))ᢜ hc hsub
See it in the graphDiscuss this resultChallenge it