Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let S and T be two countably infinite sets. Suppose S is not a subset of T and vice-versa. Is the intersection of S and T a finite set? If not, please provide counterexamples.

I originally asked this question because it occurred to me when trying to prove that the union of two countably infinite sets is countable. I recently picked up Ralph Boas' Primer of Real Functions and have been trying to do the exercises. However, in the book, Boas doesn't introduce the notion of countability using injective functions and I have been trying to come up with a proof that doesn't involve injections. I fooled myself with a 'proof' but now I'm just stuck. Any hints to help me along the way? I'm very new to real analysis. So please bear with me. Also, what proportion of exercises should I be able to do if I really understand the material? I guess what I'm asking is that how do the exercises serve as a barometer for my mathematical skill?

share|improve this question

3 Answers 3

up vote 1 down vote accepted

Before we worry about countability of items related to $S$ and $T$, draw a generic Venn Diagram, two circles or ovals. This Venn Diagram divides the world into $4$ pieces.

Now look at a desired property, such as $S$ and $T$ countably infinite and $S\cap T$ infinite. Can we produce such sets? Sure, put lots of stuff in $S\cap T$, say all the integers.

To make sure that $S$ is not a subset of $T$, and $T$ is not a subset of $S$, we want to make sure that there are some things in $S$ that are not in $S\cap T$, and some things in $T$ that are not in $S\cap T$. No problem, put Alice in $S$ but not in $T$, and Bob in $T$ but not in $S$. Or, more boringly, $-1/2$ and $1/2$.

Do we want to see, as the OP asked in a comment, whether the symmetric difference of $S$ and $T$ can be infinite? No problem! Just let the picture guide you.

In problems of this type, if we draw a Venn Diagram as an aid, the diagram leads quickly to examples if they exist, and to a proof of non-existence if they don't.

share|improve this answer
    
Nice. I believe this must be the most useful answer in this case. –  Vadim Apr 21 '12 at 4:13
    
Indeed, this answer is extremely helpful. Thank you very much. –  Sakif Khan Apr 22 '12 at 2:53

Let $$P_n=\mathbb{N}-\{m\cdot n|m>1\}$$ i.e. $P_n$ contains $n$ and all positive integers that are not divisible by $n$.

Then $$\cap_{n\ge 2}P_n$$ is the set containing $1$ and all prime numbers (this is called Sieve of Eratosthenes).

Note that, for example, $P_2$ and $P_3$ satisfy your requirement. Their intersection is countably infinite: it excludes all numbers greater than 3 divisible by 2 or by 3, but, for example, it contains all numbers divisible by 5, by 7 etc.

Note also, that we could have taken the intersection over all prime numbers $n$ $$\cap_{n\space is\space prime}P_n$$ with the same result. But for any two prime numbers $p$ and $q$ neither $P_p$ contains $P_q$ nor vice versa. This shows that even countable intersection of countably infinite sets satisfying your property pairwise, can be countably infinite.

share|improve this answer

Not necessarily. Take $S=\{1\}\cup\{3,4,5,\ldots\}$. $T=\{2\}\cup\{3,4,5,\ldots\}$.

Perhaps more interesting:

$S=\{-1,-3,-5,\ldots\}\cup\{1,2,3,\ldots\}$ and $T=\{-2,-4,-6,\ldots\}\cup\{1,2,3,\ldots\}$

share|improve this answer
    
Thanks a lot! I feel dumb not having thought of that. –  Sakif Khan Apr 21 '12 at 2:05
    
Just wondering.....if the intersection is countably infinite, does that mean that the symmetric difference of S and T is finite? –  Sakif Khan Apr 21 '12 at 2:13
    
@mathcurious No. See the edit. –  David Mitra Apr 21 '12 at 2:18
    
@mathcurious: Any countable set can be broken up into two disjoint countable sets. By repeating the procedure, you can break it up into any finite number of pairwise disjoint countable sets you may desire. So take a countable set $A$, and break it up as $B\cup C\cup D$, pairwise disjoint; then take $S=B\cup C$, $T=C\cup D$. –  Arturo Magidin Apr 21 '12 at 4:28

Your Answer

 
discard

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.