AFTD Auto-Formalizing Theoretical Domains

unrestricted_partition_family_four_intersecting_and_card

theoremverifiedformalization

For every natural number n ≥ 1, the family partition_A n of partitions of n is 1-intersecting (is_t_intersecting_partition_family 1 (partition_A n)), and its cardinality coerced to ℤ satisfies ((partition_A n).card : ℤ) = partition_number (n - 3 : ℤ) + partition_number (n - 4 : ℤ) + partition_number (n - 5 : ℤ) - partition_number (n - 6 : ℤ) - partition_number (n - 7 : ℤ) - partition_number (n - 8 : ℤ) + partition_number (n - 9 : ℤ).

Statement

theorem unrestricted_partition_family_four_intersecting_and_card (n : ℕ) (hn : 1 ≤ n) :
    is_t_intersecting_partition_family 1 (partition_A n) ∧
    ((partition_A n).card : ℤ) =
      partition_number (n - 3 : ℤ) + partition_number (n - 4 : ℤ) + partition_number (n - 5 : ℤ) -
      partition_number (n - 6 : ℤ) - partition_number (n - 7 : ℤ) - partition_number (n - 8 : ℤ) +
      partition_number (n - 9 : ℤ)
Formalizes
arXiv:2610.01747 Proposition 6.1
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • partition_A_is_one_intersectingFor every n, any two partitions in A_n share at least one common part, so A_n is 1-intersecting.
  • partition_numberThe function partition_number maps an integer m : ℤ to an integer in ℤ: if 0 ≤ m, it returns the cardinality Nat.card of the type of…

Read back from the Lean

For any natural number $n \ge 1$: 1. The family of partitions $\text{partition\_A}(n)$ is $1$-intersecting: for any two partitions $p, q \in \text{partition\_A}(n)$, the multiset intersection of their parts has cardinality at least $1$ (i.e., they share at least one common part). 2. The number of partitions in $\text{partition\_A}(n)$ is equal to: $$p(n - 3) + p(n - 4) + p(n - 5) - p(n - 6) - p(n - 7) - p(n - 8) + p(n - 9)$$ where $p(m)$ denotes the partition function (partition_number), which equals the number of partitions of $m$ if $m \ge 0$, and $0$ if $m < 0$. Here, $\text{partition\_A}(n)$ is the set of all partitions of $n$ whose parts contain both $1$ and $2$, both $1$ and $3$, both $1$ and $4$, or all three of $2$, $3$, and $4$.

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

The theorem states that the partition family partition_A n is 1-intersecting and derives an alternating formula for its size in terms of partition numbers p(n - k). The 1-intersecting property is established by an earlier lemma. To count the family, its membership condition is formulated as a Boolean function on the presence of parts 1, 2, 3, and 4, which expands via inclusion-exclusion into indicators for specified pairs and triples. Removing those parts establishes a bijection with unrestricted partitions of n minus their sum, so each term contributes p(n - k).

  1. The inclusion-exclusion algebraic identity holds for the 4-variable Boolean indicator automation

    Reverting all four Boolean variables reduces the identity to a finite check over all 2⁴ = 16 truth assignments, which is discharged by exhaustive evaluation using decide.

    lines 14–15

      revert x1 x2 x3 x4
      decide
  2. Membership of partition p in partition_A n matches the Boolean formula (x₁ ∧ x₂) ∨ (x₁ ∧ x₃) ∨ (x₁ ∧ x₄) ∨ (x₂ ∧ x₃ ∧ x₄)

    Unfolding the definition of partition_A n as a filter on the universe of partitions and translating Boolean conjunctions and disjunctions to propositional logic proves the equivalence.

    lines 23–30

    uses Bool.eq_iff_iff, decide_eq_true_iff, Finset.mem_filter

      intro x1 x2 x3 x4
      rw [Bool.eq_iff_iff]
      rw [decide_eq_true_iff]
      rw [partition_A, Finset.mem_filter]
      simp only [mem_univ, true_and]
      dsimp [x1, x2, x3, x4]
      simp only [Bool.or_eq_true, Bool.and_eq_true, decide_eq_true_iff]
      tauto
  3. The sum over all partitions of the indicator of membership in a set s equals the cardinality of s

    Rewriting the indicator b2z (decide (p ∈ s)) into an if-then-else expression allows applying Finset.sum_filter in reverse, expressing the sum as the count of elements in s.

    lines 34–40

    uses Finset.sum_filter

      have h : ∀ p, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (p ∈ s)) = if p ∈ s then (1 : ℤ) else 0 := by
        intro p
        simp [unrestricted_partition_family_four_intersecting_and_card_b2z]
      simp_rw [h]
      rw [← Finset.sum_filter]
      simp
    
  4. If multiset s is a submultiset of t, then s.sum ≤ t.sum automation

    Since s + (t - s) = t by submultiset difference, taking multiset sums shows t.sum = s.sum + (t - s).sum, and linear arithmetic over ℕ concludes s.sum ≤ t.sum.

    lines 41–45

    uses tsub_add_cancel_of_le, sum_add

    lemma unrestricted_partition_family_four_intersecting_and_card_multiset_sum_le_sum_of_le {s t : Multiset ℕ} (h : s ≤ t) : s.sum ≤ t.sum := by
      have : s + (t - s) = t := add_comm s (t - s) ▸ tsub_add_cancel_of_le h
      rw [← this, sum_add]
      omega
    
  5. Partitions of n containing submultiset M are in bijection with partitions of n - M.sum

    The bijection sends partition p to parts p.parts - M, and the inverse adds M to the parts. Both directions preserve positivity of parts and the sum invariant, and are two-sided inverses.

    lines 46–70

    uses Subtype.ext, Nat.Partition.ext, add_tsub_cancel_left

    def unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv {n : ℕ} (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) (hsum : M.sum ≤ n) :
        {p : Nat.Partition n // M ≤ p.parts} ≃ Nat.Partition (n - M.sum) where
      toFun p := ⟨p.1.parts - M, fun hx => p.1.parts_pos (mem_of_le tsub_le_self hx), by
        have hle := p.2
        have hsum_eq : (p.1.parts - M).sum + M.sum = p.1.parts.sum := by
          rw [← sum_add, tsub_add_cancel_of_le hle]
        have hp := p.1.parts_sum
        omega⟩
      invFun q := ⟨⟨M + q.parts, fun hx => by
        rcases mem_add.mp hx with h | h
        · exact hpos _ h
        · exact q.parts_pos h, by
        rw [sum_add, q.parts_sum]
        omega⟩, le_add_right _ _⟩
      left_inv p := by
        apply Subtype.ext
        apply Nat.Partition.ext
        dsimp
        rw [add_comm]
        exact tsub_add_cancel_of_le p.2
      right_inv q := by
        apply Nat.Partition.ext
        dsimp
        exact add_tsub_cancel_left _ _
    
  6. The number of partitions of n containing submultiset M equals partition_number (n - M.sum) automation

    If M.sum ≤ n, the bijection submultisetPartitionEquiv transfers cardinality to partitions of n - M.sum. If n < M.sum, any partition containing M would have parts summing to > n, so the subtype is empty and both sides are 0.

    lines 71–89

    uses partition_number, unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv, Nat.card_congr, Nat.card_eq_zero

    theorem unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multiset (n : ℕ) (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) :
        ((Nat.card {p : Nat.Partition n // M ≤ p.parts} : ℤ)) = partition_number (n - (M.sum : ℤ)) := by
      rw [partition_number]
      split_ifs with h
      · have hle : M.sum ≤ n := by omega
        have htoNat : (n - (M.sum : ℤ)).toNat = n - M.sum := by omega
        rw [htoNat]
        have e := unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv M hpos hle
        rw [Nat.card_congr e]
      · have hlt : n < M.sum := by omega
        have h_empty : IsEmpty {p : Nat.Partition n // M ≤ p.parts} := by
          constructor
          intro ⟨p, hp⟩
          have hsum := unrestricted_partition_family_four_intersecting_and_card_multiset_sum_le_sum_of_le hp
          have hp_sum := p.parts_sum
          omega
        have : Nat.card {p : Nat.Partition n // M ≤ p.parts} = 0 := Nat.card_eq_zero.mpr (Or.inl h_empty)
        rw [this, Nat.cast_zero]
    
  7. The sum of indicators that M ≤ p.parts over all partitions of n equals partition_number (n - M.sum)

    Converting the sum of indicators into the cardinality of the subtype {p // M ≤ p.parts} using Finset.sum_filter and card_partition_containing_multiset yields the result.

    lines 90–98

    uses Finset.sum_filter, Nat.card_eq_fintype_card, unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multiset

    lemma unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq (n : ℕ) (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) :
        (∑ p : Nat.Partition n, (if M ≤ p.parts then (1 : ℤ) else 0)) = partition_number (n - (M.sum : ℤ)) := by
      have h1 : (∑ p : Nat.Partition n, (if M ≤ p.parts then (1 : ℤ) else 0)) = (Nat.card {p : Nat.Partition n // M ≤ p.parts} : ℤ) := by
        rw [← Finset.sum_filter]
        simp only [sum_const, nsmul_eq_mul, mul_one]
        congr 1
        rw [Nat.card_eq_fintype_card, Fintype.card_subtype]
      rw [h1, unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multiset n M hpos]
    
  8. Two distinct elements both belong to multiset s if and only if the multiset {a, b} is a submultiset of s

    Since a ≠ b, a is not in the multiset {b}, so cons_le_of_notMem decomposes {a, b} ≤ s into a ∈ s and b ∈ s.

    lines 99–105

    uses cons_le_of_notMem

    lemma unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two {a b : ℕ} (hab : a ≠ b) (s : Multiset ℕ) :
        (a ∈ s ∧ b ∈ s) ↔ (a ::ₘ b ::ₘ 0) ≤ s := by
      have h1 : a ∉ (b ::ₘ 0 : Multiset ℕ) := by simp [hab]
      have h2 : b ∉ (0 : Multiset ℕ) := by simp
      rw [cons_le_of_notMem h1, cons_le_of_notMem h2]
      simp [and_comm]
    
  9. Three pairwise distinct elements all belong to multiset s if and only if {a, b, c} is a submultiset of s

    Applying cons_le_of_notMem inductively three times, using the pairwise distinctness of a, b, c, reduces {a, b, c} ≤ s to the conjunction of memberships in s.

    lines 106–113

    uses cons_le_of_notMem

    lemma unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three {a b c : ℕ} (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (s : Multiset ℕ) :
        (a ∈ s ∧ b ∈ s ∧ c ∈ s) ↔ (a ::ₘ b ::ₘ c ::ₘ 0) ≤ s := by
      have h1 : a ∉ (b ::ₘ c ::ₘ 0 : Multiset ℕ) := by simp [hab, hac]
      have h2 : b ∉ (c ::ₘ 0 : Multiset ℕ) := by simp [hbc]
      have h3 : c ∉ (0 : Multiset ℕ) := by simp
      rw [cons_le_of_notMem h1, cons_le_of_notMem h2, cons_le_of_notMem h3]
      simp
    
  10. All elements in the multiset {a, b} are strictly positive when a > 0 and b > 0

    Any element in {a, b} is either a or b, both of which are positive by hypothesis.

    lines 114–118

    uses Multiset.mem_cons

    lemma unrestricted_partition_family_four_intersecting_and_card_hpos_two {a b : ℕ} (ha : 0 < a) (hb : 0 < b) : ∀ x ∈ (a ::ₘ b ::ₘ 0 : Multiset ℕ), 0 < x := by
      intro x hx
      simp only [Multiset.mem_cons, Multiset.notMem_zero, or_false] at hx
      rcases hx with rfl | rfl <;> assumption
    
  11. All elements in the multiset {a, b, c} are strictly positive when a, b, c > 0

    Any element in {a, b, c} is a, b, or c, all of which are positive by hypothesis.

    lines 119–124

    uses Multiset.mem_cons

    lemma unrestricted_partition_family_four_intersecting_and_card_hpos_three {a b c : ℕ} (ha : 0 < a) (hb : 0 < b) (hc : 0 < c) :
        ∀ x ∈ (a ::ₘ b ::ₘ c ::ₘ 0 : Multiset ℕ), 0 < x := by
      intro x hx
      simp only [Multiset.mem_cons, Multiset.notMem_zero, or_false] at hx
      rcases hx with rfl | rfl | rfl <;> assumption
    
  12. The sum over partitions of the indicator that both a and b are parts equals partition_number (n - (a + b))

    The conjunction a ∈ p.parts ∧ b ∈ p.parts is equivalent to {a, b} ≤ p.parts, which by sum_if_submultiset_eq sums to partition_number (n - (a + b)).

    lines 125–137

    uses if_congr, unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two, unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq, unrestricted_partition_family_four_intersecting_and_card_hpos_two

    lemma unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two (n : ℕ) (a b : ℕ) (hab : a ≠ b) (ha : 0 < a) (hb : 0 < b) :
        (∑ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts))) =
          partition_number (n - ((a ::ₘ b ::ₘ 0 : Multiset ℕ).sum : ℤ)) := by
      have h : ∀ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts)) =
          if (a ::ₘ b ::ₘ 0) ≤ p.parts then (1 : ℤ) else 0 := by
        intro p
        simp only [unrestricted_partition_family_four_intersecting_and_card_b2z]
        apply if_congr _ rfl rfl
        rw [Bool.and_eq_true, decide_eq_true_iff, decide_eq_true_iff]
        exact unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two hab p.parts
      simp_rw [h]
      exact unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq n (a ::ₘ b ::ₘ 0) (unrestricted_partition_family_four_intersecting_and_card_hpos_two ha hb)
    
  13. The sum over partitions of the indicator that a, b, c are parts equals partition_number (n - (a + b + c))

    The conjunction a ∈ p.parts ∧ b ∈ p.parts ∧ c ∈ p.parts is equivalent to {a, b, c} ≤ p.parts, which sums to partition_number (n - (a + b + c)).

    lines 138–151

    uses if_congr, unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three, unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq, unrestricted_partition_family_four_intersecting_and_card_hpos_three

    lemma unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three (n : ℕ) (a b c : ℕ) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c)
        (ha : 0 < a) (hb : 0 < b) (hc : 0 < c) :
        (∑ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts) && decide (c ∈ p.parts))) =
          partition_number (n - ((a ::ₘ b ::ₘ c ::ₘ 0 : Multiset ℕ).sum : ℤ)) := by
      have h : ∀ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts) && decide (c ∈ p.parts)) =
          if (a ::ₘ b ::ₘ c ::ₘ 0) ≤ p.parts then (1 : ℤ) else 0 := by
        intro p
        simp only [unrestricted_partition_family_four_intersecting_and_card_b2z]
        apply if_congr _ rfl rfl
        simp only [Bool.and_eq_true, decide_eq_true_iff, and_assoc]
        exact unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three hab hac hbc p.parts
      simp_rw [h]
      exact unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq n (a ::ₘ b ::ₘ c ::ₘ 0) (unrestricted_partition_family_four_intersecting_and_card_hpos_three ha hb hc)
    
  14. The partition family partition_A n is 1-intersecting, reducing the theorem to the cardinality formula

    The 1-intersecting property is supplied by partition_A_is_one_intersecting n, leaving only the evaluation of the cardinality.

    line 159

    uses partition_A_is_one_intersecting

      refine ⟨partition_A_is_one_intersecting n, ?_⟩
  15. The cardinality of partition_A n equals the sum over all partitions of the indicator of membership in partition_A n

    Applying unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_mem in reverse expresses the cardinality as the total sum of the indicators.

    lines 160–161

    uses unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_mem

      have h_card := (unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_mem n (partition_A n)).symm
      rw [h_card]
  16. The indicator of p ∈ partition_A n expands into an alternating sum of pair and triple indicators

    For each partition p, the membership indicator is rewritten into the 4-variable Boolean condition via decide_mem_partition_A, which is expanded by bool_pie into the inclusion-exclusion sum of pair and triple indicators.

    lines 162–174

    uses unrestricted_partition_family_four_intersecting_and_card_decide_mem_partition_A, unrestricted_partition_family_four_intersecting_and_card_bool_pie

      have h_eq : ∀ p : Nat.Partition n,
          unrestricted_partition_family_four_intersecting_and_card_b2z (decide (p ∈ partition_A n)) =
            unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts)) +
            unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (3 ∈ p.parts)) +
            unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (4 ∈ p.parts)) -
            unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts) && decide (3 ∈ p.parts)) -
            unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts) && decide (4 ∈ p.parts)) -
            unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (3 ∈ p.parts) && decide (4 ∈ p.parts)) +
            unrestricted_partition_family_four_intersecting_and_card_b2z (decide (2 ∈ p.parts) && decide (3 ∈ p.parts) && decide (4 ∈ p.parts)) := by
        intro p
        rw [unrestricted_partition_family_four_intersecting_and_card_decide_mem_partition_A]
        exact unrestricted_partition_family_four_intersecting_and_card_bool_pie _ _ _ _
      simp_rw [h_eq]
  17. The summation distributes over additions and subtractions of indicator terms

    Distributing the sum over each term splits the expression into seven separate sums of indicators of pairs and triples of parts.

    line 175

    uses Finset.sum_add_distrib, Finset.sum_sub_distrib

      simp only [Finset.sum_add_distrib, Finset.sum_sub_distrib]
  18. The multiset sums of the relevant pairs and triples equal 3, 4, 5, 6, 7, 8, and 9

    The sums of multisets {1, 2}, {1, 3}, {1, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4} are computed by reflexivity.

    lines 176–182

      have s12 : ((1 ::ₘ 2 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 3 := by rfl
      have s13 : ((1 ::ₘ 3 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 4 := by rfl
      have s14 : ((1 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 5 := by rfl
      have s123 : ((1 ::ₘ 2 ::ₘ 3 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 6 := by rfl
      have s124 : ((1 ::ₘ 2 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 7 := by rfl
      have s134 : ((1 ::ₘ 3 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 8 := by rfl
      have s234 : ((2 ::ₘ 3 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 9 := by rfl
  19. Each indicator sum evaluates to the corresponding partition number, completing the cardinality formula automation

    Using sum_b2z_two and sum_b2z_three, each sum of pair or triple indicators becomes partition_number (n - sum), with side conditions on distinctness and positivity resolved by decide. Substituting the precomputed sums yields the final alternating sum.

    lines 183–189

    uses unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two, unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three

      rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 2 (by decide) (by decide) (by decide), s12]
      rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 3 (by decide) (by decide) (by decide), s13]
      rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 4 (by decide) (by decide) (by decide), s14]
      rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 2 3 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s123]
      rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 2 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s124]
      rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 3 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s134]
      rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 2 3 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s234]
Bool.eq_iff_iff
Two Booleans are equal if and only if their truth values are logically equivalent
decide_eq_true_iff
For any decidable proposition p, decide p = true is equivalent to p holding
Finset.mem_filter
An element belongs to Finset.filter p s if and only if it belongs to s and satisfies p
Finset.sum_filter
Summing a function over a filtered set Finset.filter p s equals summing the if-then-else indicator over s
tsub_add_cancel_of_le
For natural numbers or in an ordered additive semigroup with subtraction, if a ≤ b then b - a + a = b
sum_add
The sum of elements in a sum of multisets s + t is s.sum + t.sum
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal
Nat.Partition.ext
Two partitions of n are equal if their multisets of parts are equal
add_tsub_cancel_left
In an ordered subtractive structure, a + b - a = b
partition_number
The partition function p(m): defined as the number of partitions of m if m ≥ 0, and 0 if m < 0
unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv
Partitions of n whose parts contain multiset M are in bijection with partitions of n - M.sum, provided M has positive elements and M.sum ≤ n
Nat.card_congr
An equivalence between types preserves their cardinalities
Nat.card_eq_zero
The cardinality of a type is 0 if and only if the type is empty (or infinite)
Nat.card_eq_fintype_card
For a finite type α, Nat.card α equals Fintype.card α
unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multiset
The number of partitions of n containing a given submultiset M of positive parts equals partition_number (n - M.sum)
cons_le_of_notMem
If an element a is not in multiset s, then a ::ₘ s ≤ t if and only if a ∈ t and s ≤ t
Multiset.mem_cons
An element x is in the multiset a ::ₘ s if and only if x = a or x ∈ s
if_congr
If propositions P and Q are equivalent, then the conditional expressions with condition P and Q are equal
unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two
For distinct positive integers a ≠ b, both a and b belong to multiset s if and only if {a, b} ≤ s
unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq
The sum over all partitions p of n of the indicator that M ≤ p.parts equals partition_number (n - M.sum)
unrestricted_partition_family_four_intersecting_and_card_hpos_two
Every element of the multiset {a, b} is strictly positive when a > 0 and b > 0
unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three
For pairwise distinct integers a, b, c, all three belong to multiset s if and only if {a, b, c} ≤ s
unrestricted_partition_family_four_intersecting_and_card_hpos_three
Every element of the multiset {a, b, c} is strictly positive when a, b, c > 0
partition_A_is_one_intersecting
The partition family partition_A n is 1-intersecting
unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_mem
The sum of the indicator values of membership in a finite set s of partitions equals the cardinality of s coerced to ℤ
unrestricted_partition_family_four_intersecting_and_card_decide_mem_partition_A
Membership of a partition p in partition_A n is logically equivalent to the Boolean formula on parts 1, 2, 3, 4
unrestricted_partition_family_four_intersecting_and_card_bool_pie
The inclusion-exclusion expansion of the indicator of the 4-variable Boolean formula defining partition_A n
Finset.sum_add_distrib
The sum of a sum distributes: ∑ x, (f x + g x) = ∑ x, f x + ∑ x, g x
Finset.sum_sub_distrib
The sum of a difference distributes: ∑ x, (f x - g x) = ∑ x, f x - ∑ x, g x
unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two
The sum over partitions of the indicator that distinct positive integers a and b are parts equals partition_number (n - (a + b))
unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three
The sum over partitions of the indicator that pairwise distinct positive integers a, b, c are parts equals partition_number (n - (a + b + c))

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

open Multiset Finsetdef unrestricted_partition_family_four_intersecting_and_card_b2z (b : Bool) : ℤ := if b then 1 else 0lemma unrestricted_partition_family_four_intersecting_and_card_bool_pie (x1 x2 x3 x4 : Bool) :    unrestricted_partition_family_four_intersecting_and_card_b2z ((x1 && x2) || (x1 && x3) || (x1 && x4) || (x2 && x3 && x4)) =      unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x2) +      unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x3) +      unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x4) -      unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x2 && x3) -      unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x2 && x4) -      unrestricted_partition_family_four_intersecting_and_card_b2z (x1 && x3 && x4) +      unrestricted_partition_family_four_intersecting_and_card_b2z (x2 && x3 && x4) := by  revert x1 x2 x3 x4  decidelemma unrestricted_partition_family_four_intersecting_and_card_decide_mem_partition_A (n : ℕ) (p : Nat.Partition n) :    let x1 := decide (1 ∈ p.parts)    let x2 := decide (2 ∈ p.parts)    let x3 := decide (3 ∈ p.parts)    let x4 := decide (4 ∈ p.parts)    decide (p ∈ partition_A n) = ((x1 && x2) || (x1 && x3) || (x1 && x4) || (x2 && x3 && x4)) := by  intro x1 x2 x3 x4  rw [Bool.eq_iff_iff]  rw [decide_eq_true_iff]  rw [partition_A, Finset.mem_filter]  simp only [mem_univ, true_and]  dsimp [x1, x2, x3, x4]  simp only [Bool.or_eq_true, Bool.and_eq_true, decide_eq_true_iff]  tautolemma unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_mem (n : ℕ) (s : Finset (Nat.Partition n)) :    ∑ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (p ∈ s)) = (s.card : ℤ) := by  have h : ∀ p, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (p ∈ s)) = if p ∈ s then (1 : ℤ) else 0 := by    intro p    simp [unrestricted_partition_family_four_intersecting_and_card_b2z]  simp_rw [h]  rw [← Finset.sum_filter]  simplemma unrestricted_partition_family_four_intersecting_and_card_multiset_sum_le_sum_of_le {s t : Multiset ℕ} (h : s ≤ t) : s.sum ≤ t.sum := by  have : s + (t - s) = t := add_comm s (t - s) ▸ tsub_add_cancel_of_le h  rw [← this, sum_add]  omegadef unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv {n : ℕ} (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) (hsum : M.sum ≤ n) :    {p : Nat.Partition n // M ≤ p.parts} ≃ Nat.Partition (n - M.sum) where  toFun p := ⟨p.1.parts - M, fun hx => p.1.parts_pos (mem_of_le tsub_le_self hx), by    have hle := p.2    have hsum_eq : (p.1.parts - M).sum + M.sum = p.1.parts.sum := by      rw [← sum_add, tsub_add_cancel_of_le hle]    have hp := p.1.parts_sum    omega⟩  invFun q := ⟨⟨M + q.parts, fun hx => by    rcases mem_add.mp hx with h | h    · exact hpos _ h    · exact q.parts_pos h, by    rw [sum_add, q.parts_sum]    omega⟩, le_add_right _ _⟩  left_inv p := by    apply Subtype.ext    apply Nat.Partition.ext    dsimp    rw [add_comm]    exact tsub_add_cancel_of_le p.2  right_inv q := by    apply Nat.Partition.ext    dsimp    exact add_tsub_cancel_left _ _theorem unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multiset (n : ℕ) (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) :    ((Nat.card {p : Nat.Partition n // M ≤ p.parts} : ℤ)) = partition_number (n - (M.sum : ℤ)) := by  rw [partition_number]  split_ifs with h  · have hle : M.sum ≤ n := by omega    have htoNat : (n - (M.sum : ℤ)).toNat = n - M.sum := by omega    rw [htoNat]    have e := unrestricted_partition_family_four_intersecting_and_card_submultisetPartitionEquiv M hpos hle    rw [Nat.card_congr e]  · have hlt : n < M.sum := by omega    have h_empty : IsEmpty {p : Nat.Partition n // M ≤ p.parts} := by      constructor      intro ⟨p, hp⟩      have hsum := unrestricted_partition_family_four_intersecting_and_card_multiset_sum_le_sum_of_le hp      have hp_sum := p.parts_sum      omega    have : Nat.card {p : Nat.Partition n // M ≤ p.parts} = 0 := Nat.card_eq_zero.mpr (Or.inl h_empty)    rw [this, Nat.cast_zero]lemma unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq (n : ℕ) (M : Multiset ℕ) (hpos : ∀ x ∈ M, 0 < x) :    (∑ p : Nat.Partition n, (if M ≤ p.parts then (1 : ℤ) else 0)) = partition_number (n - (M.sum : ℤ)) := by  have h1 : (∑ p : Nat.Partition n, (if M ≤ p.parts then (1 : ℤ) else 0)) = (Nat.card {p : Nat.Partition n // M ≤ p.parts} : ℤ) := by    rw [← Finset.sum_filter]    simp only [sum_const, nsmul_eq_mul, mul_one]    congr 1    rw [Nat.card_eq_fintype_card, Fintype.card_subtype]  rw [h1, unrestricted_partition_family_four_intersecting_and_card_card_partition_containing_multiset n M hpos]lemma unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two {a b : ℕ} (hab : a ≠ b) (s : Multiset ℕ) :    (a ∈ s ∧ b ∈ s) ↔ (a ::ₘ b ::ₘ 0) ≤ s := by  have h1 : a ∉ (b ::ₘ 0 : Multiset ℕ) := by simp [hab]  have h2 : b ∉ (0 : Multiset ℕ) := by simp  rw [cons_le_of_notMem h1, cons_le_of_notMem h2]  simp [and_comm]lemma unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three {a b c : ℕ} (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (s : Multiset ℕ) :    (a ∈ s ∧ b ∈ s ∧ c ∈ s) ↔ (a ::ₘ b ::ₘ c ::ₘ 0) ≤ s := by  have h1 : a ∉ (b ::ₘ c ::ₘ 0 : Multiset ℕ) := by simp [hab, hac]  have h2 : b ∉ (c ::ₘ 0 : Multiset ℕ) := by simp [hbc]  have h3 : c ∉ (0 : Multiset ℕ) := by simp  rw [cons_le_of_notMem h1, cons_le_of_notMem h2, cons_le_of_notMem h3]  simplemma unrestricted_partition_family_four_intersecting_and_card_hpos_two {a b : ℕ} (ha : 0 < a) (hb : 0 < b) : ∀ x ∈ (a ::ₘ b ::ₘ 0 : Multiset ℕ), 0 < x := by  intro x hx  simp only [Multiset.mem_cons, Multiset.notMem_zero, or_false] at hx  rcases hx with rfl | rfl <;> assumptionlemma unrestricted_partition_family_four_intersecting_and_card_hpos_three {a b c : ℕ} (ha : 0 < a) (hb : 0 < b) (hc : 0 < c) :    ∀ x ∈ (a ::ₘ b ::ₘ c ::ₘ 0 : Multiset ℕ), 0 < x := by  intro x hx  simp only [Multiset.mem_cons, Multiset.notMem_zero, or_false] at hx  rcases hx with rfl | rfl | rfl <;> assumptionlemma unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two (n : ℕ) (a b : ℕ) (hab : a ≠ b) (ha : 0 < a) (hb : 0 < b) :    (∑ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts))) =      partition_number (n - ((a ::ₘ b ::ₘ 0 : Multiset ℕ).sum : ℤ)) := by  have h : ∀ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts)) =      if (a ::ₘ b ::ₘ 0) ≤ p.parts then (1 : ℤ) else 0 := by    intro p    simp only [unrestricted_partition_family_four_intersecting_and_card_b2z]    apply if_congr _ rfl rfl    rw [Bool.and_eq_true, decide_eq_true_iff, decide_eq_true_iff]    exact unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_iff_le_two hab p.parts  simp_rw [h]  exact unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq n (a ::ₘ b ::ₘ 0) (unrestricted_partition_family_four_intersecting_and_card_hpos_two ha hb)lemma unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three (n : ℕ) (a b c : ℕ) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c)    (ha : 0 < a) (hb : 0 < b) (hc : 0 < c) :    (∑ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts) && decide (c ∈ p.parts))) =      partition_number (n - ((a ::ₘ b ::ₘ c ::ₘ 0 : Multiset ℕ).sum : ℤ)) := by  have h : ∀ p : Nat.Partition n, unrestricted_partition_family_four_intersecting_and_card_b2z (decide (a ∈ p.parts) && decide (b ∈ p.parts) && decide (c ∈ p.parts)) =      if (a ::ₘ b ::ₘ c ::ₘ 0) ≤ p.parts then (1 : ℤ) else 0 := by    intro p    simp only [unrestricted_partition_family_four_intersecting_and_card_b2z]    apply if_congr _ rfl rfl    simp only [Bool.and_eq_true, decide_eq_true_iff, and_assoc]    exact unrestricted_partition_family_four_intersecting_and_card_mem_and_mem_and_mem_iff_le_three hab hac hbc p.parts  simp_rw [h]  exact unrestricted_partition_family_four_intersecting_and_card_sum_if_submultiset_eq n (a ::ₘ b ::ₘ c ::ₘ 0) (unrestricted_partition_family_four_intersecting_and_card_hpos_three ha hb hc)/-- Proposition 6.1 (arXiv:2610.01747): A_n is 1-intersecting and its cardinality satisfies the alternating sum formula in terms of p(n-k). -/theorem unrestricted_partition_family_four_intersecting_and_card (n : ℕ) (hn : 1 ≤ n) :    is_t_intersecting_partition_family 1 (partition_A n) ∧    ((partition_A n).card : ℤ) =      partition_number (n - 3 : ℤ) + partition_number (n - 4 : ℤ) + partition_number (n - 5 : ℤ) -      partition_number (n - 6 : ℤ) - partition_number (n - 7 : ℤ) - partition_number (n - 8 : ℤ) +      partition_number (n - 9 : ℤ) := by  refine ⟨partition_A_is_one_intersecting n, ?_⟩  have h_card := (unrestricted_partition_family_four_intersecting_and_card_sum_b2z_decide_mem n (partition_A n)).symm  rw [h_card]  have h_eq : ∀ p : Nat.Partition n,      unrestricted_partition_family_four_intersecting_and_card_b2z (decide (p ∈ partition_A n)) =        unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts)) +        unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (3 ∈ p.parts)) +        unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (4 ∈ p.parts)) -        unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts) && decide (3 ∈ p.parts)) -        unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (2 ∈ p.parts) && decide (4 ∈ p.parts)) -        unrestricted_partition_family_four_intersecting_and_card_b2z (decide (1 ∈ p.parts) && decide (3 ∈ p.parts) && decide (4 ∈ p.parts)) +        unrestricted_partition_family_four_intersecting_and_card_b2z (decide (2 ∈ p.parts) && decide (3 ∈ p.parts) && decide (4 ∈ p.parts)) := by    intro p    rw [unrestricted_partition_family_four_intersecting_and_card_decide_mem_partition_A]    exact unrestricted_partition_family_four_intersecting_and_card_bool_pie _ _ _ _  simp_rw [h_eq]  simp only [Finset.sum_add_distrib, Finset.sum_sub_distrib]  have s12 : ((1 ::ₘ 2 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 3 := by rfl  have s13 : ((1 ::ₘ 3 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 4 := by rfl  have s14 : ((1 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 5 := by rfl  have s123 : ((1 ::ₘ 2 ::ₘ 3 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 6 := by rfl  have s124 : ((1 ::ₘ 2 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 7 := by rfl  have s134 : ((1 ::ₘ 3 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 8 := by rfl  have s234 : ((2 ::ₘ 3 ::ₘ 4 ::ₘ 0 : Multiset ℕ).sum : ℤ) = 9 := by rfl  rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 2 (by decide) (by decide) (by decide), s12]  rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 3 (by decide) (by decide) (by decide), s13]  rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_two n 1 4 (by decide) (by decide) (by decide), s14]  rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 2 3 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s123]  rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 2 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s124]  rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 1 3 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s134]  rw [unrestricted_partition_family_four_intersecting_and_card_sum_b2z_three n 2 3 4 (by decide) (by decide) (by decide) (by decide) (by decide) (by decide), s234]
See it in the graphDiscuss this resultChallenge it