Welcome to our community

Be a part of something great, join today!

[SOLVED] Give a set and a relation that satisfies the properties

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,028
Hey!! :eek:

I am looking at the following:

There are the terms reflexive, symmetric, antisymmetric and transitive.
Give for each combination of the properties (if possible) a set $M$ and a relation $R$ on $M$, such that $R$ satisfies these properties.


What is meant exactly? Every possible combination? So do we have to give a set and a relation that satisfies the below properties?
  • reflexive, symmetric
  • reflexive, antisymmetric
  • reflexive, transitive
  • symmetric, antisymmetric
  • symmetric, transitive
  • antisymmetric, transitive
  • reflexive, symmetric, antisymmetric
  • reflexive, symmetric, transitive
  • reflexive, antisymmetric, transitive
  • symmetric, antisymmetric, transitive
  • reflexive, symmetric, antisymmetric transitive

(Wondering)
 

HallsofIvy

Well-known member
MHB Math Helper
Jan 29, 2012
1,151
Well, you have four properties so 4!= 24 possible "combinations" (25 if you include the "empty combination"- that none of those properties are true).

I think you should give special consideration to two of those properties. What must be true of a set so that it will be both "symmetric" and "anti-symmetric"?
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,028
Well, you have four properties so 4!= 24 possible "combinations" (25 if you include the "empty combination"- that none of those properties are true).
Since the order of the properties doesn't matter do we not have $\binom{4}{2}+\binom{4}{3}+\binom{4}{4}=11$ combinations?


I think you should give special consideration to two of those properties. What must be true of a set so that it will be both "symmetric" and "anti-symmetric"?
A relation R is symmetric if it holds $aRb \iff bRa$ for $a,b\in M$.
A relation R is ant-symmetric if it holds $aRb$ then it doesn't hold that $bRa$ for $a\neq b\in M$.

So this combination is not possible, right? (Wondering)
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,489
Well, you have four properties so 4!= 24 possible "combinations" (25 if you include the "empty combination"- that none of those properties are true).
I believe there are $2^4=16$ possible combinations of 4 properties.

A relation R is symmetric if it holds $aRb \iff bRa$ for $a,b\in M$.
A relation R is ant-symmetric if it holds $aRb$ then it doesn't hold that $bRa$ for $a\neq b\in M$.

So this combination is not possible, right?
It is possible.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,028
It is possible.
Ah yes! For the empty set, right?

So do we have the following?

We consider the set $M=\{0,1,2\}$.

  • reflexive, symmetric : $R=\{(0,0), (1,1), (2,2), (0,1), (1,0)\}$.
  • reflexive, anti-symmetric : $R=\{(0,0), (1,1), (2,2), (0,1)\}$.
  • reflexive, transitive : $R=\{(0,0), (1,1), (2,2), (0,1), (1,2), (0,2)\}$.
  • symmetric, anti-symmetric : $R=\emptyset$.
  • symmetric, transitive : $R=\{(0,0), (0,1), (1,0)\}$.
  • anti-symmetric, transitive : $R=\{(0,0), (1,1), (0,1)\}$.
  • reflexive, symmetric, anti-symmetric : $R=\emptyset$.
  • reflexive, symmetric, transitive : $R=\{(0,0), (1,1), (2,2), (0,1), (1,0), (1,2),(2,1),(0,2), (2,0)\}$.
  • reflexive, anti-symmetric, transitive : $R=\{(0,0), (1,1), (2,2), (0,1), (1,2),(0,2), (2,1)\}$.
  • symmetric, anti-symmetric, transitive : $R=\emptyset$.
  • reflexive, symmetric, anti-symmetric, transitive : $R=\emptyset$.

(Wondering)
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,489
For the empty set, right?
No, for any subset of the diagonal relation $\Delta=\{(x,x)\mid x\in M\}$.

I don't have time now to check all your answers, but as I said, there are 16 combinations, and they should be enumerated in a systematic way that makes it easy to see that nothing is missing. In your enumeration the first item "reflexive, symmetric" does not mean "reflexive, symmetric, not antisymmetric and not transitive" because this relation is transitive.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,028
No, for any subset of the diagonal relation $\Delta=\{(x,x)\mid x\in M\}$.

I don't have time now to check all your answers, but as I said, there are 16 combinations, and they should be enumerated in a systematic way that makes it easy to see that nothing is missing. In your enumeration the first item "reflexive, symmetric" does not mean "reflexive, symmetric, not antisymmetric and not transitive" because this relation is transitive.
So a relation that is symmetric, anti-symmetric and transitiveis is every relation in the form $\{(x,x)\mid x\in M\}$, right? But the empty set satisfies also these properties, or not? (Wondering)
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,489
So a relation that is symmetric, anti-symmetric and transitiveis is every relation in the form $\{(x,x)\mid x\in M\}$, right?
$\{(x,x)\mid x\in M\}$ is a fixed set. You would not say, "Any number of the form 5", right? But yes, a relation is both symmetric and antisymmetric iff it is a subset of the diagonal relation $\Delta=\{(x,x)\mid x\in M\}$. The empty relation is also a subset of $\Delta$ and is symmetric and antisymmetric.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,028
$\{(x,x)\mid x\in M\}$ is a fixed set. You would not say, "Any number of the form 5", right? But yes, a relation is both symmetric and antisymmetric iff it is a subset of the diagonal relation $\Delta=\{(x,x)\mid x\in M\}$. The empty relation is also a subset of $\Delta$ and is symmetric and antisymmetric.
Ah ok!

So $\Delta$ is symmetric and antisymmetric and so also transitive, right? (Wondering)
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,489
Yes, every subset of $\Delta$, including $\Delta$ itself, is transitive.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,028