AFTD Auto-Formalizing Theoretical Domains

has_three_by_three_grid

def

For a hypergraph with edge set H : Set (Finset V) of finite subsets of V, H contains a 3x3 grid if there exist families R, C : Fin 3 → Finset V of edges in H such that R is pairwise disjoint, C is pairwise disjoint, and ¬ Disjoint (R i) (C j) for all i, j : Fin 3.

Statement

def has_three_by_three_grid {V : Type*} (H : Set (Finset V)) : Prop
Defined in
arXiv:2611.05261 Section 1 and Section 3
Verified
05 Nov 2026
Axioms
none listed

Read back from the Lean

Given a type V and a family of finite subsets H : Set (Finset V), has_three_by_three_grid H asserts that there exist two sequences of three finite subsets of V, R : Fin 3 → Finset V (the rows) and C : Fin 3 → Finset V (the columns), such that: 1. For every i : Fin 3, R i ∈ H; 2. For every j : Fin 3, C j ∈ H; 3. For all i, i' : Fin 3, if i ≠ i', then R i and R i' are disjoint; 4. For all j, j' : Fin 3, if j ≠ j', then C j and C j' are disjoint; 5. For all i, j : Fin 3, R i and C j are not disjoint (i.e., they have non-empty intersection).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Predicate that a hypergraph of finite edges contains a 3x3 grid of edges. -/
def has_three_by_three_grid {V : Type*} (H : Set (Finset V)) : Prop := ∃ (R C : Fin 3 → Finset V),
    (∀ i, R i ∈ H) ∧
    (∀ j, C j ∈ H) ∧
    (∀ i i', i ≠ i' → Disjoint (R i) (R i')) ∧
    (∀ j j', j ≠ j' → Disjoint (C j) (C j')) ∧
    (∀ i j, ¬ Disjoint (R i) (C j))
See it in the graphDiscuss this resultChallenge it