Functions vs Relations [closed]

Question

Okay, so I was not introduced to functions in my elementary logic textbook. But they appeared in my mathematical logic textbook.

I noticed that in statements like 1 + 2, + is called a function symbol, whereas the P in Pa might be a relation symbol denoting 'a is a prime number'. The idea seemed to be that 1 + 2 refers to a particular individual in the domain, where as 'a is a prime number' is a declarative statement about the individual a.

I wondered how this could be extended to natural languages.

Like we might say 'Joe is the son of Mary' and denote it with the relation S(Joe,Mary). But it seems that we can also refer to Joe in an indirect way, by saying 'the son of Mary' (so long as there is no other son of Mary). Could we denote this Z(Mary), where Z = 'the son of...', or something like that? Or perhaps even make a declarative statement like Z(Mary)=Joe?

Answer 1

Functions and relations have a long mathematical history, and can be approached from many sides (e.g. category theory, set theories). From a standard set-theoretic perspective, we begin with the notion of an ordered pair (a, b), which can either be taken as a primitive or defined in terms purely of sets. Either way, the explication is only to satisfy the following condition: (a, b) = (c, d) iff a = c and b = d. Once we have ordered pairs, we can define relations of arbitrary arity as follows:

Def 2. (Relations over multiple sets) An n-ary relation over sets A₁,...,A_n is any subset of A₁ × ... × A_n.

Informally, this means that n-ary relation is a set of n-tuples of elements selected from a bunch of sets. A special type of relation used often in introductory logic courses is that of the predicate, which is simply a 1-ary or unary relation over the domain of individuals. In single-sorted logics such as classical first-order logic, the domain of individuals is some set D, so we have a simpler definition of relations:

Def 3. (Relations over a single set) An n-ary relation on set A is any subset of Aⁿ.

As examples of such relations take the relations LeftOf, SmallerThan, LessThan, and so on. For 3-ary relations Between, CloserThan come to mind. For 1-ary relations or predicates we have Small, Even, Prime, and so on. Now that we have defined relations, we can define functions in terms of them:

Def 4. (Functions) An n-ary function from A to B is a total deterministic n-ary relation on A × B.

Relation R ⊆ A × B is total iff for all x ∈ A, there exists a y ∈ B s.t. (x, y) ∈ R. In other words, every element of A is mapped to some element of B. Relation R ⊆ A × B is deterministic iff there is no x ∈ A for which there are y, z ∈ B s.t. (x, y) ∈ R and (x, z) ∈ R. In other words, every element of A is mapped to no more than one element of B.

                                                                     Application

These notions are applied to natural language semantics exactly in the way you described. Consider:

(5) Joe is the son of Mary.

If we let 'j' denote Joe, 'm' Mary, we'll have two possible explications of (5): one using a binary relation symbol 'S' (which holds of (x,y) just in case x is the sone of y) and one using the identity relation on the domain of individuals and the unary function symbol 's' (which refers to the unique individual that is the son of x). Following the first way we get:

(6) S(j, m) ∧ ∀_x : S(x,m) → x = j.

This says that John is a son of Mary and every person x who is a son of Mary is John, which is the intended meaning of (5) I assume. Following the second approach we get:

(7) j = s(m).

It's easy to check that (6) is true exactly when (7) is true. After all, S is a set of pairs (x, y) s.t. x is a son of y, and the second conjunct of (6) implies that x is j which according to (7) is s(m).

Remark. The distinction between (6) and (7) roughly corresponds to the famous distinction between Russelian and Fregean views of definite descriptions. According to the Fregean view, 'the φ' denotes the unique individual satisfying condition φ, if such an individual exists. The Russellian view, on the other hand, regards 'the φ' as meaningful only in a context of a complete sentence (e.g. (6)). That, however, is another discussion.

                                                                     References

Halmos, P. (1960) Naive Set Theory; Chapters 6–8.
Heim, I., Kratzer, A. (1998) Semantics in Generative Grammar; §4.4.

Answer 2

To precisely define the notion of a function, you really have to use the language of set theory.

Let A and B be sets. Let AxB be the Cartesian product of A and B. A subset f of AxB is said to be a function if and only if for all x, if x is an element of A, then there exists a unique element y in B such that (x,y) is in f.

An example in natural language: Let A be the set of men and B be the set of women. Then the relation "is the son of" would be a function mapping every man to a unique woman.