Documentation

InfinitaryLogic.Methods.WellOrdering.Descent

Generic relation lemmas for the boundedness corollaries (issue #12, step 6 layer 1) #

Pure order-theoretic consequences of the raw positive conclusion RelPreserving, with no model extraction involved:

theorem FirstOrder.Language.RelPreserving.injective_of_irreflexive {L : Language} {M : Type} [L.Structure M] {lt : L.Relations 2} {f : M} (hf : RelPreserving lt f) (hirr : ∀ (x : M), ¬Structure.RelMap lt ![x, x]) :

Derived injectivity: a relation-preserving map from into a structure whose interpreted relation is irreflexive is injective — if q < r collided, preservation would put the collision point below itself.

theorem FirstOrder.Language.RelPreserving.descending {L : Language} {M : Type} [L.Structure M] {lt : L.Relations 2} {f : M} (hf : RelPreserving lt f) (n : ) :
Structure.RelMap lt ![f (-↑(n + 1)), f (-n)]

The descending sequence: the negative rationals turn a relation-preserving map into an infinite strictly descending sequence for the interpreted relation.

theorem FirstOrder.Language.not_descending_of_wellFounded {α : Type u_1} {r : ααProp} (hwf : WellFounded r) (g : α) :
¬∀ (n : ), r (g (n + 1)) (g n)

A well-founded relation admits no infinite descending sequence (direct, via WellFounded.has_min — no strict-order hypotheses on the relation).

theorem FirstOrder.Language.not_relPreserving_of_wellFounded {L : Language} {M : Type} [L.Structure M] {lt : L.Relations 2} (hwf : WellFounded fun (x y : M) => Structure.RelMap lt ![x, y]) (f : M) :

No relation-preserving map into a well-founded relation: the target of the step-5 theorem can never have a well-founded interpreted relation.