1

Let $R$ be a relation on a set $A$, then define $R’$ on $A\times A$ by $$(a_1,a_2)R'(b_1,b_2)\Leftrightarrow a_1R\,a_2\wedge b_1R\,b_2$$

  1. Prove that $R’$ is an ordering relation when $R$ is an ordering relation.
  2. the relation $R’$ is a linear ordering when $R=\mathrm{id}_A$ and the number of elements in $A$ is $1$

An ordering relation is reflexive, antisymmetric, and transitive. Where as a linear one is connex , antisymmetric and transitive. I have no clue how to use the definition of $R’$ compared to $R$. For reflexivity, I said if $R$ is reflexive, it means that the set A must contain the $R=\mathrm{id}_A$ and therefor the set $A \times A$ would also contain $R=\mathrm{id}_A$, therefore $R’$ is reflexive exactly when $R$ is reflexive, but I still don’t know how to fill in the definition. My idea so far is working on the right side of the equation where both $a_1$ and $a_2$ equals $x$, both $b_1$ and $b_2$ equals $y$ but I’m not sure how to proceed.

KaiserKatze
  • 247
Maxim Jorje
  • 11

1 Answers1

1

Partial Answer: $\newcommand{\op}[2]{ \left\langle #1 ,\, #2 \right\rangle }$ $\newcommand{\rel}[1]{ \mathcal{#1} }$

Let $a = \op{a_1}{a_2}$ and $b = \op{b_1}{b_2}$. We can redefine $\rel{R'}$: \begin{align} \op{a}{b} \in \rel{R'} \iff \{ a ,\, b \} \subseteq \rel{R} \end{align}

The order of elements in a set does not matter, i.e. $\{ a ,\, b \} = \{ b ,\, a \}$, so the relation $\rel{R'}$ is always symmetric.

Because $\rel{R}$ is reflexive, we have $\forall x \in A \left( \op{x}{x} \in \rel{R} \right)$.

Let $a = b = \op{x}{x}$, obviously $\{ a ,\, b \} = \{ a ,\, a \} = \{ a \} \subseteq \rel{R}$, therefore $\op{a}{a} \in \rel{R'}$, i.e. $\rel{R'}$ is reflexive.

Let $x = \op{x_1}{x_2},\; y = \op{y_1}{y_2},\; z = \op{z_1}{z_2}$, and $\{ x,\, y,\, z \} \subseteq \rel{R}$.

\begin{align} \{ x ,\, y \} \subseteq \rel{R} &\implies \op{x}{y} \in \rel{R'} \\ \{ y ,\, z \} \subseteq \rel{R} &\implies \op{y}{z} \in \rel{R'} \\ \{ x ,\, z \} \subseteq \rel{R} &\implies \op{x}{z} \in \rel{R'} \end{align}

Therefore, $\rel{R'}$ is always transitive.

To prove $\rel{R'}$ is antisymmetric, we have to prove $\rel{R'} \cap \rel{R'}^{-1} \subseteq \Delta x$, where $\Delta x = \{ \op{x}{x} :\: x \in A \}$. Because $\rel{R'}$ is always symmetric, $\rel{R'} = \rel{R'}^{-1}$. Then we have to prove $\rel{R'} \cap \rel{R'}^{-1} = \rel{R'} \subseteq \Delta x$. Meanwhile, $\rel{R'}$ is reflexive, so $\Delta x \subseteq \rel{R'}$. Therefore, to prove $\rel{R'}$ is antisymmetric, we have to prove $\rel{R'} = \Delta x$, or $$\forall x,\,y \in A \left( \begin{array}{c} x = y \iff \op{x}{y} \in \rel{R'} \\ x \neq y \iff \op{x}{y} \notin \rel{R'} \end{array} \right)$$ Furthermore, $$\forall x,\,y \in A \left( \begin{array}{c} x = y \iff \{ x,\,y \} \subseteq \rel{R} \\ x \neq y \iff \{ x,\,y \} \nsubseteq \rel{R} \end{array} \right)$$

For all $x_1,\,x_2 \in A$, let $x = \op{x_1}{x_2},\; y = \op{x_2}{x_1}$. Obviously, $x = y$ when $x_1 = x_2$, $x \neq y$ when $x_1 \neq x_2$.

Because $\rel{R}$ is antisymmetric, assumming $x_1 \neq x_2$ and $x = \op{x_1}{x_2} \in \rel{R}$, we can get $y = \op{x_2}{x_1} \notin \rel{R}$. Now we have $x \neq y \implies \{ x,\, y \} \nsubseteq \rel{R}$.

Assume $\{ x,\, y \} \nsubseteq \rel{R}$, then $ x \notin \rel{R} \lor y \notin \rel{R}$, i.e. $ \op{x_1}{x_2} \notin \rel{R} \lor \op{x_2}{x_1} \notin \rel{R}$ holds. Because $\rel{R}$ is reflexive, $\op{x_1}{x_1} \in \rel{R}$ and $\op{x_2}{x_2} \in \rel{R}$. Now we get $x_1 \neq x_2$, i.e. $\{ x,\, y \} \nsubseteq \rel{R} \implies x \neq y$.

Therefore, $\rel{R'}$ is antisymmetric.

All in all, $\rel{R'}$ is an ordering relation when $\rel{R}$ is one.

KaiserKatze
  • 247