9.1 Relations and their properties Flashcards
Binary Relation:
Relationships between elements of two sets are represented using the structure called a binary relation, which is just a subset of the Cartesian product of the
sets.
Let A and B be sets. A binary relation from A to B is a subset of A × B
The most direct way to express a relationship between elements of two sets is to use ordered pairs
made up of two related elements. For this reason, these ordered pairs are called binary relations.
Binary relations represent relationships between the elements of two sets
Binary Relation:
Notation.
Let R be the set of ordered pairs. 1st element comes from A and 2nd from B.
We use the notation
aRb to denote that (a, b) ∈ R and
a ̸R b to denote that (a, b) ∉ R. Moreover, when (a, b) belongs to R, a is said to be related to b by R.
Representation of relations at end of 9.1.1:
Using a graph, using arrows to represent ordered pairs.
A table
Functions as relations:
Function f from a set A to a set B assigns exactly
one element of B to each element of A.
The graph of the function f from A to B is
the set of ordered pairs (a, f(a)) for a ∈ A.
b = f(a)
This means the graph of f is a subset of A X B.
It’s property being, that every element of A is the first element of exactly
one ordered pair of the graph.
Conversely, if R is a relation from A to B such that every element in A is the first element
of exactly one ordered pair of R, then a function can be defined with R as its graph.
This can
be done by assigning to an element a of A the unique element b ∈ B such that (a, b) ∈ R.
The relation can express one to many relation, but function represents exactly one element of B is related to each element of A.
Relations on a set:
A relation on a set A is a relation from A to A.
In other words, a relation on a set A is a subset of
A × A.
Any path to find number of relations on a finite set?
How many relations are there on a set with n elements?
It is not hard to determine the number of relations on a finite set, because a relation on a
set A is simply a subset of A × A.
A relation on a set A is a subset of A × A.
Because A × A has n^2 elements when A has
n elements, and a set with m elements has 2^m subsets, there are 2^(n^2)
subsets of A × A.
Thus, there are 2^(n^2) relations on a set with n elements.
Reflexive relation:
In some relations, an element is always related to itself. For instance, let R be the relation on
the set of all people consisting of pairs (x, y) where x and y have the same mother and the same
father. Then xRx for every person x.
A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A.
∀a((a, a) ∈ R),
where the universe of discourse is the set of all elements in A.
A relation on A is reflexive if every element of A is related to itself.
Is the “divides” relation on the set of integers reflexive?
the relation is not reflexive
because by definition 0 does not divide 0.
Symmetric Relation
Antisymmetric relation
How to verify these relations..
A relation R on a set A is called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all a, b ∈ A.
∀a∀b((a, b) ∈ R → (b, a) ∈ R)
To verify it’s not symmetric: finding a pair (a, b) such that it is in the relation but (b, a) is not.
A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is
called antisymmetric.
∀a∀b(((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b))
To verify it’s not antisymmetric:
finding a pair (a, b) with
a ≠ b such that (a, b) and (b, a) are both in the relation.
To check for
antisymmetry we make sure that no pair (a, b) with a != b and its opposite are both in the relation. In other
words, at most one of (a, b) and (b, a) is in the relation if a != b.
These are not opposites of each other.
A relation cannot be both symmetric and antisymmetric if
it contains some pair of the form (a, b) in which a ≠ b
Transitive Property:
A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R,
then (a, c) ∈ R, for all a, b, c ∈ A.
∀a∀b∀c(((a, b) ∈ R ∧ (b, c) ∈ R) → (a, c) ∈ R)
A common mistake to try to avoid is forgetting that a transitive
relation that has pairs (a, b) and (b, a) must also include (a, a) and (b, b)
How many reflexive relations are there on a set with n elements?
A relation R on a set A is a subset of A × A. Consequently, a relation is determined by
specifying whether
each of the n^2 ordered pairs in A × A is in R. However, if R is reflexive, each of the n ordered pairs (a, a) for
a ∈ A must be in R. Each of the other n(n − 1) ordered pairs of
the form (a, b), where a ≠ b, may or may not be in R. Hence, by the product rule for counting,
there are 2^ (n (n−1) ) reflexive relations [this is the number of ways to choose whether each element
(a, b), with a ≠ b, belongs to R].
Combining Relations:
Because relations from A to B are subsets of A × B, two relations from A to B can be combined
in any way two sets can be combined.
Example 18 gives the gist.
Composite of relations:
Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite
of R and S is the relation consisting of ordered pairs (a, c), where a ∈ A, c ∈ C, and for which
there exists an element b ∈ B such that (a, b) ∈ R and (b, c) ∈ S. We denote the composite
of R and S by S ◦R.
The powers of a relation R:
Let R be a relation on the set A. The powers R^n, n = 1, 2, 3, … , are defined recursively by
R^1 = R and R^(n+1) = R^n ◦ R.
The definition shows that R^2 = R ◦ R,
R^3 = R^2 ◦ R = (R ◦ R)◦ R, and so on
Theorem for transitive relation
and powers of relation…
and its proof also
The relation R on a set A is transitive if and only if
R^n ⊆ R for n = 1, 2, 3, … .
proof, pg 608
