Theorem: LO.FirstOrder.UFormula.bv_primrec (Logic/FirstOrder/Computability/Formula.lean)

State before:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
⊢ Primrec bv
Tactic:
have hr : Primrec (fun p => ((List.ofFn p.2.2).map UTerm.bv).sup : (k : ℕ) × L.Rel k × (Fin k → UTerm L μ) → ℕ) :=
  (list_sup nat_max).comp
    (list_map (by apply sigma_finArrow_list_ofFn.comp (sigma_prod_right (β := L.Rel))) (UTerm.bv_primrec.comp₂ Primrec₂.right))
State after:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
⊢ Primrec bv

State before:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
⊢ Primrec bv
Tactic:
have hb : Primrec₂ (fun m n => max m n : ℕ → ℕ → ℕ) := Primrec.nat_max
State after:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
⊢ Primrec bv

State before:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
⊢ Primrec bv
Tactic:
have hq : Primrec (fun n => n.pred : ℕ → ℕ) := Primrec.pred
State after:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
⊢ Primrec bv

State before:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
⊢ Primrec bv
Tactic:
have := elim_primrec 0 0 hr hr hb hb hq hq
State after:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
⊢ Primrec bv

State before:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
⊢ Primrec bv
Tactic:
exact this.of_eq (fun p => by
  simp[Function.comp]
  induction p <;> simp[elim, *]
  { simp[List.sup_ofFn] }
  { simp[List.sup_ofFn] })
State after:
no goals

State before:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
⊢ Primrec fun p => List.ofFn p.snd.2
Tactic:
apply sigma_finArrow_list_ofFn.comp (sigma_prod_right (β := L.Rel))
State after:
no goals

State before:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
p : UFormula L μ
⊢ elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) (fun n => n.pred) p =
    p.bv
Tactic:
simp[Function.comp]
State after:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
p : UFormula L μ
⊢ elim 0 0 (fun {k} f v => (List.ofFn fun x => (v x).bv).sup) (fun {k} f v => (List.ofFn fun x => (v x).bv).sup)
      (fun m n => max m n) (fun m n => max m n) (fun n => n - 1) (fun n => n - 1) p =
    p.bv

State before:
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
p : UFormula L μ
⊢ elim 0 0 (fun {k} f v => (List.ofFn fun x => (v x).bv).sup) (fun {k} f v => (List.ofFn fun x => (v x).bv).sup)
      (fun m n => max m n) (fun m n => max m n) (fun n => n - 1) (fun n => n - 1) p =
    p.bv
Tactic:
induction p <;> simp[elim, *]
State after:
case rel
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
arity✝ : ℕ
a✝¹ : L.Rel arity✝
a✝ : Fin arity✝ → UTerm L μ
⊢ (List.ofFn fun x => (a✝ x).bv).sup = Finset.univ.sup fun x => (a✝ x).bv

case nrel
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
arity✝ : ℕ
a✝¹ : L.Rel arity✝
a✝ : Fin arity✝ → UTerm L μ
⊢ (List.ofFn fun x => (a✝ x).bv).sup = Finset.univ.sup fun x => (a✝ x).bv

State before:
case rel
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
arity✝ : ℕ
a✝¹ : L.Rel arity✝
a✝ : Fin arity✝ → UTerm L μ
⊢ (List.ofFn fun x => (a✝ x).bv).sup = Finset.univ.sup fun x => (a✝ x).bv

case nrel
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
arity✝ : ℕ
a✝¹ : L.Rel arity✝
a✝ : Fin arity✝ → UTerm L μ
⊢ (List.ofFn fun x => (a✝ x).bv).sup = Finset.univ.sup fun x => (a✝ x).bv
Tactic:
{ simp[List.sup_ofFn] }
State after:
case nrel
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
arity✝ : ℕ
a✝¹ : L.Rel arity✝
a✝ : Fin arity✝ → UTerm L μ
⊢ (List.ofFn fun x => (a✝ x).bv).sup = Finset.univ.sup fun x => (a✝ x).bv

State before:
case nrel
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
arity✝ : ℕ
a✝¹ : L.Rel arity✝
a✝ : Fin arity✝ → UTerm L μ
⊢ (List.ofFn fun x => (a✝ x).bv).sup = Finset.univ.sup fun x => (a✝ x).bv
Tactic:
{ simp[List.sup_ofFn] }
State after:
no goals

State before:
case rel
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
arity✝ : ℕ
a✝¹ : L.Rel arity✝
a✝ : Fin arity✝ → UTerm L μ
⊢ (List.ofFn fun x => (a✝ x).bv).sup = Finset.univ.sup fun x => (a✝ x).bv
Tactic:
simp[List.sup_ofFn]
State after:
no goals

State before:
case nrel
L : Language
μ : Type v
inst✝⁴ : (k : ℕ) → Primcodable (L.Func k)
inst✝³ : (k : ℕ) → Primcodable (L.Rel k)
inst✝² : UniformlyPrimcodable L.Func
inst✝¹ : UniformlyPrimcodable L.Rel
inst✝ : Primcodable μ
hr : Primrec fun p => (List.map UTerm.bv (List.ofFn p.snd.2)).sup
hb : Primrec₂ fun m n => max m n
hq : Primrec fun n => n.pred
this :
  Primrec
    (elim 0 0 (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup)
      (fun {k} f v => (List.map UTerm.bv (List.ofFn ⟨k, (f, v)⟩.snd.2)).sup) (fun m n => max m n) (fun m n => max m n)
      (fun n => n.pred) fun n => n.pred)
arity✝ : ℕ
a✝¹ : L.Rel arity✝
a✝ : Fin arity✝ → UTerm L μ
⊢ (List.ofFn fun x => (a✝ x).bv).sup = Finset.univ.sup fun x => (a✝ x).bv
Tactic:
simp[List.sup_ofFn]
State after:
no goals