Suppose $A$ and $B$ are both sets, and $B$ is for sure countably infinite. What are the conditions that $A$ must have so that $A\times B$ is countable? The possible answers (I suspect more than one is true) are
- necessary that $A$ is countably infinite
- necessary that $A$ is just countable
- sufficient that $A$ is countably infinite
- sufficient that $A$ is just countable
I don't quite understand the difference between "necessary" and "sufficient", and I'm also not quite clear on how being countable vs countably infinite changes the problem.
For example, I know that if $A, B$ are both countably infinite, $A\times B$ is countably infinite. But does that mean that the fact that $A$ is countably infinite is "necessary" or just "sufficient"? I really don't understand. Thank you so much for your help!
Best Answer
If $P$ and $Q$ are two propositions, then you have the following equivalences:
$$\begin{matrix} \text{If } P \text{ then } Q & & & P \implies Q & & & P \text{ is a sufficient condition for }Q, \\[6pt] \text{If } Q \text{ then } P & & & P \impliedby Q & & & P \text{ is a necessary condition for }Q. \\[6pt] \end{matrix}$$
That means that $A$ and $B$ being countably infinite is sufficient for $A \times B$ to be countably infinite. In this case, necessity would mean that if $A \times B$ is countably infinite then $A$ and $B$ are countably infinite, which is false.