Number of possible relations with following restrictions | Discrete Mathematics

Question

I am new to math. stack exchange, I am really not sure how I am supposed to ask this but I need a logical explanation and a way to logical way to approach questions like these. I tried doing it myself. Thank you.

The question is as follows:

$$\text{Let } A = \{a, b, c, d, f, g, h, k, u, x, z,y\}. \\$$

$(1)$ How many relations are there on $A$ that are reflexive, symmetric, and contain all the elements $(a,z), (u,u)$ and $(z,a)$?

(2) How many relations are there on $A$ that are antisymmetric and contain all the elements $(c,c), (x,a)$ and $(b,c)$, but do not contain the element $(c,b)$?

(3) ) ) How many relations are there on A that are reflexive, antisymmetric, and contain all the elements (x,a),(a,a),(b,d), and (a,z), but do not contain any of the elements (a,x),(a,b),(d,z),(z,d) or (c,d)?

My Solution

Let $A$ = {a,b,c,d,e,f,g,h,k,w,x,y,z}.

(1) . But I can use the formulas outlined for reflective and systematic. the formula is $$2^{\frac{n^2-n}{2}}$$

since the last condition says, the relation should also include (a,z),(u,u), and (z, a). We will subtract 3 from the power of the whole expression as these elements are already contained.

(2) not sure about the other 2.

Answer 1

Well, I think it is better not representing the relation as $n^2$ directed pairs that either exist or not, but as a graph of $\frac{n\left(n-1\right)}{2}$ general edges between 2 elements that can exist in 4 states - $a{\not-}b$, $a{\Rightarrow}b$, $a{\Leftarrow}b$, $a{\iff}b$ and $n$ self-edges that either are, $a{\iff}a$ or are not, $a{\not-}a$.

With $n$ being 12 makes it 66 normal and 12 self-edges

This way you can easily encompass requirements like reflexive or symmetric by simply excluding some of the states

• reflexive relation has simply all $n$ self-edges in the $a{\iff}a$ state
• symmetric relation can have the normal edges only in 2 states, $a{\not-}b$ or $a{\iff}b$
• antisymmetric relation can have the normal edges in 3 states, $a{\not-}b$, $a{\Rightarrow}b$, $a{\Leftarrow}b$

So

• in your $(1)$ it is reflexive and symmetric thus the normal edges can exist in 2 states only and the self-edges don't contribute, so you get ${\Large2}^{\left(\frac{n\left(n-1\right)}{2} - 1\right)}$ , subtracting the 1 known edge $a{\iff}z$
• in your $(2)$ you get ${\Large3}^{\left(\frac{n\left(n-1\right)}{2} - 2\right)} {\Large*} {\Large2}^{n-1}$ subtracting 2 normal edges and 1 self-edge with known states
• in your $(3)$ we get ${\Large3}^{\left(\frac{n\left(n-1\right)}{2} - 6\right)}{\Large*} {\Large2}^2$ as we know the exact states of $a{\Rightarrow}x$, $a{\Rightarrow}z$, $b{\Rightarrow}d$ and $d{\not-}z$ but for $ab$ there are still 2 possibilities left, $a{\not-}b$ or $a{\Leftarrow}b$ and the same goes for $cd$ ( we just subtract them from the 3-s and give them back as 2-s )