0

Let $A=\{1,2,\ldots,n\},n\ge1$. Find the number of all relations $R\subseteq A\times A$ which are both both symmetric and antisymmetric.

Okay, so a relation is symmetric if $(\forall a\forall b)(aRb\Rightarrow bRa)$ and a relation is antisymmetric if $(\forall a\forall b)(aRb \land bRa\Rightarrow a=b).$

Graphically, a relation is symmetric if from the existence of the black arrow we can conclude that the red arrow (relation) also exists (and vice versa). But exactly this diagram is not allowed when we have an antisymmetric relation.

enter image description here

So I am a little confused and don't know how to count them. Thanks!

SAQ
  • 367
  • 3
    If the black arrow exists, then the red arrow exists, and the beginning and the end of the arrows must be the same member of $A$. In other words, if $aRb$, then $bRa$ and $a=b$. So each $a\in A$ could only possibly be related to itself, and not anyone else. –  Feb 04 '24 at 21:54
  • You're on the right track. Remember that elements can be related to themselves. – Karl Feb 04 '24 at 21:55
  • @jwhite, okay so for $n$ elements I have just one choice, right? So $n$ such relations? $(1,1)\in R, (2,2) \in R, ...$. – SAQ Feb 04 '24 at 22:00
  • You can choose independently for each pair... – lulu Feb 04 '24 at 22:02
  • An element of the form $(1,1)$ by itself isn't a relation. A relation is a set of such elements. So, as @lulu said, $(1,1)$ may or may not be in $R$, $(2,2)$ may or may not be in $R$, etc. And whether or not $(1,1)$ is in $R$ does not impact whether or not $(2,2)$ is in $R$. –  Feb 04 '24 at 22:03
  • @lulu, well, I can't see how to find the answer then. We can have relations which consist of just one element (e.g. ${(1,1)}, {(2,2)}$), then we can have relations which consist of two elements, and so on. I don't know how to find their count. – SAQ Feb 04 '24 at 22:04
  • @jwhite, so actually $2^n$? – SAQ Feb 04 '24 at 22:07
  • @lulu, am I right now? – SAQ Feb 04 '24 at 22:18
  • Yes, $2^n$ is correct. –  Feb 04 '24 at 22:20
  • Yes! $2^n$ is right. – lulu Feb 04 '24 at 22:22

0 Answers0