Take the 2-minute tour ×

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?

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

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

share|improve this answer
Thank you very much! I've got it! –  17SI.34SA Nov 2 '12 at 19:20
@17SI.34SA: Excellent! You’re welcome. –  Brian M. Scott Nov 2 '12 at 19:21
add comment

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.

share|improve this answer
Thank you as well! –  17SI.34SA Nov 2 '12 at 19:22
add comment

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.

share|improve this answer
add comment

Your Answer


