Documentation

Mathlib.Order.OrderIsoNat

Relation embeddings from the naturals #

This file allows translation from monotone functions ℕ → α→ α to order embeddings ℕ ↪ α↪ α and defines the limit value of an eventually-constant sequence.

Main declarations #

def RelEmbedding.natLt {α : Type u_1} {r : ααProp} [inst : IsStrictOrder α r] (f : α) (H : (n : ) → r (f n) (f (n + 1))) :
(fun x x_1 => x < x_1) ↪r r

If f is a strictly r-increasing sequence, then this returns f as an order embedding.

Equations
@[simp]
theorem RelEmbedding.coe_natLt {α : Type u_1} {r : ααProp} [inst : IsStrictOrder α r] {f : α} {H : (n : ) → r (f n) (f (n + 1))} :
(RelEmbedding.natLt f H).toEmbedding = f
def RelEmbedding.natGt {α : Type u_1} {r : ααProp} [inst : IsStrictOrder α r] (f : α) (H : (n : ) → r (f (n + 1)) (f n)) :
(fun x x_1 => x > x_1) ↪r r

If f is a strictly r-decreasing sequence, then this returns f as an order embedding.

Equations
@[simp]
theorem RelEmbedding.coe_natGt {α : Type u_1} {r : ααProp} [inst : IsStrictOrder α r] {f : α} {H : (n : ) → r (f (n + 1)) (f n)} :
(RelEmbedding.natGt f H).toEmbedding = f
theorem RelEmbedding.exists_not_acc_lt_of_not_acc {α : Type u_1} {a : α} {r : ααProp} (h : ¬Acc r a) :
b, ¬Acc r b r b a
theorem RelEmbedding.acc_iff_no_decreasing_seq {α : Type u_1} {r : ααProp} [inst : IsStrictOrder α r] {x : α} :
Acc r x IsEmpty { f // x Set.range f.toEmbedding }

A value is accessible iff it isn't contained in any infinite decreasing sequence.

theorem RelEmbedding.not_acc_of_decreasing_seq {α : Type u_1} {r : ααProp} [inst : IsStrictOrder α r] (f : (fun x x_1 => x > x_1) ↪r r) (k : ) :
¬Acc r (f.toEmbedding k)
theorem RelEmbedding.wellFounded_iff_no_descending_seq {α : Type u_1} {r : ααProp} [inst : IsStrictOrder α r] :
WellFounded r IsEmpty ((fun x x_1 => x > x_1) ↪r r)

A relation is well-founded iff it doesn't have any infinite decreasing sequence.

theorem RelEmbedding.not_wellFounded_of_decreasing_seq {α : Type u_1} {r : ααProp} [inst : IsStrictOrder α r] (f : (fun x x_1 => x > x_1) ↪r r) :
def Nat.orderEmbeddingOfSet (s : Set ) [inst : Infinite s] [inst : DecidablePred fun x => x s] :

An order embedding from to itself with a specified range

Equations
  • One or more equations did not get rendered due to their size.
noncomputable def Nat.Subtype.orderIsoOfNat (s : Set ) [inst : Infinite s] :
≃o s

Nat.Subtype.ofNat as an order isomorphism between and an infinite subset. See also Nat.Nth for a version where the subset may be finite.

Equations
  • One or more equations did not get rendered due to their size.
@[simp]
theorem Nat.coe_orderEmbeddingOfSet {s : Set } [inst : Infinite s] [inst : DecidablePred fun x => x s] :
(Nat.orderEmbeddingOfSet s).toEmbedding = Subtype.val Nat.Subtype.ofNat s
theorem Nat.orderEmbeddingOfSet_apply {s : Set } [inst : Infinite s] [inst : DecidablePred fun x => x s] {n : } :
(Nat.orderEmbeddingOfSet s).toEmbedding n = ↑(Nat.Subtype.ofNat s n)
@[simp]
theorem Nat.Subtype.orderIsoOfNat_apply {s : Set } [inst : Infinite s] [dP : DecidablePred fun x => x s] {n : } :
theorem Nat.orderEmbeddingOfSet_range (s : Set ) [inst : Infinite s] [inst : DecidablePred fun x => x s] :
Set.range (Nat.orderEmbeddingOfSet s).toEmbedding = s
theorem Nat.exists_subseq_of_forall_mem_union {α : Type u_1} {s : Set α} {t : Set α} (e : α) (he : ∀ (n : ), e n s t) :
g, (∀ (n : ), e (g.toEmbedding n) s) ∀ (n : ), e (g.toEmbedding n) t
theorem exists_increasing_or_nonincreasing_subseq' {α : Type u_1} (r : ααProp) (f : α) :
g, ((n : ) → r (f (g.toEmbedding n)) (f (g.toEmbedding (n + 1)))) ∀ (m n : ), m < n¬r (f (g.toEmbedding m)) (f (g.toEmbedding n))
theorem exists_increasing_or_nonincreasing_subseq {α : Type u_1} (r : ααProp) [inst : IsTrans α r] (f : α) :
g, ((m n : ) → m < nr (f (g.toEmbedding m)) (f (g.toEmbedding n))) ∀ (m n : ), m < n¬r (f (g.toEmbedding m)) (f (g.toEmbedding n))

This is the infinitary Erdős–Szekeres theorem, and an important lemma in the usual proof of Bolzano-Weierstrass for .

theorem WellFounded.monotone_chain_condition' {α : Type u_1} [inst : Preorder α] :
(WellFounded fun x x_1 => x > x_1) ∀ (a : →o α), n, ∀ (m : ), n m¬a n < a m
theorem WellFounded.monotone_chain_condition {α : Type u_1} [inst : PartialOrder α] :
(WellFounded fun x x_1 => x > x_1) ∀ (a : →o α), n, ∀ (m : ), n ma n = a m

The "monotone chain condition" below is sometimes a convenient form of well foundedness.

noncomputable def monotonicSequenceLimitIndex {α : Type u_1} [inst : Preorder α] (a : →o α) :

Given an eventually-constant monotone sequence a₀ ≤ a₁ ≤ a₂ ≤ ...≤ a₁ ≤ a₂ ≤ ...≤ a₂ ≤ ...≤ ... in a partially-ordered type, monotonicSequenceLimitIndex a is the least natural number n for which aₙ reaches the constant value. For sequences that are not eventually constant, monotonicSequenceLimitIndex a is defined, but is a junk value.

Equations
noncomputable def monotonicSequenceLimit {α : Type u_1} [inst : Preorder α] (a : →o α) :
α

The constant value of an eventually-constant monotone sequence a₀ ≤ a₁ ≤ a₂ ≤ ...≤ a₁ ≤ a₂ ≤ ...≤ a₂ ≤ ...≤ ... in a partially-ordered type.

Equations
theorem WellFounded.supᵢ_eq_monotonicSequenceLimit {α : Type u_1} [inst : CompleteLattice α] (h : WellFounded fun x x_1 => x > x_1) (a : →o α) :