Determine if $R \subseteq A \times A$ is reflexive, transitive, symmetric, antisymmetric

elementary-set-theory

Let A be the set of bit strings $a = a_1a_2 \ldots a_9$ of length 9. Let $R \subset A \times A$ be the set of pairs $(a, b)$ such that $a_1 = b_1$ or $a_2 = b_2$.
Decide whether or not the relation $R$ is

  1. reflexive
  2. transitive
  3. symmetric
  4. antisymmetric
  5. an equivalence relation.

I do not understand this question. I know that $A \times A = \{(a_1a_2a_3a_4a_5a_6a_7a_8a_9, a_1a_2a_3a_4a_5a_6a_7a_8a_9)\}$. Here's my attempt:

  1. $R$ is reflexive since $aRa$ where $a = a_1a_2a_3a_4a_5a_6a_7a_8a_9$ is true since $a_1 = a_1$.
  2. I'm not sure about this one
  3. If $R$ is symmetric, aRb is true then $bRa$ is true. Since $aRb$ is true where $a_1 = b_1$ or $a_2 = b_2$ then $bRa$ is true because $b_1 = a_1$ or $b_2 = a_2$.
  4. It cannot be antisymmetric if it's symmetric

Best Answer

$A \ \mathrm{x}\ A=\{(a,b) | a=a_1...a_9 , b=b_1...b_9, a,b \in A\}$

i) Reflexive: is $(a,a) \in R$, where $a=a_1...a_9$? Yes, because $a_1=a_1$.

ii) Transitive: if $(a,b) \in R$ and $(b,c) \in R$ do we have $(a,c) \in R$? No, take for example $a_1=b_1$, $a_2 \neq b_2$ and $b_1 \neq c_1$, $b_2 = c_2$. We have $a_1 \neq c_1$ and $a_2 \neq c_2$, thus $(a,c) \notin R$.

iii) Symmetric: if $(a,b) \in R$ it means that $a_1=b_1$ or $a_2=b_2$. Therefore we have $b_1=a_1$ or $b_2=a_2$ i.e. $(b,a) \in R$.

iv) Antisymmetric: if $(a,b) \in R$ and $(b,a) \in R$ then we can have $a \neq b$: take for example $a_3 \neq b_3$. Thus it's not antisymmetric

v) It can't be an equivalence relation since it's not transitive.

Related Question