Let $A$ be a set with $n$ elements

540 Views Asked by At

How many reflexive relations are there on $A$?

How many symmetric, reflexive relations are there on $A$?

How many equivalence relations are there on $A$, if $n=5$?

How are you supposed to find how many of something there are when you don't know what the relation is?

3

There are 3 best solutions below

0
On BEST ANSWER

You know that if a set $A$ has $n$ elements, then it has $\binom{n}3$ subsets of cardinality $3$, even though you cannot name those subsets. It’s the same thing here: for the first question, for instance, we simply want to count the subsets of $A\times A$ that are reflexive relations. Suppose that $R\subseteq A\times A$ is reflexive; that means that $\langle x,x\rangle\in R$ for every $x\in A$. In other words, there are only two requirements for a set $R$ to be a reflexive relation on $A$:

  • $R\subseteq A\times A$ (so that $R$ is a relation on $A$), and
  • $R\supseteq\{\langle x,x\rangle:x\in A\}$ (so that $R$ is reflexive).

Since $A$ has $n$ elements, $|A\times A|=n^2$. That’s a total of $n^2$ ordered pairs, each of which might or might not belong to any given relation on $A$. If the relation is reflexive, however, the $n$ pairs of the form $\langle x,x\rangle$ must all belong to $R$; that leaves $n^2-n$ ordered pairs that may but need not belong to a reflexive relation on $A$. To build a reflexive relation on $A$ you must include all of the pairs $\langle x,x\rangle$ with $x\in A$, but for each of the remaining $n^2-n$ ordered pairs you can say yes, you’re in my relation or no, you’re not in my relation. That’s $n^2-n$ independent two-way choices, so you can make them in a total of $2^{n^2-n}$ different ways.

Equivalently, there are $n^2-n$ ordered pairs $\langle x,y\rangle$ with $x\ne y$, and you can include any subset of them in your reflexive relation (along with all of the $\langle x,x\rangle$ pairs). A set of $n^2-n$ elements has $2^{n^2-n}$ subsets, so there are $2^{n^2-n}$ ways to fill out the optional part of your reflexive relation. Either approach leads to the correct result: there are $2^{n^2-n}$ different reflexive relations on $A$.

For the second part of the question you need to determine how many of those $2^{n^2-n}$ reflexive relations are also symmetric. HINT: If $x,y\in A$ with $x\ne y$, a symmetric relation must either include both of the pairs $\langle x,y\rangle$ and $\langle y,x\rangle$, or neither of them. You get only one choice for the pair.

For the last part of the question I would start with the relatively small number of reflexive, symmetric relations on a set of cardinality $5$ and investigate which of them are transitive.

0
On

A reflexive relation is one such that $(x,x) \in R$, for all $x \in A$, where $R$ is the relation. Once the $(x,x)$ must be chosen, you have $n^2 - n$ (minus the diagonal) more possible relations to include, so there are $2^{n^2 - n}$ reflexive relations on a set of size $n$.

A symmetric and reflexive relation is one such that all $(x,x) \in R$ and $(x,y) \in R \implies (y,x) \in R$. So when choosing the remaining elements in a reflexive set we can only pick up to $\frac{n^2 - n}{2}$, since the corresponding symmetric elements are automaticallly chosen each time, so it's a choice of whether ore not each $\{(x,y), (y,x)\}$ is included in the set, and there are precisely $\frac{n^2 - n}{2}$ of those. Thus, there are exactly $$ 2^{\dfrac{n^2 - n}{2}} $$ symmetric reflexive relations on a set of size $n$.

The equivalence relations correspond bijectively with the partitions of $A$, so count how many ways there are to partition a set of size $n$.

0
On

Hint for equivalence relations on $A$: they have a one-to-one correspondence with partitions of $A$. How many partitions can you find when $n=5$?