AFTD Auto-Formalizing Theoretical Domains

op314_poset_tower_order_iso_converse

theoremverified

For any natural number k and any types α and β equipped with partial orders [PartialOrder α] and [PartialOrder β], if there exists an order-isomorphism α ≃o β, then there exists an order-isomorphism poset_tower α k ≃o poset_tower β k between their height-k right-associated exponentiation towers.

Statement

theorem op314_poset_tower_order_iso_converse (k : ℕ) (α β : Type*) [PartialOrder α] [PartialOrder β] (h : Nonempty (α ≃o β)) : Nonempty (poset_tower α k ≃o poset_tower β k)
Source
arXiv:2610.20802 Sec. 5
Verified
26 Oct 2026
Axioms
Quot.soundpropext
Built on 1
  • poset_towerGiven an unbundled type α equipped with a partial order [PartialOrder α], the function poset_tower (α : Type*) [PartialOrder α] : ℕ →…

Read back from the Lean

For every natural number $k$ and any two types $\alpha$ and $\beta$ with partial orders, if there exists an order isomorphism between $\alpha$ and $\beta$ (i.e., α ≃o β is nonempty), then there exists an order isomorphism between poset_tower α k and poset_tower β k.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem is proved by induction on the tower height k using the custom induction principle `poset_tower.induct`. For k = 0 and k = 1, the exponentiation tower is definitionally the base poset, so the assumed order-isomorphism between α and β settles both base cases immediately. For the inductive step from k to k + 1 (with k ≠ 0), the tower is the poset of monotone maps from the height-k tower to the base poset; composing with the induction hypothesis on the domain and the base isomorphism on the codomain yields the required order-isomorphism.

  1. Given order-isomorphisms eP : P ≃o Q and eA : A ≃o B, any monotone map f : P →o A induces a monotone map Φ(f) : Q →o B defined by q ↦ eA (f (eP.symm q)).

    The induced map is defined by precomposing f with eP.symm and postcomposing with eA. Its monotonicity is verified by composing the monotonicity of eP.symm, f, and eA. Line 10 records the definitional unfolding rule by reflexivity.

    lines 1–11

    private def op314_poset_tower_order_iso_converse_arrowFun {P Q A B : Type*} [PartialOrder P]
        [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B)
        (f : P →o A) : Q →o B :=
      OrderHom.mk (fun q => eA (f (eP.symm q)))
        (by intro a b hq; exact eA.monotone (f.monotone (eP.symm.monotone hq)))
    
    private lemma op314_poset_tower_order_iso_converse_arrowFun_apply {P Q A B : Type*}
        [PartialOrder P] [PartialOrder Q] [PartialOrder A] [PartialOrder B]
        (eP : P ≃o Q) (eA : A ≃o B) (f : P →o A) (q : Q) :
        op314_poset_tower_order_iso_converse_arrowFun eP eA f q = eA (f (eP.symm q)) := rfl
    
  2. Given order-isomorphisms eP : P ≃o Q and eA : A ≃o B, any monotone map g : Q →o B induces an inverse monotone map Ψ(g) : P →o A defined by p ↦ eA.symm (g (eP p)).

    Symmetrically, the inverse map is defined by precomposing g with eP and postcomposing with eA.symm. It is monotone as a composition of monotone maps, with the unfolding rule verified by reflexivity on line 21.

    lines 12–22

    private def op314_poset_tower_order_iso_converse_arrowInv {P Q A B : Type*} [PartialOrder P]
        [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B)
        (g : Q →o B) : P →o A :=
      OrderHom.mk (fun p => eA.symm (g (eP p)))
        (by intro a b hp; exact eA.symm.monotone (g.monotone (eP.monotone hp)))
    
    private lemma op314_poset_tower_order_iso_converse_arrowInv_apply {P Q A B : Type*}
        [PartialOrder P] [PartialOrder Q] [PartialOrder A] [PartialOrder B]
        (eP : P ≃o Q) (eA : A ≃o B) (g : Q →o B) (p : P) :
        op314_poset_tower_order_iso_converse_arrowInv eP eA g p = eA.symm (g (eP p)) := rfl
    
  3. The map Ψ is a left inverse to Φ: for every monotone map f : P →o A, Ψ(Φ(f)) = f.

    By extensionality on p ∈ P, the left-hand side expands to eA.symm (eA (f (eP.symm (eP p)))). Applying the fact that eP.symm is inverse to eP and eA.symm is inverse to eA simplifies the expression to f(p).

    lines 23–32

    uses op314_poset_tower_order_iso_converse_arrowInv_apply, op314_poset_tower_order_iso_converse_arrowFun_apply

    private lemma op314_poset_tower_order_iso_converse_left_inv {P Q A B : Type*} [PartialOrder P]
        [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B)
        (f : P →o A) :
        op314_poset_tower_order_iso_converse_arrowInv eP eA
          (op314_poset_tower_order_iso_converse_arrowFun eP eA f) = f := by
      ext p
      rw [op314_poset_tower_order_iso_converse_arrowInv_apply,
        op314_poset_tower_order_iso_converse_arrowFun_apply, eP.symm_apply_apply,
        eA.symm_apply_apply]
    
  4. The map Ψ is a right inverse to Φ: for every monotone map g : Q →o B, Φ(Ψ(g)) = g.

    By extensionality on q ∈ Q, the composition evaluates to eA (eA.symm (g (eP (eP.symm q)))). Using the round-trip identities eP (eP.symm q) = q and eA (eA.symm b) = b reduces this expression to g(q).

    lines 33–42

    uses op314_poset_tower_order_iso_converse_arrowFun_apply, op314_poset_tower_order_iso_converse_arrowInv_apply

    private lemma op314_poset_tower_order_iso_converse_right_inv {P Q A B : Type*} [PartialOrder P]
        [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B)
        (g : Q →o B) :
        op314_poset_tower_order_iso_converse_arrowFun eP eA
          (op314_poset_tower_order_iso_converse_arrowInv eP eA g) = g := by
      ext q
      rw [op314_poset_tower_order_iso_converse_arrowFun_apply,
        op314_poset_tower_order_iso_converse_arrowInv_apply, eP.apply_symm_apply,
        eA.apply_symm_apply]
    
  5. The induced map Φ preserves and reflects the pointwise partial order, assembling into an order-isomorphism (P →o A) ≃o (Q →o B).

    By definition, f ≤ g in the pointwise order means f(x) ≤ g(x) for all x. If Φ(f) ≤ Φ(g), evaluating at q = eP(p) yields eA(f(p)) ≤ eA(g(p)), which implies f(p) ≤ g(p) because eA reflects order. Conversely, if f ≤ g, applying the monotone map eA to f(eP.symm q) ≤ g(eP.symm q) shows Φ(f) ≤ Φ(g). Finally, combining this order reflection with the two-sided inverse property yields the order-isomorphism arrowOrderIso via RelIso.mk.

    lines 43–68

    uses OrderHom.le_def, op314_poset_tower_order_iso_converse_arrowFun_apply

    private lemma op314_poset_tower_order_iso_converse_map_rel {P Q A B : Type*} [PartialOrder P]
        [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B)
        {f g : P →o A} :
        op314_poset_tower_order_iso_converse_arrowFun eP eA f ≤
          op314_poset_tower_order_iso_converse_arrowFun eP eA g ↔ f ≤ g := by
      rw [OrderHom.le_def, OrderHom.le_def]
      constructor
      · intro h p
        have h' := h (eP p)
        simp only [op314_poset_tower_order_iso_converse_arrowFun_apply,
          eP.symm_apply_apply] at h'
        exact (eA.le_iff_le).1 h'
      · intro h q
        rw [op314_poset_tower_order_iso_converse_arrowFun_apply]
        exact eA.monotone (h (eP.symm q))
    
    private def op314_poset_tower_order_iso_converse_arrowOrderIso {P Q A B : Type*} [PartialOrder P]
        [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B) :
        (P →o A) ≃o (Q →o B) :=
      RelIso.mk
        { toFun := op314_poset_tower_order_iso_converse_arrowFun eP eA
          invFun := op314_poset_tower_order_iso_converse_arrowInv eP eA
          left_inv := op314_poset_tower_order_iso_converse_left_inv eP eA
          right_inv := op314_poset_tower_order_iso_converse_right_inv eP eA }
        (op314_poset_tower_order_iso_converse_map_rel eP eA)
    
  6. For k = 0, the height-0 exponentiation towers poset_tower α 0 and poset_tower β 0 are order-isomorphic.

    We induct on k using poset_tower.induct. For the base case k = 0, poset_tower.eq_1 reduces both towers to the underlying posets α and β. The assumed order-isomorphism h : Nonempty (α ≃o β) directly provides the witness.

    lines 69–75

    uses poset_tower.induct, poset_tower.eq_1

    /-- Order-isomorphic posets have order-isomorphic right-associated exponentiation towers at any height k. -/
    theorem op314_poset_tower_order_iso_converse (k : ℕ) (α β : Type*) [PartialOrder α] [PartialOrder β] (h : Nonempty (α ≃o β)) : Nonempty (poset_tower α k ≃o poset_tower β k) := by
      induction k using poset_tower.induct with
      | case1 =>
          rw [poset_tower.eq_1 α, poset_tower.eq_1 β]
          change Nonempty (α ≃o β)
          exact h
  7. For k = 1, the height-1 exponentiation towers poset_tower α 1 and poset_tower β 1 are order-isomorphic.

    For the second base case k = 1, poset_tower.eq_2 also reduces both towers to the base posets α and β, and the hypothesis h again immediately supplies the order-isomorphism.

    lines 76–79

    uses poset_tower.eq_2

      | case2 =>
          rw [poset_tower.eq_2 α, poset_tower.eq_2 β]
          change Nonempty (α ≃o β)
          exact h
  8. For any non-zero k, if the height-k towers are order-isomorphic, then so are the height-(k+1) towers.

    By the induction hypothesis, there exists an order-isomorphism eP between the height-k towers, and h provides an isomorphism eA : α ≃o β. Rewriting with poset_tower.eq_3 expresses the height-(k+1) towers as the monotone function spaces poset_tower α k →o α and poset_tower β k →o β. Applying the helper op314_poset_tower_order_iso_converse_arrowOrderIso to eP and eA produces the required order-isomorphism.

    lines 80–84

    uses poset_tower.eq_3, op314_poset_tower_order_iso_converse_arrowOrderIso

      | case3 k hk ih =>
          obtain ⟨eP⟩ := ih
          obtain ⟨eA⟩ := h
          rw [poset_tower.eq_3 α k hk, poset_tower.eq_3 β k hk]
          exact ⟨op314_poset_tower_order_iso_converse_arrowOrderIso eP eA⟩
OrderHom.le_def
Two monotone maps satisfy f ≤ g if and only if f(x) ≤ g(x) for all x in the domain.
op314_poset_tower_order_iso_converse_arrowFun_apply
Applying the forward induced monotone map to an element q yields eA(f(eP.symm q)).
op314_poset_tower_order_iso_converse_arrowInv_apply
Applying the inverse induced monotone map to an element p yields eA.symm(g(eP p)).
poset_tower.eq_1
The height-0 tower over α is definitionally the base poset α.
poset_tower.eq_2
The height-1 tower over α is definitionally the base poset α.
poset_tower.eq_3
For k ≠ 0, the height-(k+1) tower over α is the poset of monotone maps from the height-k tower into α.
poset_tower.induct
Induction principle for `poset_tower`: to prove P(k) for all k, it suffices to prove P(0), P(1), and that P(k) implies P(k+1) for any non-zero k.
op314_poset_tower_order_iso_converse_arrowOrderIso
Given order-isomorphisms P ≃o Q and A ≃o B, there is an order-isomorphism (P →o A) ≃o (Q →o B) between their posets of monotone functions.

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

private def op314_poset_tower_order_iso_converse_arrowFun {P Q A B : Type*} [PartialOrder P]    [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B)    (f : P →o A) : Q →o B :=  OrderHom.mk (fun q => eA (f (eP.symm q)))    (by intro a b hq; exact eA.monotone (f.monotone (eP.symm.monotone hq)))private lemma op314_poset_tower_order_iso_converse_arrowFun_apply {P Q A B : Type*}    [PartialOrder P] [PartialOrder Q] [PartialOrder A] [PartialOrder B]    (eP : P ≃o Q) (eA : A ≃o B) (f : P →o A) (q : Q) :    op314_poset_tower_order_iso_converse_arrowFun eP eA f q = eA (f (eP.symm q)) := rflprivate def op314_poset_tower_order_iso_converse_arrowInv {P Q A B : Type*} [PartialOrder P]    [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B)    (g : Q →o B) : P →o A :=  OrderHom.mk (fun p => eA.symm (g (eP p)))    (by intro a b hp; exact eA.symm.monotone (g.monotone (eP.monotone hp)))private lemma op314_poset_tower_order_iso_converse_arrowInv_apply {P Q A B : Type*}    [PartialOrder P] [PartialOrder Q] [PartialOrder A] [PartialOrder B]    (eP : P ≃o Q) (eA : A ≃o B) (g : Q →o B) (p : P) :    op314_poset_tower_order_iso_converse_arrowInv eP eA g p = eA.symm (g (eP p)) := rflprivate lemma op314_poset_tower_order_iso_converse_left_inv {P Q A B : Type*} [PartialOrder P]    [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B)    (f : P →o A) :    op314_poset_tower_order_iso_converse_arrowInv eP eA      (op314_poset_tower_order_iso_converse_arrowFun eP eA f) = f := by  ext p  rw [op314_poset_tower_order_iso_converse_arrowInv_apply,    op314_poset_tower_order_iso_converse_arrowFun_apply, eP.symm_apply_apply,    eA.symm_apply_apply]private lemma op314_poset_tower_order_iso_converse_right_inv {P Q A B : Type*} [PartialOrder P]    [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B)    (g : Q →o B) :    op314_poset_tower_order_iso_converse_arrowFun eP eA      (op314_poset_tower_order_iso_converse_arrowInv eP eA g) = g := by  ext q  rw [op314_poset_tower_order_iso_converse_arrowFun_apply,    op314_poset_tower_order_iso_converse_arrowInv_apply, eP.apply_symm_apply,    eA.apply_symm_apply]private lemma op314_poset_tower_order_iso_converse_map_rel {P Q A B : Type*} [PartialOrder P]    [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B)    {f g : P →o A} :    op314_poset_tower_order_iso_converse_arrowFun eP eA f ≤      op314_poset_tower_order_iso_converse_arrowFun eP eA g ↔ f ≤ g := by  rw [OrderHom.le_def, OrderHom.le_def]  constructor  · intro h p    have h' := h (eP p)    simp only [op314_poset_tower_order_iso_converse_arrowFun_apply,      eP.symm_apply_apply] at h'    exact (eA.le_iff_le).1 h'  · intro h q    rw [op314_poset_tower_order_iso_converse_arrowFun_apply]    exact eA.monotone (h (eP.symm q))private def op314_poset_tower_order_iso_converse_arrowOrderIso {P Q A B : Type*} [PartialOrder P]    [PartialOrder Q] [PartialOrder A] [PartialOrder B] (eP : P ≃o Q) (eA : A ≃o B) :    (P →o A) ≃o (Q →o B) :=  RelIso.mk    { toFun := op314_poset_tower_order_iso_converse_arrowFun eP eA      invFun := op314_poset_tower_order_iso_converse_arrowInv eP eA      left_inv := op314_poset_tower_order_iso_converse_left_inv eP eA      right_inv := op314_poset_tower_order_iso_converse_right_inv eP eA }    (op314_poset_tower_order_iso_converse_map_rel eP eA)/-- Order-isomorphic posets have order-isomorphic right-associated exponentiation towers at any height k. -/theorem op314_poset_tower_order_iso_converse (k : ℕ) (α β : Type*) [PartialOrder α] [PartialOrder β] (h : Nonempty (α ≃o β)) : Nonempty (poset_tower α k ≃o poset_tower β k) := by  induction k using poset_tower.induct with  | case1 =>      rw [poset_tower.eq_1 α, poset_tower.eq_1 β]      change Nonempty (α ≃o β)      exact h  | case2 =>      rw [poset_tower.eq_2 α, poset_tower.eq_2 β]      change Nonempty (α ≃o β)      exact h  | case3 k hk ih =>      obtain ⟨eP⟩ := ih      obtain ⟨eA⟩ := h      rw [poset_tower.eq_3 α k hk, poset_tower.eq_3 β k hk]      exact ⟨op314_poset_tower_order_iso_converse_arrowOrderIso eP eA⟩
See it in the graphDiscuss this resultChallenge it