Describing relations

Question

(a). Describe all relations $R$ on $A$ which are simultaneously symmetric and antisymmetric.

(b). Describe all relations $R$ on $A$ which are reflexive, symmetric, and antisymmetric.

I have no idea what this even means. I know what symmetric, antisymmetric, reflexive and simultaneous means but I don't know what it means for how general this question this.

Thanks for the help!

Huh? Neither (a) nor (b) uses the word "spaces." So I have no idea what you even mean! Do you know what all of the words mean, first of all (relations, simultaneously, symmetric, antisymmetric, reflexive)? — anon, Nov 13 '13 at 04:37
@TheChaz2.0 OP is probably feeling the same way. $A$ is just a generic, unspecified set. — anon, Nov 13 '13 at 04:58

score 1 · Accepted Answer · answered Nov 13 '13 at 13:16

1

HINT: Suppose that $R$ is a symmetric relation on $A$; then whenever $\langle x,y\rangle\in R$, we also have $\langle y,x\rangle\in R$. Informally, for any $x,y\in A$, either both $\langle x,y\rangle$ and $\langle y,x\rangle$ are in $R$, or neither is in $R$: $R$ cannot contain just one of the two.

Now suppose that $R$ is an antisymmetric relation on $A$; then whenever $R$ contains both $\langle x,y\rangle$ and $\langle y,x\rangle$, it turns out that $x=y$. In other words, if $x,y\in A$ and $x\ne y$, then $R$ cannot contain both $\langle x,y\rangle$ and $\langle y,x\rangle$.

Finally, suppose that $R$ is both symmetric and antisymmetric. If $x,y\in A$ and $x\ne y$, then $R$ cannot contain both $\langle x,y\rangle$ and $\langle y,x\rangle$, because $R$ is antisymmetric; and because $R$ is symmetric, it must contain either both of them or neither of them. So $R$ must contain ... ?

Note that this says nothing about whether $R$ contains pairs like $\langle x,x\rangle$; those are considered in the second part of the question.

answered Nov 13 '13 at 13:16

Brian M. Scott

616,228

"So $R$ must contain...": neither of them? – mharris7190 Nov 13 '13 at 16:46
@mharris7190: Yes, exactly so. – Brian M. Scott Nov 13 '13 at 16:46
Thanks for the help. But isn't the set of integers $\mathbb{Z}$ both symmetric and antisymmetric? Could you help me with part b? – mharris7190 Nov 13 '13 at 16:47
@mharris7190: Symmetry and antisymmetry are properties of relations, and $\Bbb Z$ is not a relation. // From (a) you know that the symmetric, antisymmetric relations on $A$ are those that contain only ordered pairs of the type $\langle x,x\rangle$. If in additon you require the relation to be reflexive, you can say exactly which ordered pairs are in it. They are ... ? – Brian M. Scott Nov 13 '13 at 16:50
They are the ordered pairs of equalities? ${(x,x), (y,y), (z,z), \text{etc...??}}$ – mharris7190 Nov 13 '13 at 16:53
@mharris7190: Yes, and if $R$ is reflexive, you have to have all of them. On the other hand, (a) tells you that you can’t have anything else. Thus, the only reflexive, symmetric, antisymmetric relation on $A$ is ... ? – Brian M. Scott Nov 13 '13 at 16:55
Im lost is it $R = {(x,x) \in \mathbb{R} \times \mathbb{R} \mid x \in \mathbb{R}}$? That's what I got from your explanation that it must contain "all of them". Sorry, relations are just hard for me to understand. – mharris7190 Nov 13 '13 at 16:58
@mharris7190: Yes, if the underlying set is $\Bbb R$. However, it appears from your question that the underlying set is some unspecified set $A$, in which case $$R={\langle x,x\rangle:x\in A};.$$ In other words, it’s the relation of equality on the set $A$, and that’s the only reflexive, symmetric, antisymmetric relation on $A$. The relations on $A$ that are symmetric and antisymmetric are the ones that are subsets of this equality relation. – Brian M. Scott Nov 13 '13 at 17:00

score 0 · Answer 2 · answered Nov 13 '13 at 13:47

The second question is actually simpler to answer, so let's start by it.

(b). If $x R y$, then $yRx$ by symmetry. But antisymmetry means that $x=y$. Conversely, if $x=y$, then $xRy$ since $R$ is reflexive. Thus, we proved that $xRy\ \Leftrightarrow x=y$, i.e. $R$ is the equality. To sum up, there is exacyly one symmetric, antisymmetric, reflexive relation on $A$, the equality.

(a) Similarly, if $xRy$, then $x=y$, but the converse is false, since $R$ is not assumed to be reflexive. Then $R$ is completely determined by the subset $B$ of $A$ of elements $x$ such that $xRx$.

Alternative ways of saying this is: the set of all symmetric and antisymmetric relations on $A$ is in bijection with the power set $\mathcal{P}(A)$. Or, since a relation is just a subset of $A\times A$, a relation $R$ is symmetric and antisymmetric if and only if it is included in the diagonal $\Delta=\{ (x,x)\ |\ x\in A \}$.

Describing relations

2 Answers2