8.3 Function Symbols and Constants

Function and Constant Symbols

Function symbols and constants expand what predicate logic can express. Constants let you name specific, fixed objects in your domain, while function symbols represent operations that take inputs and produce outputs. Together with variables, they form terms, which are the building blocks you plug into predicates to make formulas.

Defining Function and Constant Symbols

Constant symbols refer to specific, fixed elements in the domain of discourse. They never take arguments and always pick out the same object. For example, if your domain is the natural numbers, you might use a constant $c$ to denote the number zero.

Function symbols represent operations that take one or more arguments and return a single value from the domain. Think of them as mappings: you feed in objects, and the function gives back an object.

• The arity of a function symbol is the number of arguments it takes.
  • A unary function (arity 1) takes one argument, like a "successor" function $s(x)$.
  • A binary function (arity 2) takes two arguments, like an addition function $f(x, y)$.

A useful way to think about it: constants are actually just function symbols with arity 0. They take no inputs and simply return a fixed element.

Syntax and Notation

• Function symbols are typically written as lowercase letters: $f$, $g$, $h$
• Constant symbols are also lowercase letters: $a$, $b$, $c$
• The arity of a function shows up in how many argument places follow the symbol:
  • $f(x, y)$ has arity 2
  • $g(x)$ has arity 1
• Functions and constants can be combined into more complex expressions. For instance, $f(a, g(b))$ applies the function $f$ to two arguments: the constant $a$ and the result of applying $g$ to $b$.

Terms

Defining Terms

A term is any well-formed expression that refers to an object in the domain of discourse. Terms are what you slot into the argument places of predicates to build atomic formulas.

Terms come in two varieties:

• Simple terms: a single variable ($x$, $y$) or a single constant ($a$, $b$).
• Complex terms: formed by applying a function symbol to other terms, like $f(a)$ or $g(x, b)$.

More precisely, the set of terms is defined recursively:

1. Every variable is a term.
2. Every constant symbol is a term.
3. If $f$ is a function symbol of arity $n$, and $t_1, t_2, \ldots, t_n$ are terms, then $f(t_1, t_2, \ldots, t_n)$ is a term.
4. Nothing else is a term.

Constructing Complex Terms

Complex terms are built by applying function symbols to simpler terms, and there's no limit to how deeply you can nest them.

For example, $h(f(a), g(b, c))$ is constructed in layers:

1. Start with the constants $a$, $b$, and $c$ (simple terms).
2. Apply the unary function $f$ to $a$, producing the complex term $f(a)$.
3. Apply the binary function $g$ to $b$ and $c$, producing $g(b, c)$.
4. Apply the binary function $h$ to the results from steps 2 and 3, producing $h(f(a), g(b, c))$.

At each step, the arity of the function must match the number of arguments you provide. Writing $g(a)$ when $g$ is a binary function symbol would be a syntax error.

Semantics

Interpreting Function Symbols

On their own, symbols like $f$ and $a$ are just letters. An interpretation (also called a structure) gives them concrete meaning by specifying:

• A domain of discourse (the set of objects you're reasoning about).
• A mapping from each constant symbol to a specific element in the domain.
• A mapping from each function symbol to an actual function on the domain, respecting arity. A binary function symbol must map to a function that takes exactly two inputs.

The same symbol can mean different things under different interpretations. Under one interpretation, $f(x, y)$ might represent addition on the integers; under another, it might represent multiplication.

Evaluating Terms

Once you have an interpretation (and an assignment of domain elements to any variables), you can compute the value of any term by working from the inside out:

1. Constants: Look up the element assigned by the interpretation.
2. Variables: Look up the element assigned by the variable assignment.
3. Complex terms: Evaluate all the subterms first, then apply the concrete function that the interpretation assigns to the function symbol.

For example, suppose your domain is the integers, $a$ is interpreted as 3, $b$ as 5, $g$ as the successor function (adds 1), and $f$ as addition. To evaluate $f(g(a), b)$:

1. $a$ evaluates to 3.
2. $g(a)$ evaluates to $3 + 1 = 4$.
3. $b$ evaluates to 5.
4. $f(g(a), b)$ evaluates to $4 + 5 = 9$.

This recursive evaluation process is what lets predicate logic assign precise, determinate meanings to even deeply nested terms.