1
$\begingroup$

As this question clearly shows that the countable many product of countable sets is uncountable. However, I do not understand why the below proof is wrong:

(False) Proof:

Let $A$ be a countable set. We use induction to show that the countably many product of $A$ with itself is countable. We use induction. When $n=1$, the theorem is true by our hypothesis.Let assume it is true for $A^n = A\times ... A : n$ times.

Since $A^{n+1} = A^n \times A$, which is the finite product of countable sets, it is also countable by this question. Hence, by induction $A^n$ is countable for all $n \in \mathbb{N}$. QED

Question:

Why is the above proof wrong ? Where is the flaw ?

Edit:

I'm trying to show that $A^{|\mathbb{N}|}$ is countable.

$\endgroup$

marked as duplicate by Asaf Karagila set-theory Oct 10 '18 at 7:53

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ To assert that every finite product of countable sets is countable implies that an infinite product of countable sets is countable is a non sequitur. $\endgroup$ – Lord Shark the Unknown Oct 10 '18 at 6:20
  • 2
    $\begingroup$ To put it another way, there is an important distinction to be drawn between arbitrarily large (but finite) $n$ and infinitely large $n$. $\endgroup$ – Brian Tung Oct 10 '18 at 6:23
  • $\begingroup$ @LordSharktheUnknown I used induction. Isn't that a valid move ? $\endgroup$ – onurcanbektas Oct 10 '18 at 6:23
  • 1
    $\begingroup$ @onurcanbektas You successfully proved that $A^n$ is countable for any $n\in\Bbb N$. Well done! But your "proof" does not even consider infinite products. $\endgroup$ – Lord Shark the Unknown Oct 10 '18 at 6:25
3
$\begingroup$

The proof you give proves that $A^n$ is countable for all $n \in \mathbb{N}$ however what you wish to prove is $A^\omega$ is countable. That is the propitiation is true for the infinite case. However $\omega$ isn't in $\mathbb{N}$ so the induction you use doesn't work.

$\endgroup$
  • $\begingroup$ I'm not trying to show that the uncountable product of countable sets is countable. I just want to show that countable product of countable sets is countable. $\endgroup$ – onurcanbektas Oct 10 '18 at 6:29
  • $\begingroup$ i.e $A^{|\mathbb{N}|}$ is countable. $\endgroup$ – onurcanbektas Oct 10 '18 at 6:30
  • 1
    $\begingroup$ @onurcanbektas $|\Bbb N|\notin\Bbb N$. $\endgroup$ – Lord Shark the Unknown Oct 10 '18 at 6:32
  • $\begingroup$ @LordSharktheUnknown I did not know that. Thanks $\endgroup$ – onurcanbektas Oct 10 '18 at 6:33
  • 2
    $\begingroup$ $ |\mathbb{N}| = \aleph_0 = \omega $ $\endgroup$ – Q the Platypus Oct 10 '18 at 6:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.