Conditions for $A \times B$ to be countable 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!
 A: Suppose we have propositions $P$ and $Q$. We say that $P$ is necessary for $Q$ if you can never have $Q$ without $P$ (so whenever you have $Q$ you have $P$, i.e. $Q \Rightarrow P$). Conversely, $P$ is sufficient for $Q$ if whenever you have $P$ you have $Q$, i.e. $Q \Leftarrow P$.
So let's suppose that $B$ is countably infinite, and take $Q$ to be the statement "$A\times B$ is countable.


*

*Is it true that $A \times B$ being countable implies that $A$ is countably infinite? No, $A$ could be a finite set.

*Is it possible for $A \times B$ to be countable but $A$ not countable? No (try to prove this!). So it is necessary that $A$ is countable.


3) and 4) proceed similarly.
Re: Countable vs countably infinite. A set is countably infinite if it is in bijection with $\mathbb{N}$, and countable if it's countably infinite or finite.
A: I will call infinite countable sets simply countable. Sets with finite number of elements are finite.
It is necessary and sufficient that the set $A$ is non-empty and at most countable.

If the set $A$ is empty, then $A\times B=\emptyset$ obviously cannot be countable, therefore it is necessary that $A\neq\emptyset$.
It suffices for $A\neq\emptyset$ to be finite. It's also known that the direct product of countable sets is countable.  Option 3 is definitely correct. With option 4, it must be specified that $A\neq\emptyset$.
It is not necessary for $A$ to be countable (=countably infinite). If it were necessary then the following implication would be true:
$$ |A\times B| = |\mathbb N| \quad\mbox{and}\quad |B| = |\mathbb N|\implies |A| = |\mathbb N|.\quad \text{(why is this false?)} $$
Neither is it necessary for $A$ to be finite (because it can be countable).

In case of 2, if it is specified that $A\neq\emptyset$ then it is necessary that $A$ is at most countable i.e
$$ |A\times B| = |\mathbb N| \quad\mbox{and}\quad |B| = |\mathbb N|\implies \exists n\in\mathbb N\setminus\{0\}\ :|A|= n\quad\mbox {or}\quad |A| = |\mathbb N|. $$
A: 
...I'm also not quite clear on how being countable vs countably infinite changes the problem.

For a set to be countably infinite it has to be infinite, but a countable set can also be finite.
A: 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}$$

For example, I know that if A,B are both countably infinite, A×B is countably infinite. But does that mean that the fact that A is countably infinite is "necessary" or just "sufficient"?

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.
