Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Define on $2^{\mathbb{N}}$ equivalence relation $$ X\sim Y\Leftrightarrow \text{Card}((X\setminus Y)\cup(Y\setminus X))<\aleph_0 $$ Is there exist a function $f\colon 2^{\mathbb{N}}\to 2^{\mathbb{N}}$ such that $$ f(X)\sim X $$ $$ X\sim Y \Rightarrow f(X)=f(Y) $$ $$ f(X\cap Y)=f(X)\cap f(Y) $$

share|cite|improve this question
No. Think about what would happen with an uncountable almost disjoint family. – user83827 Nov 16 '11 at 23:21
Sets ${X_\alpha}$ of such a family will belong to different equialence classes. From properties 1 and 2 we see that it implies $f(X_\alpha)\cap f(X_\beta)=\varnothing$. If I understood almost disjoint mean $\text{Card}(X_\alpha\Delta X_\beta)\geq\aleph_0$. Hence $f(X_\alpha\cap X_\beta)\nsim\varnothing=f(X_\alpha)\cap f(x_\beta)$. Right? – Norbert Nov 16 '11 at 23:33
Not quite. Two sets are almost disjoint if their intersection is finite. Your properties imply that $f(X_\alpha)\cap f(X_\beta)=f(X_\alpha\cap X_\beta)=f(\varnothing)$ whenever $\alpha\ne\beta$. Now look at the sets $f(X_\alpha)\setminus f(\varnothing)$. – Brian M. Scott Nov 16 '11 at 23:38
Thanks, now the rest is clear. – Norbert Nov 16 '11 at 23:43
Why don’t you go ahead and write up the answer yourself, so that the question doesn’t stay on the Unanswered list; this is not only okay, it’s explicitly encouraged. – Brian M. Scott Nov 17 '11 at 0:14
up vote 2 down vote accepted

Let $\{X_\alpha : \alpha\in\mathcal{A}\}\subset\mathbb{N}$ be an uncountable family of sets such that $$ \alpha,\beta\in\mathcal{A},\quad\alpha\neq\beta\Rightarrow \text{Card}(X_\alpha\cap X_\beta)<\aleph_0 $$ Such a family does exist. Indeed for each irrational number $x\in\mathbb{I}$ consider sequence of rational numbers $\{x_n\}_{n=1}^{\infty}\subset\mathbb{Q}$ tending to $x$. Let $\varphi(x)=\{x_n:n\in\mathbb{N}\}$ be the set of this rational numbers. Obviously for $x,y\in\mathbb{I}$ such that $x\neq y$ we have $\text{Card}(\varphi(x)\cap\varphi(y))<\aleph_0$. Also obviously for all $x\in\mathbb{I}$ we have $\text{Card}(\varphi(x))=\aleph_0$. Let $i\colon 2^\mathbb{Q}\to 2^\mathbb{N}$ be some bijection between $2^\mathbb{Q}$ and $2^\mathbb{N}$ then we may take by definition $\{X_\alpha : \alpha\in\mathcal{A}\}=\{i(\varphi(x)):x\in\mathbb{I}\}$. This will be desired family.

Let $\alpha,\beta\in\mathcal{A},\alpha\neq\beta$. Then $X_\alpha\cap X_\beta\sim\varnothing$. And from the second and third properties we obtain $f(X_\alpha)\cap f(X_\beta)=f(X_\alpha\cap X_\beta)=f(\varnothing)$.

Now for each $\alpha\in\mathcal{A}$ consider $Y_\alpha=f(X_\alpha)\setminus f(\varnothing)$. By construction $X_\alpha$ is infinite, so does $f(X_\alpha)$, and as the consequence $Y_\alpha\neq\varnothing$. Now for all $\alpha,\beta\in\mathcal{A},\alpha\neq\beta$ we have $$ Y_\alpha\cap Y_\beta=f(X_\alpha\cap X_\beta)\setminus f(\varnothing)=\varnothing $$ Thus we built an uncountable family of disjoint subsets $\{Y_\alpha : \alpha\in\mathcal{A}\}$ in countable set $\mathbb{N}$. Contradiction, hence such a function doesn't exist.

share|cite|improve this answer
I've corrected Let $i\colon 2^\mathbb{Q}\to 2^\mathbb{N}$ be some bijection between $\mathbb{Q}$ and $\mathbb{N}$ to $i\colon \mathbb{Q}\to \mathbb{N}$.\\ I guess you should also mention that $Y_\alpha$'s are non-empty to get a contradiction. – Martin Sleziak Nov 17 '11 at 13:19
You corrected my typo to another typo. In first redaction a meant bijection between $2^{\mathbb{Q}}$ and $2^\mathbb{N}$. I meant exactly such a bijection because $\varphi$ maps $\mathbb{I}$ into $2^\mathbb{N}$. So I will edit my post again. – Norbert Nov 17 '11 at 13:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.