Library Deduxit.Linear.Terms
First-order terms
- a symbol applied to a list of terms (a constant is a symbol applied to none);
- a variable bound by a quantifier;
- an eigenvariable.
A term.
a bound variable, a de Bruijn index
an eigenvariable
f(t₁, …, tₙ)
Substitutes u for the bound variable k of t.
Fixpoint tsubst (k : nat) (u : term) (t : term) : term :=
match t with
| bound n ⇒ if Nat.eqb n k then u else bound n
| eigen a ⇒ eigen a
| tapp f l ⇒ tapp f (map (tsubst k u) l)
end.
match t with
| bound n ⇒ if Nat.eqb n k then u else bound n
| eigen a ⇒ eigen a
| tapp f l ⇒ tapp f (map (tsubst k u) l)
end.
Whether the eigenvariable a occurs in t.
Fixpoint toccurs (a : nat) (t : term) : bool :=
match t with
| bound _ ⇒ false
| eigen b ⇒ Nat.eqb a b
| tapp _ l ⇒ existsb (toccurs a) l
end.
match t with
| bound _ ⇒ false
| eigen b ⇒ Nat.eqb a b
| tapp _ l ⇒ existsb (toccurs a) l
end.
Whether t is closed: no bound variable occurs in it, so it can be
substituted under any number of quantifiers without being
captured.