# pairwise disjoint subset question

• Oct 10th 2011, 06:11 PM
wopashui
pairwise disjoint subset question
A) Show that $\displaystyle N$ contains infinitely many pairwise disjoint infinite subsets. [Hint: It was shown that $\displaystyle N$~$\displaystyle N$x$\displaystyle N$

what is a pairwise disjoint infinite subset, can someone provide the definition of it?

B) Prove that any infinite set can be written as the countably infinite union of pairwise disjoint infinite subsets.
• Oct 10th 2011, 10:23 PM
Drexel28
Re: pairwise disjoint subset question
Quote:

Originally Posted by wopashui
A) Show that $\displaystyle N$ contains infinitely many pairwise disjoint infinite subsets. [Hint: It was shown that $\displaystyle N$~$\displaystyle N$x$\displaystyle N$

what is a pairwise disjoint infinite subset, can someone provide the definition of it?

B) Prove that any infinite set can be written as the countably infinite union of pairwise disjoint infinite subsets.

The basic idea is as was stated to you. If $\displaystyle X$ is infinite then $\displaystyle X$ is equipotent to $\displaystyle X\times X$, say that $\displaystyle f:X\times X\to X$ is the bijection. We then have that $\displaystyle \left\{\{x\}\times X\right\}_{x\in X}$ is an infinite collection of pairwise disjoint sets in $\displaystyle X\times X$, thus $\displaystyle \left\{f(X\times\{x\})\right\}_{x\in X}$ is an infinite collection of pairwise disjoint subsets of $\displaystyle X$.
• Oct 10th 2011, 10:48 PM
Deveno
Re: pairwise disjoint subset question
to answer the original poster, a pair-wise disjoint collection of sets is a family $\displaystyle \{A_j\}_{j \in J}$ of sets such that:

$\displaystyle A_i \cap A_j \neq \emptyset \implies A_i = A_j\ \forall i,j \in J$
• Oct 11th 2011, 05:28 PM
wopashui
Re: pairwise disjoint subset question
Quote:

Originally Posted by Deveno
to answer the original poster, a pair-wise disjoint collection of sets is a family $\displaystyle \{A_j\}_{j \in J}$ of sets such that:

$\displaystyle A_i \cap A_j \neq \emptyset \implies A_i = A_j\ \forall i,j \in J$

so is this just mean a union of infinite many mutually exclusive sets?
• Oct 11th 2011, 05:36 PM
wopashui
Re: pairwise disjoint subset question
Quote:

Originally Posted by Drexel28
The basic idea is as was stated to you. If $\displaystyle X$ is infinite then $\displaystyle X$ is equipotent to $\displaystyle X\times X$, say that $\displaystyle f:X\times X\to X$ is the bijection. We then have that $\displaystyle \left\{\{x\}\times X\right\}_{x\in X}$ is an infinite collection of pairwise disjoint sets in $\displaystyle X\times X$, thus $\displaystyle \left\{f(X\times\{x\})\right\}_{x\in X}$ is an infinite collection of pairwise disjoint subsets of $\displaystyle X$.

this approach seems to work for both question, I do not understand the difference of part A and B? Need some explainations please!
• Oct 11th 2011, 07:35 PM
Drexel28
Re: pairwise disjoint subset question
Quote:

Originally Posted by wopashui
this approach seems to work for both question, I do not understand the difference of part A and B? Need some explainations please!

In my example there is no need for the union to be countable. Give us an idea how to the second part, a little effort would be nice.
• Oct 12th 2011, 01:01 PM
wopashui
Re: pairwise disjoint subset question
Quote:

Originally Posted by Drexel28
In my example there is no need for the union to be countable. Give us an idea how to the second part, a little effort would be nice.

for B) if S is an infinite set, we have 2 cases, S can be uncountable or countably infinite, if S uncountable, this is not possible, so we need to show that S is countable
since S is infinite, then we have$\displaystyle f:N-->S$ , f is injective, so if we show that f is also a surjection, we have f is a bijectiion, i.e. $\displaystyle N~S$ . i.e we need to show that for all$\displaystyle s\in S$ there exisis $\displaystyle n_s\in N$ $\displaystyle s.tf(n_s)=s$

If we have f is a bijection, then by part A, we have part B

so how can I do this?
• Oct 12th 2011, 01:32 PM
Plato
Re: pairwise disjoint subset question
Quote:

Originally Posted by wopashui
for B) if S is an infinite set, we have 2 cases, S can be uncountable or countably infinite, if S uncountable, this is not possible, so we need to show that S is countable?

It is not necessary to consider cases to prove part B.
If $\displaystyle S$ is infinite then there is a countable subset $\displaystyle T\subset S$.
Moreover, there is surjection $\displaystyle f:S\to T$.
Then $\displaystyle \left\{ {f^{ - 1} \left( {\{ x\} } \right):x \in T} \right\}$ is pairwise disjoint countable collection and $\displaystyle S = \bigcup\limits_{x \in T} {f^{ - 1} \left( {\{ x\} } \right)}$.
• Oct 12th 2011, 06:34 PM
wopashui
Re: pairwise disjoint subset question
Hi, Plato, I don't understand what$\displaystyle f^{-1}$ comes from, and can a uncountable set has a countable subset, so if S is uncountable, can T be countable? Do I need part A to show part B?