Discrete Mathematics· Note 02
Relations
Jan 7
Relations
Intuitively, a relation is a way of “comparing” two elements
- , , , , , among numbers
- set of people, set of cities
- We can define a relation to hold between person and city if lives in .
- set of people
- We can define a relation to hold between person and person if they share a family connection.
Formal Definition:
Let be sets. A relation from to is a subset of .
Yeah, that’s it. The relation doesn’t have to be anything meaningful. It’s just a subset of the Cartesian product of the two sets.
,
- “less than” relation:
- “greater than” relation:
- “arbitrary” relation:
A relation from to itself (i.e. ) is called a relation on .
For example, see the third example in the intuitive definition above.
Simple Relations
- Empty relation:
- No pairs satisfy the relation
- E.g, iff
- because there are no negative numbers in
- Complete relation:
- Every pair satisfies the relation
- E.g, , , “less than”
- because every element of is less than every element of
The usual set operations can be applied to relations, e.g. union, intersection, complement, etc. since relations are just sets.
Inverse Relations
Definition:
Let be a relation from to . The inverse relation of (denoted ) is the relation from to defined by .
, “less than” =
“greater than” =
Note that we just swapped the order of the elements in each pair.
Composition of Relations
Suppose and are relations.
Definition:
The composition of and (denoted ) is the relation from to defined by .
A composition of relations and is a new relation that contains all pairs where there exists some such that and .
are sets of people
is relation “is a brother of” (i.e. iff is a brother of )
is relation “is a parent of” (i.e. iff is a parent of )
is relation “is an uncle of” (i.e. iff is an uncle of )
Notation: , , etc.
Properties of Relations
- Associative:
Equivalence Relations
Partitions
Definition:
Let be any set. A partition of is a set of subsets of :
such that two conditions are met:
- For all
- Subsets in are disjoint
-
- Every element of is in some subset of the partition
Let
Let
Let
Let
Let
Then the partition of looks like this:
Equivalence Relations
Definition:
Given a partition of , define a relation as follows:
whenever belong to the same subset in the partition .
In our above example, , , , .
Let
Let the partition be defined as specified in this diagram:
Then,
is called an equivalence relation, and we say that is induced by the partition .
Any relation on is:
- Reflexive
- Every belongs to the same “cell” as itself
- Symmetric
- If is in ’s cell, then is in ’s cell
- Transitive
- If is in ’s cell, and is in ’s cell, then is in ’s cell
Equivalence Relation Theorem
Any relation on which is reflexive, symmetric, and transitive is an equivalence relation (induced by some partition of ).
I.e., we can “work backwards” from a relation satisfying these three properties to find the partition which induced it.
Claim: is reflexive, symmetric, and transitive.
Proof:
- ; hence
- If then
- If then
- If and , then
Therefore, is an equivalence relation.
Equivalence Classes
Definition:
The cells of a partition (which induces ) are called the equivalence classes of .
For each , means the equivalence class of .
E.g., in the last example, (because they are both two less than multiples of 5)
The set of all equivalence classes of in the relation is denoted (“ modulo ”) and is called the quotient set of .
In the last example,
set of people
is a relation on : when share last names.
It’s easy to see that is reflexive, symmetric, and transitive, and hence is an equivalence relation.
It’s also easy to see that each equivalence class corresponds to a family name.
The quotient set is the set of all last names.
Jan 14
Order Relations
Definition:
An order relation generalizes the familiar “orders” like ≤ or ≥ on sets of numbers.
Formally, a relation on a set is an order relation if it has three properties:
Properties of Order Relations
- is reflexive
- is transitive
- is antisymmetric
- i.e., if and , then
- cannot hold between different elements in both directions
- Note that this is not the same as being asymmetric
- Formally, is antisymmetric iff
If is an order relation, then we use the notation
in place of using or .
- on sets of numbers
- Lexicographic order of points on an plane
- Order by first point, if those are equal, order by the next point, etc…
- Let be any set and define the relation on by:
iff . - Let .
Define on as: if ( divides ).
Definition:
An order relation on a set is a total order if, for every , either or (or both, if ).
Otherwise, is called a partial order.
Examples 1 and 2 above are examples of total orders, and examples 3 and 4 above are partial orders.
Hasse Diagrams
A partial order on a set can be illustrated using a Hasse diagram.
For example, , and is the divisibility relation (example 3 from above)
Property of Hasse Diagrams
We can get from to by moving up edges iff then
Rules of HD
- All minimal elements go on the bottom.
- ( is minimal if there does s.t. )
- If there is a single minimum element , then is called a minimum in .
- In the above example, is a minimum.
- If we delete from , then are all minimal elements, but there is no minimum.
- An edge exists from “goes up” to if:
- s.t. and
- Under these conditions, we call a successor element of .
- E.g., in our example, are successors of .
- is called a predecessor of .
- An element can have multiple predecessors and/or successors.
- An element with no successors is called maximal
- E.g., in our example, are maximal.
- If only one element is maximal, then it is called a maximum of .
The Hasse Diagram of a total order looks like a straight line: