Relations and Functions

Relations

The order in which elements in a set are listed does not matter. That is, \(\{a, b\}\) is the same set as \(\{b, a\}\) (they both denote the set consisting of two elements '\(a\)' and '\(b\)'). Similarly, listing the same element multiple times does not change a set. So, for instance, \(\{a,a,b\}\) is the same set as \(\{a,b\}\).

There are many situations in which the order in which the elements appear is important. In such situations, we use '\((\)' and '\()\)'. The ordered pair, or tuple of length 2, is denoted \((a,b)\). The first component is \(a\) and the second component is \(b\). Since the order in which the elements appear matters, we have that \((a, b)\ne (b,a)\). While there is only one set with two elements \(\{a, b\}\), there are 4 different ordered pairs that can be constructed using the elements \(a\) and \(b\):

• \((a, a)\)
• \((a, b)\)
• \((b, a)\)
• \((b, b)\)

Note that in the 2nd and 4th tuple we allow the same element to be repeated.

Product

Suppose that \(A\) and \(B\) are non-empty sets. The product of \(A\) and \(B\), denoted \(A\times B\), is the set of ordered pairs where the first component comes from \(A\) and the second component comes from \(B\). That is,

\[ A\times B=\{(a,b)\ |\ a\in A\text{ and } b\in B\}. \]

Note that the set \(X\times X\) is the product of \(X\) with itself, i.e., it is the set of all pairs of elements from \(X\).

Example

Suppose that \(X=\{a, b, c\}\) and \(Y=\{1, 2\}\). Then,

1. \(X\times Y=\{(a,1), (a,2), (b,1), (b,2), (c,1), (c,2)\}.\)
2. \(Y\times X=\{(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)\}.\)
3. \(X\times X=\{(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c)\}.\)
4. \(\begin{align} (X\times X)\times Y = &\ \{((a,a),1), ((a,b),1), ((a,c),1), ((b,a),1), ((b,b),1), ((b,c),1),\\ & \ \ \ \,((c,a),1), ((c,b),1), ((c,c),1), ((a,a),2), ((a,b),2), ((a,c),2),\\ & \ \ \ \, ((b,a),2), ((b,b),2), ((b,c),2),((c,a),2), ((c,b),2), ((c,c),2)\}.\end{align}\)

Tuples of length \(n>2\)

Note that in item 4 of the above Example, \((X\times X) \times Y\) consists of tuples where the first component is a tuple of length 2 (where each component is from \(X\)) and the second component is an element of \(Y\). Often we will drop the parentheses, writing \(X\times X\times Y\), and think of the elements of this set as tuples of length 3:

\(\begin{align} (X\times X)\times Y= & \ \{(a,a,1), (a,b,1), (a,c,1), (b,a,1), (b,b,1), (b,c,1),(c,a,1), \\ &\ \ \ \,(c,b,1), (c,c,1), (a,a,2), (a,b,2), (a,c,2), (b,a,2), (b,b,2), \\ & \ \ \ \,(b,c,2), (c,a,2), (c,b,2), (c,c,2)\}.\end{align}\)

The parentheses can be recovered by associating them to the left.

A relation \(R\) on a set \(X\) is a subset of \(X\times X\) (the set of pairs of elements from \(X\)). Formally, \(R\) is a relation on \(X\) means that \(R\subseteq X\times X\). It is often convenient to write \(a\mathrel{R}b\) for \((a,b)\in R\). To illustrate the idea of a relation, suppose that \(X\) is the set of people in a room. The following are two examples of relations on \(X\):

1. Suppose that \(R\) describes who is pointing at whome. So, \(R\subseteq X\times X\) is the relations where for \(a,b\in X\), \(a\mathrel{R} b\) means that person \(a\) is pointing at person \(b\).
2. Suppose that \(T\) is the "taller-than" relation. So \(T\subseteq X\times X\) is the relation where for \(a,b\in X\), \(a\mathrel{T} b\) means that person \(a\) is taller than person \(b\).

Typically, we are interested in relations satisfying special properties.

Properties of relations

Suppose that \(R\subseteq X\times X\) is a relation.

• \(R\) is reflexive provided that for all \(a\in X\), \(a\mathrel{R} a\).
• \(R\) is irreflexive provided that for all \(a\in X\), it is not the case that \(a\mathrel{R} a\).
• \(R\) is complete provided that for all \(a,b\in X\), \(a\mathrel{R} b\) or \(b\mathrel{R} a\) (or both).
• \(R\) is symmetric provided that for all \(a,b\in X\), if \(a\mathrel{R} b\) then \(b\mathrel{R} a\).
• \(R\) is asymmetric provided that for all \(a,b\in X\), if \(aRb\) then not-\(b\mathrel{R} a\).
• \(R\) is anti-symmetric provided that for all \(a,b \in X\) if \(a\mathrel{R} b\) and \(b\mathrel{R} a\), then \(a=b\).
• \(R\) is transitive provided that for all \(a,b,c\in X\), if \(a\mathrel{R} b\) and \(b\mathrel{R} c\) then \(a\mathrel{R} c\).

Note

As stated, completeness implies reflexivity (let \(a=b\) in the above definition of completeness). Often, completeness is defined as follows: for all distinct \(a,b\in X\), \(a\mathrel{R} b\) or \(b\mathrel{R} a\). In what follows, we will use the above stronger definition of completeness where completeness implies reflexivity.

Recall the example of a relation \(R\) that describes people pointing at other people in the room. If \(R\) is reflexive, then this means everyone is pointing at themselves. If \(R\) is irreflexive, then this means that no-one is pointing at themselves. This example illustrates the fact that irrelexivity is not the negation of reflexivity. That is, there are examples of relations that are neither reflexive nor irreflexive. If \(R\) is complete, then this means that every person in the room is either pointing at somebody or being pointed at (allowing people to point at themselves). Symmetry of \(R\) means that every person that is being pointed at is pointing back at the person pointing at them. Asymmetry of \(R\) means that nobody is pointing back at the person pointing at them. Similar to the relationship between reflexivity and irreflexivity, asymmetry is not the negation of symmetry. Picturing transitivity of the relation \(R\) is a bit more complicated. If the relation \(R\) is transitive, then everyone is pointing at the person that is being pointed to by the person that they are pointing at.

Functions

A function from a set \(A\) to a set \(B\) is a way of associating elements of \(A\) with elements of \(B\). Formally, a function is a special type of relation:

Function

A function \(F\) is a binary relation on \(A\) and \(B\) (i.e., \(f\subseteq A\times B\)) such that for all \(a\in A\), there exists a unique \(b\in B\) such that \((a,b)\in f\).

We write \(F:A\rightarrow B\) when \(F\) is a function, and if \((a,b)\in f\), then write \(F(a)=b\).

Example of a function

Suppose that \(A=\{1, 2, 3\}\) and \(B=\{a,b\}\). Examples of relations that are functions include:

• \(R_1=\{(1,a), (2,a), (3,b)\}\)
• \(R_2=\{(1,a), (2,a), (3,a)\}\)
• \(R_3=\{(1,a), (3,b)\}\)

An example of a relation that is not a function is \(R_4=\{(1,a), (1,b), (3,b)\}\).

Suppose \(F:A\rightarrow B\) is a function. The set \(A\) is called the domain and \(B\) is called the codomain. The following standard notions are usefule for reasoning about and with functions.

Image

Suppose that \(F:A\rightarrow B\). The image of a set \(A'\subseteq A\) is the set:

\[ F(A')=\{b\ |\ b=F(a) \text{ for some }a\in A'\} \]

Range

The range of a function is the image of its domain.

Surjection

A function \(F\) is a surjection (or onto) if its range is equal to its codomain. I.e., \(F:A\rightarrow B\) is surjective when for each \(b\in B\), there exists an \(a\in A\) such that \(F(a)=b\)

Injection

A function \(F\) is an injection (or 1-1) if distinct elements of the domain produce distinct elements of the codomain. I.e., \(F:A\rightarrow B\) is 1-1 when for all \(a,a'\in A\), \(a\ne a'\) implies \(F(a)\ne F(a')\), or equivalently \(F(a)=F(a')\) implies \(a=a'\).

Bijection

A function \(F\) is a bijection if it is injective and surjective. In this case, \(F\) is often called a one-to-one correspondence.

Inverse Image

Suppose that \(F:A\rightarrow B\) and that \(Y\subseteq B\). The inverse image of \(Y\) is the set

\[ F^{-1}(Y)=\{x\ |\ x\in A\text{ and } F(x)\in Y\}. \]

Function on the powerset

Suppose that \(X=\{a, b, c\}\). A function from non-empty subsets of \(X\) to non-empty subsets of \(X\) is denoted \(F:(\wp(X)-\emptyset) \rightarrow (\wp(X)-\emptyset)\). An example of such a function is:

\[ \begin{align} F(\{a\}) & = & \{a\}\\[2pt] F(\{b\}) & = & \{b\}\\[2pt] F(\{c\}) & = & \{c\}\\[2pt] F(\{a,b\}) & = & \{a\}\\[2pt] F(\{a,c\}) & = & \{c\}\\[2pt] F(\{b,c\}) & = & \{b\}\\[2pt] F(\{a,b,c\}) & = & \{b,c\}\\[2pt] \end{align} \]

Sequences

A sequence is an enumerated list of elements. For instance, \((b, a, c, b)\) is a sequence of length 4. Above, this mathematical object was called a tuple of length 4. It will be convenient to view a sequence as a function from an index set to some set of objects. For example, the sequence \((b, a, c, b)\) can be viewed as a function \(s:\{0,1,2,3\} \rightarrow\{a,b,c\}\) where \(s(0)=b\), \(s(1)=a\), \(s(2)=c\) and \(s(3)=b\). Conversely, a function \(s:\mathbb{N}\rightarrow A\) can be viewed as a (possibly infinite) sequence of elements from \(A\). When the function \(s\) is viewed as a sequence, we write \(s_i\) for \(s(i)\).

Additional Reading

• Chapter 2 of Mathematical Methods in Linguistics by Partee, Ter Meulen and Wall.

• Chapters 2 and 3 of Open Logic Initiative Notes on Sets, Functions and Relations

Exercises

1. Suppose that \(A=\{b,c\}\), \(B=\{2,3\}\) and \(C=\{b,d\}\). Find all the following sets.

   1. \(A\times B\)
   2. \((A\cap C)\times B\)
   3. \((C-B)\times B\)
   4. \(A\times A\)
   5. \((A\times B)\cup (B\times A)\)
   Show Answer

   1. \(A\times B = \{(b, 2), (b, 3), (c, 2), (c, 3)\}\)
   2. \((A\cap C)\times B = \{b\}\times \{2,3\} = \{(b, 2), (b, 3)\}\)
   3. \((C-B)\times B = \{b, d\}\times \{2, 3\}=\{(b, 2), (b, 3), (d, 2), (d, 3)\}\)
   4. \(A\times A = \{(b,b), (b,c), (c,b), (c,c)\}\)
   5. \((A\times B)\cup (B\times A) = \{(b, 2), (b, 3), (c, 2), (c, 3)\}\cup \{(2, a), (2, c), (3, b), (3, c)\}\) \(= \{(b, 2), (b, 3), (c, 2), (c, 3), (2, a), (2, c), (3, b), (3, c)\}\)

2. What is the set \(\varnothing \times A\)?

   Show Answer

   \(\varnothing \times A = \varnothing\)

3. Consider the relation \(R = \{(a,a), (b,b), (c,c), (d,d), (a,b), (b,a)\}\) on the set \(A=\{a,b,c,d\}\). Determined which of the following properties are satisfied by \(R\):

   1. Reflexive
   2. Symmetric
   3. Transitive
   Show Answer

   1. \(R\) is reflexive.
   2. \(R\) is symmetric.
   3. \(R\) is transitive.

4. Consider the relation \(R = \{(a,b), (a,c), (c,c), (b,b), (c,b), (b,c)\}\) on the set \(A=\{a,b,c\}\). Determined which of the following properties are satisfied by \(R\):

   1. Reflexive
   2. Symmetric
   3. Transitive
   Show Answer

   1. \(R\) is not reflexive. This follows since \((a,a)\not\in R\)
   2. \(R\) is not symmetric. This follows since \((a,b)\in R\) but \((b,a)\not\in R\).
   3. \(R\) is transitive.

5. Let \(R\) and \(S\) be transitive relations on a set \(A\). Does it follow that \(R\cup S\) is transitive? (Explain your answer.)

   Show Answer

   No. Suppose that \(R=\{(a,b)\}\) and \(S=\{(b,c)\}\). Both \(R\) and \(S\) are transitive; however, \(R\cup S=\{(a,b),(b,c)\}\) is not transitive.

6. Suppose \(R\) and \(S\) are transitive relations on the set \(A\). Is \(R \cap S\) transitive? (Explain your answer.)

   Show Answer

   Yes. Suppose that \(R\) and \(S\) are transitive relations. Let \(x\mathrel{R\cap S} y\) and \(y\mathrel{R\cap S} z\) (i.e., \((x,y),(y,z)\in R\cap S\)). Then, we have 1) \(x\mathrel{R} y\) and \(y\mathrel{R}z\); and 2) \(x\mathrel{S} y\) and \(y\mathrel{S}z\). Since \(R\) is transitive, 1) implies that \(x\mathrel{R}z\); and since \(S\) is transitive, 2) implies that \(x\mathrel{S}z\). Thus, \(x\mathrel{R\cap S} z\), as desired.

7. Suppose that \(A\ne\varnothing\). Since \(\varnothing \subseteq A\times A\), then \(R=\varnothing\) is a relation on \(A\). Is \(R\) reflexive? Symmetric? Transitive? If a property does not hold, say why.

   Show Answer

   \(R\) is not reflexive. Since \(A\ne \varnothing\), there is some \(a\in A\). However, \((a,a)\not\in \varnothing\). \(R\) is symmetric.
   \(R\) is transitive.

8. Suppose that \(X=\{a,b,c\}\) and \(Y=\{e, f, g\}\). Give an example of a function from \(X\) to \(Y\) that is not surjective and not injective.

   Show Answer

   Let \(F:X\rightarrow Y\) be the funciton where where \(F(a)=e\), \(F(b)=f\) and \(F(c)=e\).

9. Suppose that \(X=\{a,b,c\}\) and \(Y=\{e, f, g\}\). Give an example of an injective and surjective function from \(X\) to \(Y\)

   Show Answer

   Let \(F:X\rightarrow Y\) be the function where where \(F(a)=e\), \(F(b)=f\) and \(F(c)=g\)

10. Suppose that \(Y=\{e, f, g\}\) and \(Z=\{a,b,c,d\}\). Can you find a surjective function from \(Y\) to \(Z\)? If yes, give an example and if no, explain why not.

    Show Answer

    No, there is no surjective function from \(Y\) to \(Z\). The reason is that \(Z\) has more elements that \(Y\). If \(F:Y\rightarrow Z\) is a surjective function, then for each \(z\in Z\), there is some \(y\in Y\) such that \(F(y)=z\). In order to satisfy this property, some element of \(Y\) must be mapped to two different elements of \(Z\).

11. Suppose that \(Y=\{e, f, g\}\) and \(Z=\{a,b,c,d\}\). Can you find a surjective function from \(Z\) to \(Y\)? If yes, give an example and if no, explain why not.

    Show Answer

    Yes, for instance \(F:Z\rightarrow Y\) where \(F(a) = e\), \(F(b)=e\), \(F(c)=f\), \(F(d)=g\).

12. Suppose that \(Y=\{e, f, g\}\) and \(Z=\{a,b,c,d\}\). Can you find an injective function from \(Z\) to \(Y\)? If yes, give an example and if no, explain why not.

    Show Answer

    No, there is no injective function from \(Z\) to \(Y\). The reason is that \(Z\) has more elements that \(Y\). If \(F:Z\rightarrow Y\) is an injective function, then for all \(z,z'\in Z\), if \(F(z)=F(z')\) then \(z=z'\). In order to satisfy this property, some element of \(Z\) must not be in the domain of the function (i.e., the function would be a partial function).

13. Suppose that \(Y=\{e, f, g\}\) and \(Z=\{a,b,c,d\}\). Can you find an injective function from \(Y\) to \(Z\)? If yes, give an example and if no, explain why not.

    Show Answer

    Yes, for instance \(F:Y\rightarrow Z\) where \(F(e) = a\), \(F(f)=b\), and \(F(g)=c\).

https://umd.instructure.com/courses/1301043/assignments/5494699