Give proofs by induction for the following relation properties.

Question

1. Let $R$ and $S$ be relations such that $R\subseteq S$. Prove that $R^n$ is a subset of $S^n$ for all positive integers $n$.

2. Let $R$ be a symmetric relation. Prove that $R^n$ is symmetric for all positive integers $n$.

This is what I have done up to now. I am not used to proving relation properties.

1. The result is true for $n=1$, suppose $R^{n-1}$ is a subset of $S^{n-1}$.

   Note that if $A$ is a subset of $C$ and $B$ is a subset of $D$ then $A\times B$ is a subset of $C\times D$, thus :

   $R^n = R^{n-1} \times R$ is a subset of $S^{n-1} \times S = S^n$.

   Hence proved.

2. The result is true for $n=1$, suppose $R^{n-1}$ is symmetric.

   Let $(x_0,y_0,x_1,y_1,\dots,x_n,y_n)\in R^n=R \times R^{n-1}$

   Since $R$ is symmetric then $(y_0,x_0)\in R$.

   Since $R^{n-1}$ is symmetric then $(y_1,x_1,y_2,x_2,\dots,y_{n-1},x_{n-1})\in R^{n-1}$

   Hence $(y_0,x_0,y_1,x_1,\dots,y_n,x_n)\in R \times R^{n-1} = R^n$

   So $R^n$ is symmetric.

Answer 1

The correct answer would be:

1. Let $R$ and $S$ be relations such that $R\subseteq S$. Prove that $R^n$ is a subset of $S^n$ for all positive integers $n$.

2. Let $R$ be a symmetric relation. Prove that $R^n$ is symmetric for all positive integers $n$.

This is what I have done up to now. I am not used to proving relation properties.

1. The result is true for $n=1$, suppose $R^{n-1}$ is a subset of $S^{n-1}$.

   Note that if $A$ is a subset of $C$ and $B$ is a subset of $D$ then $A\times B$ is a subset of $C\times D$, thus :

   $R^n = R^{n-1} \times R$ is a subset of $S^{n-1} \times S = S^n$.

   Hence proved.

2. The result is true for $n=1$, suppose $R^{n-1}$ is symmetric.

   Let $(x_0,y_0,x_1,y_1,\dots,x_n,y_n)\in R^n=R^{n-1} \times R$

   Since $R$ is symmetric then $(y_n,x_n)\in R$.

   Since $R^{n-1}$ is symmetric then $(y_0,x_0,y_1,x_1,\dots,y_{n-1},x_{n-1})\in R^{n-1}$

   Hence $(y_0,x_0,y_1,x_1,\dots,y_n,x_n)\in R^{n-1} \times R = R^n$

   So $R^n$ is symmetric.