We define a relation between subsets of $\mathbb R ^n$. $A \sim B\Longleftrightarrow$ we can partition $A,B$ in sets $A_1,\dots,A_n$ and $B_1,\dots,B_n$(i.e $\displaystyle A=\bigcup_{i=1} ^n A_i,\ B=\bigcup_{i=1} ^n B_i, A_i\cap A_j=\emptyset,\ B_i\cap B_j=\emptyset$) and $A_i\simeq B_i$. Say the the following sets have the relation $\sim$ or not ? a) Natural numbers and composite numbers. b) Rational numbers and rational numbers with finite digits in base 10. c) $\{x\in\mathbb Q|x<\sqrt 2\}$ and $\{x\in\mathbb Q|x<\sqrt 3\}$ d) $A=\{(x,y)\in\mathbb R^2|x^2+y^2<1\}$ and $A\setminus \{(0,0)\}$
Problem
Source: Iran 2005
Tags: geometry, group theory, abstract algebra, geometric transformation, Gauss, topology, absolute value
21.09.2005 14:49
I think it isn't $geometry$ , Omid !
21.09.2005 16:02
For (b): I believe the answer is "no". The rationals with finitely many decimal digits are precisely those with denominators having only $2$ and $5$ as prime factors (when the rationals are in their lowest terms). This means that they form a subgroup $H\ne \mathbb Q$ of $\mathbb Q$. Suppose we can partition each of $\mathbb Q,H$ into $n$ parts $A_i,B_i$, as described above. For each $i$, any two elements in $A_i$ must have a difference lying in $B_i\subset H$, so every two elements in $A_i$ have the same image through the canonical projection $\mathbb Q\to \mathbb Q/H$. This implies that $H$ is a subgroup of finite index of $\mathbb Q$. This is impossible, since $\mathbb Q$ has no subgroups of finite index, other than itself. For (c): The answer is "yes" here. Choose some $b_0<\sqrt 3$ s.t. $\sqrt 2-b_0\in\mathbb Q$, then some $a_0<\sqrt 2$ with $\sqrt 3-a_0\in\mathbb Q$, map the rationals in $(a_0,\sqrt 2)$ onto those in $(b_0-\sqrt 2+a_0,b_0)$ through a translation, and those in $(a_0-\sqrt 3+b_0,a_0)$ onto those in $(b_0,\sqrt 3)$ through another translation. Now repeat the procedure with $a_0+b_0-\sqrt 2,a_0+b_0-\sqrt 3$ instead of $\sqrt 3,\sqrt 2$ respectively, and so on. At each step, every interval is divided into two intervals, and the pairs of intervals are congruent. We can thus divide each of our initial two sets into two parts, by choosing one interval from each step and putting them in one part, and taking the other intervals and putting them in the second part. This is not exactly clear, but I think you get the idea . For (d): Again, the answer is "yes". Moreover, we can prove that given any open subset $A$ of $\mathbb R^2$ and any point $p\in A$, the sets $A$ and $A\setminus\{p\}$ are equivalent by division into two parts (i.e. we can take $n=2$ in the definition of our equivalence relation). Suppose WLOG that our open set contains the unit disk and that $p=1$ (we can scale the set and translate it, and the problem is the same). Take $z$ to be any complex number of absolute value $1$ which is not a root of unity, and put $A_1=\{z^n\ |\ n\ge 0\},A_2=A\setminus A_1$ and $B_1=\{z^n\ |\ n\ge 1\},B_2=A\setminus\{p=1\}\setminus B_1$. These are the partitions of $A$ and $B=A\setminus\{p\}$ ($A_1$ is congruent to $B_1$ via the map that sends $x$ to $zx$, while $A_2$ and $B_2$ coincide). I'll modify this post if I figure out the other one.
21.09.2005 21:15
I'm sory about posting such a trivial question, but what does $\simeq$ mean?
21.09.2005 21:39
I'm sure it's the usual congruence in $\mathbb R^n$.
27.09.2005 23:13
behzad wrote: I think it isn't $geometry$ , Omid ! The relation described above is called "equi-decomposability" and there is some tradition of studying it in geometry (Gauss, Hilbert, Dehn, Banach and Tarski, etc). For (a) the answer is "no", because the difference in the number of points in the two sets contained in a ball of radius $R$ must be bounded (independent of $R$), but the infinitude of prime numbers prevents such a situation.
28.09.2005 02:54
Here are a couple of more problems: Prove that the following pairs of sets are equivalent by division into two parts (i.e. $n=2$ in Omid's definition): (1) the real line and the real line from which any bounded set has been eliminated; (2) the real line and the real line from which any countable set has been eliminated (actually, "countable" can be replaced with "less than continuum").