prioritized_borel_exponential_profile_frontier
For every n, there is a set of 2^n pairs of length-n binary profiles in which distinct pairs are incomparable when both components are ordered lexicographically.
Statement
theorem prioritized_borel_exponential_profile_frontier (n : ℕ) :
∃ S : Finset ((Fin n → Bool) × (Fin n → Bool)),
S.card = 2^n ∧
∀ x ∈ S, ∀ y ∈ S,
toLex x.1 ≤ toLex y.1 → toLex x.2 ≤ toLex y.2 → x = y- Source
- Filed by the prover as a step towards another result
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
The proof, explained
To construct an antichain of size $2^n$ under the product lexicographic order on pairs of binary sequences of length $n$, we take the set of pairs $S = \{ (p, \neg p) : p \in \{0, 1\}^n \}$, pairing each binary sequence with its bitwise complement. First, we show that bitwise complementation strictly reverses lexicographic order: if $p <_{\text{lex}} q$, their first differing bit has $p(i) = 0$ and $q(i) = 1$, which makes $\neg q(i) = 0 < 1 = \neg p(i)$. Consequently, if both $p \le_{\text{lex}} q$ and $\neg p \le_{\text{lex}} \neg q$, then $p$ must equal $q$, so no two distinct pairs in $S$ can be ordered in both components. Finally, since $p \mapsto (p, \neg p)$ is injective, $S$ has cardinality $2^n$.
Identify the first index $i$ where $p$ and $q$ differ to witness the lexicographic inequality $\neg q <_{\text{lex}} \neg p$.
Unfolding the definition of lexicographic inequality $p <_{\text{lex}} q$ yields an index $i \in \text{Fin } n$ such that $p(j) = q(j)$ for all $j < i$ and $p(i) < q(i)$. To establish $\neg q <_{\text{lex}} \neg p$, we propose this same index $i$ as the differing position.
change Pi.Lex (· < ·) (· < ·) p q at h obtain ⟨i, hprev, hbit⟩ := h change Pi.Lex (· < ·) (· < ·) (fun i => !q i) (fun i => !p i) refine ⟨i, ?_, ?_⟩
The complement profiles $\neg q$ and $\neg p$ agree on all coordinates preceding $i$.
For any index $j < i$, the hypothesis states $p(j) = q(j)$. Taking the boolean negation of both sides yields $\neg q(j) = \neg p(j)$.
· intro j hj change (!(q j)) = (!(p j)) rw [hprev j hj]
At coordinate $i$, the complement of $q$ is strictly less than the complement of $p$, completing the proof of `in784_complement_lex_reverses`.
Case analysis on the boolean values of $p(i)$ and $q(i)$ leaves only $p(i) = \text{false}$ and $q(i) = \text{true}$ consistent with $p(i) < q(i)$. In this case, $\neg q(i) = \text{false} < \text{true} = \neg p(i)$. The other combinations contradict $p(i) < q(i)$ and are closed by simplification.
· cases hp : p i <;> cases hq : q i <;> simp_all
Assume for contradiction that $p \ne q$, which implies that their lexicographic encodings are distinct.
To prove $p = q$ in `in784_complement_profiles_pareto`, we assume for contradiction that $p \ne q$. If their lexicographic encodings were equal, applying `ofLex` via `congrArg` would yield $p = q$, contradicting the assumption.
uses
congrArg,ofLexby_contra hne have hnelex : toLex p ≠ toLex q := by intro h apply hne exact congrArg ofLex h
Derive strict lexicographic inequality, apply complement reversal, and reach a contradiction, proving `in784_complement_profiles_pareto`.
From $p \le_{\text{lex}} q$ and $p \ne_{\text{lex}} q$, we deduce $p <_{\text{lex}} q$ via `lt_of_le_of_ne`. By `in784_complement_lex_reverses`, this implies $\neg q <_{\text{lex}} \neg p$. But the second hypothesis is $\neg p \le_{\text{lex}} \neg q$, which via `not_lt_of_ge` contradicts $\neg q <_{\text{lex}} \neg p$.
uses
lt_of_le_of_ne,in784_complement_lex_reverses,not_lt_of_gehave hlt : toLex p < toLex q := lt_of_le_of_ne hfirst hnelex have hreverse := in784_complement_lex_reverses n p q hlt exact (not_lt_of_ge hsecond) hreverse
Define the profile pairing function sending $p \mapsto (p, \neg p)$ and prove it is injective.
We define the map `make` associating each profile $p$ with the pair $(p, \neg p)$. If $\text{make}(p) = \text{make}(q)$, applying the projection `Prod.fst` via `congrArg` gives $p = q$, establishing injectivity.
uses
congrArg,Prod.fstclassical let make : (Fin n → Bool) → (Fin n → Bool) × (Fin n → Bool) := fun p => (p, fun i => !p i) have hinj : Function.Injective make := by intro p q h exact congrArg Prod.fst h
Construct $S$ as the image of the universe under `make`, and show $|S| = 2^n$. automation
The set $S$ is defined as the image under `make` of all binary profiles of length $n$. Since `make` is injective (`Finset.card_image_of_injective`), the cardinality of $S$ equals the cardinality of $\text{Fin } n \to \text{Bool}$, which simplifies to $2^n$.
uses
Finset.card_image_of_injectivelet S := Finset.univ.image make refine ⟨S, ?_, ?_⟩ · rw [Finset.card_image_of_injective _ hinj] simp
Prove that any two pairs in $S$ that are comparable in both components are identical.
Given $x, y \in S$, using `Finset.mem_image.mp` we write $x = (p, \neg p)$ and $y = (q, \neg q)$. The comparability hypotheses mean $p \le_{\text{lex}} q$ and $\neg p \le_{\text{lex}} \neg q$. By `in784_complement_profiles_pareto`, we conclude $p = q$, hence $x = y$.
uses
Finset.mem_image.mp,in784_complement_profiles_pareto· intro x hx y hy hfirst hsecond obtain ⟨p, _, rfl⟩ := Finset.mem_image.mp hx obtain ⟨q, _, rfl⟩ := Finset.mem_image.mp hy have heq : p = q := in784_complement_profiles_pareto n p q hfirst hsecond subst q rfl
congrArg- If $a_1 = a_2$, then $f(a_1) = f(a_2)$ for any function $f$.
ofLex- The canonical equivalence mapping an element of `Lex α` back to `α`.
lt_of_le_of_ne- In a partial order, if $a ≤ b$ and $a ≠ b$, then $a < b$.
not_lt_of_ge- In a preorder, if $a ≤ b$, then ¬(b < a).
in784_complement_lex_reverses- For length-$n$ boolean profiles, if $p <_{\text{lex}} q$, then their bitwise complements satisfy $\neg q <_{\text{lex}} \neg p$.
Prod.fst- The projection function returning the first component of an ordered pair: $(a, b) \mapsto a$.
Finset.card_image_of_injective- The image of a finite set under an injective map has the same cardinality as the original set.
Finset.mem_image.mp- If $y \in f(S)$, then there exists $x \in S$ such that $f(x) = y$.
in784_complement_profiles_pareto- If length-$n$ boolean profiles satisfy $p \le_{\text{lex}} q$ and $\neg p \le_{\text{lex}} \neg q$, then $p = q$.
- In step 7 (line 39), `simp` automatically evaluates the cardinality of `Finset.univ` for `Fin n → Bool` to `2^n` by appealing to Mathlib's fintype instance for function spaces.
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 in784_complement_lex_reverses (n : ℕ) (p q : Fin n → Bool) (h : toLex p < toLex q) : toLex (fun i => !q i) < toLex (fun i => !p i) := by change Pi.Lex (· < ·) (· < ·) p q at h obtain ⟨i, hprev, hbit⟩ := h change Pi.Lex (· < ·) (· < ·) (fun i => !q i) (fun i => !p i) refine ⟨i, ?_, ?_⟩ · intro j hj change (!(q j)) = (!(p j)) rw [hprev j hj] · cases hp : p i <;> cases hq : q i <;> simp_alltheorem in784_complement_profiles_pareto (n : ℕ) (p q : Fin n → Bool) (hfirst : toLex p ≤ toLex q) (hsecond : toLex (fun i => !p i) ≤ toLex (fun i => !q i)) : p = q := by by_contra hne have hnelex : toLex p ≠ toLex q := by intro h apply hne exact congrArg ofLex h have hlt : toLex p < toLex q := lt_of_le_of_ne hfirst hnelex have hreverse := in784_complement_lex_reverses n p q hlt exact (not_lt_of_ge hsecond) hreversetheorem prioritized_borel_exponential_profile_frontier (n : ℕ) : ∃ S : Finset ((Fin n → Bool) × (Fin n → Bool)), S.card = 2^n ∧ ∀ x ∈ S, ∀ y ∈ S, toLex x.1 ≤ toLex y.1 → toLex x.2 ≤ toLex y.2 → x = y := by classical let make : (Fin n → Bool) → (Fin n → Bool) × (Fin n → Bool) := fun p => (p, fun i => !p i) have hinj : Function.Injective make := by intro p q h exact congrArg Prod.fst h let S := Finset.univ.image make refine ⟨S, ?_, ?_⟩ · rw [Finset.card_image_of_injective _ hinj] simp · intro x hx y hy hfirst hsecond obtain ⟨p, _, rfl⟩ := Finset.mem_image.mp hx obtain ⟨q, _, rfl⟩ := Finset.mem_image.mp hy have heq : p = q := in784_complement_profiles_pareto n p q hfirst hsecond subst q rfl