Lemma·L62
Term(L) is the least term-admissible set
The set of terms is itself term-admissible, and it is contained in every term-admissible set: it is built from variables and function applications, and nothing more.
For a language
: (i)
is term-admissible for
; (ii)
for every
term-admissible for
.
In words
The set of terms is itself closed under term formation, and it sits inside every other set with that closure property: it is the smallest one there is.
Rests onF09
Never needed: F02 · F03 · F04 · F05 · F06 · F08 · F10 · F11 · F12 · F13 · F14 · A01 · A02 · A03 · A04 · A05 · A06 · A07 · A08 (computed from the citation graph, not asserted).
Proof
- 1
- 2
- 3(i), closure clause: let with , and let with . Let be any term-admissible set; by part (ii), , so is also a member of with (each of its values lies in ). By the closure clause of D081 applied to : . As was an arbitrary term-admissible set (universal generalization), belongs to every term-admissible set, i.e. it lies in by D082. So is term-admissible.
∎
Remarks
The two parts together say
is the least term-admissible set, the precise sense in which the terms of
are "variables, function applications, and nothing more". This licenses structural induction on terms: to prove a property holds of every term, it suffices to prove it holds of every
and is preserved by
whenever it already holds of every entry of
- exactly the naturals' own induction principle, one level up, and proved the same way L04 proves it for
. Formulas are built by the same technique next, over both terms and relation symbols.