A subset of $A \times B$ is a relation between $A$ and $B$. If $R$ is the relation, then the notation $aRb$ means $(a,b) \in R.$ A subset of $A^2$ is a relation over $A,$ or sometimes it is said like $R$ is a relation on $A.$
Problem 1: If $R \subseteq A \times B$ and $|A| = a$ and $|B| = b,$ how many elements could $R$ have?
$R$ could have up to $ab$ elements in it.
A relation $R$ on $A$ is reflexive if $\forall a \in A,$ $aRa.$
Problem 2: Why can't a reflexive relation be between unequal sets?
Suppose $R$ is a reflexive relation between $A$ and $B$ and $a \in A$ and $a \notin B.$ This leads to a contradiction. On one hand, since $R$ is reflexive, $aRa$, but on the other hand, since $a \notin B,$ $(a,a) \notin A \times B.$
Problem 3: If $|A| = n,$ how many reflexive relations on $A$ are there?
There are $2^{n^2-n}$ reflexive relations on $A.$
Problem 4: If $A = \{1,2\},$ list all reflexive relations on $A.$
$\{(1,1),(2,2)\},$ $\{(1,1),(1,2),(2,2)\},$ $\{(1,1),(2,1),(2,2)\},$ $\{(1,1),(1,2),(2,1),(2,2)\}$
Problem 5: Let $R$ be a relation on $\mathbb{R}^2$ such that $aRb$ if and only if $a \leq b.$ Is $R$ reflexive? What if we replace $\leq$ with a less than symbol?
Yes and no.
A relation $R$ between $A$ and $B$ is symmetric if $\forall a \in A,$ $\forall b \in B,$ $(aRb$ $\implies bRa).$
Problem 6: Show that if a symmetric relation $R$ is between $A$ and $B$, then $R \subseteq (A \cap B)^2.$
A relation $R$ between $A$ and $C$ is transitive if $\forall a \in A,$ $\forall b \in A \cap C,$ $\forall c \in C,$ $((aRb$ and $bRc)$ $\implies aRc).$
Problem 7: Is the "less than or equal to" relation transitive?
Yes.
Problem 8: Given a set $X$, define $R$ such that $URV$ if and only if $U \subseteq V \subseteq X.$ Is $R$ transitive?
Yes.
The symbol $\sim$ may also be used as a relation, but usually it is only used for a special kind of relation called an equivalance relation. $R$ is an equivalence relation if it is reflexive, symmetric, and transitive.
Problem 9: If $R_1$ and $R_2$ are equivalence relations on $A$, is $R_1 \cap R_2$ an equivalence relation?
Yes.
A relation $R$ between $A$ and $B$ is antisymmetric if $\forall a \in A,$ $\forall b \in B,$ $(aRb$ and $bRa)$ $\implies a=b.$
Problem 10: If $R$ is a relation on $\mathbb{Z}$ such that $aRb$ if and only if $a \leq b,$ then is $R$ antisymmetric? What if we replaced $\leq$ with a "less than" symbol?
Yes and yes.
Problem 11: If $|A| = n,$ how many symmetric and antisymmetric relations on $A$ are there?
For every $a \in A,$ $(a,a)$ could either be in the relation or not. Other than that, the relation could have no other kinds of elements. Thus, there are $2^n$ symmetric and antisymmetric relations on $A.$
Problem 12: What if we wanted to define an antisymmetric relation on a set like this: a relation $R$ on $A$ is antisymmetric if $\forall a,b \in A,$ $aRb$ $\implies$ it is not the case that $bRa.$ Would the definition be equivalent to the previous definition?
The former definition allows for elements of the form (a,a) to be in $R,$ whereas the latter definition would forbid such elements.
A relation $R$ on $A$ is a partial order if $R$ is reflexive, antisymmetric, and transitive. Usually, we will use the symbol $\leq$ to mean a partial order.
Problem 13: Given a set $X$, define $R$ such that $URV$ if and only if $U \subseteq V \subseteq X.$ Is $R$ a partial order?
Yes.
Problem 14: Define a relation $R$ on $\mathbb{R}^n$ as $uRv$ if and only if ($|u|$ is less than $|v|$ or $u=v).$ Is $R$ a partial order?
Yes.
A partial order $\leq$ on $A$ is a total order if $\forall a,b \in A,$ $aRb$ or $bRa.$
Problem 15: Come up with a total order on $\mathbb{R}.$
Use $\leq.$
Problem 16: Suppose $R_1$ is a total order on $A$. Define $R_2$ to be a relation on $A$ such that $aR_2b$ if and only if $bR_1a.$ Is $R_2$ a total order?
Yes.