I came across following problem:

If $A$ is a countable set, and $B$ is an uncountable set, then the most we can say about $A\cap B$ is that it is

  1. Empty.
  2. Finite, countable, or uncountable.
  3. Countable.
  4. Uncountable.
  5. Countable or uncountable.
  6. Finite.
  7. At most countable.

I understand it has to be countable, that is option 3. But the answer given was option 7 - "at most countable". I am confused what it means to say by prefix "at most". The explanation given was "The intersection of A and B could be smaller than countable." What does it means "smaller than countable"? Empty and/or finite? Or is there something more to it?

  • 5
    $\begingroup$ Apparently, some authors use "countable" as short for "countably infinite"? I've even seen some exclude empty from the notion of finite ... $\endgroup$ – Hagen von Eitzen Jun 24 '18 at 7:56
  • 1
    $\begingroup$ yess it seems that here "countable"="countably infinite" and "at most countable"="empty or finite or countably infinite". In next question (quiz), it says intersection of finite and uncountable set is "finite" but not countable. So I guess it clears that author means "countably infinite" when he says "countable" $\endgroup$ – anir Jun 24 '18 at 8:39
  • $\begingroup$ Indeed, from the existence of option 2, I assume that the author in question also considers finite to imply non-empty, or else option 2 would cover all sets. $\endgroup$ – celtschk Jun 24 '18 at 15:15
  • $\begingroup$ The preferred meaning of "countable" is "finite or countably infinite" so that "uncountable" means "not countable". Whoever posed this problem does not seem to agree. $\endgroup$ – DanielWainfleet Jun 25 '18 at 5:44

I'm going to opt for $7$. The reason is that there are three possibilities: $$i)\,\emptyset \\ ii)\text { finite }\\iii)\text { countably infinite }$$.

Note: $A\cap B\subset A\implies \lvert A\cap B\rvert\le\lvert A\rvert$.


Option 7 is the right one, the others are all false:

  1. empty is possible, not necessary (take $\mathbb{N}$ and $\mathbb{R}$).
  2. uncountable is not possible as $A \cap B \subseteq A$ so the intersection is at most countable. As "finite, countable or uncountable" essentially means "all sets", I discount it as an option, also because it suggests uncountable is even possible.
  3. countable, not, as it can also be finite or empty. ($\mathbb{N}$ and the irrationals, say).
  4. uncountable, not, as $A \cap B \subseteq A$ so this is out.
  5. countable or uncountable, not as finite is also possible, see 3. or for even suggesting uncountable is possible which it is not (see 2.)
  6. finite, not, because infinite is an option too, as we saw.
  7. Clearly true, as $A \cap B \subseteq A$ and a subset of a countable set is at most countable. Also, the last option remaining...
  • $\begingroup$ "countable, not, as it can also be finite or empty." MANY indeed I would surmise most texts define countable so that finite sets are countable. WHich is precisely the OP's question. The OP is not familiar with the claim that finite is not countable (and I'm not familiar with the claim empty is not finite.) $\endgroup$ – fleablood Jun 25 '18 at 0:22
  • $\begingroup$ @fleablood according to the comments he is aware that finite is not countable in his text. $\endgroup$ – Henno Brandsma Jun 25 '18 at 4:11

There are many text that define countable and finite as mutually incompatible. A finite set is not countable and a countable set must be infinite. Many others, and my person preference, define countable as including finite as well and countably infinite.

BOTH conventions will define "at most countable" as "not uncountable" to include the options of being finite or empty.

Although I do prefer the latter, I am sympathetic to this question. To ask what is "the most" we can say, I figure we must specify that although the set could be countably infinite (but never uncountable), that it need not be infinite.

And "at most countable" is the most accurate answer.


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.