0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – drhab
    Apr 28 '17 at 6:27
0
$\begingroup$

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}

$\endgroup$
0
$\begingroup$

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\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.