Let A be A={1,2,3}, let K be the set of all symmetric and not reflexive relations of A. Is K $$ K=\{(\phi,\phi)\quad((\phi,\phi),(1,2),(2,1))\quad ((\phi,\phi),(1,3),(3,1))\quad ((\phi,\phi),(2,3),(3,2))\quad((\phi,\phi),(1,2),(2,1),(1,3),(3,1))\quad ((\phi,\phi),(1,2),(2,1),(2,3),(3,2))\quad ((\phi,\phi),(1,3),(3,1),(2,3),(3,2))\quad ((\phi,\phi),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2))\} $$


  • $\begingroup$ Is $K$ a group or just a set? And what is $\phi$? $\endgroup$ – 57Jimmy Feb 9 '18 at 15:39
  • $\begingroup$ @Arthur Losnikov: A relation on $A$ is a set (possibly empty) of ordered pairs of elements of $A$. But note: $\varnothing$ is not an element of $A$, so $(\varnothing,\varnothing)$ is not an ordered pair of elements of $A$, hence, it should not be in any of the relations. $\endgroup$ – quasi Feb 9 '18 at 15:42
  • $\begingroup$ ϕ is an empty set. K is a group of all possible symmetric and not reflexive relations of A. $\endgroup$ – Arthur Losnikov Feb 9 '18 at 15:43
  • $\begingroup$ The word "group" should not be used (since it has another meaning). Instead, just refer to $K$ as a set, or as a collection. $\endgroup$ – quasi Feb 9 '18 at 15:45
  • $\begingroup$ K is P(AxA) here. Is it a group or a set? $\endgroup$ – Arthur Losnikov Feb 9 '18 at 15:46

If $R$ is a relation not reflexive, we cannot have $(1,1),(2,2),(3,3) \in R$ together but for example you may have $(1,1) \in R$ and $(2,2),(3,3) \notin R$. Or $(1,1),(2,2) \in R$ and $(3,3) \notin R$. So if you want to list them systematically, answer should also include the relations:

$$K=\big\{\{(1,1)\},\{(2,2)\},\{(3,3)\},\{(1,1),(2,2)\},\{(1,1),(3,3)\},\{(2,2),(3,3)\},\{(1,1),(1,2),(2,1)\},\{(1,1),(1,3),(3,1)\},\{(1,1),(2,3),(3,2)\},... \big\}$$

and none of the elements of $K$ should not include $(\emptyset,\emptyset)$ since $\emptyset$ is not an element but a representation of empty set.


Let $K$ be the set of relations $R$ on $A$ such that $R$ is symmetric, but not reflexive.

Then $R \in K$ if and only if $R=S\cup T$, where $S$ is a proper subset of $$\{(1,1),(2,2),(3,3)\}$$ and $T$ is the union of zero or more of the three sets $$\{(1,2),(2,1)\},\{(2,3),(3,2)\},\{(3,1),(1,3)\}$$

It follows that there are $2^3-1=7$ choices for $S$, and $2^3=8$ choices for $T$, so there are $(7)(8)=56$ possibilities for $R$.

Thus, $K$ has $56$ elements.

  • $\begingroup$ What is the least element of this K set? $\endgroup$ – Arthur Losnikov Feb 9 '18 at 18:12
  • $\begingroup$ The empty set is an element of $K$, so that qualifies as a kind of "least" element. But $K$ is not a set of numbers. It's a set of sets (since relations on $A$ are subsets of $A\times A$). $\endgroup$ – quasi Feb 9 '18 at 18:15
  • $\begingroup$ To form an element of $R$ of $K$, choose any proper subset $S$ of $$\{(1,1),(2,2),(3,3)\}$$ and let $T$ be the union of zero or more of the three sets $$\{(1,2),(2,1)\},\{(2,3),(3,2)\},\{(3,1),(1,3)\}$$and then let $R=S\cup T$. $\endgroup$ – quasi Feb 9 '18 at 18:22
  • $\begingroup$ Then why the empty set is an element of K if its not there? $\endgroup$ – Arthur Losnikov Feb 9 '18 at 18:22
  • $\begingroup$ The empty set is a subset of $A\times A$. As a relation, the empty set is symmetric, but not reflexive, so it qualifies as an element of $K$. $\endgroup$ – quasi Feb 9 '18 at 18:23

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.