partition_A_is_one_intersecting
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
- unrestricted_partition_family_four_intersecting_and_cardFor every natural number n ≥ 1, the family partition_A n of partitions of n is 1-intersecting (is_t_intersecting_partition_family 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.
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.
uses
Finset.mem_filterintro p hp q hq rw [partition_A, Finset.mem_filter] at hp hq obtain ⟨-, hp⟩ := hp obtain ⟨-, hq⟩ := hq
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.
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⟩
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.
uses
Multiset.mem_inter.mpr,Multiset.card_pos_iff_exists_mem.mprobtain ⟨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.
- In Lean, the inequality `1 ≤ k` on natural numbers is definitionally equivalent to `0 < k`, allowing `Multiset.card_pos_iff_exists_mem.mpr` (which establishes `0 < Multiset.card s`) to directly close the goal `1 ≤ (p.parts ∩ q.parts).card`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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⟩