AFTD Auto-Formalizing Theoretical Domains

turan_hypergraph_three_uniform

theoremverified

For every natural number n, the balanced 3-partite Turán hypergraph T_n is 3-uniform.

Statement

theorem turan_hypergraph_three_uniform (n : ℕ) : is_three_uniform (turan_hypergraph n)
Source
arXiv:2611.16654:380
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • turan_hypergraphThe balanced 3-partite Turán 3-uniform hypergraph T_n on vertex set Fin n: its edges are all 3-element subsets e of Fin n such that either…
  • is_three_uniformA hypergraph F (a finite family of finite sets of vertices) is 3-uniform if every hyperedge e in F has cardinality 3.

Read back from the Lean

For every natural number $n$, the hypergraph turan_hypergraph n is 3-uniform; that is, every edge $e \in \text{turan\_hypergraph}(n)$ has cardinality 3.

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

The proof, explained

By definition, a hypergraph is 3-uniform if every edge in it has cardinality 3. The Turán hypergraph T_n is defined by filtering the subsets of Fin n with a predicate whose first conjunct is that the subset has cardinality 3. For any edge in the hypergraph, unpacking this filter condition directly establishes that its cardinality is 3.

  1. Every edge in the Turán hypergraph T_n has cardinality 3.

    By definition, a hypergraph is 3-uniform if every edge has cardinality 3. For an arbitrary edge e in `turan_hypergraph n`, the lemma `Finset.mem_filter.mp` unpacks the filter condition into the ambient set membership and the conjunction defining the hypergraph. Taking the first conjunct of that defining property yields `e.card = 3`.

    line 2

    uses Finset.mem_filter.mp

    theorem turan_hypergraph_three_uniform (n : ℕ) : is_three_uniform (turan_hypergraph n) := fun _ he => (Finset.mem_filter.mp he).2.1
Finset.mem_filter.mp
If an element belongs to a filtered finite set `Finset.filter p s`, then it belongs to `s` and satisfies the predicate `p`.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The Turán construction T_n is 3-uniform. -/theorem turan_hypergraph_three_uniform (n : ℕ) : is_three_uniform (turan_hypergraph n) := fun _ he => (Finset.mem_filter.mp he).2.1
See it in the graphDiscuss this resultChallenge it