Equivalence relations Cartesian products

Question

For each of the following, I am trying to determine if it is an equivalence relation and all of its equivalence classes. However I am not sure what the variables a sub 1, b sub 1 etc. or y sub1 y sub2 are referring to in either of these problems. Does it have something to do with Cartesian products? If so I still don’t understand which variables would be which, especially for the set of permutations problem.

• R = {(a,b) : {a1,a2,a3} = {b1,b2,b3}} on the set of permutations of 1,...,n.

•R={(a,b) : a1·a2=b1·b2}on {0,1}^3.

• R={(x,y) : x1 ·y2 =y1 ·x2}on Z ×(Z - {0}).

Answer 1

It is context dependent, but the incredibly general answer is that variables represent arbitrary elements, and that variables with subscripts are also variables but depending on context if you have variables both with and without subscripts then those with subscripts generally have something to do with the variable corresponding to it which doesn't have a subscript. For example, we could be talking about a vector $v\in \Bbb R^3$ and referring to the individual entries in the vector like $v = \left[\begin{smallmatrix}v_1\\v_2\\v_3\end{smallmatrix}\right]$ where $v_1$ is the first entry in the vector $v$, etc...

For your specific examples:

$\mathcal{R} = \{(a,b)~:~\{a_1,a_2,a_3\} = \{b_1,b_2,b_3\}\}$ on the set of permutations of $1,\dots,n$

Here, $a$ and $b$ are permutations in the symmetric group $S_n$. My interpretation of the notation used here is that $a_1$ is just an alternate way of writing $a(1)$ and is the element to which $1$ is mapped by the permutation.

For example, when interpreting a permutation as a sequence and writing it in sequence form, if the permutation $a$ can be written as 4172536 then $a_1 = 4$, $a_2 = 1$, and $a_3 = 7$ respectively.

If you continue to interpret permutations in their sequence form then the relation in words is "The set formed by the first three terms of both permutations are the same" so you have for example 4172536 has the same first three terms as 4175623 and so are related.

Note that the way it was written was that $\{a_1,a_2,a_3\}=\{b_1,b_2,b_3\}$ so it isn't necessary that the first three elements appear in the exact same order. You would also have 4172536 is also related to 1742356 since in both permutations you have the numbers $1$, $4$ and $7$ appearing in some order.

$\mathcal{R} = \{(a,b)~:~a_1\cdot a_2 = b_1\cdot b_2\}$ on $\{0,1\}^3$

Here, $a$ and $b$ are elements of $\{0,1\}^3$, in other words can be thought of as ordered triples where each entry are either zero or one. For example $a = (1,0,1)$. Here, we would have $a_1$ would correspond to the first entry of $a$, $a_2$ would correspond to the second entry etc... which in this running example would have $a_1 = 1, a_2 = 0, a_3 = 1$ respectively.

The relation here reworded is then "$a$ and $b$ are related iff the product of the first two entries of $a$ is the same as the product of the first two entries of $b$."

For example $(1,0,1)$ is related to $(0,1,0)$ since in both cases the product of their first two entries are both equal to zero.

which can be reworded even more simply as $a$ and $b$ are related iff they either both neither have any zeroes in their first two entries or they both have at least one zero in their first two entries

$~$

$\mathcal{R} = \{(x,y)~:~x_1\cdot y_2 = y_1\cdot x_2\}$

This is in fact a very important example... it is related to how we rigorously define rational numbers and this relation is how we define equality of rational numbers.

Note, $\dfrac{x_1}{x_2} = \dfrac{y_1}{y_2} \iff x_1\cdot y_2 = y_1\cdot x_2$

Here, $x$ and $y$ are each ordered pairs of integers where the second entry in each pair is explicitly not allowed to be zero and $x_1,x_2$ refer to the first and second elements of the ordered pair $x$ respectively.

We have an example like $(3,5)$ is related to $(9,15)$ (which is just like how $\dfrac{3}{5} = \dfrac{9}{15}$)

Warning:... since this is how rational numbers and equality of rational numbers is rigorously defined in the first place, you may not simply divide and prove that the last is an equivalence relation using properties of rational numbers and foreknowledge that equality of rational numbers is an equivalence relation. That would be circular logic, using itself to prove itself, and is not allowed. Approach this problem directly via definitions and first principles.