Cardinality of different properties of binary relations

195 Views Asked by At

English isn't my first language, so I tried to translate it as best as I could.

$A$ and $B$ are finite sets. In dependence of $|A|$ and $|B|$ give the number of relations of $R \subset A \times B$ with the following properties:

a) R is right-unique

b)R is right-unique but not left-total

c)R is left-total or not right-unique.

Hint: The number of functions from $A$ to $B$ is $|B^A| = |B|^{|A|}$


My Answer:

a)Right-unique: $\forall a\in A$ $\forall b\in B$ $\forall c\in B$: $(a,b)\in R \land (a,c)\in R \Rightarrow b=c$

That means every $a\in A$ can have at most one partner in $B$ ("One or less").

So the number of relations should be $|B^A| \leq |A|$

b)Right-unique: $\forall a\in A$ $\forall b\in B$ $\forall c\in B$: $(a,b)\in R \land (a,c)\in R \Rightarrow b=c$

And not left-total:$\lnot(\forall a\in A$ $\exists b\in B: (a,b) \in R) \Leftrightarrow \exists a\in A$ $\forall b\in B: (a,b) \notin R$

Right-unique: every $a\in A$ can have at most one partner in $B$.

not left-total: There exists at least one $a\in A$ for all $b \in B$ so that $(a,b)\notin R$ (so that there is no relation).

$|B^A| \lt |A|$, it can't be $|A|$ since there exists at least one $a \in A$ so that the relation doesn't work

c)left-total: $\forall a\in A$ $\exists b\in B: (a,b) \in R$

not right-unique: $\lnot[\forall a\in A$ $\forall b,c\in B$ : $(a,b)\in R \land (a,c)\in R \Rightarrow b=c]$

$\Longleftrightarrow $$\exists a\in A$$\exists b\in B$ $\exists c\in B$: $\lnot((a,b)\in R \land (a,c)\in R \Rightarrow b=c)$

$\Longleftrightarrow $$\exists a\in A$$\exists b\in B$ $\exists c\in B$: $(a,b)\in R \land (a,c)\in R \Rightarrow b \neq c)$

left-total: every $a\in A$ has at least one partner in B

not right-unique: There exists at least one $a\in A$, at least one $b \in B$ and at least one $c \in B$ so that $(a,b)\in R \land (a,c)\in R$ so that $b \neq c$.

That means there is at least one $a \in A$ that has at least two partners in $B$.

There have to be more relations then there are elements in $A$.

If it was only left-total then $|B^A| \geq |A|$

But since it's left-total or not right-unique:

$|B^A| \gt |A|$

Is my answer correct? Because I didn't use the cardinality of B at all.

1

There are 1 best solutions below

6
On BEST ANSWER

In the case of (a), right-uniqueness does not guarantee the domain of $R$ is $A$. In fact, the domain could be empty. However, if the domain of $R$ is known, say it $X$, then $R$ must be a function between $X$ and $B$. Furthermore, any function from $X\subseteq A$ to $B$ is right-unique. Therefore the number of right-unique relations is $$\sum_{X\subseteq A}|B|^{|X|} = \sum_{k=0}^{|A|} \binom{|A|}{k} |B|^k.$$

For (b), observe that right-unique, left-total relations are exactly functions from $A$ to $B$. Therefore we can count relations satisfying (b) by subtracting $|B|^{|A|}$ from the result in (a).

(c) is the mere negation of (b), and the total number of relations is $2^{|A||B|}$. Could you see how to get an answer?