EF Basics

🔗

Section 17.1 Basics

🔗

relation (working definition): 🔗
a rule which assigns to some elements of a set $A$ several elements from a set $B$
$a R b$: 🔗
element $a \in A$ is related to element $b \in B$ by relation $R$
relation on a set: 🔗
a relation between elements of the same set

🔗

Remark 17.1.1.

🔗

Compare this working definition of relation with our working definition of function in Section 10.1.

🔗

As the name implies, a relation describes some relationship of elements of a set

A

to elements of a set

B .

🔗

Example 17.1.2. Pet relation.

🔗

Let

C

represent the set of living cats, and let

H

represent the set of living humans. Then one relationship between elements of these two sets can be expressed by writing

c R h

to mean that cat

c

is the pet of human

h .

🔗

Example 17.1.3. Parent relation.

🔗

Let

H

represent the set of living humans. Then one type of relationship between elements of this set can be expressed by writing

h_{1} R h_{2}

to mean that human

h_{1}

is the parent of human

h_{2} .

🔗

Example 17.1.4. Division relation.

🔗

One type of relationship between elements of

N_{> 0}

can be expressed by writing

m ∣ n

to mean that nonzero natural number

m

divides nonzero natural number

n .

🔗

Just as with functions, we want to avoid the use of the undefinable word “rule”. Notice that a relation just pairs elements of a set

A

with elements of a set

B;

we have seen this before.

relation (formal definition): 🔗
a subset of a Cartesian product

🔗

With this formal definition, writing

R \subseteq A \times B

becomes the same as saying “

R

is a relation between elements of

A

and

B,

” and writing

(a, b) \in R

becomes the same as writing

a R b .

🔗

Note 17.1.5.

🔗

With this formal definition, a relation on a set

A

means a subset of

A \times A .

🔗

Remark 17.1.6.

🔗

Recall that our formal definition of function states that a function

A \to B

is a special kind of subset of

A \times B .

But every subset of

A \times B

can be considered as a relation, so a function is a special kind of relation.

🔗

The difference is that a function

A \to B

must assign exactly one element of

B

to each element of

A,

whereas a relation from

A

B

can assign any number of elements of

B

(even zero) to each element of

A .

That is, a relation does not have to be well-defined, and can be left undefined on some elements of

A .

🔗

Example 17.1.7. Identity relation.

🔗

Consider

R = {(a, a) | a \in A} \subseteq A \times A .

🔗

Then

a_{1} R a_{2}

means

a_{1} = a_{2} .

This relation is the same as the identity function

{id}_{A} : A \to A .

🔗

Example 17.1.8. Element relation.

🔗

Consider

R = {(a, C) | a \in C} \subseteq A \times P (A) .

🔗

Then

a R C

means

a \in C .

This relation is in general not a function, since it is not well-defined: an element of

A

can be contained in several subsets of

A .

🔗

A relation between pairs of objects, such as the ones we have considered so far, is sometimes called a binary relation. But we can consider relationships between collections of more than two objects.

ternary relation: 🔗
a subset of $A \times B \times C$ for sets $A, B, C$

🔗

Example 17.1.9. A human (usually) has two biological parents.

🔗

Let

H

represent the set of all living humans. Then we can define a ternary relation

R \subseteq H^{3}

by taking

(h_{1}, h_{2}, h_{3}) \in R

to mean that humans

h_{1}, h_{2}

are the parents of human

h_{3} .

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results: