O'Reilly logo

A First Course in Mathematical Logic and Set Theory by Michael L. O'Leary

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

CHAPTER 4

RELATIONS AND FUNCTIONS

4.1 RELATIONS

A relation is an association between objects. A book on a table is an example of the relation of one object being on another. It is especially common to speak of relations among people. For example, one person could be the niece of another. In mathematics, there are many relations such as equals and less-than that describe associations between numbers. To formalize this idea, we make the next definition.

images DEFINITION 4.1.1

A set R is an (n-ary) relation if there exist sets A0, A1, ... , An−1 such that

images

In particular, R is a unary relation if n = 1 and a binary relation if n = 2. If RA × A for some set A, then R is a relation on A and we write (A, R).

The relation on can be represented as a subset of the Cartesian product of the set of all books and the set of all tables. We could then write (dictionary, desk) to mean that the

dictionary is on the desk. Similarly, the set {(2, 4), (7, 3), (0, 0)} is a relation because it is a subset of Z × Z. The ordered pair (2, 4) means that 2 is related to 4. Likewise, R × Q is a relation where every real number is related to every rational number, and according to Definition 4.1.1, the empty set is also a relation because ∅ = ∅ × ∅.

EXAMPLE 4.1.2

For any set A, define

Call this set the identity ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required