1
$\begingroup$

It looks like for all "nice" sets, the set $S\times S$ will have symmetry and reflexivity by default. The tough part is usually showing transitivity. However, are there any non-empty sets such that $S\times S$ is not symmetric and reflexive?

$\endgroup$
  • 1
    $\begingroup$ What exactly is the equivalence relation you're working with here? $\endgroup$ – Alfred Yerger May 7 '15 at 4:31
  • 3
    $\begingroup$ The set $S\times S$ is always an equivalence relation, and is reflexive, symmetric, and transitive: it is the relation that says that every element of $S$ is related to every element of $S$. Perhaps you meant something else? Some subset of $S\times S$ perhaps? $\endgroup$ – MJD May 7 '15 at 4:31
  • $\begingroup$ If you take $S \times S $ to be the (equivalence) relation then it will always be trivially reflexive, symmetric and transitive for any set $S$. It is only when you take a non-trivial relation that this might not happen. $\endgroup$ – Rogelio Molina May 7 '15 at 4:32
  • $\begingroup$ @MJD I am afraid you answered my question. $\endgroup$ – SalmonKiller May 7 '15 at 4:32
  • $\begingroup$ I'm glad I could help! $\endgroup$ – MJD May 7 '15 at 4:32
2
$\begingroup$

The set $S\times S$ is always an equivalence relation, and is reflexive, symmetric, and transitive: it is the relation that says that every element of $S$ is related to every element of $S$.


To answer your question from the comments, suppose we have some set $S$, and we have a relation on $S$, say $\sim$. We want to represent $\sim$ as a subset $R_\sim\subset S\times S$, and your question is which subset $R_\sim$ corresponds to the relation $\sim$. The correspondence is very straightforward: We have $a \sim b$ if and only if $\langle a,b\rangle \in R_\sim$.

For example, let $R_\le$ be the subset of $\Bbb Z\times \Bbb Z$ that represents the $\le$ relation. Then $\langle 1,2\rangle$ and $\langle 1,17\rangle$ and $\langle 9,9\rangle$ are elements of $R_\le$, because $1\le2$ and $1\le 17$ and $9\le 9$, but $\langle 3,1\rangle$ is not because $3\not\le 1$.


When $R = S\times S$, we have that $\langle a,b\rangle\in R$ for all $a$ and $b$, and so the relation represented by this $R$ has $a\sim b$ for all $a$ and $b$—that is, $a$ and $b$ are always related. It should be easy to prove that this relation is reflexive, symmetric, and transitive. Similarly, when $R = \emptyset$, we get the relation where $a$ and $b$ are never related, which is symmetric and transitive, but not reflexive.

$\endgroup$
  • $\begingroup$ So when I see $b \in X, a \sim b$, I should be thinking what? Because I understand that $\sim$ is a set, but what does it mean for $a$ and $b$ to be related in that way? $\endgroup$ – SalmonKiller May 7 '15 at 4:35
  • $\begingroup$ @SalmonKiller That needs some context. The point here is that certain subsets of $S \times S$ may fail reflexivity and symmetry. $\endgroup$ – Dustan Levenstein May 7 '15 at 4:37
  • $\begingroup$ @DustanLevenstein The context is equivalence classes. They are defined as $\lbrace x \in X; a\sim x \rbrace$ $\endgroup$ – SalmonKiller May 7 '15 at 4:38
  • $\begingroup$ That's the definition of the equivalence class containing $a$ (assuming an equivalence relation on $X$). The equivalence classes partition $X$, meaning that $X$ is the disjoint union of those equivalence classes. $\endgroup$ – Dustan Levenstein May 7 '15 at 4:41
  • $\begingroup$ Can you clarify what it means for a Cartesian product to be an equivalence relation? I don't understand. Edit: Now I see it. Thanks. I've never seen this notation before! $\endgroup$ – Alfred Yerger May 7 '15 at 4:42

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.