1

I am not sure if my proof here is sound, please could I have some opinions on it? If you disagree, I would appreciate some advice on how to fix my proof. Thanks

$X_1, X_2, ..., X_n$ are countably infinite sets.

Let $X_1 = \{{x_1}_1, {x_1}_2, {x_1}_3, ... \}$

Let $X_2 = \{{x_2}_1, {x_2}_2, {x_2}_3, ... \}$

...

Let $X_n = \{{x_n}_1, {x_n}_2, {x_n}_3, ... \}$

Let $P_n$ be the list of the first $n$ ordered primes: $P_n = (2,3,5,...,p_n) = (p_1,p_2,p_3,...,p_n)$

Define the injection: $\sigma: X_1 \times X_2 \times ... \times X_n \to \mathbb{N}$

$\sigma (({x_1}_A, {x_2}_B, {x_3}_C,...,{x_n}_N)) = p_1^A\cdot p_2^B \cdot p_3^C \cdot ... \cdot p_n^N$

By the Fundamental Theorem of Arithmetic, $\sigma$ is an injection, because if two elements in the domain map to the same element in the codomain, they must be the same element.

Clearly, the image is finite. So by definition, the Cartesian product of n sets which are all countably infinite, is itself, countably infinite.

EDIT: Is it worth noting that my $X_n$ sets should be ordered or does that not matter?

subscript42
  • 59
  • 1
    another way to prove this is just to prove that $X \times Y$ is countable provided $X$ and $Y$ are. From there on, you can do a recursion using $X^n \cong X^{n-1}\times X$. – Olivier Roche Dec 20 '21 at 19:18
  • Thank you, I have proven it for $X \times Y$ but I wasn't entirely sure how to induct. Would my base case be $X \times Y$ or just $X$ ? – subscript42 Dec 20 '21 at 19:21
  • CORRECTION : I meant to write the trivial $X_1 \times X_2 \times \dots \times X_n = \big(X_1 \times X_2 \times \dots \times X_{n-1} \big) \times X_n$. – Olivier Roche Dec 20 '21 at 19:33

2 Answers2

1

Your very last part is wrong, which part is...

Clearly, the image is finite. So by definition, the Cartesian product of n sets which are all countably infinite, is itself, countably infinite.

It must be change to this...

Clearly, the image is denumerable. So by definition, the Cartesian product of $n$ sets which are all countably infinite, is itself, countably infinite.

And other part are perfect.

MH.Lee
  • 5,568
1

Do not cascade indices outwards : x_{1,1} should be preferred to {x_1}_1.

Do not use an alphabetical list to index, $\sigma ((x_{1,A}, x_{2,B}, x_{3,C},...,x_{n,N})) = p_1^A\cdot p_2^B \cdot p_3^C \cdot ... \cdot p_n^N$ is unclear (and implicitely implies $n \leqslant 26$).

Say you want your exponent to be a capital letter, then use (eg) $A_1, A_2,\dots, A_n$. You get the well written definition $$\sigma (x_{1, A_1},\, x_{2,A_2}, x_{3, A_3},\dots,x_{n, A_n})) := p_1^{A_1}\cdot p_2^{A_2} \cdot p_3^{A_3} \cdot \dots \cdot p_n^{A_n}$$.

Olivier Roche
  • 5,319
  • 9
  • 16