10
$\begingroup$

Let $\mathcal{X}$ be the set of all nonempty subsets of the set $\{1,2,3,...,10\}$. Define the relation $\mathcal{R}$ on $\mathcal{X}$ by: $\forall A, B \in \mathcal{X}, A \mathcal{R} B$ iff the smallest element of $A$ is equal to the smallest element of $B$. For example, $\{1,2,3\} \mathcal{R} \{1,3,5,8\}$ because the smallest element of $\{1,2,3\}$ is $1$ which is also the smallest element of $\{1,3,5,8\}$.

Prove that $\mathcal{R}$ is an equivalence relation on $\mathcal{X}$.

From my understanding, the definition of reflexive is:

$$\mathcal{R} \text{ is reflexive iff } \forall x \in \mathcal{X}, x \mathcal{R} x$$

However, for this problem, you can have the relation with these two sets:

$\{1\}$ and $\{1,2\}$

Then wouldn't this not be reflexive since $2$ is not in the first set, but is in the second set?

I'm having trouble seeing how this is reflexive. Getting confused by the definition here.

$\endgroup$
  • 5
    $\begingroup$ Reflexive means that every element is related to itself. Thus, for reflexivity you have to consider one set only. Ok, we have that $\{ 1 \} \mathcal R \{ 1,2 \}$ but we have also $\{ 1 \} \mathcal R \{ 1 \}$ and $\{ 1,2 \} \mathcal R \{ 1,2 \}$ $\endgroup$ – Mauro ALLEGRANZA Apr 7 at 17:34
  • 7
    $\begingroup$ Note: “reflexive” does not mean that if $x$ is related to $y$, then $x=y$. It means that if $x=y$, then $x$ is related to $y$. $\endgroup$ – Arturo Magidin Apr 7 at 17:44
  • $\begingroup$ So it must be reflexive because both $A$ and $B$ belong to the same set $\mathcal{X}$? $\endgroup$ – qbuffer Apr 7 at 18:00
  • $\begingroup$ @qbuffer Have a look at the updated version of my answer. $\endgroup$ – Haris Gusic Apr 7 at 18:49
11
$\begingroup$

Why are you testing reflexivity by looking at two different elements of $\mathcal{X}$? The definition of reflexivity says that a relation is reflexive iff each element of $\mathcal X$ is in relation with itself.

To check whether $\mathcal R$ is reflexive, just take one element of $\mathcal X$, let's call it $x$. Then check whether $x$ is in relation with $x$. Because $x=x$, the smallest element of $x$ is equal to the smallest element of $x$. Thus, by definition of $\mathcal R$, $x$ is in relation with $x$. Now, prove that this is true for all $x \in \mathcal X$. Of course, this is true because $\min(x) = \min(x)$ is always true, which is intuitive. In other words, $x \mathcal{R} x$ for all $x \in \mathcal X$, which is exactly what you needed to prove that $\mathcal R$ is reflexive.

You must understand that the definition of reflexivity says nothing about whether different elements (say $x,y$, $x\neq y$) can be in the relation $\mathcal R$. The fact that $\{1\}\mathcal R \{1,2\}$ does not contradict the fact that $\{1,2\}\mathcal R \{1,2\}$ as well.

$\endgroup$
6
$\begingroup$

A binary relation $R$ over a set $\mathcal{X}$ is reflexive if every element of $\mathcal{X}$ is related to itself. The more formal definition has already been given by you, i.e. $$\mathcal{R} \text{ is reflexive iff } \forall x \in \mathcal{X}, x \mathcal{R} x$$

Note here that you've picked two different elements of the set to make your comparison when you should be comparing an element with itself. Also make sure you understand that an element may be related to other elements as well, reflexivity does not forbid that. It just says that every element must be related to itself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.