CommunicationComplexity.Deterministic.Protocol.aux_card_step
theoremverifiedimported Lean
Union bound for two power-of-two cardinalities. Let $S_0, S_1$ be sets in a type $\beta$ and let $c_0, c_1 \in \mathbb{N}$. If $\abs{S_0} \le 2^{c_0}$ and $\abs{S_1} \le 2^{c_1}$, then \[ \abs{S_0 \cup S_1} \;\le\; 2^{\,1 + \max(c_0, c_1)}, \] where $\abs{\cdot}$ denotes the number of elements of a set.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in lemma CommunicationComplexity.Deterministic.Protocol.aux_card_step {β : Type*} {S₀ S₁ : Set β} {c₀ c₁ : ℕ} (h₀ : S₀.ncard ≤ 2 ^ c₀) (h₁ : S₁.ncard ≤ 2 ^ c₁) : (S₀ ∪ S₁).ncard ≤ 2 ^ (1 + max c₀ c₁)
- Source
- TCSlib, `CommunicationComplexity.Deterministic.Protocol.aux_card_step`
- Lean proof
- By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.CommunicationComplexity.Deterministic.Protocol.aux_card_step← CommunicationComplexity.Deterministic.Protocol.aux_card_step (TCSlib/CommunicationComplexity/DeterministicCC/DetRectangle.lean:383): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- CommunicationComplexity.Deterministic.Protocol.aux_cardLeaf rectangle count bounded by two to the complexity. Let $p$ be a deterministic two-party communication protocol with input types $X$…
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.
set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {X Y α : Type*} in/-- Shared counting step of `aux_card`: if `S₀` has at most `2 ^ c₀` elements and `S₁` at most `2 ^ c₁`, then `S₀ ∪ S₁` has at most `2 ^ (1 + max c₀ c₁)` elements. The proof is the union bound, `2 ^ c ≤ 2 ^ max c₀ c₁`, and `2 ^ m + 2 ^ m = 2 ^ (1 + m)`. -/lemma CommunicationComplexity.Deterministic.Protocol.aux_card_step {β : Type*} {S₀ S₁ : Set β} {c₀ c₁ : ℕ} (h₀ : S₀.ncard ≤ 2 ^ c₀) (h₁ : S₁.ncard ≤ 2 ^ c₁) : (S₀ ∪ S₁).ncard ≤ 2 ^ (1 + max c₀ c₁) := calc (S₀ ∪ S₁).ncard ≤ S₀.ncard + S₁.ncard := Set.ncard_union_le _ _ _ ≤ 2 ^ c₀ + 2 ^ c₁ := Nat.add_le_add h₀ h₁ _ ≤ 2 ^ max c₀ c₁ + 2 ^ max c₀ c₁ := Nat.add_le_add (Nat.pow_le_pow_right (by omega) (Nat.le_max_left _ _)) (Nat.pow_le_pow_right (by omega) (Nat.le_max_right _ _)) _ = 2 ^ (1 + max c₀ c₁) := by ring