Relations - Mathematical Sentences

Mathematical Writing - Vivaldi Franco 2014

Relations
Mathematical Sentences

(This section is not essential for the rest of the book: it may be skipped on first reading.)

Relations are special types of logical functions which are ubiquitous in higher mathematics. We introduce some relevant words and symbols.

Let $$X$$ and $$Y$$ be sets. A relation $${\fancyscript{R}}$$ on $$X\times Y$$ is a predicate over $$X \times Y$$. If $$X=Y$$, we speak of a relation on $$X$$. It is customary to write $$x{\fancyscript{R}}y$$ to mean $${\fancyscript{R}}(x,y)$$; the expression $$x{\fancyscript{R}}y$$ is called a relational expression, and $${\fancyscript{R}}$$ is a relational operator . All relational expressions introduced at the beginning of this chapter are of this form. Thus the membership operator $$\in $$ defines a relation on $$X\times \mathbf {P}(X)$$, where $$X$$ is some ambient set.

A relation on a set $$X$$ is sometimes defined as a subset of $$X^2$$, rather than a predicate over $$X^2$$. In this sense, the set $$\{(1,1),(2,1)\}$$ is a relation on $$\{1,2\}$$. The correspondence between sets and predicates described in Sect. 4.3 clarifies the connection between the two constructs.

Among relations on a set $$X$$, the equivalence relations hold a special place. They are defined by the following properties:

The notation $$x\sim y$$ is usually employed to denote equivalence.

Equivalence relations allow us to regroup the elements of a set according to certain criteria. Specifically, given an equivalence relation on $$X$$ and $$x\in X$$, one collects together in the set $$[x]$$ all elements of $$X$$ equivalent to $$x$$:

$$ [x]:=\{y\in X\,:\, x\sim y\}. $$

The collection of such equivalence classes forms a partition of $$X$$ (see Sect. 2.3.1), given by:

$$\begin{aligned} X/\sim :=\{[x]\,:\,x\in X\}. \end{aligned}$$

(4.29)

The set $$X/\sim $$ is called the quotient set of $$X$$ by $$\sim $$; it’s a set of sets. The idiomatic notation $$X/\sim $$ reminds us of the way this set is constructed: we subdivide $$X$$ according to the criterion ’$$\sim $$’. The minimalist definition (4.29) is sleek but inefficient, since all the elements of $$X$$ that belong to the same equivalence class result in just one partition element. So there is a wholesale repetition of partition elements, and the formula works because we agreed to identify repeated elements in set definitions.

The following examples illustrate some applications of this construct.

EXAMPLE. The relational operator ’$$=$$’ defines an equivalence relation on any set. This is the trivial equivalence; it corresponds to the trivial partition consisting of one-element subsets.

EXAMPLE. Given a function $$f:X\rightarrow Y$$, we let $$x_1\sim x_2$$ if $$f(x_1)=f(x_2)$$. This is an equivalence relation on $$X$$. The equivalence classes are the inverse images of the elements of the co-domain of $$f$$:

$$\begin{aligned} \{f^{-1}(\{y\})\,:\, y\in Y\}. \end{aligned}$$

(4.30)

Any equivalence relation on a set $$X$$ can be represented in this way, for some function $$f$$.

EXAMPLE. For any natural number $$m$$, the congruence relation $$x\, {\equiv } \,y (\text {mod}\, m)$$ defined in Sect. 2.1.3 is an equivalence relation on $$\mathbb {Z}$$. The equivalence classes are the congruence classes introduced in Sect. 2.3.2.

EXAMPLE. The relation on $$\mathbb {N}\times \mathbb {N}$$, defined by $$(m,n)\sim (j,k)$$ if $$m+k=n+j$$, is an equivalence relation. By interpreting the pair $$(m,n)$$ as the quantity $$z=m-n$$, we see that equivalent pairs correspond to the same value of $$z$$. With this device, one can construct integers from pairs of natural numbers, whereby every integer is an equivalence class of infinitely many pairs of natural numbers. The value of this abstract construction lies with its reductionist character: it requires only natural numbers and addition in $$\mathbb {N}$$; there is no mention of negative integers or subtraction.

EXAMPLE. The relation ’$$\sim $$’ on $$\mathbb {Z}\times (\mathbb {Z}{\backslash }\{0\})$$, defined by $$(m,n)\sim (j,k)$$ if $$mk=nj$$, is an equivalence relation. By interpreting the pair $$(m,n)$$ as $$r=m/n$$, we see that equivalent pairs correspond to the same value of $$r$$. With this device, one can define a rational number as an infinite collection of equivalent pairs of integers, without introducing fractions or division.

A relation $${\fancyscript{R}}$$ on a set $$X$$ is called a partial ordering if it is reflexive, transitive and anti-symmetric. The latter property is defined as follows:

A set is partially ordered if a partial ordering is defined on it. A partial ordering is usually denoted by the symbol ’$$\leqslant $$’. So we write $$x\leqslant y$$ instead of $$x{\fancyscript{R}}y$$.

The relational operator $$\leqslant $$ defines a partial ordering in $$\mathbb {N}$$, $$\mathbb {Z}$$, $$\mathbb {Q}$$, and $$\mathbb {R}$$ (but not in $$\mathbb {C}$$). The set $$\mathbf {P}(X)$$ of all subsets of a set $$X$$ is partially ordered by set inclusion, whereby $$\leqslant $$ means $$\subset $$.

A partially ordered set $$X$$ is said to be ordered if all pairs of elements of $$X$$ are comparable, meaning that we either have $$x \leqslant y$$ or $$y\leqslant x$$. The real line is an ordered set; the power set $$\mathbf {P}(X)$$ of a set $$X$$, which is partially ordered by set inclusion, is not ordered.

An ordered set $$X$$ is said to be well-ordered if any non-empty subset $$A\subset X$$ has a smallest element. The symbolic definition requires three quantifiers:

$$ \forall A\in \mathbf {P}(X){\backslash }\emptyset ,\,\,\exists a\in A, \,\,\forall x\in A,\,\,a\leqslant x. $$

Any finite ordered set is well-ordered. The closed unit interval $$[0,1]$$ is ordered but not well-ordered, because the subset $$(0,1]$$ has no smallest element. The natural numbers are well-ordered. This property forms the basis of the principle of induction, which we consider in Chap. 8.

Exercise 4.1

Rewrite each symbolic sentence using the quantifier $$\exists $$.

1.

2.

3.

4.

5.

6.

7.

Exercise 4.2

Write each sentence with symbols, using at least one quantifier.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

Exercise 4.3

Consider the following statements.

1.

2.

3.

4.

5.

6.

7.

8.

9.

In each case:

(i)

(ii)

(iii)

(iv)

Exercise 4.4

(W. Hodges). We wish to to build up a set of predicates to describe family relations. You are given the two predicates

$$\begin{aligned} {\textit{x is a son of y}} \quad \qquad {\textit{x is a daughter of y}}. \end{aligned}$$

Your task is to write definitions of the following predicates, in some appropriate order such that the later definitions use only the given predicates and earlier definitions. (The order below is just alphabetical.)

·  $$x$$ is an aunt of $$y$$

·  $$x$$ is a brother of $$y$$

·  $$x$$ is a child of $$y$$

·  $$x$$ is the father of $$y$$

·  $$x$$ is female

·  $$x$$ is a grandchild of $$y$$

·  $$x$$ is a half-brother of $$y$$

·  $$x$$ is male

·  $$x$$ is the mother of $$y$$

·  $$x$$ is a nephew of $$y$$

·  $$x$$ is a parent of $$y$$

·  $$x$$ is a sister of $$y$$.

Use the symbols $$x,y,z$$, etc., to denote people, words for everything else, and parentheses to specify the order of evaluation of logical operators. Why are the given data not quite sufficient to define the ’aunt’ predicate?

Exercise 4.5

Let $$x$$ and $$y$$ be natural numbers, and let $${\fancyscript{P}}(x,y)$$ mean: ’$$x$$ is a proper divisor of $$y$$’ (that is, $$x|y$$ and $$x\not = 1,y$$). Thus $${\fancyscript{P}}$$ is a predicate over $$\mathbb {N}\times \mathbb {N}$$.

(a)

(b)

(c)

Exercise 4.6

The following expressions define sets; turn symbols into words. [ $$\not \varepsilon \,$$ ]

1.

2.

3.

Exercise 4.7

Decide if each sentence is true or false, hence write its negation with symbols. Then rewrite both with words. [ $$\not \varepsilon \,$$ ]

1.

2.

3.

4.

5.

6.

7.

8.

9.

Exercise 4.8

The following cryptic symbolic sentence states an interesting mathematical fact:

$$\begin{aligned} \forall n\in \mathbb {N},\,\,\exists k\in \mathbb {N},\,\,\forall j\in \mathbb {N},\,\,(k+j)!\geqslant n^{k+j}. \end{aligned}$$

(4.31)

Rewrite it in words.

Exercise 4.9

Consider the sentences

1.

2.

3.

We wish to determine the computational effort required to find out if a sentence is true or false. With the notation of Sect. 4.4, let the set $$G$$ have $$n$$ elements. First suppose that the sentence is true. How many evaluations of the predicate ’$$x$$ loves $$y$$’ are needed to verify this? Give the minimum and maximum number of evaluations, with an explanation. Do the same assuming that the sentence is false.

Exercise 4.10

In this exercise we collect some straightforward proofs.

1.

2.

3.

Exercise 4.11

Define some interesting predicates on the power set of $$\mathbb {Z}$$. Do the same for the power set of $$\mathbb {Z}[x]$$.

Exercise 4.12

Let $$X$$ be any set. Show that there is a one-to-one correspondence between the partitions of $$X$$ and the equivalence relations on $$X$$. Show that any equivalence relation on $$X$$ may be represented by a suitable function $$f:X\rightarrow Y$$ such that the equivalence classes are the pre-images of the elements of $$Y$$—see Eq. (4.30).

Exercise 4.13

You are given an equivalence relation over a finite set $$X$$. Develop an algorithm—more efficient than formula (4.29)—to construct the associated partition of $$X$$.

Footnotes

1

This expression refers to the largest known prime (as of January 2014) with 17425170 digits: see [6].

2

There is also an exclusive version of OR, called XOR ($$\veebar $$), for which $${\text {T}}\veebar {\text {T}}= {\text {F}}$$.

3

Augustus De Morgan (British: 1806—1871).

4

Joseph-Louis Lagrange, born Giuseppe Lodovico Lagrangia (Italian: 1736—1813).

5

The trivial divisor $$1^2$$ is excluded.

6

See (4.4).