## 6 Jul 2016

### Suppes (11.1) Introduction to Logic, 'Definition [of functions]’, summary

[Search Blog Here. Index-tags are found on the bottom of the left column.]

[The following is summary. My commentary is in brackets. Boldface is mine. I apologize in advance for any distracting typos or other errors.]

Summary of

Patrick Suppes

Introduction to Logic

Ch. 11. Functions

§11.1 Definition

Brief summary:

A function is a binary relation that relates to each element of its domain a unique element of its counterdomain:

A function R is a binary relation such that if xRy and xRz then y = z.

Consider the following cases of binary relations:

R1 = {<1, 2>, <Madison, Pinckney>}

R2 = {<1, 2>, <1, 3>, <Plato, Aristotle>}

R1 is a function, but  Ris not, because in R2, the number 1 is related to two members of the counterdomain, namely, 2 and 3, and thus the member of the domain is not related to a unique member of the counterdomain. We often used lowercase letters to symbolize functions, and they normally take the form f(x) = [something]. The domain of a function is called the domain of definition and the counterdomain, the range of values. A function is sometimes said to map its domain onto its range, and thus a function is also called a mapping. And when x is an element of the domain of f, then f(x) is the image of x. A binary operation on the set A is a function whose domain is A × A and whose range is a subset of A. For example, N = the positive integers and + is the binary operation of addition applied to positive integers. In this case, + is a binary operation from N × N to N. The range of + is N ~ {1}, as no two positive integers add up to one.

Summary

Suppes begins with Webster’s Dictionary’s definition for the mathematical notion of a function:

A magnitude so related to another magnitude that to values of the latter there correspond values of the former.

(Suppes 229, qtg Webster’s)

Suppes’ problem here is that there is something unclear in the definition. What are magnitudes and what does it mean for them to correspond? Suppes then gives a definition that is equally problematic given that certain important terms’ meanings are still not obvious.

A variable is a quantity to which an unlimited number of values can be assigned in an investigation . . . . When two variables are so related that the value of the first variable is determined when the value of the second is given, then the first variable is said to be a function of the second . . . . The second variable . . . is called the independent variable, or argument; and the first variable . . . is called the dependent variable, or function.

(229)

Suppes then gives a better definition:

A function is a rule which assigns to each element of a given set a unique ele­ment of some other, not necessarily distinct, set.

(229)

He says it is still problematic, because the notion of “rule” is vague (229-230).

[Suppes will now give the good definition for function. Before we look at it, let us review some concepts from section 10.2. We first think of a binary relation. Let us suppose xRy. And let us just think of R meaning “is the parent of”. There will be many people in the domain of discourse. But only those with children can take the x variable. However, every person will be eligible to take the y variable. The set of objects that can take the first variable, in this example, x, is called the domain of the relation. Then, the set of things that can take the second variable, in this case y, is the counterdomain or converse domain. And finally, the field is the combination (the union) of both the sets for the first and second terms. The following quotes from our summary of section 10.2:

The three concepts deal with the sets of objects that can be substituted for the parts of the binary relation. The set that can be substituted for the first of the two parts, as in the x of ⟨x, y⟩ is called the domain of the relation. The set for the second part (for the y) is the counterdomain or the converse domain. And finally, the field is the combination (the union) of both the sets for the first and second terms. Here is some quotation for these concepts:

If R is a binary relation, then the domain of R – in symbols: D(R) – is the set of all things x such that, for some y, ⟨x, y⟩ ∈ R. Thus if M is the | relation which consists of all couples ⟨x, y⟩ such that x is the mother of y, then the domain of M is the set of all women who are not childless. If

R1 = {⟨Λ, Plato⟩, ⟨Jane Austen, 101⟩, ⟨the youngest bride in Tibet, Richelieu⟩},

then

D(R1) = {Λ, Jane Austen, the youngest bride in Tibet}.

The counterdomain (or converse domain) of a binary relation R (in symbols : C(R)) is the set of all things y such that, for some x, ⟨x, y⟩ ∈ R. The counterdomain of the relation M considered just above is the set of all people – since everyone has a mother. If B is the relation which consists of all couples ⟨x, y⟩ such that x is the brother of y, then the domain of B is the set of all men who have at least one brother or sister, and the counterdomain is the set of all people who have at least one brother. We have for the relation R1 defined above:

C(R1) = {Plato, 101, Richelieu}.

The field of a binary relation R (in symbols: F(R)) is the union of its domain and its counterdomain. Thus z belongs to the field of a binary relation R if and only if either ⟨x, z⟩ ∈ R for some x or ⟨z, y⟩ ∈ R for some y. The field of the relation B considered just above is the set of all people who belong to families containing at least two children, at least one of which is male. As another example,

F(R1) = {Λ, Jane Austen, the youngest bride in Tibet, Plato, 101, Richelieu}.

(Suppes 212)

A function will be defined as a binary relation. And what makes it special is that it relates for each member of the domain a unique member of the counterdomain. What is important is the uniqueness of the member of the counterdomain. The functional relation establishes a certain consistency of correlation between the domain and counterdomain.]

Fortunately there is a way out which bypasses these difficulties. We may define functions as binary relations which relate to each element of their domains a unique element of their counterdomains. More formally, a function R is a binary relation such that if xRy and xRz then y = z.

You are probably used to thinking of functions in numerical terms, but there is no necessity for this. For example, in our society the relation of being a husband is a function, since a person has at most one wife (at a given time). On the other hand, the relation of being a mother is not a function since one person can be the mother of several distinct children, but the converse is a function. It will be useful to consider some simple constructed relations. Let

R1 = {<1, 2>, <Madison, Pinckney>}

R2 = {<1, 2>, <1, 3>, <Plato, Aristotle>}.

It should be clear at once that R1 is a function and R2 is not, but to avoid any possible misunderstandings let us examine the situation in some detail. The domain of R1 is the set

To each element in D(R1) there corresponds a unique element in the counterdomain of R1 (i.e., C(R1)). Thus,

1 R1 2    and    Madison R1 Pinckney.

The domain of R2 is the set

{1, Plato}.

To Plato there corresponds a unique element in C(R2), namely, Aristotle, but to the number one there does not correspond a unique element in C(R2), for we have:

1 R2 2    and    1 R2 3,

and

2 ≠ 3

Thus R2 is not a function.

(Suppes 230)

[Suppes will mention our two ways of noting relations and then add a third. I am not certain if I will get it right, but let me try to characterize them. The first way to notate relations treats them as predicates to constants or variables. In Suppes’ system, for binary relations we place the symbol in between the terms it predicates, as in xRy (See section 10.2). The other way treats binary relations as sets, namely, the sets of couples that are related by the relation, as in: <x, y> ∈ R (See section 10.6). Now we introduce the third notation that is for binary relations that are functions. Here the relation symbol comes first, then next to it in parentheses is the domain term, then an equals sign, and finally the counterdomain term. Often lowercase letters (especially the letter ‘f’) are used for the function symbol.]

We have already used two notations for relations: xRy and <x, y> ∈ R. We now introduce a third and customary notation for the special case of functions. In the case of R1 above, which is a function, we write :

R1(1) = 2,

Notice that this special functional notation cannot be used for relations which are not functions. For example, if we apply it to R2 we obtain the following absurdity:

R2(1) = 2,

R2(1) = 3,

and hence

2 = 3.

It is often convenient to use lower case letters to denote functions. For example,

f1 = {<Romeo, Juliet>, <Abelard, Heloise>},

and

f1(Romeo) = Juliet,

f1(Abelard) = Heloise.

(Suppes 230-231)

Suppes now begins discussing functions as they are used in mathematics. He notes that they are often formulated using equations, like:

f2(x) = x2 + 2x + 5

Thus,

f2(1) = 8 and f2(2) = 13

(Suppes 231)

Suppes then notes that a function does not need to be defined by just one equation. [What we should remember of course is that even when it is defined by more than one equation, the function will only assign one unique term in the counterdomain for ones in the domain. I am not sure at this point, but it seems this might be ensured by dividing the domain up such that certain parts are calculated using one formula and the other parts with other formulas, so that way, perhaps, the same number in the domain is not calculated twice using an additional equation.]

A function need not be defined by a single equation. Consider, for instance, the function g such that the domain of g is the set of all real numbers and for any real number x, (1) is equivalent to the more formal expression:

(2)     g(x) = y ↔ [(x ≤ 0 → y = x2) & (x > 0 → y 5x3 + 17)],

but for obvious typographical reasons it is customary to use the more informal notation, which is also often written:

(Suppes 231)

In addition to giving the equations, it is formally required that you state the domain of the function. However, sometimes it is obvious and can be left unmentioned (231-232).

Suppes then gives an example of a function that is defined with three equations. It is for the function h whose domain is the set of positive real numbers and which is such that for any positive real number x (Suppes 232)

[Suppes then makes a distinction between linguistic and set-theoretical entities, and he places functions under the heading of set-theoretical. One important aspect of set-theoretical entities is that they are not a part of a language. The distinction is not entirely clear to me, so let me quote.]

It also needs to be emphasized that a function is a set-theoretical, not a linguistic, entity. Functions exist independent of any language. We may digress for a moment and classify the main entities introduced in this book as set-theoretical or linguistic.

 LINGUISTIC SET-THEORETICAL Formulas Individuals Sentences Ordered Couples Sentential Connectives Sets Variables The empty set Terms Relations Quantifiers Functions

Linguistic entities are, of course, always part of some language, whereas set-theoretical entities in general are not. At first blush it may seem strange to say that an individual like Thomas Aquinas is a set-theoretical entity. The justification is that individuals are the ingredients out of which we build up sets. At level zero we have individuals, at level one sets of individuals, at level two sets of sets of individuals, and so on. Linguistic entities are themselves set-theoretical entities, and it would be more appropriate to entitle the right-hand column above “Set-theoretical entities which are not linguistic entities”.

(Suppes 232)

Suppes now introduces special terminology for the domain and counterdomain of functions, which are called the domain of definition and the range of values, respectively.

Since every function is a relation, we may speak of the domain and counterdomain of a function. Certain special terminology is used for functions. The domain is often called the domain of definition of the function, and the counterdomain is called the range of values of the function, for which we sometimes use the script letter ‘ℛ.’ Thus if f is a function,

C(f) = ℛ(f),

that is, the counterdomain of f is the same thing as the range of f. The range of the function h defined by (4) is the set of non-negative integers. If f is the function whose domain of definition is the set of all real numbers and which is such that for every real number x

f(x) = x2,

then the range of f is the set of all non-negative real numbers.

(Suppes 233)

Suppes then introduces some more terminology. A function maps its domain onto its range, and thus a function is itself a mapping. Whenever an element x of a function f is a member of f’s domain, then f(x) is the image of x. [This notion of image is a little less clear to me. Suppose we have f(x) = x2. Does that mean we say f(x) is the image of x2? Or does it mean we say 2 is the image of 4 when f(x) = x2? Probably not this possibility, but is it that the variable x is actually in the domain, like x somehow being a member of the real numbers (but of course not, but I am still not sure what would be an example of an image)?] The term ‘function’ can also be called a correspondence. Suppes also notes that certain types of functions are called transformations and operators, but he will not discuss those cases.

A function is sometimes said to map its domain onto its range. Thus the function h maps the set of real numbers onto the set of non-negative integers. Using this sort of terminology, we sometimes say that a function f is a mapping, and when x is an element of the domain of f, then f(x) is the image of x. A function is occasionally called a correspondence (which provides, by the way, a sharp definition of ‘correspondence’). Also certain special functions are called transformations and operators, but we shall not go into the basis of this usage.

(Suppes 233)

[Recall that a function maps to a member of the domain a unique member of the range. I suppose this means that multiple different members of the domain can be mapped onto the same member of the range. I should not try to guess at an example, but what about f(x) = x ×0? I would think that any number in the domain would map onto just zero. At any rate, this might be why a function is called a ‘many-one relation’, as many terms can be related to one. But I am not sure. This is what Suppes says.] “In logic a function is often called a many-one relation. The genesis of this terminology should be clear, from the definition of a function” (233). [I am not sure if I got the idea of the many-one relation yet, and I am less sure I understand the next concept of the one-many relation. There is a wiki page on multi-valued functions. One example of these is that every real number greater than zero has two real square roots (a positive and negative one), while the square root of zero has just one. I am not sure if this is what Suppes is talking about. He says he will mention these concepts in the next section anyway, so we will probably get examples then.]

In logic a function is often called a many-one relation. The genesis of this terminology should be clear, from the definition of a function. Analo­gously, a relation R is one-many if whenever yRx and zRx, then y = z. We shall further refer to these notions in the next section.

(233)

[The next concept is a little difficult but Suppes says is also quite important. We consider the example of addition as a function whose domain is the positive integers. When we apply the function of addition, we take one member from the domain, then we take another member of the domain, and they together will map onto a member of the range. That range would also have to be a positive integer, because that is the only sort of number that can result from the addition of positive integers. Now we ask, are there any numbers in the domain that are not in the range? Well, what is the smallest number in the range? It cannot be 1, because there are no two positive integers that will add to 1. Therefore the range is a subset of the domain. So when you have a function that takes a member from the domain and applies it to another member of the domain and also for whose range is a subset of the domain, then we call that function a binary operation on the set.]

A particularly important class of functions is the class of binary operations. A binary operation on the set A is a function whose domain is A × A and whose range is a subset of A. It is customary to speak of a binary operation from A × A to A, and it is understood when this language is used that the range of the operation need not be the whole of A, but merely a subset of A. For example, if N is the set of positive integers and + is the binary operation of addition of positive integers, then we say + is a binary operation from N × N to N, although the range of + is N ~ {1}, for no two positive integers sum to one.

(Suppes 233)

[Recall from section 10.1 that ordered triples can be defined as ordered couples. The following takes from the summary material in that section ...

If we have an ordering of three terms, we would have an ordered triple. More generally we can speak of ordered n-tuples, which we may define in terms of ordered couples (208).

An ordered triple, for instance, is an ordered couple whose first member is an ordered couple, that is,

(2)     ⟨x, y, z⟩ = ⟨⟨x, y⟩, z⟩.

(Suppes 208)

Then on this basis we can define ordered quadruples:

x, y, z, w⟩ = ⟨⟨x, y, z⟩, w

In general, then, we can define any ordered n-tuple in the following way:

x1, x2, ..., xn⟩ = ⟨⟨x1, x2, ..., xn-1⟩, xn

(Suppes 209)

... There is still something I am not entirely sure about. So consider the ordered triple example from above.

x, y, z⟩ = ⟨⟨x, y⟩, z

One might say that we still have the problem that one of the internal parts is not properly defined, because the first term is a couple, but the whole thing is supposed to be a couple. I think this sort of formulation depends on the assumption that this internal couple (the first term) is defined the same way as the whole couple, namely as decomposible into two parts. So the quadruple is defined as a couple composed of a single and a triple. But that triple is defined as a couple of a single term and a couple. And that couple is defined as a single term with a single term. I am not sure. But at any rate, Suppes’ point now is that we can characterize binary operations as ternary relations. I am not entirely certain, but I think the idea is the following. We have three terms at work normally, one from the domain, another from that domain, and a third from the counterdomain. For convenience, let us call them, respectively, x, y, and z. So in a sense we have an ordered couple: <<x, y>,  z>. Now recall the definition of a function:

A function R is a binary relation such that if xRy and xRz then y = z.

And recall from above that relation can be also written as xRy <x, y> ∈ R. If we were to structure this relation as couples, it would be:

A function R is a binary relation such that if <x, y> ∈ R and <x, z> ∈ R then y = z.

So recall our ordered triple as an ordered couple from our example:

<<x, y>,  z>

I think Suppes is saying that we can just as well write that as:

<x, y, z>

Now, the point about uniqueness of the counterdomain member was that for any member of the domain there can only be one member of the counterdomain. In our case of binary operations, that would mean any ordered couple from the domain × domain can only map upon one from the counterdomain; or, using our example, we would say that for any <x, y> there can only be one z. But suppose we wanted to use the triple formulation for the binary relation but also define it in the same way functions were defined (also using the set membership schema)? In the function formulation, a third term, z, was supposed for the counterdomain. So if one member of the domain maps to a certain member of the counterdomain in one case and that same member of the domain maps to another member of the counterdomain in another case, both those counterdomain members would have to be identical if this is really a function. So in the case of our ordered triple, we should posit a fourth term, so that there are two in the counterdomain to which the couple in the domain may be said to map onto. Then we say that this third and this fourth term in the counterdomain would have to be equal. In this way we can define binary operations as functions, in terms of ternary relations.]

Since ordered triples are simply certain special ordered couples, namely those ordered couples | whose first members are ordered couples, we may also characterize binary operations as certain ternary relations.

A ternary relation T is a binary operation if and only if for every x, y, z, and w if <x, y, z> T & <x, y, w> T then z = w.

(233-234)

From:

Suppes, Patrick. Introduction to Logic. New York: Van Nostrand Reinhold / Litton Educational, 1957.

.