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!


  • 1
    $\begingroup$ I think you mean $K\subseteq P(A\times A)$. $\endgroup$ – GPerez Dec 6 '14 at 15:35
  • $\begingroup$ You're right, fixed, thanks. $\endgroup$ – PainKiller Dec 6 '14 at 15:37
  • 1
    $\begingroup$ 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. $\endgroup$ – GPerez Dec 6 '14 at 15:39
  • $\begingroup$ Yeah fixed it right away, also the union of symmetric relations keeps all the properties. $\endgroup$ – 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.

Thansk to GPerez for leading me to an answer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.