336
Relations, Functions, and Matrices
For the rest of this section we will concentrate on two types of binary relations
that are characterized by which properties (reflexivity, symmetry, antisymmetry,
and transitivity) they satisfy.
partial orderings
DefInItIon paRtial oRdeRing
A binary relation on a set S that is reflexive, antisymmetric, and transitive is
called a partial ordering on S.
From previous examples and Practice 5, we have the following instances of
partial orderings:
On N, x r y 4 x ≤ y.
On `(N), A r B 4 A # B.
On Z
+
, x r y 4 x divides y.
On 50, 16, x r y 4 x = y
2
.
If r is a partial ordering on S, then the ordered pair (S, r) is called a partially
ordered set (also known as a poset). We will denote an arbitrary, partially ordered
set by (S, d); in any particular case, d has some definite meaning such as “less
than or equal to,” “is a subset of,” “divides,” and so on. (The symbol for a generic
partial ordering, d, is designed to resemble the inequality symbol #, which, as
we’ve just noted, is a partial ordering on the set N or on any other set in which a
less-than-or-equal-to relation makes sense.)
Let (S, d) be a partially ordered set, and let A # S. Then d is a set of ordered pairs of elements of S, some of which may be ordered pairs of elements
of A. If we select from d the ordered pairs of elements of A, this new set is called
the restriction of d to A and is a partial ordering on A. (Do you see why the
three required properties still hold?) For instance, once we know that the relation
“x divides y” is a partial ordering on Z
+
, we automatically know that “x divides y” is
a partial ordering on 51, 2, 3, 6, 12, 186.
We want to introduce some terminology about partially ordered sets. Let
(S, d) be a partially ordered set. If x d y, then either x = y or x ∙ y. If x d y
but x ∙ y, we write x a y and say that x is a predecessor of y or y is a successor
of x. A given y may have many predecessors, but if x a y and there is no z with
x a z a y, then x is an immediate predecessor of y.
PRaCtiCe 8 Consider the relation “x divides y” on 51, 2, 3, 6, 12, 186.
a. Write the ordered pairs (x, y) of this relation.
b. Write all the predecessors of 6.
c. Write all the immediate predecessors of 6.
■
If S is finite, we can visually depict a partially ordered set (S, d) by using
a hasse diagram. Each of the elements of S is represented by a dot, called a
Relations, Functions, and Matrices
For the rest of this section we will concentrate on two types of binary relations
that are characterized by which properties (reflexivity, symmetry, antisymmetry,
and transitivity) they satisfy.
partial orderings
DefInItIon paRtial oRdeRing
A binary relation on a set S that is reflexive, antisymmetric, and transitive is
called a partial ordering on S.
From previous examples and Practice 5, we have the following instances of
partial orderings:
On N, x r y 4 x ≤ y.
On `(N), A r B 4 A # B.
On Z
+
, x r y 4 x divides y.
On 50, 16, x r y 4 x = y
2
.
If r is a partial ordering on S, then the ordered pair (S, r) is called a partially
ordered set (also known as a poset). We will denote an arbitrary, partially ordered
set by (S, d); in any particular case, d has some definite meaning such as “less
than or equal to,” “is a subset of,” “divides,” and so on. (The symbol for a generic
partial ordering, d, is designed to resemble the inequality symbol #, which, as
we’ve just noted, is a partial ordering on the set N or on any other set in which a
less-than-or-equal-to relation makes sense.)
Let (S, d) be a partially ordered set, and let A # S. Then d is a set of ordered pairs of elements of S, some of which may be ordered pairs of elements
of A. If we select from d the ordered pairs of elements of A, this new set is called
the restriction of d to A and is a partial ordering on A. (Do you see why the
three required properties still hold?) For instance, once we know that the relation
“x divides y” is a partial ordering on Z
+
, we automatically know that “x divides y” is
a partial ordering on 51, 2, 3, 6, 12, 186.
We want to introduce some terminology about partially ordered sets. Let
(S, d) be a partially ordered set. If x d y, then either x = y or x ∙ y. If x d y
but x ∙ y, we write x a y and say that x is a predecessor of y or y is a successor
of x. A given y may have many predecessors, but if x a y and there is no z with
x a z a y, then x is an immediate predecessor of y.
PRaCtiCe 8 Consider the relation “x divides y” on 51, 2, 3, 6, 12, 186.
a. Write the ordered pairs (x, y) of this relation.
b. Write all the predecessors of 6.
c. Write all the immediate predecessors of 6.
■
If S is finite, we can visually depict a partially ordered set (S, d) by using
a hasse diagram. Each of the elements of S is represented by a dot, called a