op869_union_side_choice
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.
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$.
uses
lt_of_le_of_lt,le_max_left,le_max_rightby_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
$|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|$.
uses
Finset.card_union_of_disjoint,Finset.disjoint_sdiff,Finset.union_sdiff_self_eq_unionhave 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]
$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|$.
uses
Finset.mem_inter,Finset.mem_sdiff,Finset.disjoint_left.mp,Finset.card_le_cardhave 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
$|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|$.
uses
Finset.card_union_add_card_inter,Finset.inter_commhave hu := Finset.card_union_add_card_inter Q X rw [Finset.inter_comm] at hu
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.
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$
- In Lean's natural number arithmetic, truncated division `(t + 1) / 2` computes the ceiling $\lceil t / 2 \rceil$.
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.
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