GUIDE TO LOGIC

Relations I

Contents

1. Relations Defined by Incomplete Statements
2. Sets of Related Elements
3. One-one Relations
4. One-many Relations
5. Many-one Relations
6. Many-many Relations
7. Negation
8. Double Negation
9. Logical AND
10. Laws for the Logical AND
11. Logical OR
12. Laws for the Logical OR
13. Laws for Mixed Composite Relations
14. Inverse Relations
15. Inverse of an Inverse
16. Composition of Relations
17. Non-commutative Law for the Composition of Relations
18. Inverse of a Composition of Relations
19. Associative Law for the Composition of Relations

1. Relations Defined by Incomplete Statements

An incomplete statement P(x,y) with two variables, where x stands for an element in a set A, and y stands for an element in a set B, defines a relation between the elements of A and B.

For example, let A be a set of books, and let B be a set of people. Suppose x = The red book, and y = Peter. Let P(x,y) mean x belongs to y. Then P(x,y) means The red book belongs to Peter.

We may write this incomplete statement in symbols in another way as follows: x R y, where R stands for the relation belongs to, and the whole statement x R y again means The red book belongs to Peter.

EXERCISE

Let x stand for a person, let y stand for a town, and let R stand for the relation lives in. Give the meaning of x R y when x = Mr Lim, and y = Singapore.

2. Sets of Related Elements

The variables x and y in the incomplete statement represented by x R y may stand for elements in different sets or elements in the same set.

For example, when x R y means The red book belongs to Peter, x and y stand for elements in different sets, namely the set of books and the set of people. However, if x R y means Peter is older than John, where R stands for the relation is older than, x and y stand for elements in the same set of people.

EXERCISE

In each of the following statements having the form x R y say whether x and y stand for elements in the same set or different sets. What are the sets in each statement?
  1. The Indian Ocean is smaller than the Pacific Ocean.
  2. Bangkok is the capital of Thailand.
  3. Nigeria is in Africa.
  4. The Yellow River is longer than the Irrawaddy.

3. One-one Relations

In a one-one relation between the elements of a set A and the elements of a set B each element of A is related to exactly one element of B, and each element of B is related to exactly one element of A.

For example, let x stand for one of the twenty-six numbers in the set {1, 2, ..., 25, 26} and let y stand for one of the letters of the alphabet: {A, B, ..., Y, Z}. Let x R y mean x is the position of the letter y in alphabetical order. Then we have a one-one relation with the elements related as follows: 1 R A, 2 R B, ..., 25 R Y, 26 R Z.

EXERCISE

The colours of traffic lights are red, yellow and green. The positions of the lights are top, middle and bottom. Give the one-one relation between the colours and their positions in traffic lights.

4. One-many Relations

In a one-many relation between the elements of a set A and the elements of a set B each element of A may be related to more than one element of B, but each element of B is related to only one element of A.

For example, let x and y stand for people, and let x R y mean x is the father of y. This is a one-many relation because each father can have any number of children, but each child has only one father. Note that in this example the people in the set A are all men with children.

EXERCISE

Let x stand for a day of the year, and let y stand for a person. Say which of the following relations in the sentences x R y is a one-many relation.
  1. x is a holiday for y.
  2. x is the birthday of y.

5. Many-one Relations

In a many-one relation between the elements of a set A and the elements of a set B each element of A is related to only one element of B, but each element of B may be related to more than one element of A.

For example, let x stand for a person, let y stand for a number of years, and let x R y mean x is y years old. This is a many-one relation because there are many people with the same age in years, but each person has only one age.

EXERCISE

Let x stand for an employee in a large company, and let y stand for an amount of money paid as a monthly salary. Give a many-one relation between x and y.

6. Many-many Relations

In a many-many relation between the elements of a set A and the elements of a set B each element of A may be related to more than one element of B, and each element of B may be related to more than one element of A.

For example, let x and y stand for airports, and let x R y mean There is a direct flight from x to y every day. This is a many-many relation because large airports have flights to and from many other airports every day.

EXERCISE

Let x and y stand for people. Say which of the following relations are many-many.
  1. x is a friend of y.
  2. x is a mother of y.
  3. x is a cousin of y.

7. Negation

The negation of a relation R may be written not-R. The definiton of this negation is as follows:
x not-R y = not-(x R y).
For example, if x R y means x is the father of y, then x not-R y means x is not the father of y.

EXERCISE

Let x and y be islands in the sea. Let x R y mean It is possible to fly from x to y. Give the meaning of x not-R y.

8. Double Negation

Since the negation of a relation is defined by means of the negation of a statement, and since the negation of a negative statement is the original positive statement, it follows that the negation of a negative relation is the original positive relation. We summarize this fact in symbols as follows:
not-(not-R) = R
For example, let x R y mean x is the father of y. Then x not-R y means x is not the father of y, and x not-(not-R) y means the same as the original statement: x is the father of y.

9. Logical AND

Two relations R and S may be joined by the word and to make a composite relation (R and S). The definition of this composite relation is as follows:
x (R and S) y = (x R y) and (x S y).
For example, let x and y stand for people, let x R y mean x is the father of y, and let x S y mean x is the teacher of y. Then x (R and S) y means x is the father and teacher of y. This has the same meaning as x is the father of y, and x is the teacher of y.

As another example, let x and y stand for people, let R mean x is the brother of y, and let S mean x is the sister of y. Then x (R and S) y means x is the brother and sister of y. Because it is impossible for anyone to be a brother and a sister at the same time, there are no people connected by the composite relation (R and S).

EXERCISE

Let x and y stand for people, let R mean is the mother of, let S mean is younger than, and let T mean is the doctor of. Give the meanings of the following composite relations. Say whether each composite relation is possible or impossible.
  1. R and S
  2. R and T
  3. S and T.

10. Laws for the Logical AND

Since the composite relation (R and S) is defined by means of the logical AND for statements, it follows that the laws for these composite relations are the same as the laws for the logical AND between statements. The laws are summarized below.

Commutative law:

R and S = S and R.
Associative law:
(R and S) and T = R and (S and T).
Contradiction:
R and not-R = O,
where O stands for an empty relation because there are no elements associated by the composite relation (R and not-R).

11. Logical OR

Two relations R and S may be joined by the word or to make a composite relation (R or S). The definition of this composite relation is as follows:
x (R or S) y = (x R y) or (x S y).
For example, let x stand for a passenger, and let y stand for a row of seats in an aircraft. Let x R y mean x has a seat in y, and let x S y mean x has a seat behind y. Let x = Mr Brown, and let y = row 20. Then x (R or S) y means Mr Brown has a seat in or behind row 20.

EXERCISE

Let x and y be people. Let R mean is the mother of, and let S mean is the father of. Give the meaning of x (R or S) y.

12. Laws for the Logical OR

Since the composite relation R or S is defined by means of the logical OR for statements, it follows that the laws for these composite relations are the same as the laws for the logical OR between statements. The laws are summarized below.

Commutative law:

R or S = S or R.
Associative law:
(R or S) or T = R or (S or T).
Excluded middle:
R or not-R = U,
where U stands for a universal relation because all pairs of elements are connected by the composite relation (R or not-R).

13. Laws for Mixed Composite Relations

More laws for composite relations with the logical NOT, the logical AND, and the logical OR are listed below.

De Morgan's laws:

not-(R and S) = not-R or not-S
not-(R or S) = not-R and not-S.
Distributive laws:
R or (S and T) = (R or S) and (R or T).
R and (S or T) = (R and S) or (R and T).

14. Inverse Relations

A relation R between the elements x of a set A and the elements y of a set B has an inverse relation, represented by the symbol R-1, between the elements y of B and the elements x of A such that:
y R-1 x if and only if x R y.
For example, let x and y stand for buildings. Here the sets A and B are both sets of buildings. Let x R y mean x is higher than y. This has the same meaning as y is lower than x, which we write as y R-1 x. Therefore R stands for the relation is higher than, and R-1 stands for the inverse relation is lower than.

As another example, let x stand for a motor-car, and let y stand for a person. Here A is a set of motor-cars and B is a set of people. Let x R y mean The motor-car x belongs to the person y. This has the same meaning as The person y is the owner of the motor-car x, which we write as y R-1 x. Therefore R stands for the relation belongs to, and R-1 stands for the inverse relation is the owner of.

The inverse of a relation is not the same as the negation of the same relation. For example, if R stands for belongs to, then not-R stands for does not belong to, and this is different from R-1, which stands for is the owner of.

EXERCISE

Give the inverses of the following relations.
  1. Let x and y stand for metals, and let R stand for the relation melts at a lower temperature than.
  2. Let x stand for a town, let y stand for a person, and let R stand for the relation is the home town of.

15. Inverse of an Inverse

The inverse of an inverse relation is the original relation.

For example, let x and y stand for buildings, and let R stand for the relation is higher than. Then R-1 stands for the relation is lower than, and (R-1)-1 is the inverse of the relation is lower than, namely: is higher than.

As another example, let x stand for a motor-car in a set A, let y stand for a person in a set B, and let x R y mean The motor-car x belongs to the person y. Then R is the relation belongs to between the elements of A and B, R-1 is the relation is the owner of between the elements of B and A, and (R-1)-1 is the original relation R belongs to between the elements of A and B.

We summarize the law for the inverse of an inverse relation in symbols as follows:

(R-1)-1 = R.

16. Composition of Relations

Let R be a relation between the elements x in a set A and the elements y in a set B. Let S be a relation between the elements y in the set B and the elements z in a set C. When there exists y such that x R y and y S z, we have a relation connecting x and z through y, which is written x RS z. This relation RS is called the composition of R and S, and RS is called a composite relation.

For example, let x, y and z stand for people. Let x R y mean x is the sister of y, and let y S z mean y is the son of z. Then x RS z means x is the daughter of z.

The definition of the composition of two relations in symbols is as follows:

x RS z means Ey: x R y and y S z.

EXERCISE

Let x stand for a month, let y stand for an amount of rainfall, and let z stand for a vegetable. Let x R y mean The month x has an amount of rainfall at least y. Let y S z mean In a month with rainfall at least y we can grow the vegetable z. Give the meaning of x RS z.

17. Non-commutative Law for the Composition of Relations

When the sets of individuals x, y and z in the incomplete statements x R y and y S z all belong to the same universal set we may use the composition of R and S in the reverse order SR.

For example, let x, y and z stand for people. Let x R y mean x is the sister of y, and let y S z mean y is the son of z. Then x RS z means x is the daughter of z. Also, x S y means x is the son of y, and y R z means y is the sister of z. Then x SR z means x is the nephew of z. Here the composite relation SR is different from the composite relation RS.

This fact is called the non-commutative law for compositions of relations. It is summarized in symbols as follows:

SR is not generally the same as RS.

EXERCISE

Let x, y, and z be quantities of rice. Let x R y mean x is half y. Let y S z mean y is six more kilograms than z. Give the meanings of the two composite expressions x RS z and x SR z. Are the two meanings the same?

18. Inverse of a Composition of Relations

Let x stand for an element in a set A, let y stand for an element in a set B, and let z stand for an element in a set C. Let R stand for a relation between the elements of A and the elements of B, and let S stand for a relation between the elements of B and the elements of C. Then RS is a relation between the elements of A and the elements of C, and (RS)-1 is the same relation between the elements of C and the elements of A. In other words the sentences x RS z and z (RS)-1 x have the same meaning.

By the definition of a composite relation, the sentence x RS z means There exists an element y such that x R y and y S z. By the definition of the inverse of a relation, the sentence z (RS)-1 x also means There exists an element y such that x R y and y S z.

The sentence x R y may be written y R-1 x, and the sentence y S z may be written z S-1 y. Therefore, the sentence z (RS)-1 x means There exists an element y such that y R-1 x and z S-1 y. By the commutative law for the logical AND, it follows that z (RS)-1 x means There exists an element y such that z S-1 y and y R-1 x. Therefore, by the definition of the composition of two relations, it follows that: z (RS)-1 x means z S-1R-1 x.

This gives the following law for the inverse of a composition of two relations:

(RS)-1 = S-1R-1.
Example:

Let x stand for a woman, and let y and z stand for men. Let x R y mean x is the daughter of y, and let y S z mean y is the son of z. Then x RS z means x is the granddaughter of z. Also, z S-1 y means z is the father of y, and y R-1 x means y is the father of x. Therefore, z S-1R-1 x means z is the grandfather of x, which is also the meaning of z (RS)-1 x.

EXERCISE

Let x, y and z stand for quantities of rice. Let x R y mean x is half y . Let y S z mean y is six more kilograms than z. Give the meanings of:
  1. x RS z
  2. z S-1 y
  3. y R-1 x.
  4. z S-1R-1 x.

19. Associative Law for the Composition of Relations

Let w and x stand for men, and let y and z stand for women. Let R mean is the son of. Let S mean is the brother of. Let T mean is the mother of. Suppose w = Richard, x = John, y = Caroline, and z = Betty. Then we have:

w R x = Richard is the son of John.
x S y = John is the brother of Caroline.
y T z = Caroline is the mother of Betty.

The composition of R and S gives:

w RS y = Richard is the nephew of Caroline,

and the composition of RS and T gives:

w (RS)T z = Richard is the cousin of Betty.

Also, the composition of S and T gives:

x ST z = John is the uncle of Betty,

and the composition of R and ST gives:

w R(ST) z = Richard is the cousin of Betty.

Therefore (RS)T has the same meaning as R(ST), namely is the cousin of.

In a composition of three relations R, S, and T we may combine R and S first to make RS, and then combine RS with T. Or we may combine S and T first to make ST and then combine R with ST. Both of these methods of combining R, S, and T give the same composite relation. This is because the relations connecting the elements w, x, y, and z in four sets are fixed by the relations w R x, x S y, and y T z, and are not changed by how we consider them in pairs.

This general law is the associative law for the composition of relations. It is summarized in symbols as follows:

(RS)T = R(ST).
It follows from this law that we may omit the brackets and write RST for the composition of the three relations.

EXERCISE

Suppose there are four villages a, b, c, and d. Let R = is three kilometres west of. Let S = is one kilometre east of. Let T = is two kilometres west of. Give the meanings of: a R b, b S c, c T d, a RS c, a (RS)T d, b ST d, a R(ST) d. Does a (RS)T d have the same meaning as a R(ST) d?

Backward links: Statements I   Statements II   Quantifiers I   Quantifiers II   Sets I   Sets II

Forward links: Relations II

By R. H. B. Exell, 1998. King Mongkut's University of Technology Thonburi.
Back to Home Page