AFTD Auto-Formalizing Theoretical Domains

op869_union_side_choice

theoremverified

For finite sets P, Q, X with |P|, |Q| at least a, |X| = t and X disjoint from P, one of P ∪ Q and Q ∪ X has at least a + ⌈t/2⌉ elements.

Statement

theorem op869_union_side_choice {α : Type} [DecidableEq α] (P Q X : Finset α) (a t : ℕ)
    (hP : a ≤ P.card) (hQ : a ≤ Q.card) (hX : X.card = t) (hXP : Disjoint X P) :
    a + (t + 1) / 2 ≤ max (P ∪ Q).card (Q ∪ X).card
Source
arXiv:2610.41516, Lemma 2.1
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem states that when $P$ and $Q$ have size at least $a$, $X$ has size $t$, and $X$ is disjoint from $P$, at least one of $P \cup Q$ or $Q \cup X$ has size at least $a + \lceil t/2 \rceil$. The proof argues by contradiction, assuming both union sizes are strictly smaller than $a + \lceil t/2 \rceil$. Disjointness of $X$ and $P$ ensures that $X \cap Q \subseteq Q \setminus P$, allowing the sum $|P \cup Q| + |Q \cup X|$ to be bounded below by $|P| + |Q| + |X| \ge 2a + t$, which contradicts the assumed upper bounds.

  1. Both $|P \cup Q| < a + (t + 1) / 2$ and $|Q \cup X| < a + (t + 1) / 2$

    Assume for contradiction that $\max(|P \cup Q|, |Q \cup X|) < a + (t + 1) / 2$. Since $|P \cup Q| \le \max(|P \cup Q|, |Q \cup X|)$ by `le_max_left` and $|Q \cup X| \le \max(|P \cup Q|, |Q \cup X|)$ by `le_max_right`, transitivity of strict inequality (`lt_of_le_of_lt`) implies that both union sizes are strictly less than $a + (t + 1) / 2$.

    lines 4–7

    uses lt_of_le_of_lt, le_max_left, le_max_right

      by_contra hcon
      push Not at hcon
      have h1 : (P ∪ Q).card < a + (t + 1) / 2 := lt_of_le_of_lt (le_max_left _ _) hcon
      have h2 : (Q ∪ X).card < a + (t + 1) / 2 := lt_of_le_of_lt (le_max_right _ _) hcon
  2. $|P \cup Q| = |P| + |Q \setminus P|$

    Decomposing $P \cup Q$ into the disjoint union $P \cup (Q \setminus P)$ via `Finset.union_sdiff_self_eq_union` and `Finset.disjoint_sdiff`, `Finset.card_union_of_disjoint` equates the cardinality of $P \cup Q$ to $|P| + |Q \setminus P|$.

    lines 8–9

    uses Finset.card_union_of_disjoint, Finset.disjoint_sdiff, Finset.union_sdiff_self_eq_union

      have hsd : (P ∪ Q).card = P.card + (Q \ P).card := by
        rw [← Finset.card_union_of_disjoint Finset.disjoint_sdiff, Finset.union_sdiff_self_eq_union]
  3. $X \cap Q \subseteq Q \setminus P$, and therefore $|X \cap Q| \le |Q \setminus P|$

    Take an element $x \in X \cap Q$, so $x \in X$ and $x \in Q$ by `Finset.mem_inter`. Because $X$ and $P$ are disjoint, $x \notin P$ by `Finset.disjoint_left.mp`. By `Finset.mem_sdiff`, $x \in Q \setminus P$, proving $X \cap Q \subseteq Q \setminus P$. Applying `Finset.card_le_card` then yields $|X \cap Q| \le |Q \setminus P|$.

    lines 10–15

    uses Finset.mem_inter, Finset.mem_sdiff, Finset.disjoint_left.mp, Finset.card_le_card

      have hsub : X ∩ Q ⊆ Q \ P := by
        intro x hx
        rw [Finset.mem_inter] at hx
        rw [Finset.mem_sdiff]
        exact ⟨hx.2, Finset.disjoint_left.mp hXP hx.1⟩
      have hc := Finset.card_le_card hsub
  4. $|Q \cup X| + |X \cap Q| = |Q| + |X|$

    By inclusion-exclusion on $Q$ and $X$ (`Finset.card_union_add_card_inter`), $|Q \cup X| + |Q \cap X| = |Q| + |X|$. Applying commutativity of intersection (`Finset.inter_comm`) rewrites the second term to $|X \cap Q|$.

    lines 16–17

    uses Finset.card_union_add_card_inter, Finset.inter_comm

      have hu := Finset.card_union_add_card_inter Q X
      rw [Finset.inter_comm] at hu
  5. A contradiction is reached automation

    Summing the two union cardinalities gives $|P \cup Q| + |Q \cup X| = |P| + |Q \setminus P| + |Q \cup X| \ge |P| + |X \cap Q| + |Q \cup X| = |P| + |Q| + |X| \ge 2a + t$. However, the contradictory assumption implies $|P \cup Q| + |Q \cup X| \le 2(a + (t + 1) / 2 - 1) < 2a + t$. The `omega` tactic detects that this system of linear integer inequalities has no solution and closes the goal.

    line 18

      omega
lt_of_le_of_lt
if $a \le b$ and $b < c$, then $a < c$
le_max_left
for any $a$ and $b$, $a \le \max(a, b)$
le_max_right
for any $a$ and $b$, $b \le \max(a, b)$
Finset.card_union_of_disjoint
the cardinality of the union of two disjoint finite sets is the sum of their cardinalities
Finset.disjoint_sdiff
a set $s$ is disjoint from the set difference $t \setminus s$
Finset.union_sdiff_self_eq_union
the union $s \cup (t \setminus s)$ equals $s \cup t$
Finset.mem_inter
an element belongs to the intersection $s_1 \cap s_2$ if and only if it belongs to both $s_1$ and $s_2$
Finset.mem_sdiff
an element belongs to the set difference $s \setminus t$ if and only if it belongs to $s$ and not to $t$
Finset.disjoint_left.mp
if two sets are disjoint, any element of the first does not belong to the second
Finset.card_le_card
if $s \subseteq t$ for finite sets, then $|s| \le |t|$
Finset.card_union_add_card_inter
for finite sets $s$ and $t$, $|s \cup t| + |s \cap t| = |s| + |t|$
Finset.inter_comm
intersection of finite sets is commutative: $s_1 \cap s_2 = s_2 \cap s_1$

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

theorem op869_union_side_choice {α : Type} [DecidableEq α] (P Q X : Finset α) (a t : ℕ)    (hP : a ≤ P.card) (hQ : a ≤ Q.card) (hX : X.card = t) (hXP : Disjoint X P) :    a + (t + 1) / 2 ≤ max (P ∪ Q).card (Q ∪ X).card := by  by_contra hcon  push Not at hcon  have h1 : (P ∪ Q).card < a + (t + 1) / 2 := lt_of_le_of_lt (le_max_left _ _) hcon  have h2 : (Q ∪ X).card < a + (t + 1) / 2 := lt_of_le_of_lt (le_max_right _ _) hcon  have hsd : (P ∪ Q).card = P.card + (Q \ P).card := by    rw [← Finset.card_union_of_disjoint Finset.disjoint_sdiff, Finset.union_sdiff_self_eq_union]  have hsub : X ∩ Q ⊆ Q \ P := by    intro x hx    rw [Finset.mem_inter] at hx    rw [Finset.mem_sdiff]    exact ⟨hx.2, Finset.disjoint_left.mp hXP hx.1⟩  have hc := Finset.card_le_card hsub  have hu := Finset.card_union_add_card_inter Q X  rw [Finset.inter_comm] at hu  omega
See it in the graphDiscuss this resultChallenge it