AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_exponential_profile_frontier

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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$.

  1. 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.

    lines 4–7

      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, ?_, ?_⟩
  2. 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)$.

    lines 8–10

      · intro j hj
        change (!(q j)) = (!(p j))
        rw [hprev j hj]
  3. 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.

    line 11

      · cases hp : p i <;> cases hq : q i <;> simp_all
  4. 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.

    lines 16–20

    uses congrArg, ofLex

      by_contra hne
      have hnelex : toLex p ≠ toLex q := by
        intro h
        apply hne
        exact congrArg ofLex h
  5. 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$.

    lines 21–23

    uses lt_of_le_of_ne, in784_complement_lex_reverses, not_lt_of_ge

      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) hreverse
  6. 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.

    lines 30–35

    uses congrArg, Prod.fst

      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
  7. 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$.

    lines 36–39

    uses Finset.card_image_of_injective

      let S := Finset.univ.image make
      refine ⟨S, ?_, ?_⟩
      · rw [Finset.card_image_of_injective _ hinj]
        simp
  8. 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$.

    lines 40–45

    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$.

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 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
See it in the graphDiscuss this resultChallenge it