How can relations on three-element set have seven elements?

[Eclair_de_XII]

Homework Statement

"Determine the max number of elements in a three-element set that is not reflexive, symmetric, or transitive?"

Homework Equations

$a R b⇔(a,b)∈R$

The Attempt at a Solution

Basically, my professor has stated that there are a total number of seven possible elements in a relation on a three element set that is not reflexive, symmetric, or transitive.

I began again by listing all possible relations of a three element set: $A=${$x,y,z,$}. Let $R$ be a relation on $A$. Then $R=${$(x,x),(x,y),(x,z),(y,x),(y,y),(y,z),(z,x),(z,y),(z,z)$}. There are nine elements in $R$ and by eliminating {$(x,x),(y,y),(z,z)$}, I already have fewer than the maximum number of elements in an $R$ that is not reflexive, symmetric, or transitive. And you kind of must nix those three elements for those three properties, anyway. I feel like I'm missing something... Can anyone point out what it is? Thanks.

 

[fresh_42]

I assume the trick is behind the formulation "not or". What is "not (A or B or C)" and what "not A or not B or not C"? Which one is probably meant?

 

[Eclair_de_XII]

I don't know; I feel like that for all three properties, you would have to remove $(x,x),(y,y),$ and $(z,z)$. Reflexive is already out. To make it not symmetric, I would still have to deal with the fact that $(x,x)$ implies that its reciprocal (itself) is in the set. Similarly, I would have problems with eliminating the transitive property from my set. If $aRa$ and $aRa$, then $aRa$.

I mean, I could just say that $R$ is not reflexive, and add in the null-set...

 

[fresh_42]

My interpretation of the question with regard to seven as the answer and a maximum requirement is: "not reflexive or not symmetric or not transitive". An and between them would simply rule out too many relations, as you already observed.

 

[Eclair_de_XII]

So for the symmetric and transitive properties, does the statement that $a$ R $b$ implies $b$ R $a$ apply when $a=b$, or no?

 

[fresh_42]

What is $a=b$? You named your elements $x,y,z$ and the relation $R$. So $aRb \Rightarrow bRa$ for all $a,b \in A$ means $R$ is symmetric. $a=b$ isn't defined anywhere, since it is another relation.

 

[Eclair_de_XII]

I guess my question is... can $x$ be symmetric or transitive with itself?

 

[fresh_42]

I guess my question is... can $x$ be symmetric or transitive with itself?

$xRx$ is a possibility and if also $yRy$ and $zRz$ then $R$ is reflexive. It makes no sense to speak of symmetry, if you only compare it with itself, or transitive, for which you also need at least two elements.

 

[Eclair_de_XII]

I got it; they must be distinct elements of the set the relation is on.

 

[Eclair_de_XII]

Okay, I ended up nixing $(x,y)$ and $(y,x)$ from the set to yield $S=${$(x,x),(x,z),(y,y),(y,z),(z,x),(z,y),(z,z)$}.

 

[PeroK]

Okay, I ended up nixing $(x,y)$ and $(y,x)$ from the set to yield $S=${$(x,x),(x,z),(y,y),(y,z),(z,x),(z,y),(z,z)$}.

That is reflexive.

 

[nuuskur]

How is one supposed to determine the maximum number of elements of a set whose number of elements is fixed? If you are supposed to construct a so called "maximal relation" that is not reflexive, you merely have to omit one pair $(x,x)$ or $(y,y)$ or $(z,z)$ and the maximum number can therefore be?

 

[Eclair_de_XII]

I mean, I was trying to make it not transitive. But making it not reflexive works even better.

 

[PeroK]

I mean, I was trying to make it not transitive. But making it not reflexive works even better.

The task, it seems to me, is to make it not reflexive, not transitive and not symmetric.

 

[nuuskur]

If you begin with a, let's call it complete, relation on a three element set i.e one whose relation matrix is
<br /> \begin{array}{ccc}1&amp;1&amp;1\\1&amp;1&amp;1\\1&amp;1&amp;1\end{array}<br />
By omitting, say $(x,x)$ you will have given up reflexivity, but also relinquished transitivity (why?). All that is left now is to give up symmetry. Therefore, indeed, desired relation can, at most, contain seven elements.

 

[Eclair_de_XII]

Oh, right. Because in order for a relation $R$ to be reflexive on a set $A$, $s$ R $s$ must apply for all $s∈A$. Since eliminating $(x,x)$ would make it so that there exists one element that does not relate to itself, $R$\$(x,x)$ would not be reflexive. Additionally, could you not just remove $(x,y)$ and make it so that $R$ is not symmetric?

 

[nuuskur]

Oh, right. Because in order for a relation $R$ to be reflexive on a set $A$, $s$ R $s$ must apply for all $s∈A$. Since eliminating $(x,x)$ would make it so that there exists one element that does not relate to itself, $R\(x,x)$ would not be reflexive. Additionally, could you not just remove $(x,y)$ and make it so that $R$ is not symmetric?

Almost, but in this case, when you give up reflexivity, you also give up transitivity. Why is that so? You cannot throw away $(x, t)$ or $(t,x), t\in\{y,z\}$, though. If you eliminate $(x,x)$, then you must additionally eliminate $(y,z)$ or $(z,y)$, but why?

 

[Eclair_de_XII]

I'm guessing that since $x$ R $x$ is no longer in $R$, there is no relation $x$ R $x$ to transition $(x,x)$ to $(x,y)$ or $(x,z)$.

And why is the max number of elements seven when I have eliminated only one element from my nine-element relation?

 

[nuuskur]

It is seven, because you cannot kill all three birds with one stone i.e, if you give up any diagonal pair $(a,a)$, you can't omit symmetry with it. Therefore, it's also necessary to remove another pair.

Can you state precisely why giving up $(x,x)$ removes transitivity property? A relation on the set $S$, $R\subseteq S\times S$, is transitive if for all $a,b,c\in S,\ aRb$ and $bRc\Longrightarrow aRc$. By removing $(x,x)$, how is this implication violated?

 

[Eclair_de_XII]

Can you state precisely why giving up $(x,x)$ removes transitivity property?

It removes the transition from $x$ to itself, then to $y$ or $z$?

 

[nuuskur]

Indeed, which also explains why, when you remove $(x,x)$, you cannot remove $(x,y), (x,z), (y,x)$ or $(z,x)$. If you did, then you give up symmetry, yes, but not transitivity.

 

[Eclair_de_XII]

Even if I removed either $(y,z)$ or $(z,y)$, there would still be $(z,x)$ and $(y,x)$ to transition into $(y,x)$ and $(z,x)$ respectively, though.

I'm guessing that even if that were so, there would be no $(x,x)$ for $(y,x)$ to transition from $(x,z)$ to $(y,z)$?

 

[nuuskur]

Your expression is incredibly ambiguous to me, which is why I asked you to state precisely the reason that so and so.

When you remove, say, $(x,x)$ and nothing else, you omit reflexivity and transitivity. The reason for that is, because $xRy \mbox{ and } yRx$, but there is no $xRx$. Now, if you removed, say, $(x,y)$, you merely exchange symmetry for transitivity. You don't want that.
Remove, say, $(y,z)$, instead. You still have $zRy$, but no $yRz$, therefore symmetry is gone.

 

[Eclair_de_XII]

The reason for that is, because $xRy$ $\mbox{ and } yRx$ , but there is no $xRx$.

Oh, so that's why the transitive property is removed... So why does removing $(x,y)$ reintroduce transitivity into $R$? Is it something to do with vacuous truth? Like, the transitive property states that if $xRy$, and $yRx$, then $xRx$. If there is no $(x,y)$, then that would make the statement that $R$ is transitive vacuously true, I think?

 

[nuuskur]

Oh snap, you are right. It doesn't, that's a mistake on my part. Removing ANY non diagonal pair will remove symmetry and problem is solved.

There still is $xRz, zRx$, but no $xRx$. For some reason, I forgot about it