(You really want to know more about mathematical logic, or even model theory, to understand these concepts; this is just a short explanation which should help you keep your head above the water in the NSA series)
Every
formal language talks about
something. To do this, it uses a few
universal symbols: things like "&" for
conjunction" or "
and", "~" for "
negation" or "
not", a symbol used to say
for all, a symbol "=" for "
equal to", and maybe a few more convenient symbols which may be defined in terms of this small group ("v" for "
disjunction" or "
or", a symbol for
exists, a symbol for "
not equal to", ...). These symbols let it say generalities of
logic, but it cannot yet talk about the world!
It also needs to be able to talk about some of the objects in the world. This is achieved by adding 3 categories of names to the language:
- constants
- A constant is a symbol c which refers to some object in the world. For instance, in a language to describe the real numbers, "0", "1" and "e" may all be constants. Not every object of the world must have a name! The connection between a constant and the actual object is given by the model.
- predicate names
- A predicate name is a symbol P and an arity (a natural number) k such that P(x1,...,xk) is a valid sentence whenever the x's are all valid terms. In other words, we give names to some predicates on objects. For instance, for our real numbers language, we could have a 2-place predicate name "<" and a 1-place predicate name "Integer". Again, the connection to actual predicates is given by the model.
- function names
- A function name is a symbol f and an arity k such that f(x1,...,xk) is a valid term whenever the x's are all valid terms. Here we're giving names to some functions of objects. For our real numbers language, we could have 2-place function names "+" and "*", and a 1-place function name "sin". Once more, the model connects the names to actual functions.