1
$\begingroup$

I'm sure this is a super simple question but I'm a bit stuck on how exactly I'm supposed to solve this. I have a feeling this might be a counting related question but I'm not sure. If anyone could just help me with (a) I think I might be able to chug through the rest.

Let $A = \left\{ 1, 2, 3, 4, 5, 6, 7, 8 \right\} $. Determine the number of relations on $A$ that are:

(a) Reflexive and symmetric

(b) Symmetric and contain (1, 2)

(c) Antisymmetric

(d) Symmetric and antisymmetric

$\endgroup$
1
$\begingroup$

hint

Any relation on a finite set $A$ to itself can be represented as a square matrix of size $|A|$. With the idea that if element $a_i$ is related to element $a_j$ then the $ij-$th entry is $1$ otherwise it will be zero.

With this, for reflexivity you need all the diagonal elements $ii-$elements to be $1$. So out of $8^2=64$ entries the fate of these $8$ is already decided.

For symmetric relation, the matrix should be symmetric, i.e the $ij$ entry should be same as $ji$ entry. So essentially you can only play with $(64-8)/2=28$ Off diagonal entries of the matrix. Each of those can be either $0$ or $1$. So there are $2^{28}$ such matrices possible, hence that many reflexive and symmetric relations.

$\endgroup$

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.