A relation is some property between elements that may or may not hold. As a non-mathematical example, the phrase “is a child of” is a relation. “You are a child of your father” is a true statement, so the relation holds. However “Your father is a child of you” is false, so the relation does not hold.
Definition
Let A be a set. A relation R on the set A is any subset of the cartesian product A \times A.
Then we’ve defined a relation R to be a set of ordered pairs (a,b) where a,b \in A. Any pair of elements is either belonging to R or not. If (a,b) \in R, we say “a is in the relation R to b”, and that the relation between the two elements holds or is true.
It is common to use \sim as a general relation symbol, and we almost always use infix notation for relations, and write a \sim b to mean {(a,b) \in\, \sim}. When (a,b) \not \in\, \sim we write a \not \sim b.
Properties
Relations have many properties, the following three being the most useful.
Let \sim be a relation on a set A.
- We call \sim reflexive if for all a \in A
a \sim a.
- We call \sim symmetric if for all a,b \in A
a \sim b \implies b \sim a.
- We call \sim transitive if for all a,b \in A
a \sim b \text{ and } b \sim c \implies a \sim c
There are also special properties when a relation is never reflexive, symmetric, or transitive.
Let \sim be a relation on a set A.
- We call \sim anti-reflexive if for all a\in A,
a \not \sim a.
- We call \sim anti-symmetric if for all a,b \in A,
a \sim b \implies b \not \sim a.
- We call \sim anti-transitive if for all a,b,c \in A,
a \sim b \text{ and } b \sim c \implies a \not \sim c.
Equivalence Relations
An equivalence relation on a set A is a relation \sim such that \sim is reflexive, symmetric, and transitive.
Equivalence relations are (not surprisingly) related to equality, and cover notions like equivalence and congruency.
Let \sim be an equivalence relation on a set A. Let [a] be a subset of A determined by the equation
[a] = \{x \mid a \sim x\}.
We call [a] the equivalence class of A generated by a.
While context is usually enough to know which relation an equivalence class is referring to, [a]_\sim is used to mean the equivalence class of A generated by a with the relation \sim.
Equivalence classes have the following properties:
Let \sim be an equivalence relation on a set A. Then the equivalence class [a] will always contain a as an element.
Because \sim is an equality relation, it is reflexive by definition. Therefore a \sim a, and thus a \in [a].
Let \sim be an equivalence relation on a set A. Then the equivalence classes [a] and [b] are either disjoint or equal.
If [a] \cap [b] is empty, then the equivalence classes are disjoint.
If instead there exists some element c \in [a] \cap [b], then by definition we have a \sim c and b \sim c. Using the symmetrical property of our relation, b \sim c implies c \sim b, and then by transitivity we have a \sim c and c \sim b implies a \sim b.
Suppose [a] contains some element a_2. Then we have a \sim a_2, which via symmetry gives a_2 \sim a, transitivity with a \sim b implies a_2 \sim b, and symmetry again gives b \sim a_2. Thus a_2 \in [b]. Since then every element in [a] belongs to [b], we have [a] \subseteq [b].
Similarly, this can be repeated to show [b] \subseteq [a], and thus [a] = [b]. Therefore, two equivalence classes are either disjoint, or equivalent.
Using these theorems, we can show that the collection of equivalence classes formed by an equivalence relation have a special property.
Let \sim be an equivalence relation on A. The collection of equivalence classes of A form disjoint subsets of A whose union is all of A.
Let \sim be an equivalence relation on a set A, and let \mathcal{E} be the collection of all the equivalence classes determined by this relation
\mathcal{E} = \{[x] \mid x \in A\}.
By Theorem 1.2.2, distinct elements of \mathcal{E} are disjoint. And furthermore by Lemma 1.2.1, the union of elements of \mathcal{E} is equal to A, since each element of A belongs to an equivalence class. Thus the collection of equivalence classes of A are disjoint and have a union of A.
The collection of equivalence classes is a partitcular example of what is called a partition.
Partitions
A partition of a set A is a collection of disjoint subsets of A whose union is all of A.
We proved the set of equivalence classes forms a partition. It is true also that given any partition P on a set A, there is exactly one equivalence relation \sim from which P is derived. (TO-DO PROOF)
Finatary Relations
The relations we have covered up until now take place over a single set. We can generalize the concept by letting the relation take place over an arbitrary amount of sets.
Let A_1,A_2,\dots,A_n be sets. A finatary relation R is a subset of the Cartesian product A_1 \times A_2 \times \dots \times A_n.
Not only does this definition allow us to have relations between any finite amount of sets, it also allows these sets to be distinct. The arity of a relation is the number of sets the relation is over. We call a relation over n sets an n-ary relation, and use latin terms like unary, binary and ternary for 1-ary, 2-ary and 3-ary relations respectively.
Nullary Relations
Intriguingly, this definition allows to define nullary, or 0-ary relations. Using the definition of Cartesian product, the nullary product is the set
\displaystyle{\prod_\varnothing = \{\varnothing\}}
and thus we have two nullary relations, R = \varnothing and R = \{\varnothing\}.