AFTD Auto-Formalizing Theoretical Domains

partition_A_is_one_intersecting

theoremverified

For every n, any two partitions in A_n share at least one common part, so A_n is 1-intersecting.

Statement

theorem partition_A_is_one_intersecting (n : ℕ) :
    is_t_intersecting_partition_family 1 (partition_A n)
Source
arXiv:2610.01747, Proposition 6.1
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • partition_AThe family A_n of partitions of n consists of those partitions of n whose multiset of parts contains {1, 2}, {1, 3}, {1, 4}, or {2, 3, 4}.
  • is_t_intersecting_partition_familyGiven natural numbers n and t, a finite set F of partitions of n (of type Finset (Nat.Partition n)) is t-intersecting if for every pair of…
Used by 1

Read back from the Lean

For every natural number $n$, the family of partitions partition_A n is 1-intersecting: for any two partitions $p, q$ of $n$ in partition_A n, the multiset intersection of their parts has cardinality at least 1 (i.e., $p$ and $q$ share at least one part).

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

To show that the family of partitions A_n is 1-intersecting, we must prove that any two partitions p, q in A_n share at least one part. By definition, the parts of every partition in A_n contain at least one of the subsets {1, 2}, {1, 3}, {1, 4}, or {2, 3, 4}. Because any two of these four subsets have a non-empty intersection, an exhaustive case analysis across all 16 combinations exhibits an explicit common part x. Since their multiset intersection contains x, its cardinality is at least 1.

  1. Let p and q be two partitions in partition_A n. For each of p and q, its parts contain at least one of the pairs {1, 2}, {1, 3}, {1, 4}, or the triple {2, 3, 4}.

    We introduce arbitrary partitions p and q together with their membership assumptions in `partition_A n`. Unfolding the definition of `partition_A` and applying `Finset.mem_filter`, we discard the trivial universal set membership, retaining the four-way disjunction describing which parts each partition must contain.

    lines 4–7

    uses Finset.mem_filter

      intro p hp q hq
      rw [partition_A, Finset.mem_filter] at hp hq
      obtain ⟨-, hp⟩ := hp
      obtain ⟨-, hq⟩ := hq
  2. There exists an integer x that is a part of both p and q.

    We perform an exhaustive case split on the four possible conditions for p and the four possible conditions for q, yielding 16 cases in total. The four underlying sets {1, 2}, {1, 3}, {1, 4}, and {2, 3, 4} pairwise intersect: the first three all contain 1, and the triple {2, 3, 4} shares 2, 3, and 4 with the three pairs respectively. In all 16 cases, an explicit common part x is provided as a witness.

    lines 8–29

      have h_inter : ∃ x, x ∈ p.parts ∧ x ∈ q.parts := by
        rcases hp with ⟨h1p, h2p⟩ | ⟨h1p, h3p⟩ | ⟨h1p, h4p⟩ | ⟨h2p, h3p, h4p⟩
        · rcases hq with ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨h2q, -, -⟩
          · exact ⟨1, h1p, h1q⟩
          · exact ⟨1, h1p, h1q⟩
          · exact ⟨1, h1p, h1q⟩
          · exact ⟨2, h2p, h2q⟩
        · rcases hq with ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨-, h3q, -⟩
          · exact ⟨1, h1p, h1q⟩
          · exact ⟨1, h1p, h1q⟩
          · exact ⟨1, h1p, h1q⟩
          · exact ⟨3, h3p, h3q⟩
        · rcases hq with ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨-, -, h4q⟩
          · exact ⟨1, h1p, h1q⟩
          · exact ⟨1, h1p, h1q⟩
          · exact ⟨1, h1p, h1q⟩
          · exact ⟨4, h4p, h4q⟩
        · rcases hq with ⟨-, h2q⟩ | ⟨-, h3q⟩ | ⟨-, h4q⟩ | ⟨h2q, -, -⟩
          · exact ⟨2, h2p, h2q⟩
          · exact ⟨3, h3p, h3q⟩
          · exact ⟨4, h4p, h4q⟩
          · exact ⟨2, h2p, h2q⟩
  3. The multiset intersection of the parts of p and q has cardinality at least 1.

    From the common part x, `Multiset.mem_inter.mpr` shows that x belongs to the multiset intersection `p.parts ∩ q.parts`. By `Multiset.card_pos_iff_exists_mem.mpr`, exhibiting an element in this intersection proves that its cardinality is strictly positive, completing the proof that p and q share at least 1 part.

    lines 30–32

    uses Multiset.mem_inter.mpr, Multiset.card_pos_iff_exists_mem.mpr

      obtain ⟨x, hxp, hxq⟩ := h_inter
      have hx : x ∈ p.parts ∩ q.parts := Multiset.mem_inter.mpr ⟨hxp, hxq⟩
      exact Multiset.card_pos_iff_exists_mem.mpr ⟨x, hx⟩
Finset.mem_filter
An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies the predicate `p`.
Multiset.mem_inter.mpr
If an element belongs to both multisets `s` and `t`, then it belongs to their multiset intersection `s ∩ t`.
Multiset.card_pos_iff_exists_mem.mpr
If a multiset contains at least one element, its cardinality is strictly greater than 0.

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 family A_n is 1-intersecting for any n. -/theorem partition_A_is_one_intersecting (n : ℕ) :    is_t_intersecting_partition_family 1 (partition_A n) := by  intro p hp q hq  rw [partition_A, Finset.mem_filter] at hp hq  obtain ⟨-, hp⟩ := hp  obtain ⟨-, hq⟩ := hq  have h_inter : ∃ x, x ∈ p.parts ∧ x ∈ q.parts := by    rcases hp with ⟨h1p, h2p⟩ | ⟨h1p, h3p⟩ | ⟨h1p, h4p⟩ | ⟨h2p, h3p, h4p⟩    · rcases hq with ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨h2q, -, -⟩      · exact ⟨1, h1p, h1q⟩      · exact ⟨1, h1p, h1q⟩      · exact ⟨1, h1p, h1q⟩      · exact ⟨2, h2p, h2q⟩    · rcases hq with ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨-, h3q, -⟩      · exact ⟨1, h1p, h1q⟩      · exact ⟨1, h1p, h1q⟩      · exact ⟨1, h1p, h1q⟩      · exact ⟨3, h3p, h3q⟩    · rcases hq with ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨h1q, -⟩ | ⟨-, -, h4q⟩      · exact ⟨1, h1p, h1q⟩      · exact ⟨1, h1p, h1q⟩      · exact ⟨1, h1p, h1q⟩      · exact ⟨4, h4p, h4q⟩    · rcases hq with ⟨-, h2q⟩ | ⟨-, h3q⟩ | ⟨-, h4q⟩ | ⟨h2q, -, -⟩      · exact ⟨2, h2p, h2q⟩      · exact ⟨3, h3p, h3q⟩      · exact ⟨4, h4p, h4q⟩      · exact ⟨2, h2p, h2q⟩  obtain ⟨x, hxp, hxq⟩ := h_inter  have hx : x ∈ p.parts ∩ q.parts := Multiset.mem_inter.mpr ⟨hxp, hxq⟩  exact Multiset.card_pos_iff_exists_mem.mpr ⟨x, hx⟩
See it in the graphDiscuss this resultChallenge it