1

Let $\def\Rthree{\,{\mathrm{R}_3}\,} \Rthree$ be the relation on sets $C$, $D$ of natural numbers such that $C \Rthree D$ iff $C \cap D$ is finite. Then $\Rthree$ is symmetric, but not reflexive or transitive.

I don't understand any of the 3. The example for why it was not reflexive was

$\Bbb{N} \Rthree \Bbb{N}$ is not true

If that's the case can't I say that because $\Bbb{C} \Rthree \Bbb{N}$ isn't true, it isn't symmetric either? Why is it symmetric?

I would appreciate insight onto why it's not transitive as well. Thank you.

wcarvalho
  • 163

3 Answers3

1

First of all, the relation only applies to natural numbers, so $\mathbb C R_3\mathbb N$ doesn't mean any thing. Even so, the symmetric property states:

If $A\, R\, B$, then $B\, R\, A$.

If $A\,\not R\, B$, then the property doesn't apply (we might say it is vacuously satisfied). Symmetry is true for this realtion because if $A\cap B$ is finite, then $B\cap A$ is finite. Again, if $A\cap B$ is not finite, then symmetry doesn't apply, so we don't even worry about $B\cap A$.

Plutoro
  • 22,730
  • 3
  • 41
  • 71
  • Hmm, could you elaborate on why this relation only applies to natural numbers? Sorry, I'm new to this type of math. – wcarvalho Aug 20 '15 at 04:25
  • 1
    It doesn't have to apply to only natural numbers, but you said that we are limited to sets of natural numbers for this particular case in the first sentence of your question. It's important to know the domain you are working with because a relation may have some properties in one domain, but lose those properties in a larger domain. For example, this relation is an equivalence relation if we limit ourselves to finite sets. – Plutoro Aug 20 '15 at 04:29
  • Wow! Thank you. I read it (and copied it) but never really read it. – wcarvalho Aug 20 '15 at 04:30
1

Remember the definition of a relation on $\Bbb N$:

$R$ is a relation on the power set of $\Bbb N$ $\mathscr{P}(\Bbb N)$ (the set of all subsets of $\Bbb N$) if it is a subset of $\mathscr{P}(\Bbb N) \times \mathscr{P}(\Bbb N)$.

This means that for every pair $(A,B) \in R$ we have $A \subseteq \Bbb N$ and $B \subseteq \Bbb N$. We are really only talking about subsets of $\Bbb N$.

Alex S addressed the symmetry, so I will talk about the reflexivity and the transitivity.

$R$ is not reflexive because there exists $A \subseteq \Bbb N$ such that $A \not R_3 A$, or such that $A \cap A$ is infinite. For a counterexample you can take any infinite subset of $\Bbb N$ (even $\Bbb N$ itself, as you wrote).

$R$ is not transitive, because we can find subsets of $\Bbb N$ $A,B$ and $C$ such that $A \ R_3 \ B$ and $B \ R_3 \ C$, but $A \not R_3 C$. For a counterexample, try to find two infinite sets $A,C$ whose intersection is infinite, and let $B$ be any finite set.

coldnumber
  • 3,721
  • 1
    Thank you for the super clear answer. For transitive, would the following be valid: A={ a is odd}, B = { b < 50}, C = {c is even}? – wcarvalho Aug 20 '15 at 04:35
  • Another question, Alex S stated for his answer that when $A \not R A$, the property doesn't apply so it's vacuously true. When $ \mathbb N \not R \mathbb N$, why isn't that also vacuously true? – wcarvalho Aug 20 '15 at 04:46
  • We say that the implication $P \implies Q$ is true vacuously if the hypothesis, $P$, is always false; the implication that needs to be satisfied for symmetry is $A \ R_3 \ B \implies B \ R_3 \ A$ for any $A,B \subseteq \Bbb N$. The hypothesis here is $A \ R_3 \ B$, and if two sets $A,B$ fail to satisfy it, the whole implication is vacuously true. Reflexivity isn't really given in terms of an implication, but rather in terms of a statement with a universal quantifier: "for all $A \subseteq \Bbb N$ we have $A \ R_3 \ A$". (cont.) – coldnumber Aug 20 '15 at 04:53
  • And the negation of this reflexivity statement is "there exists some $A \subseteq \Bbb N$ such that $A \not R_3 A$. So showing that $\Bbb N \not R_3 \Bbb N$ shows that the negation of the statement is true, meaning the statement is false. Does this make sense? – coldnumber Aug 20 '15 at 04:54
  • Yes, it does. Thank you. – wcarvalho Aug 20 '15 at 15:14
  • @wcarvalho I missed the edit on your first comment; the example almost works but doesn't because $A \cap C = \varnothing$. Try this: take $A,B$ as you wrote them, and take $C = \Bbb N$. – coldnumber Aug 20 '15 at 16:27
  • Ahh thank you. I misread it as a union not an intersection. – wcarvalho Aug 20 '15 at 16:29
0

As an intuition, the relation is similar to saying "not equal" or "disjoint", so it is almost the opposite of an equivalence relation. It is the relation of disjointness on sets of integers modulo finite sets (where we regard two sets as equivalent if they differ on only a finite number of elements).

ASCII Advocate
  • 2,434