For each of the following, state whether the relation is reflexive, symmetric, antisymmetric, transitive or an equivalence:
(i) R = { (a, a), (b, c), (c, b), (d, d) }
My answer:
It is not Reflexive.
It Symmetric.
[Anti-symmetric or not Anti-symmetric?]
Is not Transitive.
My lecturer gave me this formula where it shows,
Anti-Symmetric: (a, b) & (b, a), a=b
Not Anti-Symmetric: (a, b), (b, a), a≠b
I still do not know how to tell between these two.
On
Geometrically the idea behind symmetry is that there is an axis (at least one) which you could fold the object you're looking at along and everything on one side of the axis would match everything on the other side of the axis (think of a square with a line drawn from one corner to the opposite corner: if you fold along that line then the edges of the square on one side match up to the edges on the other side).
Anti-symmetry is the idea that there is no such matching at all -- there is nothing on one side of any axis that matches up to something on the other.
In terms of relations then, anti-symmetry means that if $aRb$, i.e. $a$ relates to $b$ in some way, then $bRa$ cannot be true unless $a=b$. Because if $aRb$ and $bRa$ then we have a matching, and anti-symmetry says there are no matchings.
It's a bit easier to see with a concrete example: let our relation $R$ be $\subseteq$. Given two sets $A$ and $B$, we see that if $A\subseteq B$ and $B \subseteq A$ then $A=B$. So being a subset of another set is anti-symmetric -- two sets can't be subsets of each other (which would be symmetry) unless they're the same set.
On
My lecturer gave me this formula where it shows,
Anti-Symmetric: (a, b) & (b, a), a=b
Not Anti-Symmetric: (a, b), (b, a), a≠b
Surely they did not. That is missing important details.
(Also, to avoid confusion, don't use the same terms as the actual elements of a set.)
Anti-Symmetry means: $\forall x~\forall y~(\langle x,y\rangle{\in} R\land\langle y,x\rangle{\in}R \to x=y)$
Not Anti-Symmetry means: $\exists x~\exists y~(\langle x,y\rangle{\in} R\land\langle y,x\rangle{\in}R \wedge x\neq y)$
The issue with telling if a relation is antisymmetric or not is that you're usually not looking at the relation as a subset of a set's product with itself. You're usually given a slightly more abstract formulation of the relation.
A relation $R$ would be anti-symmetric if, whenever $(a,b)$ and $(b,a)$ are in $R$, we have $a=b$.
In your proposed relation, the $(a,a),(d,d)$ pairings satisfy this trivially, but what about $(b,c)$ and $(c,b)$? It depends. Can we assume $b \ne c$? If so, it's not antisymmetric. Is there no reason to assume we cannot have $b=c$? If $b=c$, then it is symmetric.
However, if $b=c$, then we'd effectively have a repeat ordered pair in the set since $(b,c)=(c,b)$, which we usually don't like unless we're working with multi-sets or whatever. Plus why even state the problem like this because this is clearly ambiguous as heck.
Anecdotally, this would also mean the relation is reflexive and transitive if $b=c$.
So, to conclude a slightly long diatribe, my gut instinct is that $a,b,c,d$ are meant to be distinct, and thus $R$ is not anti-symmetric outright since $x = y$ (where $x,y \in \{a,b,c,d\}$) is never satisfied. But it's ambiguous and depends on the assumptions you're allowed to make.
A nice example to make a point out of what I meant by anti-symmetric being a more typical concern in more abstract formulations of relations: we say $a \mid b$ if and only if $a$ divides $b$. You can easily show from definition this is antisymmetric as a relation on the integers.
Suppose $a \mid b$ and $b \mid a$. Then $b = na$ and $a = mb$ for some integers $m,n$. But then that means $b=nmb$ or $a=mna$ by substitution of one into the other, so it has to hold that $m=n=1$. But then $b=a$.