2
$\begingroup$

If $X$ is a set and $n \in \mathbb N$, then $[X]^n$ will denote the set of all subsets of $X$ with exactly $n$ elements.

For a set $X$ and natural numbers $n$ and $m$ define a relation $R$ on $[X]^n$ and $[X]^m$ by $R(A,B)$ holds if and only $A \cap B = \emptyset$.

Is $R$ transitive if $n = m$? Need an example or proof

1 Answers 1

2

No. Take $X = \{1,2\}$ and $n = m = 1$, $A = C = \{1\}$ and $B = \{2\}$. Then $R(A,B)$ and $R(B,C)$ but not $R(A,C)$.

  • 0
    @Brian: Yes, if |X| < 2n then there exist no $A,B$ with $R(A,B)$ so by definition the relation is transitive. If $|X| \geq 2n$, then you can always take $A = C \subseteq X \setminus B$ to get a contradiction.2011-09-16