# 9.3: Functions

9-3. FUNCTIONS

Often formal presentations of functions leave students bewildered. But if you have done any high school algebra you have an intuitive idea of a function. So let's start with some simple examples from algebra.

For our algebraic examples, the letters 'x', 'y', and 'z' represent variables for numbers. Consider the expression 'y = 2x + 7'. This means that if you put in the value 3 for x you get the value 2 x 3 + 7 = 13 for y. If you put in the value 5 for x, you get the value 2 x 5 + 7 = 17 for y. Thus the expression 'y = 2x + 7' describes a rule or formula for calculating a value for y if you give it a value for x. The formula always gives you a definite answer. Given some definite value for x, there is exactly one value for y which the formula tells you how to calculate.

Mathematicians often use expressions like 'f(x)' for functions. Thus, instead of using the variable y in the last example, I could have written 'f(x) = 2x + 7' This means exactly what 'y = 2x + 7' means. When you put in a specific number for x, 'f(x)' serves as a name for the value y, so that we have y = flx). In particular, 'f(3) is a name for the number which results by putting in the value 3 for x in 2x + 7. That is, 'f(3)' is a name for the number 13, the number which results by putting in the value 3 for x in f(x) = 2x + 7.

This is all there is to functions in logic. Consider the name 'a'. Then 'f(a)' acts like another name. To what does 'f(a)' refer? That depends, of course, on what function f( ) is, which depends on how 'f( )' is interpreted. In specifying an interpretation for a sentence in which the function symbol 'f( )' occurs, we must give the rule which tells us, for any name s, what object f(s) refers to. When we deal with interpretations in which there are objects with no names, this must be put a little more abstractly: We must say, for each object (called the Argument of the function), what new object (called the Value of the function) is picked out by the function f( ) when f( ) is applied to the first object. The function must be well defined, which means that for each object to which it might be applied, we must specify exactly one object which the function picks out. For each argument there must be a unique value.

So far I have talked only about one place functions. Consider the example of the mathematical formula 'z = 3x + 5y - 8'. which we can also write as 'z = g(x,y)' or as 'g(x,y) = 3x + 5y - 8'. Here g( , ) has two '

148 Identity, Functions, and Dejnite Descripciorrr 9-3. Functions 149 arguments.

You give the function two input numbers, for example, x = 2 and y = 4, and the function gives you a single, unique output-in this case, the number 3 x 2 + 5 x 4 - 8 = 18. Again, the idea carries over to logic. If 'g( , )' is a two place function symbol occurring in a sentence, in giving an interpretation for the sentence we must specify the unique object the function will pick out when you give it a pair of objects. If our interpretation has a name for each object the same requirement can be expressed in this way: For any two names, s and t, 'g(s,t)' refers to a unique object, the one picked out by the function g( , ) when g( , ) is applied to the arguments s and t. We can characterize functions with three, four, or any number of argument places in the same kind of way.

To summarize

The interpretation of a one place function specifies, for each object in the interpretation's domain, what object the function picks out as its value when the function is applied to the first object as its argument. The interpretation of a two place function similarly specifies a value for each pair of arguments. Three and more place functions are interpreted similarly.

Incidentally, the value of a function does not have to differ from the argument. Depending on the function, these may be the same or they may be different. In particular, the trivial identity function defined by (Vx)(f(x) = X) is a perfectly well-defined function.

In the last sentence I applied a function symbol to a variable instead of a name. How should you understand such an application? In an interpretation, a name such as 'a' refers to some definite object. A variable symbol such as 'x' does not. Similarly, 'f(a)' refers to some definite object, but Xx)' does not. Nonetheless, expressions such as 'f(x)' can be very useful. The closed sentence '(Vx)Bf(x)' should be understood as saying that every value of 'f(x)' has the property named by 'B'. For example, let us understand 'Bx' as 'x is blond' and 'f(x)' as referring to the father of x. That is, for each person, x, f(x) is the father of x, so that Xa)' refers to Adam's father, Xe)' refers to Eve's father, and so on. Then '(Vx)Bf(x)' says that everyone's father is blond.

In sum, function symbols extend the kind of sentences we can write. Previously we had names, variables, predicate symbols, and connectives. Now we introduce function symbols as an extension of the category of names and variables. This involves the new category called Tern:

We extend the vocabulary of predicate logic to include Function Symboh, written with lowercase italicized letters followed by parentheses with places for writing in one, two, or more arguments.

All names and variables are Tern. A function symbol applied to any term or terms (a one place function symbol applied to one term, a two place function symbol applied to two terms, etc.) is again a term. Only such expressions are terms.

In forming sentences, terms function exactly as do names and variables. One may be written after a one place predicate, two after a two place predicate, and so on.

Do not confuse function symbols (lowercase italicized letters followed by parentheses with room for writing in arguments) with such expressions as P(u) and R(u,v). These latter expressions are really not part of predicate logic at all. They are part of English which I use to talk about arbitrary open predicate logic sentences.

Notice that these definitions allow us to apply functions to functions: If 'f( )' is a one place function symbol, 'f(f(a))' is a well-defined term. In practice, we leave out all but the innermost parentheses, writing 'f(f(a))' as tff(a)' What does such multiple application of a function symbol mean? Well, if f(x) = x2, then ff(x) is the square of the square of x. If x = 3, thenff(3) = (3')' = 9* = 81. In general, you determine the referent ofthat is, the object referred to by -ma)' as follows: Look up the referent of 'a'. Apply the function f to that object to get the referent of 'f(a)'. Now apply f a second time to this new object. The object you get after the second application off is the referent of tff(a)'.

Function symbols can be combined to form new terms in all kinds of ways. If 'f( )' is a one place function symbol and 'g( , )' is a two place function symbol, the following are all terms: 'f(a)', Xy)', 'g(a,x)', 'fg(a,x)'- that is, flg(aA1. 'g[f(a), f(b)l', and gf.f(x), g(a,b)l'.

We need one more definition:

A term in which no variables occur is called a Consant or a Constant Term.

Only constant terms actually refer to some specific object in an interpretation. But closed sentences which use nonconstant terms still have truth values. In applying the truth definitions for quantifiers, we form substitution instances, substituting names for variables within function symbols as well as elsewhere. Thus, in applying the definition for the truth of a universally quantified sentence in an interpretation to '(Vx)Laf(x)', we look at the substitution instances '4(a)', 'Laf(b)', 'Laf(c)', and so on. We then look to see if the relation L holds between a and the object f(a), between a and the object f(b), and so on. Only if all these instances hold is '(Vx)Laf(x)' true in the interpretation.

The rules for functions simply reflect the fact that constant terms formed by applying function symbols to other constant terms have definite referents, just as names do. However, the generality of these new referring terms may be restricted. For example, the constant function f defined by (Vx)(f(x) = a) can only refer to one thing, namely, a. Thus, when it is important that nothing be assumed about a constant term we must use a name and not a function symbol applied to another constant term.

150 Identity, Functions, Md Definite Descriptions

For derivations this means that we should treat constant terms all alike in applying the rules VE and 31. In applying 3E, our isolated name must still be a name completely isolated to the subderivation to which the 3E rule applies. (Strictly speaking, if you used an isolated function symbol applied to an isolated name, no difficulty would arise. But it's simpler just to let the isolated name requirement stand as a requirement to use an isolated name.)

In applying VI only names can occur arbitrarily. For example, we must never put a hat on a term such as 'f(a)'. The hat means that the term could refer to absolutely anything, but often the value of a function is restricted to only part of an interpretation's domain. So we can't apply VI to a function symbol. However, if a name appears in no governing premise or assumption and occurs as the argument of a function symbol, we can apply VI to the name. For example, if 'a' appears in no governing premise or assumption, we could have 'Bf(2)' as a line on a derivation, to which we could apply VI to get '(x)Bf(x)'. To summarize

In derivations, treat all constant terms alike in applying VE and 31. Apply VI and 3E only to names.

Let's try this out by showing that '(Vx)(3y)(f(x) = y)' is a logical truth. This sentence says that for each argument a function has a value. The way we treat functions in giving interpretations guarantees that this statement is true in all interpretations. If our rules are adequate, this fact should be certified by the rules:

Note that this derivation works without any premise or assumption. =I allows us to introduce the identity of line 1. Since 'a' does not occur in any governing premise or assumption, it occurs arbitrarily, although the larger term 'f(a)' does not occur arbitrarily. 'a' could refer to absolutely anything-that is, the argument to which the function is applied could be any object at all. However, the result of applying the function f to this arbitrary object might not be just anything. In line 2 we apply 31 to the whole term 'f(a)', not just to the argument 'a'. This is all right because we are existentially, not universally, generalizing. If f(5) =f(l), then f(2) is identical with something. Finally, in line 3, we universally generalize on the remaining arbitrarily occurring instance of 'a'.

Let's try something harder. '(Vx)(3y)lf(x) = y & (Vz)(f(x) = z 3 z = y)]' says that for each argument the function f has a value and furthermore this value is unique. Again, the way we treat functions in giving interpretations guarantees that this statement is true in all interpretations. So our rules had better enable us to show that this sentence is a logical truth:

One more example will illustrate 3E and VE as applied to terms using function symbols. Note carefully how in applying VE the constant term to use in this problem is not a name, but 'f(a)', a function symbol applied to a name:

Similar thinking goes into the rules for trees. All constant terms act as names when it comes to the rule V. But for the rule 3 we want a name that could refer to anything in the interpretation-that was the reason for requiring that the name be new to the branch. So for 3 we need a new name, which must be a name, not a function symbol, applied to another constant term:

In trees, instantiate all universally quantified sentences with all constant terms that occur along the branch, unless the branch closes. Instantiate each existentially quantified sentence with a new name.

Let us illustrate the new rules with the same sentence as before, '(Vx)(3y)lf(x) = y & (Vz)(f(x) = z 3 z = y)]'. As I mentioned, this sentence says that f has a unique value for each argument. Since the way we treat functions in giving interpretations ensures that this sentence is true in all interpretations, our rules had better make this sentence come out to be a logical truth:

152 Identity, Funcfimrr, and Definite Desmitk 9-4. Definite Desmitions 153 -

(Vx)(3y){f(x) = y & (Vz)[f(x) = z 3 z = yl} (3x)(Vy)-{f(x) = y & (Vz)[f(x) = z 3 z = yl}

Notice that to get everything to close I used the term 'f(a)' in substituting into line 3. Also, note that the right branch does not close at line 9. Line 9 is not, strictly speaking, the negation of line 8 since, strictly speaking, 'f(a) = b' and 'b = f(a)' are different sentences.

The occurrence of functions in trees has an unpleasant feature. Suppose that a universally quantified sentence such as '(Vx)Pf(x)' appears on a tree. This will be instantiated, at least once, say, with 'a', giving 'Pf(a)'. But now we have a new constant, 'f(a)', which we must put into '(Vx)Pf(x))' giving 'Pff(a)'. This in turn gives us a further constant, 'ff(a)'-and clearly we are off on an infinite chase. In general, open trees with function symbols are infinite when, as in '(Vx)Pf(x)', a function symbol occurs as a nonconstant term inside the scope of a universal quantifier

EXERCISES

9-10. Provide derivations andor trees to establish that the following are logical truths:

9-11. Provide derivations andor trees to establish the validity of the following arguments: