5
$\begingroup$

Let $\varsigma$ be a relation on $\wp(\mathbb{N})$ by defining $\langle A,B\rangle\in \varsigma$ iff exist natural $n$ such that $|A\Delta B|=n$. Is $\varsigma$ equivalence relation?

Reflexive: For all $A \in \wp(\mathbb{N})$, $|A\Delta A|=0$.

symmetry: For all $A,B \in \wp(\mathbb{N})$, exist $n$, s.t $|A\Delta B|=|B\Delta A|=n$.

What about transitivity?

3 Answers 3

3

Use the identity $A\triangle C=(A\triangle B)\triangle(B\triangle C)$. If $A\triangle B$ and $B\triangle C$ are finite, so is $A\triangle C$. Hence transitivity holds.

5

Yes. $(A \mathbin{\Delta} C) \subset (A \mathbin{\Delta} B) \cup (B \mathbin{\Delta} C)$, so if the right hand side is finite, so is the left hand side.

4

HINT: $\varsigma$ is transitive. For $A,B,C\in\wp(\Bbb N)$ try to express $A\Delta C$ in terms of $A\Delta B$ and $B\Delta C$.

Added: If you’re familiar with them, indicator (or characteristic) functions are a nice way to think about this:

$A\Delta B=\{n\in\Bbb N:1_A(n)\ne 1_B(n)\}\;,$

so $\langle A,B\rangle\in\varsigma$ if and only if there is an $m\in\Bbb N$ such that $1_A(n)=1_B(n)$ for all $n\ge m$.

  • 0
    @17SI.34SA: Excellent! You’re welcome.2012-11-02