A “binary relation” defines how pairs of set elements interact with one another. For instance, in a set of people from a family $\{John,~Tom,~Mary,~Nina,~Joe,~Liza\}$, we may define a relation “is sibling of”. So, we may say, “John is a sibling of Mary”, or “Joe is a sibling of Liza”. Or, for instance, we may define a relation “is parent of”. So, “Tom is parent of nina” or “Mary is parent of Tom”.
We note at once that the relation doesn't apply to every pair of elements in the set. So, it is entirely possible that while John and Mary are siblings, and Joe and Liza are siblings, John and Joe may not be siblings. We also note that it is not symmetric. If Mary is the parent of Tom, Tom is certainly not the parent of Mary. So clearly, the ordering of the elements is important.
Relations may also be defined between elements of different sets. So, for instance, we may have a set $\{doctor, ~engineer, ~lawyer, ~artist\}$. We could now define a relation “is a” relating the two sets. So, for instance, we may have “John is a doctor”, and “Mary is a lawyer”.
Formally, a binary relation on a set $A$ is a collection of ordered pairs of elements of $A$. Alternately stated, a relation is a subset of $A\times A$.
More generally, a binary relation between two sets $A$ and $B$ is a subset of $A \times B$. FIGURE FOR AxA AND AxB
We will represent relations generally by the symbol $R$. A binary relation relation $R$ between two sets $X$ and $Y$ is defined as the ordered triple $(X, Y, G)$, where $G$ is the subset of $X \times Y$ that specifies the relation. $X$ is called the domain of the relation, $Y$ is the codomain, and $G$ is the graph.
For any pair of elements $(x,y) \in G$, we will say “$x$ is $R$-related to $y$”, or $xRy$. Note that since relations are not symmetric, $xRy \not\Rightarrow yRx$.
A generalization of binary relations are $M$-ary relations, which are defined as subsets of the the cartesian product of $M$ sets: $A_1 \times A_2 \times \cdots \times A_M$.
A function is a special type of binary relation between a domain $X$ and a codomain $Y$ with the following properties:
In other words, every element of $X$ must be related to exactly one element of $Y$.
Another way of defining a function is to say that “a function is a relation $F$ such that if $xFy$ and $xFy'$, then $y = y'$.”
FIGURE
While $X$ is the domain of the function and $Y$ is the codomain, the precise set of vlaues in $Y$ taken by the function is called the range ofthe function.
We usually denote functions as $F(x) = y$, rather than $xFy$.
An Equivalence relation on a set $S$ is a binary relation on $S \times S$ such that the following three properties hold.
An Equivalence relation is usually represented by $x \sim y$, or $x \equiv y$.
An Equivalence Class is a subset of elements from any set that are equivalent to one another according to some specified equivalence relation.
Formally, given any set $S$ and an equivalent relation $\equiv$, an equivalence class of any element $x$ in $S$ is the sub set of all elements $y$ such that $x\equiv y$. The equivalence class of $x$ is generally denoted as $[x]$. Thus, given any set $S$ and an element $x \in S$, \[ [x] = \{y \in S | x \equiv y\} \]
In our “family” set above, if John, Mary and Nina are siblings, the Equivalence class of John under the relation “is a sibling of” is $\{John,~Mary,~Nina\}$.
An order relation on a set $S$, generally represented by the symbol $\leq$, is a binary relation between elements of $S$ that has the following properties.
Note that $\subseteq$ is an order relation. Not every pair of elements within $S$ need be related by an order relation. This leads to the following definitions of ordered sets.
A partially-ordered set or “poset” consists of a set together with an order relation such that, for some pairs of elements from the set, one of the elements precedes the other by the ordering relation. Note, however, that not all pairs may be related through this ordering relation.
A common real-life example that is often cited for a partially ordered set is the set of all people in a family tree, where the ordering relation is the genalogical descendeancy relationship “is descendant of”. Some pairs of people bear the descendant-ancestor relationship, but other pairs are not related in this manner. The figure below shows an example.
FIGURE OF FAMILY TREE
A totally-ordered set, also simply called an ordered set is a set along with an order relationship such that for every pair of elements $x$ and $y$ from the set, one of the three following conditions holds. \[ x < y~~OR \\ y < x~~OR \\ x = y \]
The above set of conditions is called trichotomy.
A well-ordered set is a totally ordered set $S$ with the property that every non-empty subset of $S$ has a least element. Since we haven't defined least elements yet, we will return to this topic later.