Rewriting System

term/formula morphisms such as Rewritings, substitutions, and embeddings are handled by the structure LO.FirstOrder.Rew.

• LO.FirstOrder.Rew.rewrite f is a Rewriting of the free variables occurring in the term by f : ξ₁ → Semiterm L ξ₂ n.
• LO.FirstOrder.Rew.substs v is a substitution of the bounded variables occurring in the term by v : Fin n → Semiterm L ξ n'.
• LO.FirstOrder.Rew.bShift is a transformation of the bounded variables occurring in the term by #x ↦ #(Fin.succ x).
• LO.FirstOrder.Rew.shift is a transformation of the free variables occurring in the term by &x ↦ &(x + 1).
• LO.FirstOrder.Rew.emb is a embedding of the term with no free variables.

Rewritings LO.FirstOrder.Rew is naturally converted to formula Rewritings by LO.FirstOrder.Rew.hom.

structure LO.FirstOrder.Rew (L : Language) (ξ₁ : Type u_1) (n₁ : ℕ) (ξ₂ : Type u_2) (n₂ : ℕ) : Type (max (max u_1 u_2) u_3)

• toFun : Semiterm L ξ₁ n₁ → Semiterm L ξ₂ n₂
• func' {k : ℕ} (f : L.Func k) (v : Fin k → Semiterm L ξ₁ n₁) : self.toFun (Semiterm.func f v) = Semiterm.func f fun (i : Fin k) => self.toFun (v i)

Instances For

• LO.FirstOrder.Rew.instCoeFunForallSemiterm
• LO.FirstOrder.Rew.instFunLikeSemiterm

@[reducible, inline]

abbrev LO.FirstOrder.SyntacticRew (L : Language) (n₁ n₂ : ℕ) : Type u_1

Equations

• LO.FirstOrder.SyntacticRew L n₁ n₂ = LO.FirstOrder.Rew L ℕ n₁ ℕ n₂

instance LO.FirstOrder.Rew.instFunLikeSemiterm {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} : FunLike (Rew L ξ₁ n₁ ξ₂ n₂) (Semiterm L ξ₁ n₁) (Semiterm L ξ₂ n₂)

Equations

• LO.FirstOrder.Rew.instFunLikeSemiterm = { coe := fun (f : LO.FirstOrder.Rew L ξ₁ n₁ ξ₂ n₂) => f.toFun, coe_injective' := ⋯ }

instance LO.FirstOrder.Rew.instCoeFunForallSemiterm {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} : CoeFun (Rew L ξ₁ n₁ ξ₂ n₂) fun (x : Rew L ξ₁ n₁ ξ₂ n₂) => Semiterm L ξ₁ n₁ → Semiterm L ξ₂ n₂

Equations

• LO.FirstOrder.Rew.instCoeFunForallSemiterm = DFunLike.hasCoeToFun

theorem LO.FirstOrder.Rew.func {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) {k : ℕ} (f : L.Func k) (v : Fin k → Semiterm L ξ₁ n₁) : ω (Semiterm.func f v) = Semiterm.func f fun (i : Fin k) => ω (v i)

theorem LO.FirstOrder.Rew.func'' {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) {k : ℕ} (f : L.Func k) (v : Fin k → Semiterm L ξ₁ n₁) : ω (Semiterm.func f v) = Semiterm.func f (⇑ω ∘ v)

@[simp]

theorem LO.FirstOrder.Rew.func0 {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) (f : L.Func 0) (v : Fin 0 → Semiterm L ξ₁ n₁) : ω (Semiterm.func f v) = Semiterm.func f ![]

@[simp]

theorem LO.FirstOrder.Rew.func1 {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) (f : L.Func 1) (t : Semiterm L ξ₁ n₁) : ω (Semiterm.func f ![t]) = Semiterm.func f ![ω t]

@[simp]

theorem LO.FirstOrder.Rew.func2 {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) (f : L.Func 2) (t₁ t₂ : Semiterm L ξ₁ n₁) : ω (Semiterm.func f ![t₁, t₂]) = Semiterm.func f ![ω t₁, ω t₂]

@[simp]

theorem LO.FirstOrder.Rew.func3 {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) (f : L.Func 3) (t₁ t₂ t₃ : Semiterm L ξ₁ n₁) : ω (Semiterm.func f ![t₁, t₂, t₃]) = Semiterm.func f ![ω t₁, ω t₂, ω t₃]

theorem LO.FirstOrder.Rew.ext {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω₁ ω₂ : Rew L ξ₁ n₁ ξ₂ n₂) (hb : ∀ (x : Fin n₁), ω₁ (Semiterm.bvar x) = ω₂ (Semiterm.bvar x)) (hf : ∀ (x : ξ₁), ω₁ (Semiterm.fvar x) = ω₂ (Semiterm.fvar x)) : ω₁ = ω₂

theorem LO.FirstOrder.Rew.ext' {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} {ω₁ ω₂ : Rew L ξ₁ n₁ ξ₂ n₂} (h : ω₁ = ω₂) (t : Semiterm L ξ₁ n₁) : ω₁ t = ω₂ t

def LO.FirstOrder.Rew.id {L : Language} {ξ : Type u_1} {n : ℕ} : Rew L ξ n ξ n

Equations

• LO.FirstOrder.Rew.id = { toFun := id, func' := ⋯ }

@[simp]

theorem LO.FirstOrder.Rew.id_app {L : Language} {ξ : Type u_1} {n : ℕ} (t : Semiterm L ξ n) : Rew.id t = t

def LO.FirstOrder.Rew.comp {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {ξ₃ : Type u_5} {n₁ n₂ n₃ : ℕ} (ω₂ : Rew L ξ₂ n₂ ξ₃ n₃) (ω₁ : Rew L ξ₁ n₁ ξ₂ n₂) : Rew L ξ₁ n₁ ξ₃ n₃

Equations

• ω₂.comp ω₁ = { toFun := fun (t : LO.FirstOrder.Semiterm L ξ₁ n₁) => ω₂ (ω₁ t), func' := ⋯ }

theorem LO.FirstOrder.Rew.comp_app {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {ξ₃ : Type u_5} {n₁ n₂ n₃ : ℕ} (ω₂ : Rew L ξ₂ n₂ ξ₃ n₃) (ω₁ : Rew L ξ₁ n₁ ξ₂ n₂) (t : Semiterm L ξ₁ n₁) : (ω₂.comp ω₁) t = ω₂ (ω₁ t)

@[simp]

theorem LO.FirstOrder.Rew.id_comp {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) : Rew.id.comp ω = ω

@[simp]

theorem LO.FirstOrder.Rew.comp_id {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) : ω.comp Rew.id = ω

def LO.FirstOrder.Rew.bindAux {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (b : Fin n₁ → Semiterm L ξ₂ n₂) (e : ξ₁ → Semiterm L ξ₂ n₂) : Semiterm L ξ₁ n₁ → Semiterm L ξ₂ n₂

Equations

• LO.FirstOrder.Rew.bindAux b e (LO.FirstOrder.Semiterm.bvar x_1) = b x_1
• LO.FirstOrder.Rew.bindAux b e (LO.FirstOrder.Semiterm.fvar x_1) = e x_1
• LO.FirstOrder.Rew.bindAux b e (LO.FirstOrder.Semiterm.func f v) = LO.FirstOrder.Semiterm.func f fun (i : Fin arity) => LO.FirstOrder.Rew.bindAux b e (v i)

def LO.FirstOrder.Rew.bind {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (b : Fin n₁ → Semiterm L ξ₂ n₂) (e : ξ₁ → Semiterm L ξ₂ n₂) : Rew L ξ₁ n₁ ξ₂ n₂

Equations

• LO.FirstOrder.Rew.bind b e = { toFun := LO.FirstOrder.Rew.bindAux b e, func' := ⋯ }

def LO.FirstOrder.Rew.rewrite {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n : ℕ} (f : ξ₁ → Semiterm L ξ₂ n) : Rew L ξ₁ n ξ₂ n

Equations

• LO.FirstOrder.Rew.rewrite f = LO.FirstOrder.Rew.bind LO.FirstOrder.Semiterm.bvar f

def LO.FirstOrder.Rew.rewriteMap {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n : ℕ} (e : ξ₁ → ξ₂) : Rew L ξ₁ n ξ₂ n

Equations

• LO.FirstOrder.Rew.rewriteMap e = LO.FirstOrder.Rew.rewrite fun (m : ξ₁) => LO.FirstOrder.Semiterm.fvar (e m)

def LO.FirstOrder.Rew.map {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (b : Fin n₁ → Fin n₂) (e : ξ₁ → ξ₂) : Rew L ξ₁ n₁ ξ₂ n₂

Equations

• LO.FirstOrder.Rew.map b e = LO.FirstOrder.Rew.bind (fun (n : Fin n₁) => LO.FirstOrder.Semiterm.bvar (b n)) fun (m : ξ₁) => LO.FirstOrder.Semiterm.fvar (e m)

def LO.FirstOrder.Rew.substs {L : Language} {ξ : Type u_1} {n n' : ℕ} (v : Fin n → Semiterm L ξ n') : Rew L ξ n ξ n'

Equations

• LO.FirstOrder.Rew.substs v = LO.FirstOrder.Rew.bind v LO.FirstOrder.Semiterm.fvar

def LO.FirstOrder.Rew.emb {L : Language} {o : Type v₁} [h : IsEmpty o] {ξ : Type v₂} {n : ℕ} : Rew L o n ξ n

Equations

• LO.FirstOrder.Rew.emb = LO.FirstOrder.Rew.map id fun (a : o) => h.elim a

@[reducible, inline]

abbrev LO.FirstOrder.Rew.embs {L : Language} {o : Type v₁} [IsEmpty o] {n : ℕ} : Rew L o n ℕ n

Equations

• LO.FirstOrder.Rew.embs = LO.FirstOrder.Rew.emb

def LO.FirstOrder.Rew.empty {L : Language} {o : Type v₁} [h : IsEmpty o] {ξ : Type v₂} {n : ℕ} : Rew L o 0 ξ n

Equations

• LO.FirstOrder.Rew.empty = LO.FirstOrder.Rew.map Fin.elim0 fun (a : o) => h.elim a

def LO.FirstOrder.Rew.bShift {L : Language} {ξ : Type u_1} {n : ℕ} : Rew L ξ n ξ (n + 1)

Equations

• LO.FirstOrder.Rew.bShift = LO.FirstOrder.Rew.map Fin.succ id

def LO.FirstOrder.Rew.bShiftAdd {L : Language} {ξ : Type u_1} {n : ℕ} (m : ℕ) : Rew L ξ n ξ (n + m)

Equations

• LO.FirstOrder.Rew.bShiftAdd m = LO.FirstOrder.Rew.map (fun (x : Fin n) => x.addNat m) id

def LO.FirstOrder.Rew.cast {L : Language} {ξ : Type u_1} {n n' : ℕ} (h : n = n') : Rew L ξ n ξ n'

Equations

• LO.FirstOrder.Rew.cast h = LO.FirstOrder.Rew.map (Fin.cast h) id

def LO.FirstOrder.Rew.castLE {L : Language} {ξ : Type u_1} {n n' : ℕ} (h : n ≤ n') : Rew L ξ n ξ n'

Equations

• LO.FirstOrder.Rew.castLE h = LO.FirstOrder.Rew.map (Fin.castLE h) id

def LO.FirstOrder.Rew.toS {L : Language} {n : ℕ} : Rew L (Fin n) 0 Empty n

Equations

• LO.FirstOrder.Rew.toS = LO.FirstOrder.Rew.bind ![] fun (x : Fin n) => LO.FirstOrder.Semiterm.bvar x

def LO.FirstOrder.Rew.toF {L : Language} {n : ℕ} : Rew L Empty n (Fin n) 0

Equations

• LO.FirstOrder.Rew.toF = LO.FirstOrder.Rew.bind (fun (x : Fin n) => LO.FirstOrder.Semiterm.fvar x) Empty.elim

def LO.FirstOrder.Rew.embSubsts {L : Language} {ξ : Type u_1} {n k : ℕ} (v : Fin k → Semiterm L ξ n) : Rew L Empty k ξ n

Equations

• LO.FirstOrder.Rew.embSubsts v = LO.FirstOrder.Rew.bind v Empty.elim

def LO.FirstOrder.Rew.q {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) : Rew L ξ₁ (n₁ + 1) ξ₂ (n₂ + 1)

Equations

• ω.q = LO.FirstOrder.Rew.bind (LO.FirstOrder.Semiterm.bvar 0 :> ⇑LO.FirstOrder.Rew.bShift ∘ ⇑ω ∘ LO.FirstOrder.Semiterm.bvar) (⇑LO.FirstOrder.Rew.bShift ∘ ⇑ω ∘ LO.FirstOrder.Semiterm.fvar)

theorem LO.FirstOrder.Rew.eq_id_of_eq {L : Language} {ξ : Type u_1} {n : ℕ} {ω : Rew L ξ n ξ n} (hb : ∀ (x : Fin n), ω (Semiterm.bvar x) = Semiterm.bvar x) (he : ∀ (x : ξ), ω (Semiterm.fvar x) = Semiterm.fvar x) (t : Semiterm L ξ n) : ω t = t

def LO.FirstOrder.Rew.qpow {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) (k : ℕ) : Rew L ξ₁ (n₁ + k) ξ₂ (n₂ + k)

Equations

• ω.qpow 0 = ω
• ω.qpow k.succ = (ω.qpow k).q

@[simp]

theorem LO.FirstOrder.Rew.qpow_zero {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) : ω.qpow 0 = ω

@[simp]

theorem LO.FirstOrder.Rew.qpow_succ {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) (k : ℕ) : ω.qpow (k + 1) = (ω.qpow k).q

@[simp]

theorem LO.FirstOrder.Rew.bind_fvar {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (b : Fin n₁ → Semiterm L ξ₂ n₂) (e : ξ₁ → Semiterm L ξ₂ n₂) (m : ξ₁) : (bind b e) (Semiterm.fvar m) = e m

@[simp]

theorem LO.FirstOrder.Rew.bind_bvar {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (b : Fin n₁ → Semiterm L ξ₂ n₂) (e : ξ₁ → Semiterm L ξ₂ n₂) (n : Fin n₁) : (bind b e) (Semiterm.bvar n) = b n

theorem LO.FirstOrder.Rew.eq_bind {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) : ω = bind (⇑ω ∘ Semiterm.bvar) (⇑ω ∘ Semiterm.fvar)

@[simp]

theorem LO.FirstOrder.Rew.bind_eq_id_of_zero {L : Language} {ξ₂ : Type u_4} (f : Fin 0 → Semiterm L ξ₂ 0) : bind f Semiterm.fvar = Rew.id

@[simp]

theorem LO.FirstOrder.Rew.map_fvar {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (b : Fin n₁ → Fin n₂) (e : ξ₁ → ξ₂) (m : ξ₁) : (map b e) (Semiterm.fvar m) = Semiterm.fvar (e m)

@[simp]

theorem LO.FirstOrder.Rew.map_bvar {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (b : Fin n₁ → Fin n₂) (e : ξ₁ → ξ₂) (n : Fin n₁) : (map b e) (Semiterm.bvar n) = Semiterm.bvar (b n)

@[simp]

theorem LO.FirstOrder.Rew.map_id {L : Language} {ξ : Type u_1} {n : ℕ} : map id id = Rew.id

theorem LO.FirstOrder.Rew.map_inj {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} {b : Fin n₁ → Fin n₂} {e : ξ₁ → ξ₂} (hb : Function.Injective b) (he : Function.Injective e) : Function.Injective ⇑(map b e)

@[simp]

theorem LO.FirstOrder.Rew.rewrite_fvar {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n : ℕ} (f : ξ₁ → Semiterm L ξ₂ n) (x : ξ₁) : (rewrite f) (Semiterm.fvar x) = f x

@[simp]

theorem LO.FirstOrder.Rew.rewrite_bvar {L : Language} {ξ₁ : Type u_3} {n : ℕ} {ξ✝ : Type u_6} {e : ξ₁ → Semiterm L ξ✝ n} (x : Fin n) : (rewrite e) (Semiterm.bvar x) = Semiterm.bvar x

theorem LO.FirstOrder.Rew.rewrite_comp_rewrite {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {ξ₃ : Type u_5} {n : ℕ} (v : ξ₂ → Semiterm L ξ₃ n) (w : ξ₁ → Semiterm L ξ₂ n) : (rewrite v).comp (rewrite w) = rewrite (⇑(rewrite v) ∘ w)

@[simp]

theorem LO.FirstOrder.Rew.rewrite_eq_id {L : Language} {ξ : Type u_1} {n : ℕ} : rewrite Semiterm.fvar = Rew.id

@[simp]

theorem LO.FirstOrder.Rew.rewriteMap_fvar {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n : ℕ} (e : ξ₁ → ξ₂) (x : ξ₁) : (rewriteMap e) (Semiterm.fvar x) = Semiterm.fvar (e x)

@[simp]

theorem LO.FirstOrder.Rew.rewriteMap_bvar {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n : ℕ} (e : ξ₁ → ξ₂) (x : Fin n) : (rewriteMap e) (Semiterm.bvar x) = Semiterm.bvar x

@[simp]

theorem LO.FirstOrder.Rew.rewriteMap_id {L : Language} {ξ : Type u_1} {n : ℕ} : rewriteMap id = Rew.id

theorem LO.FirstOrder.Rew.eq_rewriteMap_of_funEqOn_fv {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} [DecidableEq ξ₁] (t : Semiterm L ξ₁ n₁) (f g : ξ₁ → Semiterm L ξ₂ n₂) (h : Function.funEqOn t.FVar? f g) : (rewriteMap f) t = (rewriteMap g) t

@[simp]

theorem LO.FirstOrder.Rew.emb_bvar {L : Language} {ξ : Type u_1} {n : ℕ} {o : Type v₂} [IsEmpty o] (x : Fin n) : emb (Semiterm.bvar x) = Semiterm.bvar x

@[simp]

theorem LO.FirstOrder.Rew.emb_eq_id {L : Language} {n : ℕ} {o : Type v₂} [IsEmpty o] : emb = Rew.id

theorem LO.FirstOrder.Rew.eq_empty {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n : ℕ} [h : IsEmpty ξ₁] (ω : Rew L ξ₁ 0 ξ₂ n) : ω = empty

@[simp]

theorem LO.FirstOrder.Rew.bShift_bvar {L : Language} {ξ : Type u_1} {n : ℕ} (x : Fin n) : bShift (Semiterm.bvar x) = Semiterm.bvar x.succ

@[simp]

theorem LO.FirstOrder.Rew.bShift_fvar {L : Language} {ξ : Type u_1} {n : ℕ} (x : ξ) : bShift (Semiterm.fvar x) = Semiterm.fvar x

@[simp]

theorem LO.FirstOrder.Rew.bShift_ne_zero {L : Language} {ξ : Type u_1} {n : ℕ} (t : Semiterm L ξ n) : bShift t ≠ Semiterm.bvar 0

@[simp]

theorem LO.FirstOrder.Rew.bShift_positive {L : Language} {ξ : Type u_1} {n : ℕ} (t : Semiterm L ξ n) : (bShift t).Positive

theorem LO.FirstOrder.Rew.positive_iff {L : Language} {ξ : Type u_1} {n : ℕ} {t : Semiterm L ξ (n + 1)} : t.Positive ↔ ∃ (t' : Semiterm L ξ n), t = bShift t'

@[simp]

theorem LO.FirstOrder.Rew.leftConcat_bShift_comp_bvar {L : Language} {ξ : Type u_1} {n : ℕ} : Semiterm.bvar 0 :> ⇑bShift ∘ Semiterm.bvar = Semiterm.bvar

@[simp]

theorem LO.FirstOrder.Rew.bShift_comp_fvar {L : Language} {ξ : Type u_1} {n : ℕ} : ⇑bShift ∘ Semiterm.fvar = Semiterm.fvar

@[simp]

theorem LO.FirstOrder.Rew.bShiftAdd_bvar {L : Language} {ξ : Type u_1} {n : ℕ} (m : ℕ) (x : Fin n) : (bShiftAdd m) (Semiterm.bvar x) = Semiterm.bvar (x.addNat m)

@[simp]

theorem LO.FirstOrder.Rew.bShiftAdd_fvar {L : Language} {ξ : Type u_1} {n : ℕ} (m : ℕ) (x : ξ) : (bShiftAdd m) (Semiterm.fvar x) = Semiterm.fvar x

@[simp]

theorem LO.FirstOrder.Rew.substs_bvar {L : Language} {ξ : Type u_1} {n n' : ℕ} (w : Fin n → Semiterm L ξ n') (x : Fin n) : (substs w) (Semiterm.bvar x) = w x

@[simp]

theorem LO.FirstOrder.Rew.substs_fvar {L : Language} {ξ : Type u_1} {n n' : ℕ} (w : Fin n → Semiterm L ξ n') (x : ξ) : (substs w) (Semiterm.fvar x) = Semiterm.fvar x

@[simp]

theorem LO.FirstOrder.Rew.substs_zero {L : Language} {ξ : Type u_1} (w : Fin 0 → Term L ξ) : substs w = Rew.id

theorem LO.FirstOrder.Rew.substs_comp_substs {L : Language} {ξ : Type u_1} {n l k : ℕ} (v : Fin l → Semiterm L ξ k) (w : Fin k → Semiterm L ξ n) : (substs w).comp (substs v) = substs (⇑(substs w) ∘ v)

@[simp]

theorem LO.FirstOrder.Rew.substs_eq_id {L : Language} {ξ : Type u_1} {n : ℕ} : substs Semiterm.bvar = Rew.id

@[simp]

theorem LO.FirstOrder.Rew.cast_bvar {L : Language} {ξ : Type u_1} {n n' : ℕ} (h : n = n') (x : Fin n) : (cast h) (Semiterm.bvar x) = Semiterm.bvar (Fin.cast h x)

@[simp]

theorem LO.FirstOrder.Rew.cast_fvar {L : Language} {ξ : Type u_1} {n n' : ℕ} (h : n = n') (x : ξ) : (cast h) (Semiterm.fvar x) = Semiterm.fvar x

@[simp]

theorem LO.FirstOrder.Rew.cast_eq_id {L : Language} {ξ : Type u_1} {n : ℕ} {h : n = n} : cast h = Rew.id

@[simp]

theorem LO.FirstOrder.Rew.castLe_bvar {L : Language} {ξ : Type u_1} {n n' : ℕ} (h : n ≤ n') (x : Fin n) : (castLE h) (Semiterm.bvar x) = Semiterm.bvar (Fin.castLE h x)

@[simp]

theorem LO.FirstOrder.Rew.castLe_fvar {L : Language} {ξ : Type u_1} {n n' : ℕ} (h : n ≤ n') (x : ξ) : (castLE h) (Semiterm.fvar x) = Semiterm.fvar x

@[simp]

theorem LO.FirstOrder.Rew.castLe_eq_id {L : Language} {ξ : Type u_1} {n : ℕ} {h : n ≤ n} : castLE h = Rew.id

@[simp]

theorem LO.FirstOrder.Rew.toS_fvar {L : Language} {n : ℕ} (x : Fin n) : toS (Semiterm.fvar x) = Semiterm.bvar x

@[simp]

theorem LO.FirstOrder.Rew.embSubsts_bvar {L : Language} {ξ : Type u_1} {n k : ℕ} (w : Fin k → Semiterm L ξ n) (x : Fin k) : (embSubsts w) (Semiterm.bvar x) = w x

@[simp]

theorem LO.FirstOrder.Rew.embSubsts_zero {L : Language} {ξ : Type u_1} (w : Fin 0 → Term L ξ) : embSubsts w = emb

theorem LO.FirstOrder.Rew.substs_comp_embSubsts {L : Language} {ξ : Type u_1} {n k l : ℕ} (v : Fin l → Semiterm L ξ k) (w : Fin k → Semiterm L ξ n) : (substs w).comp (embSubsts v) = embSubsts (⇑(substs w) ∘ v)

@[simp]

theorem LO.FirstOrder.Rew.embSubsts_eq_id {L : Language} {ξ : Type u_1} {n : ℕ} : embSubsts Semiterm.bvar = emb

@[simp]

theorem LO.FirstOrder.Rew.q_bvar_zero {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) : ω.q (Semiterm.bvar 0) = Semiterm.bvar 0

@[simp]

theorem LO.FirstOrder.Rew.q_bvar_succ {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) (i : Fin n₁) : ω.q (Semiterm.bvar i.succ) = bShift (ω (Semiterm.bvar i))

@[simp]

theorem LO.FirstOrder.Rew.q_fvar {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) (x : ξ₁) : ω.q (Semiterm.fvar x) = bShift (ω (Semiterm.fvar x))

@[simp]

theorem LO.FirstOrder.Rew.q_comp_bShift {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) : ω.q.comp bShift = bShift.comp ω

@[simp]

theorem LO.FirstOrder.Rew.q_comp_bShift_app {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) (t : Semiterm L ξ₁ n₁) : ω.q (bShift t) = bShift (ω t)

@[simp]

theorem LO.FirstOrder.Rew.q_id {L : Language} {ξ : Type u_1} {n : ℕ} : Rew.id.q = Rew.id

@[simp]

theorem LO.FirstOrder.Rew.q_eq_zero_iff {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) {t : Semiterm L ξ₁ (n₁ + 1)} : ω.q t = Semiterm.bvar 0 ↔ t = Semiterm.bvar 0

@[simp]

theorem LO.FirstOrder.Rew.q_positive_iff {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (ω : Rew L ξ₁ n₁ ξ₂ n₂) {t : Semiterm L ξ₁ (n₁ + 1)} : (ω.q t).Positive ↔ t.Positive

@[simp]

theorem LO.FirstOrder.Rew.qpow_id {L : Language} {ξ : Type u_1} {n k : ℕ} : Rew.id.qpow k = Rew.id

theorem LO.FirstOrder.Rew.q_comp {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {ξ₃ : Type u_5} {n₁ n₂ n₃ : ℕ} (ω₂ : Rew L ξ₂ n₂ ξ₃ n₃) (ω₁ : Rew L ξ₁ n₁ ξ₂ n₂) : (ω₂.comp ω₁).q = ω₂.q.comp ω₁.q

theorem LO.FirstOrder.Rew.qpow_comp {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {ξ₃ : Type u_5} {n₁ n₂ n₃ : ℕ} (k : ℕ) (ω₂ : Rew L ξ₂ n₂ ξ₃ n₃) (ω₁ : Rew L ξ₁ n₁ ξ₂ n₂) : (ω₂.comp ω₁).qpow k = (ω₂.qpow k).comp (ω₁.qpow k)

theorem LO.FirstOrder.Rew.q_bind {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (b : Fin n₁ → Semiterm L ξ₂ n₂) (e : ξ₁ → Semiterm L ξ₂ n₂) : (bind b e).q = bind (Semiterm.bvar 0 :> ⇑bShift ∘ b) (⇑bShift ∘ e)

theorem LO.FirstOrder.Rew.q_map {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (b : Fin n₁ → Fin n₂) (e : ξ₁ → ξ₂) : (map b e).q = map (0 :> Fin.succ ∘ b) e

theorem LO.FirstOrder.Rew.q_rewrite {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n : ℕ} (f : ξ₁ → Semiterm L ξ₂ n) : (rewrite f).q = rewrite (⇑bShift ∘ f)

@[simp]

theorem LO.FirstOrder.Rew.q_rewriteMap {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n : ℕ} (e : ξ₁ → ξ₂) : (rewriteMap e).q = rewriteMap e

@[simp]

theorem LO.FirstOrder.Rew.q_emb {L : Language} {ξ₂ : Type u_4} {o : Type v₁} [e : IsEmpty o] {n : ℕ} : emb.q = emb

@[simp]

theorem LO.FirstOrder.Rew.qpow_emb {L : Language} {ξ₂ : Type u_4} {o : Type v₁} [e : IsEmpty o] {n k : ℕ} : emb.qpow k = emb

@[simp]

theorem LO.FirstOrder.Rew.q_cast {L : Language} {ξ : Type u_1} {n n' : ℕ} (h : n = n') : (cast h).q = cast ⋯

@[simp]

theorem LO.FirstOrder.Rew.q_castLE {L : Language} {ξ : Type u_1} {n n' : ℕ} (h : n ≤ n') : (castLE h).q = castLE ⋯

theorem LO.FirstOrder.Rew.q_toS {L : Language} {n : ℕ} : toS.q = bind ![Semiterm.bvar 0] fun (x : Fin n) => Semiterm.bvar x.succ

@[simp]

theorem LO.FirstOrder.Rew.qpow_castLE {L : Language} {ξ : Type u_1} {k n n' : ℕ} (h : n ≤ n') : (castLE h).qpow k = castLE ⋯

theorem LO.FirstOrder.Rew.q_substs {L : Language} {ξ : Type u_1} {n n' : ℕ} (w : Fin n → Semiterm L ξ n') : (substs w).q = substs (Semiterm.bvar 0 :> ⇑bShift ∘ w)

theorem LO.FirstOrder.Rew.q_embSubsts {L : Language} {ξ : Type u_1} {n k : ℕ} (w : Fin k → Semiterm L ξ n) : (embSubsts w).q = embSubsts (Semiterm.bvar 0 :> ⇑bShift ∘ w)

def LO.FirstOrder.Rew.shift {L : Language} {n : ℕ} : SyntacticRew L n n

Equations

• LO.FirstOrder.Rew.shift = LO.FirstOrder.Rew.map id Nat.succ

def LO.FirstOrder.Rew.free {L : Language} {n : ℕ} : SyntacticRew L (n + 1) n

Equations

• LO.FirstOrder.Rew.free = LO.FirstOrder.Rew.bind (LO.FirstOrder.Semiterm.bvar <: LO.FirstOrder.Semiterm.fvar 0) fun (m : ℕ) => LO.FirstOrder.Semiterm.fvar m.succ

def LO.FirstOrder.Rew.fix {L : Language} {n : ℕ} : SyntacticRew L n (n + 1)

Equations

• LO.FirstOrder.Rew.fix = LO.FirstOrder.Rew.bind (fun (x : Fin n) => LO.FirstOrder.Semiterm.bvar x.castSucc) (LO.FirstOrder.Semiterm.bvar (Fin.last n) :>ₙ LO.FirstOrder.Semiterm.fvar)

@[reducible, inline]

abbrev LO.FirstOrder.Rew.rewrite1 {L : Language} {n : ℕ} (t : SyntacticSemiterm L n) : SyntacticRew L n n

Equations

• LO.FirstOrder.Rew.rewrite1 t = LO.FirstOrder.Rew.bind LO.FirstOrder.Semiterm.bvar (t :>ₙ LO.FirstOrder.Semiterm.fvar)

@[simp]

theorem LO.FirstOrder.Rew.shift_bvar {L : Language} {n : ℕ} (x : Fin n) : shift (Semiterm.bvar x) = Semiterm.bvar x

@[simp]

theorem LO.FirstOrder.Rew.shift_fvar {L : Language} {n : ℕ} (x : ℕ) : shift (Semiterm.fvar x) = Semiterm.fvar (x + 1)

theorem LO.FirstOrder.Rew.shift_func {L : Language} {n k : ℕ} (f : L.Func k) (v : Fin k → SyntacticSemiterm L n) : shift (Semiterm.func f v) = Semiterm.func f fun (i : Fin k) => shift (v i)

theorem LO.FirstOrder.Rew.shift_Injective {L : Language} {n : ℕ} : Function.Injective ⇑shift

@[simp]

theorem LO.FirstOrder.Rew.free_bvar_castSucc {L : Language} {n : ℕ} (x : Fin n) : free (Semiterm.bvar x.castSucc) = Semiterm.bvar x

@[simp]

theorem LO.FirstOrder.Rew.free_bvar_castSucc_zero {L : Language} {n : ℕ} : free (Semiterm.bvar 0) = Semiterm.bvar 0

@[simp]

theorem LO.FirstOrder.Rew.free_bvar_last {L : Language} {n : ℕ} : free (Semiterm.bvar (Fin.last n)) = Semiterm.fvar 0

@[simp]

theorem LO.FirstOrder.Rew.free_bvar_last_zero {L : Language} : free (Semiterm.bvar 0) = Semiterm.fvar 0

@[simp]

theorem LO.FirstOrder.Rew.free_fvar {L : Language} {n : ℕ} (x : ℕ) : free (Semiterm.fvar x) = Semiterm.fvar (x + 1)

@[simp]

theorem LO.FirstOrder.Rew.fix_bvar {L : Language} {n : ℕ} (x : Fin n) : fix (Semiterm.bvar x) = Semiterm.bvar x.castSucc

@[simp]

theorem LO.FirstOrder.Rew.fix_fvar_zero {L : Language} {n : ℕ} : fix (Semiterm.fvar 0) = Semiterm.bvar (Fin.last n)

@[simp]

theorem LO.FirstOrder.Rew.fix_fvar_succ {L : Language} {n : ℕ} (x : ℕ) : fix (Semiterm.fvar (x + 1)) = Semiterm.fvar x

@[simp]

theorem LO.FirstOrder.Rew.free_comp_fix {L : Language} {n : ℕ} : Rew.comp free fix = Rew.id

@[simp]

theorem LO.FirstOrder.Rew.fix_comp_free {L : Language} {n : ℕ} : Rew.comp fix free = Rew.id

@[simp]

theorem LO.FirstOrder.Rew.bShift_free_eq_shift {L : Language} : Rew.comp free bShift = shift

theorem LO.FirstOrder.Rew.bShift_comp_substs {L : Language} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (v : Fin n₁ → Semiterm L ξ₂ n₂) : bShift.comp (substs v) = substs (⇑bShift ∘ v)

theorem LO.FirstOrder.Rew.shift_comp_substs {L : Language} {n₁ n₂ : ℕ} (v : Fin n₁ → SyntacticSemiterm L n₂) : Rew.comp shift (substs v) = (substs (⇑shift ∘ v)).comp shift

theorem LO.FirstOrder.Rew.shift_comp_substs1 {L : Language} {n₂ : ℕ} (t : SyntacticSemiterm L n₂) : Rew.comp shift (substs ![t]) = (substs ![shift t]).comp shift

@[simp]

theorem LO.FirstOrder.Rew.rewrite_comp_emb {L : Language} {ξ₂ : Type u_4} {ξ₃ : Type u_5} {n : ℕ} {o : Type v₁} [e : IsEmpty o] (f : ξ₂ → Semiterm L ξ₃ n) : (rewrite f).comp emb = emb

@[simp]

theorem LO.FirstOrder.Rew.shift_comp_emb {L : Language} {n : ℕ} {o : Type v₁} [e : IsEmpty o] : Rew.comp shift emb = emb

theorem LO.FirstOrder.Rew.rewrite_comp_free_eq_substs {L : Language} (t : SyntacticTerm L) : (rewrite (t :>ₙ Semiterm.fvar)).comp free = substs ![t]

theorem LO.FirstOrder.Rew.rewrite_comp_shift_eq_id {L : Language} (t : SyntacticTerm L) : (rewrite (t :>ₙ Semiterm.fvar)).comp shift = Rew.id

@[simp]

theorem LO.FirstOrder.Rew.substs_mbar_zero_comp_shift_eq_free {L : Language} : (substs ![Semiterm.fvar 0]).comp shift = free

@[simp]

theorem LO.FirstOrder.Rew.substs_comp_bShift_eq_id {L : Language} {ξ : Type u_1} (v : Fin 1 → Semiterm L ξ 0) : (substs v).comp bShift = Rew.id

theorem LO.FirstOrder.Rew.free_comp_substs_eq_substs_comp_shift {n : ℕ} {Lf : Language} {n' : ℕ} (w : Fin n' → SyntacticSemiterm Lf (n + 1)) : Rew.comp free (substs w) = (substs (⇑free ∘ w)).comp shift

@[simp]

theorem LO.FirstOrder.Rew.rewriteMap_comp_rewriteMap {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {ξ₃ : Type u_5} {n : ℕ} (f : ξ₁ → ξ₂) (g : ξ₂ → ξ₃) : (rewriteMap g).comp (rewriteMap f) = rewriteMap (g ∘ f)

@[simp]

theorem LO.FirstOrder.Rew.fix_free_app {L : Language} {n : ℕ} (t : SyntacticSemiterm L (n + 1)) : fix (free t) = t

@[simp]

theorem LO.FirstOrder.Rew.free_fix_app {L : Language} {n : ℕ} (t : SyntacticSemiterm L n) : free (fix t) = t

@[simp]

theorem LO.FirstOrder.Rew.free_bShift_app {L : Language} (t : SyntacticSemiterm L 0) : free (bShift t) = shift t

@[simp]

theorem LO.FirstOrder.Rew.substs_bShift_app {L : Language} {ξ : Type u_1} {t : Semiterm L ξ 0} (v : Fin 1 → Semiterm L ξ 0) : (substs v) (bShift t) = t

theorem LO.FirstOrder.Rew.rewrite_comp_fix_eq_substs {L : Language} (t : Semiterm L ℕ 0) : (rewrite (t :>ₙ fun (x : ℕ) => Semiterm.fvar x)).comp free = substs ![t]

theorem LO.FirstOrder.Rew.bShift_eq_rewrite {L : Language} : bShift = substs ![]

@[simp]

theorem LO.FirstOrder.Rew.q_shift {L : Language} {n : ℕ} : Rew.q shift = shift

@[simp]

theorem LO.FirstOrder.Rew.q_free {L : Language} {n : ℕ} : Rew.q free = free

@[simp]

theorem LO.FirstOrder.Rew.q_fix {L : Language} {n : ℕ} : Rew.q fix = fix

def LO.FirstOrder.Rew.fixitr {L : Language} (n m : ℕ) : SyntacticRew L n (n + m)

Equations

• LO.FirstOrder.Rew.fixitr n 0 = LO.FirstOrder.Rew.id
• LO.FirstOrder.Rew.fixitr n k.succ = LO.FirstOrder.Rew.comp LO.FirstOrder.Rew.fix (LO.FirstOrder.Rew.fixitr n k)

@[simp]

theorem LO.FirstOrder.Rew.fixitr_zero {L : Language} {n : ℕ} : fixitr n 0 = Rew.id

theorem LO.FirstOrder.Rew.fixitr_succ {L : Language} {n : ℕ} (m : ℕ) : fixitr n (m + 1) = Rew.comp fix (fixitr n m)

@[simp]

theorem LO.FirstOrder.Rew.fixitr_bvar {L : Language} (n m : ℕ) (x : Fin n) : (fixitr n m) (Semiterm.bvar x) = Semiterm.bvar (Fin.castAdd m x)

theorem LO.FirstOrder.Rew.fixitr_fvar {L : Language} (n m x : ℕ) : (fixitr n m) (Semiterm.fvar x) = if h : x < m then Semiterm.bvar (Fin.natAdd n ⟨x, h⟩) else Semiterm.fvar (x - m)

theorem LO.FirstOrder.Rew.substs_bv {L : Language} {ξ : Type u_1} {n m : ℕ} (t : Semiterm L ξ n) (v : Fin n → Semiterm L ξ m) : ((substs v) t).bv = t.bv.biUnion fun (i : Fin n) => (v i).bv

@[simp]

theorem LO.FirstOrder.Rew.substs_positive {L : Language} {ξ : Type u_1} {n m : ℕ} (t : Semiterm L ξ n) (v : Fin n → Semiterm L ξ (m + 1)) : ((substs v) t).Positive ↔ ∀ i ∈ t.bv, (v i).Positive

theorem LO.FirstOrder.Rew.embSubsts_bv {L : Language} {ξ : Type u_1} {n m : ℕ} (t : Semiterm L Empty n) (v : Fin n → Semiterm L ξ m) : ((embSubsts v) t).bv = t.bv.biUnion fun (i : Fin n) => (v i).bv

@[simp]

theorem LO.FirstOrder.Rew.embSubsts_positive {L : Language} {ξ : Type u_1} {n m : ℕ} (t : Semiterm L Empty n) (v : Fin n → Semiterm L ξ (m + 1)) : ((embSubsts v) t).Positive ↔ ∀ i ∈ t.bv, (v i).Positive

@[simp]

theorem LO.FirstOrder.Rew.bshift_positive {L : Language} {ξ : Type u_1} {n : ℕ} (t : Semiterm L ξ n) : (bShift t).Positive

theorem LO.FirstOrder.Rew.emb_comp_bShift_comm {L : Language} {ξ : Type u_1} {n : ℕ} {o : Type v₁} [IsEmpty o] : bShift.comp emb = emb.comp bShift

theorem LO.FirstOrder.Rew.emb_bShift_term {L : Language} {ξ : Type u_1} {n : ℕ} {o : Type v₁} [IsEmpty o] (t : Semiterm L o n) : bShift (emb t) = emb (bShift t)

Rewriting system of terms

instance LO.FirstOrder.Semiterm.instCoeEmptySyntacticSemiterm {L : Language} {n : ℕ} : Coe (Semiterm L Empty n) (SyntacticSemiterm L n)

Equations

• LO.FirstOrder.Semiterm.instCoeEmptySyntacticSemiterm = { coe := ⇑LO.FirstOrder.Rew.emb }

@[simp]

theorem LO.FirstOrder.Semiterm.freeVariables_emb {L : Language} {ξ : Type u_1} {n : ℕ} {ο : Type u_6} [IsEmpty ο] [DecidableEq ξ] {t : Semiterm L ο n} : (Rew.emb t).freeVariables = ∅

theorem LO.FirstOrder.Semiterm.rew_eq_of_funEqOn {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} [DecidableEq ξ₁] (ω₁ ω₂ : Rew L ξ₁ n₁ ξ₂ n₂) (t : Semiterm L ξ₁ n₁) (hb : ∀ (x : Fin n₁), ω₁ (bvar x) = ω₂ (bvar x)) (he : Function.funEqOn t.FVar? (⇑ω₁ ∘ fvar) (⇑ω₂ ∘ fvar)) : ω₁ t = ω₂ t

theorem LO.FirstOrder.Semiterm.lMap_bind {L₁ : Language} {L₂ : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (Φ : L₁.Hom L₂) (b : Fin n₁ → Semiterm L₁ ξ₂ n₂) (e : ξ₁ → Semiterm L₁ ξ₂ n₂) (t : Semiterm L₁ ξ₁ n₁) : lMap Φ ((Rew.bind b e) t) = (Rew.bind (lMap Φ ∘ b) (lMap Φ ∘ e)) (lMap Φ t)

theorem LO.FirstOrder.Semiterm.lMap_map {L₁ : Language} {L₂ : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} (Φ : L₁.Hom L₂) (b : Fin n₁ → Fin n₂) (e : ξ₁ → ξ₂) (t : Semiterm L₁ ξ₁ n₁) : lMap Φ ((Rew.map b e) t) = (Rew.map b e) (lMap Φ t)

theorem LO.FirstOrder.Semiterm.lMap_bShift {L₁ : Language} {L₂ : Language} {ξ₁ : Type u_3} {n : ℕ} (Φ : L₁.Hom L₂) (t : Semiterm L₁ ξ₁ n) : lMap Φ (Rew.bShift t) = Rew.bShift (lMap Φ t)

theorem LO.FirstOrder.Semiterm.lMap_shift {L₁ : Language} {L₂ : Language} {n : ℕ} (Φ : L₁.Hom L₂) (t : SyntacticSemiterm L₁ n) : lMap Φ (Rew.shift t) = Rew.shift (lMap Φ t)

theorem LO.FirstOrder.Semiterm.lMap_free {L₁ : Language} {L₂ : Language} {n : ℕ} (Φ : L₁.Hom L₂) (t : SyntacticSemiterm L₁ (n + 1)) : lMap Φ (Rew.free t) = Rew.free (lMap Φ t)

theorem LO.FirstOrder.Semiterm.lMap_fix {L₁ : Language} {L₂ : Language} {n : ℕ} (Φ : L₁.Hom L₂) (t : SyntacticSemiterm L₁ n) : lMap Φ (Rew.fix t) = Rew.fix (lMap Φ t)

theorem LO.FirstOrder.Semiterm.fvar?_rew {L : Language} {ξ₁ : Type u_3} {ξ₂ : Type u_4} {n₁ n₂ : ℕ} [DecidableEq ξ₁] [DecidableEq ξ₂] {ω : Rew L ξ₁ n₁ ξ₂ n₂} {t : Semiterm L ξ₁ n₁} {x : ξ₂} : (ω t).FVar? x → (∃ (i : Fin n₁), (ω (bvar i)).FVar? x) ∨ ∃ (z : ξ₁), t.FVar? z ∧ (ω (fvar z)).FVar? x

@[simp]

theorem LO.FirstOrder.Semiterm.fvar?_bShift {L : Language} {ξ : Type u_1} {n : ℕ} [DecidableEq ξ] {t : Semiterm L ξ n} {x : ξ} : (Rew.bShift t).FVar? x ↔ t.FVar? x

def LO.FirstOrder.Semiterm.toEmpty {L : Language} {ξ : Type u_1} [DecidableEq ξ] {n : ℕ} (t : Semiterm L ξ n) : t.freeVariables = ∅ → Semiterm L Empty n

Equations

• (LO.FirstOrder.Semiterm.bvar x_2).toEmpty x_3 = LO.FirstOrder.Semiterm.bvar x_2
• (LO.FirstOrder.Semiterm.fvar x_2).toEmpty h = ⋯.elim
• (LO.FirstOrder.Semiterm.func f v).toEmpty h = LO.FirstOrder.Semiterm.func f fun (i : Fin arity) => (v i).toEmpty ⋯

@[simp]

theorem LO.FirstOrder.Semiterm.emb_toEmpty {L : Language} {ξ : Type u_1} {n : ℕ} [DecidableEq ξ] (t : Semiterm L ξ n) (ht : t.freeVariables = ∅) : Rew.emb (t.toEmpty ht) = t

Rewriting system of formulae

class LO.FirstOrder.FreeVar (ξ : outParam (Type u_1)) (F : ℕ → Type u_2) : Type

class LO.FirstOrder.Rewriting (L : outParam Language) (ξ : outParam (Type u_1)) (F : ℕ → Type u_2) (ζ : Type u_3) (G : outParam (ℕ → Type u_4)) [LCWQ F] [LCWQ G] : Type (max (max (max (max u_1 u_2) u_3) u_4) u_5)

• app {n₁ n₂ : ℕ} : Rew L ξ n₁ ζ n₂ → F n₁ →ˡᶜ G n₂
• app_all {n₁ n₂ : ℕ} (ω₁₂ : Rew L ξ n₁ ζ n₂) (φ : F (n₁ + 1)) : (app ω₁₂) (∀' φ) = ∀' (app ω₁₂.q) φ
• app_ex {n₁ n₂ : ℕ} (ω₁₂ : Rew L ξ n₁ ζ n₂) (φ : F (n₁ + 1)) : (app ω₁₂) (∃' φ) = ∃' (app ω₁₂.q) φ

Instances

• LO.FirstOrder.Semiformula.instRewriting
• LO.FirstOrder.Semiformulaᵢ.instRewriting

@[reducible, inline]

abbrev LO.FirstOrder.SyntacticRewriting (L : outParam Language) (F : ℕ → Type u_1) (G : outParam (ℕ → Type u_2)) [LCWQ F] [LCWQ G] : Type (max (max u_1 u_2) u_3)

Equations

• LO.FirstOrder.SyntacticRewriting L F G = LO.FirstOrder.Rewriting L ℕ F ℕ G

def LO.FirstOrder.Rewriting.«term_▹_» : Lean.TrailingParserDescr

Equations

• One or more equations did not get rendered due to their size.

theorem LO.FirstOrder.Rewriting.smul_ext' {F : ℕ → Type u_5} {G : ℕ → Type u_4} {L : Language} {ξ : Type u_1} {ζ : Type u_2} [LCWQ F] [LCWQ G] [Rewriting L ξ F ζ G] {n₁ n₂ : ℕ} {ω₁ ω₂ : Rew L ξ n₁ ζ n₂} (h : ω₁ = ω₂) {φ : F n₁} : (app ω₁) φ = (app ω₂) φ

@[simp]

theorem LO.FirstOrder.Rewriting.smul_ball {F : ℕ → Type u_5} {G : ℕ → Type u_4} {L : Language} {ξ : Type u_1} {ζ : Type u_2} [LCWQ F] [LCWQ G] [Rewriting L ξ F ζ G] {n₁ n₂ : ℕ} (ω : Rew L ξ n₁ ζ n₂) (φ ψ : F (n₁ + 1)) : (app ω) (∀[φ] ψ) = ∀[(app ω.q) φ] (app ω.q) ψ

@[simp]

theorem LO.FirstOrder.Rewriting.smul_bex {F : ℕ → Type u_5} {G : ℕ → Type u_4} {L : Language} {ξ : Type u_1} {ζ : Type u_2} [LCWQ F] [LCWQ G] [Rewriting L ξ F ζ G] {n₁ n₂ : ℕ} (ω : Rew L ξ n₁ ζ n₂) (φ ψ : F (n₁ + 1)) : (app ω) (∃[φ] ψ) = ∃[(app ω.q) φ] (app ω.q) ψ

@[reducible, inline]

abbrev LO.FirstOrder.Rewriting.substitute {F : ℕ → Type u_1} {L : Language} {ξ : Type u_3} [LCWQ F] {n₁ n₂ : ℕ} [Rewriting L ξ F ξ F] (φ : F n₁) (w : Fin n₁ → Semiterm L ξ n₂) : F n₂

Equations

• φ ⇜ w = (LO.FirstOrder.Rewriting.app (LO.FirstOrder.Rew.substs w)) φ

def LO.FirstOrder.Rewriting.«term_⇜_» : Lean.TrailingParserDescr

Equations

• One or more equations did not get rendered due to their size.

@[reducible, inline]

abbrev LO.FirstOrder.Rewriting.shift {F : ℕ → Type u_1} {L : Language} [LCWQ F] {n : ℕ} [Rewriting L ℕ F ℕ F] (φ : F n) : F n

Equations

• LO.FirstOrder.Rewriting.shift φ = (LO.FirstOrder.Rewriting.app LO.FirstOrder.Rew.shift) φ

@[reducible, inline]

abbrev LO.FirstOrder.Rewriting.free {F : ℕ → Type u_1} {L : Language} [LCWQ F] {n : ℕ} [Rewriting L ℕ F ℕ F] (φ : F (n + 1)) : F n

Equations

• LO.FirstOrder.Rewriting.free φ = (LO.FirstOrder.Rewriting.app LO.FirstOrder.Rew.free) φ

@[reducible, inline]

abbrev LO.FirstOrder.Rewriting.fix {F : ℕ → Type u_1} {L : Language} [LCWQ F] {n : ℕ} [Rewriting L ℕ F ℕ F] (φ : F n) : F (n + 1)

Equations

• LO.FirstOrder.Rewriting.fix φ = (LO.FirstOrder.Rewriting.app LO.FirstOrder.Rew.fix) φ

def LO.FirstOrder.Rewriting.shifts {F : ℕ → Type u_1} {L : Language} [LCWQ F] {n : ℕ} [Rewriting L ℕ F ℕ F] (Γ : List (F n)) : List (F n)

Equations

• LO.FirstOrder.Rewriting.shifts Γ = List.map LO.FirstOrder.Rewriting.shift Γ

def LO.FirstOrder.«term_⁺» : Lean.TrailingParserDescr

Equations

• LO.FirstOrder.«term_⁺» = Lean.ParserDescr.trailingNode `LO.FirstOrder.«term_⁺» 1024 1024 (Lean.ParserDescr.symbol "⁺")

@[reducible, inline]

abbrev LO.FirstOrder.Rewriting.embedding {L : Language} {n : ℕ} {ο : Type u_4} {ξ : Type u_5} [IsEmpty ο] {O : ℕ → Type u_1} {F : ℕ → Type u_2} [LCWQ O] [LCWQ F] [Rewriting L ο O ξ F] (φ : O n) : F n

Equations

• ↑φ = (LO.FirstOrder.Rewriting.app LO.FirstOrder.Rew.emb) φ

def LO.FirstOrder.substituteNotation : Lean.TrailingParserDescr

Equations

• One or more equations did not get rendered due to their size.

def unexpsnderSubstitute : Lean.PrettyPrinter.Unexpander

Equations

• One or more equations did not get rendered due to their size.

class LO.FirstOrder.ReflectiveRewriting (L : outParam Language) (ξ : outParam (Type u_1)) (F : ℕ → Type u_2) [LCWQ F] [Rewriting L ξ F ξ F] : Prop

• id_app {n : ℕ} (φ : F n) : (Rewriting.app Rew.id) φ = φ

Instances

• LO.FirstOrder.Semiformula.instReflectiveRewriting
• LO.FirstOrder.Semiformulaᵢ.instReflectiveRewriting

class LO.FirstOrder.TransitiveRewriting (L : outParam Language) (ξ₁ : outParam (Type u_1)) (F₁ : ℕ → Type u_2) (ξ₂ : Type u_3) (F₂ : outParam (ℕ → Type u_4)) (ξ₃ : Type u_5) (F₃ : outParam (ℕ → Type u_6)) [LCWQ F₁] [LCWQ F₂] [LCWQ F₃] [Rewriting L ξ₁ F₁ ξ₂ F₂] [Rewriting L ξ₂ F₂ ξ₃ F₃] [Rewriting L ξ₁ F₁ ξ₃ F₃] : Prop

• comp_app {n₁ n₂ n₃ : ℕ} (ω₁₂ : Rew L ξ₁ n₁ ξ₂ n₂) (ω₂₃ : Rew L ξ₂ n₂ ξ₃ n₃) (φ : F₁ n₁) : (Rewriting.app (ω₂₃.comp ω₁₂)) φ = (Rewriting.app ω₂₃) ((Rewriting.app ω₁₂) φ)

Instances

• LO.FirstOrder.Semiformula.instTransitiveRewriting
• LO.FirstOrder.Semiformulaᵢ.instTransitiveRewriting

class LO.FirstOrder.InjMapRewriting (L : outParam Language) (ξ : outParam (Type u_1)) (F : ℕ → Type u_2) (ζ : Type u_3) (G : outParam (ℕ → Type u_4)) [LCWQ F] [LCWQ G] [Rewriting L ξ F ζ G] : Prop

• smul_map_injective {n₁ n₂ : ℕ} {b : Fin n₁ → Fin n₂} {f : ξ → ζ} (hb : Function.Injective b) (hf : Function.Injective f) : Function.Injective fun (φ : F n₁) => (Rewriting.app (Rew.map b f)) φ

Instances

• LO.FirstOrder.Semiformula.instInjMapRewriting
• LO.FirstOrder.Semiformulaᵢ.instInjMapRewriting

class LO.FirstOrder.LawfulSyntacticRewriting (L : outParam Language) (S : ℕ → Type u_1) [LCWQ S] [SyntacticRewriting L S S] extends LO.FirstOrder.ReflectiveRewriting L ℕ S, LO.FirstOrder.TransitiveRewriting L ℕ S ℕ S ℕ S, LO.FirstOrder.InjMapRewriting L ℕ S ℕ S : Prop

• id_app {n : ℕ} (φ : S n) : (Rewriting.app Rew.id) φ = φ
• comp_app {n₁ n₂ n₃ : ℕ} (ω₁₂ : Rew L ℕ n₁ ℕ n₂) (ω₂₃ : Rew L ℕ n₂ ℕ n₃) (φ : S n₁) : (Rewriting.app (ω₂₃.comp ω₁₂)) φ = (Rewriting.app ω₂₃) ((Rewriting.app ω₁₂) φ)
• smul_map_injective {n₁ n₂ : ℕ} {b : Fin n₁ → Fin n₂} {f : ℕ → ℕ} (hb : Function.Injective b) (hf : Function.Injective f) : Function.Injective fun (φ : S n₁) => (Rewriting.app (Rew.map b f)) φ

Instances

• LO.FirstOrder.Semiformula.instLawfulSyntacticRewritingSyntacticSemiformula
• LO.FirstOrder.Semiformulaᵢ.instLawfulSyntacticRewritingSyntacticSemiformulaᵢ

theorem LO.FirstOrder.LawfulSyntacticRewriting.fix_allClosure {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] {n : ℕ} (φ : S n) : ∀' Rewriting.fix (∀* φ) = ∀* Rewriting.fix φ

@[simp]

theorem LO.FirstOrder.LawfulSyntacticRewriting.shifts_cons {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] {n : ℕ} (φ : S n) (Γ : List (S n)) : Rewriting.shifts (φ :: Γ) = Rewriting.shift φ :: Rewriting.shifts Γ

@[simp]

theorem LO.FirstOrder.LawfulSyntacticRewriting.shifts_nil {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] {n : ℕ} : Rewriting.shifts [] = []

theorem LO.FirstOrder.LawfulSyntacticRewriting.shifts_union {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] {n : ℕ} (Γ Δ : List (S n)) : Rewriting.shifts (Γ ++ Δ) = Rewriting.shifts Γ ++ Rewriting.shifts Δ

theorem LO.FirstOrder.LawfulSyntacticRewriting.shifts_neg {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] {n : ℕ} (Γ : List (S n)) : Rewriting.shifts (List.map (fun (x : S n) => ∼x) Γ) = List.map (fun (x : S n) => ∼x) (Rewriting.shifts Γ)

theorem LO.FirstOrder.LawfulSyntacticRewriting.shift_conj₂ {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] {n : ℕ} (Γ : List (S n)) : Rewriting.shift (⋀Γ) = ⋀Rewriting.shifts Γ

theorem LO.FirstOrder.LawfulSyntacticRewriting.shift_injective {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] {n : ℕ} : Function.Injective fun (φ : S n) => Rewriting.shift φ

@[simp]

theorem LO.FirstOrder.LawfulSyntacticRewriting.fix_free {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] {n : ℕ} (φ : S (n + 1)) : Rewriting.fix (Rewriting.free φ) = φ

@[simp]

theorem LO.FirstOrder.LawfulSyntacticRewriting.free_fix {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] {n : ℕ} (φ : S n) : Rewriting.free (Rewriting.fix φ) = φ

@[simp]

theorem LO.FirstOrder.LawfulSyntacticRewriting.substitute_empty {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] (φ : S 0) (v : Fin 0 → Semiterm L ℕ 0) : φ ⇜ v = φ

@[simp]

theorem LO.FirstOrder.LawfulSyntacticRewriting.app_substs_fbar_zero_comp_shift_eq_free {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] (φ : S 1) : (Rewriting.shift φ)/[Semiterm.fvar 0] = Rewriting.free φ

hom_substs_mbar_zero_comp_shift_eq_free

theorem LO.FirstOrder.LawfulSyntacticRewriting.free_rewrite_eq {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] (f : ℕ → SyntacticTerm L) (φ : S 1) : Rewriting.free ((Rewriting.app (Rew.rewrite fun (x : ℕ) => Rew.bShift (f x))) φ) = (Rewriting.app (Rew.rewrite (Semiterm.fvar 0 :>ₙ fun (x : ℕ) => Rew.shift (f x)))) (Rewriting.free φ)

theorem LO.FirstOrder.LawfulSyntacticRewriting.shift_rewrite_eq {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] (f : ℕ → SyntacticTerm L) (φ : S 0) : Rewriting.shift ((Rewriting.app (Rew.rewrite f)) φ) = (Rewriting.app (Rew.rewrite (Semiterm.fvar 0 :>ₙ fun (x : ℕ) => Rew.shift (f x)))) (Rewriting.shift φ)

theorem LO.FirstOrder.LawfulSyntacticRewriting.rewrite_subst_eq {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] (f : ℕ → SyntacticTerm L) (t : Semiterm L ℕ 0) (φ : S 1) : (Rewriting.app (Rew.rewrite f)) (φ/[t]) = ((Rewriting.app (Rew.rewrite (⇑Rew.bShift ∘ f))) φ)/[(Rew.rewrite f) t]

@[simp]

theorem LO.FirstOrder.LawfulSyntacticRewriting.free_substs_nil {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] (φ : S 0) : Rewriting.free (φ/[]) = Rewriting.shift φ

theorem LO.FirstOrder.LawfulSyntacticRewriting.rewrite_substs_nil {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] (f : ℕ → SyntacticTerm L) (φ : S 0) : (Rewriting.app (Rew.rewrite (⇑Rew.bShift ∘ f))) (φ/[]) = ((Rewriting.app (Rew.rewrite f)) φ)/[]

@[simp]

theorem LO.FirstOrder.LawfulSyntacticRewriting.cast_substs_eq {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] (t : SyntacticTerm L) (φ : S 0) : (φ/[])/[t] = φ

theorem LO.FirstOrder.LawfulSyntacticRewriting.rewrite_free_eq_subst {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] (t : SyntacticTerm L) (φ : S 1) : (Rewriting.app (Rew.rewrite (t :>ₙ fun (x : ℕ) => Semiterm.fvar x))) (Rewriting.free φ) = φ/[t]

def LO.FirstOrder.LawfulSyntacticRewriting.shiftEmb {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] {n : ℕ} : S n ↪ S n

Equations

• LO.FirstOrder.LawfulSyntacticRewriting.shiftEmb = { toFun := LO.FirstOrder.Rewriting.shift, inj' := ⋯ }

theorem LO.FirstOrder.LawfulSyntacticRewriting.shiftEmb_def {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] {n : ℕ} (φ : S n) : shiftEmb φ = Rewriting.shift φ

theorem LO.FirstOrder.LawfulSyntacticRewriting.allClosure_fixitr {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] {m : ℕ} (φ : S 0) : ∀* (Rewriting.app (Rew.fixitr 0 (m + 1))) φ = ∀' (Rewriting.app Rew.fix) (∀* (Rewriting.app (Rew.fixitr 0 m)) φ)

@[simp]

theorem LO.FirstOrder.LawfulSyntacticRewriting.mem_shifts_iff {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] {n : ℕ} {φ : S n} {Γ : List (S n)} : Rewriting.shift φ ∈ Rewriting.shifts Γ ↔ φ ∈ Γ

@[simp]

theorem LO.FirstOrder.LawfulSyntacticRewriting.shifts_ss {L : Language} {S : ℕ → Type u_1} [LCWQ S] [SyntacticRewriting L S S] [LawfulSyntacticRewriting L S] {n : ℕ} (Γ Δ : List (S n)) : Rewriting.shifts Γ ⊆ Rewriting.shifts Δ ↔ Γ ⊆ Δ

theorem LO.FirstOrder.Rewriting.embedding_injective {ο : Type u_1} {ξ : Type u_2} [IsEmpty ο] {O : ℕ → Type u_3} {F : ℕ → Type u_4} [LCWQ O] [LCWQ F] {L : Language} {n : ℕ} [Rewriting L ο O ξ F] [InjMapRewriting L ο O ξ F] : Function.Injective fun (φ : O n) => ↑φ

@[simp]

theorem LO.FirstOrder.Rewriting.emb_univClosure {ο : Type u_1} {ξ : Type u_2} [IsEmpty ο] {O : ℕ → Type u_3} {F : ℕ → Type u_4} [LCWQ O] [LCWQ F] {L : Language} {n : ℕ} [Rewriting L ο O ξ F] {σ : O n} : ↑(∀* σ) = ∀* ↑σ

theorem LO.FirstOrder.Rewriting.embedding_substitute_eq_substitute_embedding {ο : Type u_1} {ξ : Type u_2} [IsEmpty ο] {O : ℕ → Type u_3} {F : ℕ → Type u_4} [LCWQ O] [LCWQ F] {L : Language} {k n : ℕ} [Rewriting L ο O ο O] [Rewriting L ο O ξ F] [Rewriting L ξ F ξ F] [TransitiveRewriting L ο O ο O ξ F] [TransitiveRewriting L ο O ξ F ξ F] (φ : O k) (v : Fin k → Semiterm L ο n) : ↑(φ ⇜ v) = ↑φ ⇜ fun (i : Fin k) => Rew.emb (v i)

coe_substs_eq_substs_coe

theorem LO.FirstOrder.Rewriting.embedding_substs_eq_substs_coe₁ {ο : Type u_1} {ξ : Type u_2} [IsEmpty ο] {O : ℕ → Type u_3} {F : ℕ → Type u_4} [LCWQ O] [LCWQ F] {L : Language} {n : ℕ} [Rewriting L ο O ο O] [Rewriting L ο O ξ F] [Rewriting L ξ F ξ F] [TransitiveRewriting L ο O ο O ξ F] [TransitiveRewriting L ο O ξ F ξ F] (φ : O 1) (t : Semiterm L ο n) : ↑(φ/[t]) = ↑φ/[Rew.emb t]

coe_substs_eq_substs_coe₁

@[simp]

theorem LO.FirstOrder.Rewriting.shifts_emb {L : Language} {ο : Type u_1} [IsEmpty ο] {O : ℕ → Type u_3} {F : ℕ → Type u_4} [LCWQ O] [LCWQ F] {n : ℕ} [Rewriting L ο O ℕ F] [Rewriting L ℕ F ℕ F] [TransitiveRewriting L ο O ℕ F ℕ F] (Γ : List (O n)) : shifts (List.map embedding Γ) = List.map embedding Γ