standard_example_reduction_min_max_subposet
Let P be a finite poset of height 2 and let (u, v) be a min-max incomparable pair in P. If d ≥ 3 and P is S_d-free, then the subposet induced by D_P(v) ∪ U_P(u) is S_{d-1}-free.
Statement
theorem standard_example_reduction_min_max_subposet {P : Type*} [Fintype P] [PartialOrder P] (hP : poset_height_two P) {u v : P} (h_uv : is_min_max_incomp_pair u v) {d : ℕ} (hd : 3 ≤ d) (h_free : is_standard_example_free P d) : is_standard_example_free {x : P // x ∈ poset_downset v ∪ poset_upset u} (d - 1)
- Formalizes
- arXiv:2610.24774 Section 3.3, Lemma 3.5
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- poset_upsetFor a poset P and an element u in P, the strict upset U_P(u) is the set of all elements y in P strictly greater than u.
- StandardExampleThe standard example S_k of order k is a type with k minimal elements and k maximal elements.
- poset_downsetFor a poset P and an element v in P, the strict downset D_P(v) is the set of all elements x in P strictly smaller than v.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - standard_example_partial_orderThe standard example of order k is a partial order under standard_example_le.
- is_min_max_incomp_pairA min-max incomparable pair (u, v) in a poset P consists of a minimal element u, a maximal element v, and u and v are incomparable.
- is_standard_example_freeA poset P is S_k-free when it does not contain the standard example S_k of order k as an induced subposet.
- poset_height_twoA poset has height two when it contains no chain of three elements.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
Read back from the Lean
Let $P$ be a finite partially ordered type.
Assume that $P$ has height at most two, in the sense that there do not exist elements $a, b, c \in P$ such that $a < b$ and $b < c$ (poset_height_two P).
Let $u, v \in P$ be such that $u$ is a minimal element of $P$, $v$ is a maximal element of $P$, and $u$ and $v$ are incomparable ($u \not\le v$ and $v \not\le u$).
Let $d$ be a natural number such that $3 \le d$.
Assume that $P$ is free of the standard example of size $d$ (is_standard_example_free P d), meaning there is no order embedding from StandardExample d into $P$.
Then the subposet of elements of $P$ that are strictly less than $v$ or strictly greater than $u$ (the subtype {x : P // x ∈ poset_downset v ∪ poset_upset u} under the induced order) is free of the standard example of size $d - 1$, meaning there is no order embedding from StandardExample (d - 1) into this subposet.
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
To show that the subposet induced by D_P(v) ∪ U_P(u) contains no induced standard example S_{d-1}, we argue by contradiction: any embedding f of S_{d-1} into this subposet can be extended to an embedding of S_d into P by sending the new minimal element to u and the new maximal element to v. Since P has height 2 and (u, v) is a min-max incomparable pair, the auxiliary lemmas guarantee that all original minimal elements embed strictly below v and all original maximal elements embed strictly above u, ensuring that the extended map strictly preserves and reflects all order relations of S_d.
In the subposet D_P(v) ∪ U_P(u), if x < y, then x < v.
By definition, x lies either in the downset of v or the upset of u. If x < v, the claim holds directly. If u < x, then together with x < y and y ∈ D_P(v) ∪ U_P(u), we would obtain a 3-element strictly increasing chain (u < x < y), which contradicts the height-2 assumption on P.
cases x.property with | inl hx => exact hx | inr hx => exfalso exact hP u x.val y.val ⟨hx, h⟩
In the subposet D_P(v) ∪ U_P(u), if x < y, then u < y.
The element y lies in the downset of v or the upset of u. If y < v, then x < y < v forms a 3-element strict chain in P, contradicting height 2. Thus y must lie in the upset of u, so u < y.
cases y.property with | inl hy => exfalso exact hP x.val y.val v ⟨h, hy⟩ | inr hy => exact hy
Any standard example embedding maps each minimal element into D_P(v).
Since k ≥ 2, Fin k is nontrivial, so for any index i there exists j ≠ i. In the standard example S_k, min i < max j whenever i ≠ j. Applying the order embedding gives f(min i) < f(max j) in the subposet. By our previous lemma, this implies f(min i) < v.
uses
lt_iff_le_and_nehave : Nontrivial (Fin k) := Fin.nontrivial_iff_two_le.mpr hk obtain ⟨j, hj⟩ := exists_ne i have h_lt : StandardExample.min i < StandardExample.max j := by rw [lt_iff_le_and_ne] refine ⟨hj.symm, fun h => by cases h⟩ have h_flt : f (StandardExample.min i) < f (StandardExample.max j) := (OrderEmbedding.lt_iff_lt f).mpr h_lt exact standard_example_reduction_min_max_subposet_subposet_lt_downset hP (Subtype.coe_lt_coe.mpr h_flt)
Any standard example embedding maps each maximal element into U_P(u).
Similarly, choosing i ≠ j gives min i < max j in S_k, so f(min i) < f(max j). By our earlier lemma, this forces u < f(max j).
uses
lt_iff_le_and_nehave : Nontrivial (Fin k) := Fin.nontrivial_iff_two_le.mpr hk obtain ⟨i, hi⟩ := exists_ne j have h_lt : StandardExample.min i < StandardExample.max j := by rw [lt_iff_le_and_ne] refine ⟨hi, fun h => by cases h⟩ have h_flt : f (StandardExample.min i) < f (StandardExample.max j) := (OrderEmbedding.lt_iff_lt f).mpr h_lt exact standard_example_reduction_min_max_subposet_subposet_lt_upset hP (Subtype.coe_lt_coe.mpr h_flt)
If x < v, then u is not less than or equal to x.
If u ≤ x, either u < x or u = x. If u < x, then u < x < v contradicts height 2. If u = x, then u < v, contradicting incomparability of u and v.
uses
lt_or_eq_of_leintro h rcases lt_or_eq_of_le h with hlt | heq · exact hP u x v ⟨hlt, hx⟩ · subst heq exact h_uv.2.2.1 hx.le
If x < v, then x is not less than or equal to u.
If x ≤ u, then since u is minimal, u ≤ x, so x = u by antisymmetry. But then u < v, contradicting incomparability of u and v.
uses
le_antisymmintro h have hu : u ≤ x := h_uv.1 h have heq : x = u := le_antisymm h hu subst heq exact h_uv.2.2.1 hx.le
If u < y, then y is not less than or equal to v.
If y ≤ v, either y < v (yielding u < y < v, contradiction to height 2) or y = v (giving u < v, contradiction to incomparability).
uses
lt_or_eq_of_leintro h rcases lt_or_eq_of_le h with hlt | heq · exact hP u y v ⟨hy, hlt⟩ · subst heq exact h_uv.2.2.1 hy.le
If u < y, then v is not less than or equal to y.
If v ≤ y, then since v is maximal, y ≤ v, so y = v by antisymmetry. This implies u < v, contradicting incomparability.
uses
le_antisymmintro h have hv : y ≤ v := h_uv.2.1 h have heq : y = v := le_antisymm hv h subst heq exact h_uv.2.2.1 hy.le
The extended embedding maps the last minimal element to u.
Evaluating the extension at the last index yields u by definition of Fin.lastCases.
uses
Fin.lastCases_lastdsimp [standard_example_reduction_min_max_subposet_embed_elem]; rw [Fin.lastCases_last]
The extended embedding maps earlier minimal elements through f.
Evaluating at castSucc i yields f(min i) by the castSucc branch of Fin.lastCases.
uses
Fin.lastCases_castSuccdsimp [standard_example_reduction_min_max_subposet_embed_elem]; rw [Fin.lastCases_castSucc]
The extended embedding maps the last maximal element to v.
Evaluating at the last index yields v by Fin.lastCases.
uses
Fin.lastCases_lastdsimp [standard_example_reduction_min_max_subposet_embed_elem]; rw [Fin.lastCases_last]
The extended embedding maps earlier maximal elements through f.
Evaluating at castSucc j yields f(max j) by Fin.lastCases.
uses
Fin.lastCases_castSuccdsimp [standard_example_reduction_min_max_subposet_embed_elem]; rw [Fin.lastCases_castSucc]
Order preservation between pairs of minimal elements in S_{k+1}.
By case analysis on whether each element is the last index or an earlier one: u ≤ u holds trivially; u cannot be ≤ f(min i') and f(min i) cannot be ≤ u by our incomparability lemmas; and between two earlier elements, f preserves the order because f is an order embedding.
uses
iff_of_true,iff_of_false,le_rfl,Subtype.coe_le_coe,OrderEmbedding.le_iff_lercases a with i | j <;> rcases b with i' | j' · induction i using Fin.lastCases with | last => induction i' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_last] exact iff_of_true le_rfl rfl | cast i' => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_last, standard_example_reduction_min_max_subposet_embed_elem_min_cast] exact iff_of_false (standard_example_reduction_min_max_subposet_not_u_le_min hP h_uv (standard_example_reduction_min_max_subposet_min_lt_v hP hk f i')) (Fin.castSucc_lt_last i').ne' | cast i => induction i' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_last, standard_example_reduction_min_max_subposet_embed_elem_min_cast] exact iff_of_false (standard_example_reduction_min_max_subposet_not_min_le_u h_uv (standard_example_reduction_min_max_subposet_min_lt_v hP hk f i)) (Fin.castSucc_lt_last i).ne | cast i' => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_cast] rw [Subtype.coe_le_coe, OrderEmbedding.le_iff_le] exact Fin.castSucc_inj.symm
Order preservation between minimal and maximal elements in S_{k+1}.
For the pair of last indices, u ≤ v fails, matching (last ≤ last) being false in S_{k+1}. For u and f(max j'), u < f(max j') holds, matching last ≠ j'. For f(min i) and v, f(min i) < v holds, matching i ≠ last. For earlier indices, the relation holds iff i ≠ j, preserving the embedding property of f.
uses
iff_of_true,iff_of_false,Subtype.coe_le_coe,OrderEmbedding.le_iff_le· induction i using Fin.lastCases with | last => induction j' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_last, standard_example_reduction_min_max_subposet_embed_elem_max_last] exact iff_of_false h_uv.2.2.1 (not_not.mpr rfl) | cast j' => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_last, standard_example_reduction_min_max_subposet_embed_elem_max_cast] exact iff_of_true (standard_example_reduction_min_max_subposet_u_lt_max hP hk f j').le (Fin.castSucc_lt_last j').ne' | cast i => induction j' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_cast, standard_example_reduction_min_max_subposet_embed_elem_max_last] exact iff_of_true (standard_example_reduction_min_max_subposet_min_lt_v hP hk f i).le (Fin.castSucc_lt_last i).ne | cast j' => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_cast, standard_example_reduction_min_max_subposet_embed_elem_max_cast] rw [Subtype.coe_le_coe, OrderEmbedding.le_iff_le] exact Fin.castSucc_inj.ne.symm
Order reflection between maximal and minimal elements in S_{k+1}.
No maximal element can be ≤ a minimal element in S_{k+1}, and correspondingly no mapped maximal element can be ≤ a mapped minimal element in P because v ≰ u, and transitivity would contradict strict inequalities or incomparability.
uses
iff_of_false,lt_irrefl,lt_of_le_of_lt,lt_of_lt_of_le,Subtype.coe_le_coe,OrderEmbedding.le_iff_le· induction j using Fin.lastCases with | last => induction i' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_last, standard_example_reduction_min_max_subposet_embed_elem_min_last] exact iff_of_false h_uv.2.2.2 id | cast i' => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_last, standard_example_reduction_min_max_subposet_embed_elem_min_cast] have hlt := standard_example_reduction_min_max_subposet_min_lt_v hP hk f i' exact iff_of_false (fun hle => lt_irrefl _ (lt_of_le_of_lt hle hlt)) id | cast j => induction i' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_cast, standard_example_reduction_min_max_subposet_embed_elem_min_last] have hlt := standard_example_reduction_min_max_subposet_u_lt_max hP hk f j exact iff_of_false (fun hle => lt_irrefl _ (lt_of_lt_of_le hlt hle)) id | cast i' => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_cast, standard_example_reduction_min_max_subposet_embed_elem_min_cast] rw [Subtype.coe_le_coe, OrderEmbedding.le_iff_le] rfl
Order preservation between pairs of maximal elements in S_{k+1}.
Case analysis on the indices: v ≤ v holds; neither v ≤ f(max j') nor f(max j) ≤ v can hold; and between earlier elements f preserves the discrete order between maximal elements.
uses
iff_of_true,iff_of_false,le_rfl,Subtype.coe_le_coe,OrderEmbedding.le_iff_le· induction j using Fin.lastCases with | last => induction j' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_last] exact iff_of_true le_rfl rfl | cast j' => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_last, standard_example_reduction_min_max_subposet_embed_elem_max_cast] exact iff_of_false (standard_example_reduction_min_max_subposet_not_v_le_max h_uv (standard_example_reduction_min_max_subposet_u_lt_max hP hk f j')) (Fin.castSucc_lt_last j').ne' | cast j => induction j' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_last, standard_example_reduction_min_max_subposet_embed_elem_max_cast] exact iff_of_false (standard_example_reduction_min_max_subposet_not_max_le_v hP h_uv (standard_example_reduction_min_max_subposet_u_lt_max hP hk f j)) (Fin.castSucc_lt_last j).ne | cast j' => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_cast] rw [Subtype.coe_le_coe, OrderEmbedding.le_iff_le] exact Fin.castSucc_inj.symm
The subposet D_P(v) ∪ U_P(u) is S_{d-1}-free.
Writing d = k + 1 with k ≥ 2, any standard example embedding f : S_k ↪o D_P(v) ∪ U_P(u) extends to an embedding g : S_{k+1} ↪o P by mapping the extra minimal and maximal elements to u and v respectively. Since P is S_d-free, no such embedding g can exist, so no f exists.
uses
OrderEmbedding.ofMapLEIff,Nat.sub_add_cancelobtain ⟨k, hk, rfl⟩ : ∃ k ≥ 2, d = k + 1 := ⟨d - 1, by omega, (Nat.sub_add_cancel (by omega)).symm⟩ change IsEmpty (StandardExample k ↪o {x : P // x ∈ poset_downset v ∪ poset_upset u}) refine ⟨fun f => ?_⟩ have g : StandardExample (k + 1) ↪o P := OrderEmbedding.ofMapLEIff (standard_example_reduction_min_max_subposet_embed_elem f) (standard_example_reduction_min_max_subposet_embed_elem_le_iff hP h_uv hk f) exact h_free.false g
lt_irrefl- No element can be strictly less than itself in a strict pre-order.
lt_of_le_of_lt- Transitivity of strict and non-strict inequality: if a ≤ b and b < c, then a < c.
lt_of_lt_of_le- Transitivity of strict and non-strict inequality: if a < b and b ≤ c, then a < c.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
OrderEmbedding.ofMapLEIff- An order embedding can be constructed from a map that preserves and reflects the order relation ≤.
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.
lemma standard_example_reduction_min_max_subposet_subposet_lt_downset {P : Type*} [PartialOrder P] (hP : poset_height_two P) {u v : P} {x y : {x : P // x ∈ poset_downset v ∪ poset_upset u}} (h : x.val < y.val) : x.val < v := by cases x.property with | inl hx => exact hx | inr hx => exfalso exact hP u x.val y.val ⟨hx, h⟩lemma standard_example_reduction_min_max_subposet_subposet_lt_upset {P : Type*} [PartialOrder P] (hP : poset_height_two P) {u v : P} {x y : {x : P // x ∈ poset_downset v ∪ poset_upset u}} (h : x.val < y.val) : u < y.val := by cases y.property with | inl hy => exfalso exact hP x.val y.val v ⟨h, hy⟩ | inr hy => exact hylemma standard_example_reduction_min_max_subposet_min_lt_v {P : Type*} [PartialOrder P] (hP : poset_height_two P) {u v : P} {k : ℕ} (hk : 2 ≤ k) (f : StandardExample k ↪o {x : P // x ∈ poset_downset v ∪ poset_upset u}) (i : Fin k) : (f (StandardExample.min i)).val < v := by have : Nontrivial (Fin k) := Fin.nontrivial_iff_two_le.mpr hk obtain ⟨j, hj⟩ := exists_ne i have h_lt : StandardExample.min i < StandardExample.max j := by rw [lt_iff_le_and_ne] refine ⟨hj.symm, fun h => by cases h⟩ have h_flt : f (StandardExample.min i) < f (StandardExample.max j) := (OrderEmbedding.lt_iff_lt f).mpr h_lt exact standard_example_reduction_min_max_subposet_subposet_lt_downset hP (Subtype.coe_lt_coe.mpr h_flt)lemma standard_example_reduction_min_max_subposet_u_lt_max {P : Type*} [PartialOrder P] (hP : poset_height_two P) {u v : P} {k : ℕ} (hk : 2 ≤ k) (f : StandardExample k ↪o {x : P // x ∈ poset_downset v ∪ poset_upset u}) (j : Fin k) : u < (f (StandardExample.max j)).val := by have : Nontrivial (Fin k) := Fin.nontrivial_iff_two_le.mpr hk obtain ⟨i, hi⟩ := exists_ne j have h_lt : StandardExample.min i < StandardExample.max j := by rw [lt_iff_le_and_ne] refine ⟨hi, fun h => by cases h⟩ have h_flt : f (StandardExample.min i) < f (StandardExample.max j) := (OrderEmbedding.lt_iff_lt f).mpr h_lt exact standard_example_reduction_min_max_subposet_subposet_lt_upset hP (Subtype.coe_lt_coe.mpr h_flt)lemma standard_example_reduction_min_max_subposet_not_u_le_min {P : Type*} [PartialOrder P] (hP : poset_height_two P) {u v : P} (h_uv : is_min_max_incomp_pair u v) {x : P} (hx : x < v) : ¬ u ≤ x := by intro h rcases lt_or_eq_of_le h with hlt | heq · exact hP u x v ⟨hlt, hx⟩ · subst heq exact h_uv.2.2.1 hx.lelemma standard_example_reduction_min_max_subposet_not_min_le_u {P : Type*} [PartialOrder P] {u v : P} (h_uv : is_min_max_incomp_pair u v) {x : P} (hx : x < v) : ¬ x ≤ u := by intro h have hu : u ≤ x := h_uv.1 h have heq : x = u := le_antisymm h hu subst heq exact h_uv.2.2.1 hx.lelemma standard_example_reduction_min_max_subposet_not_max_le_v {P : Type*} [PartialOrder P] (hP : poset_height_two P) {u v : P} (h_uv : is_min_max_incomp_pair u v) {y : P} (hy : u < y) : ¬ y ≤ v := by intro h rcases lt_or_eq_of_le h with hlt | heq · exact hP u y v ⟨hy, hlt⟩ · subst heq exact h_uv.2.2.1 hy.lelemma standard_example_reduction_min_max_subposet_not_v_le_max {P : Type*} [PartialOrder P] {u v : P} (h_uv : is_min_max_incomp_pair u v) {y : P} (hy : u < y) : ¬ v ≤ y := by intro h have hv : y ≤ v := h_uv.2.1 h have heq : y = v := le_antisymm hv h subst heq exact h_uv.2.2.1 hy.ledef standard_example_reduction_min_max_subposet_embed_elem {P : Type*} [PartialOrder P] {u v : P} {k : ℕ} (f : StandardExample k ↪o {x : P // x ∈ poset_downset v ∪ poset_upset u}) : StandardExample (k + 1) → P | StandardExample.min i => Fin.lastCases u (fun i' => (f (StandardExample.min i')).val) i | StandardExample.max j => Fin.lastCases v (fun j' => (f (StandardExample.max j')).val) j@[simp] lemma standard_example_reduction_min_max_subposet_embed_elem_min_last {P : Type*} [PartialOrder P] {u v : P} {k : ℕ} (f : StandardExample k ↪o {x : P // x ∈ poset_downset v ∪ poset_upset u}) : standard_example_reduction_min_max_subposet_embed_elem f (StandardExample.min (Fin.last k)) = u := by dsimp [standard_example_reduction_min_max_subposet_embed_elem]; rw [Fin.lastCases_last]@[simp] lemma standard_example_reduction_min_max_subposet_embed_elem_min_cast {P : Type*} [PartialOrder P] {u v : P} {k : ℕ} (f : StandardExample k ↪o {x : P // x ∈ poset_downset v ∪ poset_upset u}) (i : Fin k) : standard_example_reduction_min_max_subposet_embed_elem f (StandardExample.min i.castSucc) = (f (StandardExample.min i)).val := by dsimp [standard_example_reduction_min_max_subposet_embed_elem]; rw [Fin.lastCases_castSucc]@[simp] lemma standard_example_reduction_min_max_subposet_embed_elem_max_last {P : Type*} [PartialOrder P] {u v : P} {k : ℕ} (f : StandardExample k ↪o {x : P // x ∈ poset_downset v ∪ poset_upset u}) : standard_example_reduction_min_max_subposet_embed_elem f (StandardExample.max (Fin.last k)) = v := by dsimp [standard_example_reduction_min_max_subposet_embed_elem]; rw [Fin.lastCases_last]@[simp] lemma standard_example_reduction_min_max_subposet_embed_elem_max_cast {P : Type*} [PartialOrder P] {u v : P} {k : ℕ} (f : StandardExample k ↪o {x : P // x ∈ poset_downset v ∪ poset_upset u}) (j : Fin k) : standard_example_reduction_min_max_subposet_embed_elem f (StandardExample.max j.castSucc) = (f (StandardExample.max j)).val := by dsimp [standard_example_reduction_min_max_subposet_embed_elem]; rw [Fin.lastCases_castSucc]lemma standard_example_reduction_min_max_subposet_embed_elem_le_iff {P : Type*} [PartialOrder P] (hP : poset_height_two P) {u v : P} (h_uv : is_min_max_incomp_pair u v) {k : ℕ} (hk : 2 ≤ k) (f : StandardExample k ↪o {x : P // x ∈ poset_downset v ∪ poset_upset u}) (a b : StandardExample (k + 1)) : standard_example_reduction_min_max_subposet_embed_elem f a ≤ standard_example_reduction_min_max_subposet_embed_elem f b ↔ a ≤ b := by rcases a with i | j <;> rcases b with i' | j' · induction i using Fin.lastCases with | last => induction i' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_last] exact iff_of_true le_rfl rfl | cast i' => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_last, standard_example_reduction_min_max_subposet_embed_elem_min_cast] exact iff_of_false (standard_example_reduction_min_max_subposet_not_u_le_min hP h_uv (standard_example_reduction_min_max_subposet_min_lt_v hP hk f i')) (Fin.castSucc_lt_last i').ne' | cast i => induction i' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_last, standard_example_reduction_min_max_subposet_embed_elem_min_cast] exact iff_of_false (standard_example_reduction_min_max_subposet_not_min_le_u h_uv (standard_example_reduction_min_max_subposet_min_lt_v hP hk f i)) (Fin.castSucc_lt_last i).ne | cast i' => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_cast] rw [Subtype.coe_le_coe, OrderEmbedding.le_iff_le] exact Fin.castSucc_inj.symm · induction i using Fin.lastCases with | last => induction j' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_last, standard_example_reduction_min_max_subposet_embed_elem_max_last] exact iff_of_false h_uv.2.2.1 (not_not.mpr rfl) | cast j' => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_last, standard_example_reduction_min_max_subposet_embed_elem_max_cast] exact iff_of_true (standard_example_reduction_min_max_subposet_u_lt_max hP hk f j').le (Fin.castSucc_lt_last j').ne' | cast i => induction j' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_cast, standard_example_reduction_min_max_subposet_embed_elem_max_last] exact iff_of_true (standard_example_reduction_min_max_subposet_min_lt_v hP hk f i).le (Fin.castSucc_lt_last i).ne | cast j' => simp only [standard_example_reduction_min_max_subposet_embed_elem_min_cast, standard_example_reduction_min_max_subposet_embed_elem_max_cast] rw [Subtype.coe_le_coe, OrderEmbedding.le_iff_le] exact Fin.castSucc_inj.ne.symm · induction j using Fin.lastCases with | last => induction i' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_last, standard_example_reduction_min_max_subposet_embed_elem_min_last] exact iff_of_false h_uv.2.2.2 id | cast i' => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_last, standard_example_reduction_min_max_subposet_embed_elem_min_cast] have hlt := standard_example_reduction_min_max_subposet_min_lt_v hP hk f i' exact iff_of_false (fun hle => lt_irrefl _ (lt_of_le_of_lt hle hlt)) id | cast j => induction i' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_cast, standard_example_reduction_min_max_subposet_embed_elem_min_last] have hlt := standard_example_reduction_min_max_subposet_u_lt_max hP hk f j exact iff_of_false (fun hle => lt_irrefl _ (lt_of_lt_of_le hlt hle)) id | cast i' => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_cast, standard_example_reduction_min_max_subposet_embed_elem_min_cast] rw [Subtype.coe_le_coe, OrderEmbedding.le_iff_le] rfl · induction j using Fin.lastCases with | last => induction j' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_last] exact iff_of_true le_rfl rfl | cast j' => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_last, standard_example_reduction_min_max_subposet_embed_elem_max_cast] exact iff_of_false (standard_example_reduction_min_max_subposet_not_v_le_max h_uv (standard_example_reduction_min_max_subposet_u_lt_max hP hk f j')) (Fin.castSucc_lt_last j').ne' | cast j => induction j' using Fin.lastCases with | last => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_last, standard_example_reduction_min_max_subposet_embed_elem_max_cast] exact iff_of_false (standard_example_reduction_min_max_subposet_not_max_le_v hP h_uv (standard_example_reduction_min_max_subposet_u_lt_max hP hk f j)) (Fin.castSucc_lt_last j).ne | cast j' => simp only [standard_example_reduction_min_max_subposet_embed_elem_max_cast] rw [Subtype.coe_le_coe, OrderEmbedding.le_iff_le] exact Fin.castSucc_inj.symm/-- Standard example reduction in min-max downset-upset subposets (Lemma 3.5). -/theorem standard_example_reduction_min_max_subposet {P : Type*} [Fintype P] [PartialOrder P] (hP : poset_height_two P) {u v : P} (h_uv : is_min_max_incomp_pair u v) {d : ℕ} (hd : 3 ≤ d) (h_free : is_standard_example_free P d) : is_standard_example_free {x : P // x ∈ poset_downset v ∪ poset_upset u} (d - 1) := by obtain ⟨k, hk, rfl⟩ : ∃ k ≥ 2, d = k + 1 := ⟨d - 1, by omega, (Nat.sub_add_cancel (by omega)).symm⟩ change IsEmpty (StandardExample k ↪o {x : P // x ∈ poset_downset v ∪ poset_upset u}) refine ⟨fun f => ?_⟩ have g : StandardExample (k + 1) ↪o P := OrderEmbedding.ofMapLEIff (standard_example_reduction_min_max_subposet_embed_elem f) (standard_example_reduction_min_max_subposet_embed_elem_le_iff hP h_uv hk f) exact h_free.false g