1
$\begingroup$

Define $x\sim y$ iff $x-y\in\mathbb{Q}$.

Let $S = [0, 1)$. Define $A\subset S$ such that $A$ contains exactly one element of each class of equivalence of the relation $x\sim y$.

Let $Q = \mathbb{Q}\cap S$. Chose $q\in Q$ and build the set $A_q$ from it: cut the set $A$ in two sets $1$ and $2$, in the position $1-q$. Translate $1$ to where was $2$, and translate $2$ to where was $1$. Then you will glue such pieces in the position $q$.

In other words, define: $A_q = \{x+q : x\in A\cap[0, 1-q)\}\quad\cup\quad \{x+q-1 : x\in A\cap[1 - q, 1)\}$.

If $p\neq q$, how does one proves $A_q\cap A_p = \emptyset$?


The place I was reading proved in the following way. But I was unable to follow it. Maybe it helps you...

Let $x\in S$ and $x\sim y$ which is in $A$, then: $$ x\in A_q,\quad\mbox{where }q = \begin{cases} x-y & \mbox{if }x\ge y \\ x-y+1 & \mbox{if }x < y \end{cases} $$

Thus if existed $x\in A_q\cap A_p$ then $x-q$ and $x-p$ would be distinct and equivalent elements of $A$, which is a contradiction of the definition of $A$.

$\endgroup$
  • $\begingroup$ One basic recipe is to assume $x \in A_q$ and $x \in A_p$, then derive a contradiction. Since $A_r$ is the union of two sets I will call $A_r'$ and $A_r''$, $x \in A_r$ means the same thing as "$x \in A_r'$ or $x \in A_r''$". It might be easier to modify the basic recipe to consider four separate problems: "Assume $x \in A_q'$ and $x \in A_p'$. Derive a contradiction. Assume $x \in A_q'$ and $x \in A_p''$. Derive a contradiction. ..." Seven times out of ten, you can solve a problem like this just by unfolding the notation. $\endgroup$ – user14972 Jul 29 '16 at 0:26
2
$\begingroup$

The argument that you found is not entirely correct. Here’s a corrected and expanded version.

Suppose that $x\in A_q$ for some $q\in Q$. There are two cases to be considered.

  • If $x\ge q$, then $x$ must be of the form $y+q$ for some $y\in A\cap[0,1-q)$, so $x-q\in A$.

  • If $x<q$, then $x$ must be of the form $y-1+q$ for some $y\in A\cap[1-q,1)$, so $x-q+1\in A$.

Thus, either $x-q\in A$, or $x-q+1\in A$. Note that $x-q\sim x\sim x-q+1$.

Now suppose that $x\in A_q\cap A_p$ for some $p,q\in Q$. There are four possibilities:

  • $x-q\in A$ and $x-p\in A$: then $x-q\sim x\sim x-p$, so $x-q\sim x-p$. But $x-q$ and $x-p$ are both in $A$, which contains only one member of each $\sim$-class, so $x-q=x-p$, and therefore $q=p$.
  • $x-q\in A$ and $x-p+1\in A$: then $x-q\sim x\sim x-p+1$, so $x-q\sim x-p+1$. It follows as in the previous case that $x-q=x-p+1$ and hence that $q=p-1$. This, however, is impossible, since $0\le q,p<1$, so this case cannot actually occur. (Recall that $Q\subseteq S\subseteq[0,1)$.)
  • $x-q+1\in A$ and $x-p\in A$: this is just like the previous case.
  • $x-q+1\in A$ and $x-p+1\in A$: this is like the first case.

We conclude that $q=p$, and hence that $A_q\cap A_p=\varnothing$ whenever $q,p\in Q$ and $q\ne p$.

This shows that $\{A_q:q\in Q\}$ is a pairwise disjoint family.

The first part of the proof that you found does not seem to me to be needed in order to show that the sets $A_q$ are pairwise disjoint. It does show, however, that they cover $S$; I’ll expand on that.

Let $x\in S$. $A$ contains a member of each $\sim$-equivalence class, so there is some $y\in $ such that $x\sim y$. Now there are two possibilities: either $x\ge y$, or $x<y$.

  • If $x\ge y$, let $q=x-y$. Then $y=x-q<1-q$, since $x<1$, so $y\in A\cap[0,1-q)$, and therefore $x=y+q\in A_q$ by definition.

  • If $x<y$, let $q=x-y+1$. Then $y=x+1-q\ge 1-q$, since $x\ge 0$, and therefore $y\in A\cap[1-q),1)$, so that again $x=y+q-1\in A_q$ by definition.

The two parts together show that $\{A_q:q\in A\}$ is a partition of $S$.

$\endgroup$
  • $\begingroup$ @Physicist137: You’re welcome! $\endgroup$ – Brian M. Scott Jul 31 '16 at 1:33

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.