3.3 Relations[1YV]
[1WY]A relation between elements of two sets \(A,B\) is defined as a subset \(R⊆ A× B\) of the cartesian product. Typically, the infix notation \(aRb\) is used instead of writing \((a,b)∈ R\).
[23X]A relation \(R\) between elements of \(A\) is said to be:
irreflexive or anti-reflexive if \(\lnot xRx\) for any \(x∈ A\);
antisymmetric if \(aRb\) and \(bRa\) imply \(a=b\), for any \(a,b∈ A\);
trichotomous if for all \(x,y \in A\) one and exactly one of \(xRy\), \(yRx\) and \(x = y\) holds;
transitive if \(xRy\) and \(yRz\) imply \(xRz\), for any \(x,y,z∈ A\).
A relation \(R\) between elements of \(A\) and elements of \(B\) is said to be:
injective (also called left-unique) if \(xRy\) and \(zRy\) imply \(x = z\), for any \(x,z∈ A,y∈ B\);
functional (also called right-unique) if \(xRy\) and \(xRz\) imply \(y = z\), for any \(x∈ A,y,z∈ B\); such a binary relation is called a “partial function” (see also 3.5,17);
total (also called “left-total”) if for any \(x∈ A\) there is a \(y∈ B\) such that \(xRy\);
surjective (also called “right-total”) if for any \(y∈ B\) there is a \(x∈ A\) such that \(xRy\).
[1W5]An equivalence relation is a relation between elements of \(A\) that enjoys the properties: reflective, symmetrical, transitive.
Equivalence relations are typically denoted by symbols ”\(∼\)” , ”\(≈\)” , ”\(≃\)” , ”\(≅\)” , ”\(≊\)” etc.
[1Y5] An order relation (or simply order) is a relation between elements of \(A\) that enjoys the properties: reflective, antisymmetrical, transitive.
An order relation is total if all elements are comparable, i.e. if for every \(a,b ∈ A\) you have \(aRb ∨ bRa\).
(When an order relation is not total, it is said to be partial).
Symbols such as ”\(≤\)” or ”\(⊆\)” or ”\(⪯\)” or similar are generally used.
[24W]The above is the definition in [ 2 ] ; in other texts, a relation between elements of \(A\) that enjoys the properties: reflexive, antisymmetrical, transitive is straightforwardly called partial order. (cf Example 2.1.1 in [ 12 ] where moreover a total order is called linear order). For this reason we will sometimes add a “(partial)” to state that the order being discussed may be partial.
Order relations are discussed in Section 3.4
[1Y7]It is customary to write \(a≥ b\) as a synonym for \(b≤ a\). If \(a≤ b∧ a≠ b\) we will write \(a{\lt}b\); similarly if \(a≥ b∧ a≠ b\) we write \(a{\gt}b\). Beware that if the relation is not total, it is not true in general that \(¬ (a≤ b)\) is equivalent to \(a{\gt}b\).
See in this regard the exercise 2.
- E51
[1WH]Prerequisites:46.(Proposed on 2022-12) For each set \(A\) and each relation \(R\) between elements of \(A\), explain if it is reflective, symmetric, antisymmetric and/or transitive; if it is a order relation, determine if it is total.
- E51
[1WK]Let \(f:A→ B\) be a function, let \(∼\) be an equivalence relation on \(B\): prove that the relation \(R\) between elements of \(A\) given by
\[ xRy\iff f(x)∼ f(y) \]is an equivalence relation.
- E51
-
Given two relations \(a≤ b\) and \(a{\lt} b\) for \(a,b\in A\), show that these are equivalent:
\(a≤ b\) is a (possibly partial) order relation and we identify
\[ a{\lt}b = (a≤ b\land a\neq b)\quad ; \]\(a{\lt} b\) is an irreflexive and transitive relation and \(\forall x,y\in A\) at most one of \(x{\lt}y~ ,~ x=y ~ ,~ y{\lt}x\) holds; and we identify
\[ a≤ b = (a{\lt} b\lor a= b)\quad . \]
- E51
[24K]Prerequisites:46,48,3. Given two relations \(a≤ b\) and \(a{\lt} b\) for \(a,b\in A\) show that these are equivalent:
\(a≤ b\) is a total order relation and
\[ a{\lt}b = (a≤ b\land a\neq b)\quad , \]\(a{\lt} b\) is an irreflexive, trichotomous and transitive relations and
\[ a≤ b = (a{\lt} b\lor a= b)\quad . \]
- E51
[1YH] Consider \(A=ℝ^ 2\) and consider the relations
\[ (x,y)∼ (x',y') \iff ( x-x'∈ℤ∧ y-y'∈ℤ) \]between elements of \(ℝ^ 2\) :
show that it is an equivalence relation;
graphically represent equivalence classes;
describe the set \(A/∼\).