There is a set A with n elements. R is relation of set A.

R has 3 elements. When n ≥ 4, the symmetric closure of the R was obtained. Find a minimal and maximum value of number of R elements.

I want to figure out this question. I think I can draw a matrix to prove this, but I don't know the exact solution. Can someone give me the direction of this problem?


The minimum and maximum number of elements of $R$ is $3,$ because the problem told you that $R$ has $3$ elements.

I suspect, though, that the question has to do with how many elements are in the symmetric closure of $R,$ instead.

To figure this out, we need to ask ourselves what the symmetric closure looks like, compared to $R,$ itself.

To obtain the symmetric closure, we look at each pair $\langle x,y\rangle$ in $R,$ and add the pair $\langle y,x\rangle,$ if it isn't already an element of $R.$ Put another way, we construct the set $$S=\bigl\{\langle y,x\rangle\in A\times A:\langle x,y\rangle\in R\bigr\}.$$ The symmetric closure of $R$ is the set $R\cup S.$

Observe that $R$ and $S$ have the same number of elements. (Can you justify this?) If they have no elements in common, then the symmetric closure of $R$ must have twice as many elements as $R$ does. If they have exactly the same elements--that is, if $R$ is already symmetric--then $R\cup S=R.$ Can you see what the maximum and minimum cardinality of $R\cup S$ is from there?

It's worth noting that the number $n$ never came into play, here. In the cases $n\le 2,$ the maximum value from above will not be correct. (Can you see what it will be, instead?) However, it will hold for $n\ge 3.$ I'm not sure why the problem specifies that $n\ge 4.$

Added: You've found the correct numbers! To justify it, though, we need to be a bit more careful. After all, even if we assume that the pairs $\langle a,b\rangle, \langle c,d\rangle, \langle e,f\rangle$ are distinct, that doesn't mean that $R\cup S$ will have $6$ elements. After all, we could (for example) have $a=f,$ $b=e,$ and $c=d,$ in which case $R\cup S$ has $3$ elements.

Instead, I'd consider the set $$S\setminus R:=\bigl\{\langle x,y\rangle\in S:\langle x,y\rangle\notin R\bigr\}.$$ At that point, there are a few facts to justify:

  • $S\setminus R$ has no more than $3$ elements.

  • If $R$ is symmetric, then $S\setminus R$ has $0$ elements.

  • It is possible for $S\setminus R$ to have exactly $3$ elements. (This only works because $n\ge 3.$)

  • $R$ and $S\setminus R$ have no common elements.

  • $R\cup S = R\cup(S\setminus R)$

  • $\lvert R\cup S\rvert = \lvert R\rvert +\lvert S\setminus R\rvert.$

From there, the conclusion is immediate.

If we'd had $n=2,$ then $S\setminus R$ could not have $2$ or $3$ elements, but could have $1$. If we'd had $n\le 1,$ then $R$ couldn't have had $3$ elements, in the first place. See if you can justify these claims, along with those above.

Please let me know if you get stuck, or if you just want to have me check your reasoning. Welcome to the site!

| cite | improve this answer | |
  • $\begingroup$ I also think why do we have n≥4. But in this problem, it just give that condition. // However why do you think the minimal and maximal number are 3? When I solve this problem, I think minimal number is 3. If all 3 elements are reflexive(like (a,a), (b,b), (c,c)), we don't have to add any elements. Symmetric means, when (a,b) exists, (b,a) exists, too. // I think maximal number is 6. If (a,b), (c,d), (e,f) exist, we have to add (b,a),(d,c),(f,e). // So I think minimal number is 3 and maximal number is 6. Is this something wrong? If I have an error, please tell me. Thanks. $\endgroup$ – july May 24 at 15:13
  • $\begingroup$ You're correct! The set $R\cup S$ has at least $3$ elements, and at most $6$ elements. You haven't quite justified the maximum, though. I will edit my answer accordingly. $\endgroup$ – Cameron Buie May 24 at 15:34
  • $\begingroup$ Thank you for your answering! I checked it. $\endgroup$ – july May 25 at 11:28

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.