op314_poset_tower_order_iso_converse
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.
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.
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
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.
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
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).
uses
op314_poset_tower_order_iso_converse_arrowInv_apply,op314_poset_tower_order_iso_converse_arrowFun_applyprivate 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]
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).
uses
op314_poset_tower_order_iso_converse_arrowFun_apply,op314_poset_tower_order_iso_converse_arrowInv_applyprivate 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]
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.
uses
OrderHom.le_def,op314_poset_tower_order_iso_converse_arrowFun_applyprivate 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)
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.
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
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.
uses
poset_tower.eq_2| case2 => rw [poset_tower.eq_2 α, poset_tower.eq_2 β] change Nonempty (α ≃o β) exact hFor 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.
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.
- The custom induction principle `poset_tower.induct` splits into three cases (height 0, height 1, and successor of a non-zero height), matching the definition of `poset_tower`.
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.
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⟩