# Maximum element of a Set of all symmetric, but antireflexive Relations

So yeah, I have a problem, which goes like this :

Let A = {1,2,3,4}

K is a set of all symmetric, non reflexive relations :

$K \subseteq \ P(A \times A)$.

Meaning that for all $R \subseteq \ (A \times A), R\in \ K, (x,y)\in \ R \Longrightarrow (y,x) \in \ R$ and $I_{A} \notin \ R$

$\subseteq \$ is a partially ordered set on K

Now the last question is the one that confuses me and goes like this :

3)Prove that K does NOT have a Greatest Element( or Maximum Element).

Now I'm not sure why they're asking me to prove that there is no Maximum Element, since a relation that is Union of all relations in K should be the greatest relation which is a superset of all relations in K.

Example :

$(R_{1},R_{2}) \in \ K$ symmetric and anti-reflexive.

$K = \{R_{1},R_{2},R_{1} \cup R_{2}\}$

$K_{\subseteq \ } = \{ (R_{1},R_{1}),(R_{1},\{R_{1} \cup R_{2}\}),(R_{2},\{R_{1} \cup R_{2}\}),(\{R_{1} \cup R_{2}\},\{R_{1} \cup R_{2}\})\}$

Note : Skipped empty set on purpose.

Clearly $R_{1} \cup R_{2}\$ is the Greatest Element in K, since every element in K is a subset of $R_{1} \cup R_{2}\$, and there's nothing else that $R_{1} \cup R_{2}\$ can be a subset of, other than itself, which makes it the greatest element...

Am I missing something ?

Any help is appreciated!

Thanks.

• I think you mean $K\subseteq P(A\times A)$. – GPerez Dec 6 '14 at 15:35
• You're right, fixed, thanks. – PainKiller Dec 6 '14 at 15:37
• Also the fifth line line, $R \subseteq A\times A$. To partially answer your doubts, note that the union of relations with a certain property is a new relation that may not have the same property. – GPerez Dec 6 '14 at 15:39
• Yeah fixed it right away, also the union of symmetric relations keeps all the properties. – PainKiller Dec 6 '14 at 15:40

Ok, guys, never-mind I found the solution, my mistake was that I for some weird reason, assumed that if K is anti reflexive that means {(1,1)},{(2,2)},{(3,3)},{(4,4)} are not elements of K, which is not true.

So the solution is simple, I will always get 4 maximal relations, but none of them will be great, since none of them will be susbsets of one another, in this case :

$R_{n} = \{P((1,1),(2,2),(3,3))........R_{2},R_{3},R_{4}.... \}$, whereas $(4,4) \notin P((1,1),(2,2),(3,3))\Longrightarrow (4,4) \notin R_{n}$

$R_{n-1} = \{P((1,1),(2,2),(4,4)).........R_{2},R_{3},R_{4}....\}$, whereas $(3,3) \notin P((1,1),(2,2),(4,4))\Longrightarrow (3,3) \notin R_{n-1}$

$R_{n-2} = \{ \{(1,1)\},\{(3,3)\},\{(4,4)\}.........R_{2},R_{3},R_{4}....\}$, whereas $(2,2) \notin P((1,1),(3,3),(4,4))\Longrightarrow (2,2) \notin R_{n-2}$

$R_{n-3} = \{(2,2),(3,3),(4,4).........R_{2},R_{3},R_{4}....\}$, whereas $(1,1) \notin P((2,2),(3,3),(4,4))\Longrightarrow (1,1) \notin R_{n-3}$

Which makes these sets all maximal, but since we have at least 4 maximal sets, we can't have a Greatest Set.