# Discrete math(relations)

Let $\mathscr R$ be binary relation be defined on $P(\mathbb N)$ ($\mathbb N$ is the set of naturals) by

$A\mathscr RB$ if and only if $$|A \cap B |\le2.$$ Is $\mathscr R$ reflexive/transitive/symmetric/antisymmetric?

I thought it is reflexive and symmetric but the answer is transitive?Maybe I understood the question wrongly can someone explain?

• The relation is symmetric since $A\cap B=B\cap A$. It is not transitive since $NR\varnothing\wedge\varnothing RN$ but not $NRN$. Btw, it is not reflexive either: $\neg NRN$. Apr 28 '17 at 6:27

Let $R \subseteq \mathscr{P}(\mathbb{N}) \times \mathscr{P}(\mathbb{N})$ be defined by $A R B$ if and only if $|A \cap B| \leq 2$.

If $|A| > 2$, then $|A \cap A| = |A| > 2$. There goes reflexivity.

Since intersection is commutative, $R$ is symmetric.

$R$ is not antisymmetric because $|\{\, 0,1\,\} \cap \{\, 1,2 \,\}| \leq 2$ and yet the two sets are different.

Finally, the following three sets show that $A R B$ and $B R C$ do not imply $A R C$.

\begin{align} A &= \{\, 0, 1, 2, 3 \,\} \\ B &= \{\, 3 \,\} \\ C &= \{\, 1, 2, 3 \,\} \enspace. \end{align}

The relation $R \subseteq \mathbb{N} \times \mathbb{N}$ is not reflexive because if we take $A$ to be a set of size $3$ or more, say $A=\{1,2,3\}$, then $|A \cap A| = 3$, and so $(A,A) \notin R$.

The relation is not transitive because there exists $A, B, C \subseteq \mathbb{N}$ such that $(A,B), (B,C) \in R$ and $(A,C) \notin R$. For example, take $A$ and $C$ to have a large overlap with each other but a small overlap with $B$, say $A=\{1,2,3,4\}$, $C=\{1,2,3,5\}$, $B=\{1\}$.

The relation $R$ is symmetric since $|A \cap B| = |B \cap A|$. However, $R$ is not antisymmetric because there exists $A,B$ such that $(A,B), (B,A) \in R$ and $A \ne B$. For example, take $A=\{1,2\}, B=\{1,3\}$.