Zulip Chat Archive
Stream: general
Topic: How can I finish this instance of `PartialOrder`?
Santiago Mourenza Rivero (Apr 03 2024 at 16:33):
In order to prove that Zorn's Lemma implies the Well-Ordering Principle, I need to demonstrate that a set F is inductive. To do this, I have to define a WellOrderedSet
structure and F
as a set of this type. Now, in order to find an upper bound, I have to order the elements of F
, and for this, I must create an instance of PartialOrder
, but I am unable to complete the proof. I will leave here what I have so far:
import Mathlib.Tactic
import Mathlib.Init.Order.Defs
variable (α : Type _) [PartialOrder α]
variable (γ : Type _)
variable {β I : Type _}
variable (X : I → Set γ)
variable (S : Set γ )
open Set
open Classical
def is_chain [PartialOrder γ] (c : Set γ) : Prop := ∀ (x y : γ), x ∈ c → y ∈ c → x ≤ y ∨ y ≤ x
def is_well_ordered (R : γ → γ → Prop) : Prop := ∀ (A : Set γ), Nonempty A → ∃ n ∈ A, ∀ m ∈ A, R n m
def well_ordered_principle : Prop := ∃ (R : γ → γ → Prop), is_well_ordered γ R
variable {γ}
def axiom_of_choice : Prop := (∀ (i : I), Nonempty (X i)) → ∃ (f : (I → ⋃ i, X i)), ∀ (i : I), (f i).1 ∈ X i
--def inductive_set (S : Set α) : Prop := ∀ (c : Set α), c ⊆ S → (∀ (x y : α), x ∈ c → y ∈ c → x ≤ y ∨ y ≤ x) → ∃ (ub : α), ∀ (x : α), x ∈ c → x ≤ ub
def inductive_set [PartialOrder γ] (S : Set γ) : Prop := ∀ (c : Set γ), c ⊆ S → is_chain γ c → ∃ (ub : γ), ∀ (x : γ ), x ∈ c → x ≤ ub
def zorn [PartialOrder γ] (_ : inductive_set S ) : Prop := ∃ (m : γ), m ∈ S ∧ ∀ (x : γ), x ∈ S → x < m
structure WellOrderedSet (γ : Type _) :=
(s : Set γ)
(r : s → s → Prop)
(h_well : is_well_ordered s r)
variable (F : Set (WellOrderedSet γ))
instance : PartialOrder (WellOrderedSet γ) where
le := fun x y => x.s ⊆ y.s ∧ ∀ (a b), (ha : a ∈ x.s) → (ha' : a ∈ y.s) → (hb : b ∈ x.s) → (hb' : b ∈ y.s) → x.r ⟨a,ha⟩ ⟨b,hb⟩ → y.r ⟨a,ha'⟩ ⟨b,hb'⟩
lt := fun x y => x.s ⊂ y.s ∧ (∀ (a b), (ha : a ∈ x.s) → (ha' : a ∈ y.s) → (hb : b ∈ x.s) → (hb' : b ∈ y.s) → x.r ⟨a,ha⟩ ⟨b,hb⟩ → y.r ⟨a,ha'⟩ ⟨b,hb'⟩)
le_refl := by
intro x
simp only [imp_self, implies_true]
apply And.intro
. apply Set.Subset.refl
trivial
le_trans := by
intro x y z hxy hyz
dsimp at *
apply And.intro
. apply Set.Subset.trans (And.left hxy) (And.left hyz)
intro a b ha ha' hb hb' hxr
apply And.right hyz a b (And.left hxy ha) ha' (And.left hxy hb) hb'
exact And.right hxy a b ha (And.left hxy ha) hb (And.left hxy hb) hxr
lt_iff_le_not_le := by
intro x y
apply Iff.intro
. intro h
apply And.intro
. apply And.intro
. simp at h
exact And.left h.1
intro a b ha ha' hb hb' hxr
simp at h
exact And.right h a b ha (And.left h.1 ha) hb (And.left h.1 hb) hxr
intro h_le_yx
have not_h_s := And.right (And.left h)
have h_s := And.left h_le_yx
contradiction
intro h
apply And.intro
. have le_xy := h.1.1
have lt_xy := h.2
dsimp at lt_xy
rw[not_and_or] at lt_xy
apply HasSubset.Subset.ssubset_of_not_subset
apply le_xy
apply Or.elim lt_xy
. intro this
exact this
sorry
exact h.1.2
le_antisymm := by
intro x y le_xy le_yx
have s_eq : x.s = y.s := Set.Subset.antisymm le_xy.1 le_yx.1
have r_eq : ∀ a b, a ∈ x.s → b ∈ x.s → (x.r a b ↔ y.r a b) := by
intro a b ha hb
apply Iff.intro
. intro h
exact le_xy.2 a b ha hb h
exact le_yx.2 a b (le_xy.1 ha) (le_xy.1 hb)
rcases x with ⟨x.s,x.r⟩
rcases y with ⟨y.s,y.r⟩
simp at *
congr
apply And.intro
exact s_eq
sorry
If I manage to make progress in any aspect, I will update the information accordingly.
Last updated: May 02 2025 at 03:31 UTC