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

1. Apr 13, 2017

### Eclair_de_XII

1. The problem statement, all variables and given/known data
"Determine the max number of elements in a three-element set that is not reflexive, symmetric, or transitive?"

2. Relevant equations
$a R b⇔(a,b)∈R$

3. 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.

2. Apr 13, 2017

### Staff: Mentor

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?

3. Apr 13, 2017

### 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...

Last edited: Apr 13, 2017
4. Apr 13, 2017

### Staff: Mentor

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.

5. Apr 13, 2017

### 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?

6. Apr 13, 2017

### Staff: Mentor

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.

7. Apr 13, 2017

### Eclair_de_XII

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

8. Apr 13, 2017

### Staff: Mentor

$xRx$ is a possibilty 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.

9. Apr 13, 2017

### Eclair_de_XII

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

10. Apr 14, 2017

### 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)$}.

11. Apr 14, 2017

### PeroK

That is reflexive.

12. Apr 14, 2017

### 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?

13. Apr 14, 2017

### Eclair_de_XII

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

14. Apr 14, 2017

### PeroK

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

15. Apr 14, 2017

### nuuskur

If you begin with a, let's call it complete, relation on a three element set i.e one whose relation matrix is
$$\begin{array}{ccc}1&1&1\\1&1&1\\1&1&1\end{array}$$
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.

16. Apr 14, 2017

### 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?

17. Apr 14, 2017

### nuuskur

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?

18. Apr 14, 2017

### 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?

19. Apr 14, 2017

### 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?

20. Apr 14, 2017

### Eclair_de_XII

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