2
$\begingroup$

Let $A_i$ be a family of non-empty sets for every $i \in N$

Determine if $\prod\limits_{i=0}^\infty A_i$ is always countable, some times countable, or never countable.

a) $|A_i| \ge 2$ for each $i \in \mathbb{N}$

$A$ is the set of all infinite sequences whereby $A=\{(a_0,a_1,a_2,\ldots) \mid a_k \in A_k \forall k \in \mathbb {N} \}$. To show that $A$ is uncountable, it suffices to show that $\not \exists$ bijection $f: \mathbb{N} \to A$. Assume for contradiction that $\exists$ bijection $f: \mathbb{N} \to A$.

Note that $f(0)=(a_0^{(0)},a_1^{(0)},a_2^{(0)},\ldots)$

and that $f(1)=(a_0^{(1)},a_1^{(1)},a_2^{(1)},\ldots)$

This means that $f(K)=(a_0^{(k)},a_1^{(k)},a_3^{(k)},\ldots)$. So each natural number is mapped to some infinite sequence. To show that $f$ is not surjective, let $b \in A \ni b=(b_0, b_1, b_2, b_3, \ldots)$ where $b_k \in A_k \forall k \in \mathbb{N}$.

Since $|A_0| \ge 2, |A_1| \ge 2, |A_2| \ge 2,\ldots,|A_i| \ge i$, let $b_i \in A_i \not \{a_i^{(i )}\}$ for every $i \in \mathbb{N}$. So the i-th term of $b$ will be different from the i-th term of $f$, and hence $b \notin f(\mathbb{N})$. Thus we have $b \in A \ni f(i) \ne b \forall i \in \mathbb{N}$. However, this contradicts the premise that $f$ is surjective (i.e. $f(\mathbb{N})=A)$. Therefore, $A$ is uncountable.

b) $\exists N \in \mathbb{N} \ni \forall i > N$, $|A_i| \ge 2$.

I'm having trouble figuring out what this means. Does this mean $|A_1| \ge 2, |A_2| \ge 2, |A_3| \ge 2, \ldots,|A_n| \ge 2$ for every $n \in \mathbb{N}$ except $n=0$? I'm thinking that in this case, the zeroth term of $b$ will be the zeroth term of $f$, so $f(0)=b$. But $f$ may not be injective since $f(1)=b$, but $0 \ne 1$. So it will essentially be some times countable.

c) $\exists N \in \mathbb{N} \ni \forall i > N$, $|A_i| = 1$.

As $f(K)=(a_0^{(k)},a_1^{(k)},a_3^{(k)},\ldots)$, where each $a_i^{(k)} \in A_i$ for every $k \in \mathbb{N}$ and $|A_n|=1$. This means that $f$ cannot be surjective since every natural number maps to $b$. Thus $\prod\limits_{i=0}^n A_n$ is uncountable.

However, $\prod\limits_{i=1}^{n}A_n$ is countable since it is finite; that is, $\left|\prod\limits_{i=1}^n A_n\right|=|A_1| \times |A_2| \times |A_3| \times\cdots\times |A_n|=1$?

d) $\exists N \in \mathbb{N} \ni \forall n > N$, $|A_n| = 1$, and $\exists$ injection $f:\mathbb{N} \to A$.

I'm not sure about this. My understanding is that $A$ should infinite since by definition, a set $A$ is infinite if there exists an injection $f: \mathbb{N} \to B$.

Any insight would be appreciated. Thanks!

$\endgroup$
11
  • 1
    $\begingroup$ Your part $a$ seems fine, good use of diagonal argument, though I think you meant to write $b \notin f(\mathbb N)$ rather than $b \neq f(\mathbb N)$ $\endgroup$ Jul 11, 2021 at 18:26
  • 1
    $\begingroup$ The only case in which the product is countable is when it is finite, i.e. only finitely many of the sets have more than one element. $\endgroup$ Jul 11, 2021 at 18:35
  • 1
    $\begingroup$ @Karam. We actually can use the same technique as part $a$, just shifted over by the given $N$! However, we must assume that $A_1, \ldots, A_{N - 1}$ are nonempty. In particular, for given $f: \mathbb N \to A$ chose $b$ such that $b_i \neq \alpha^{i + N}_i$. By repeating you previous argument see that $A$ is uncountable so long as $A_1, \ldots A_{N - 1}$ are nonempty. If any of the $A_1, \ldots A_{N -1}$ are empty then $A = \emptyset$. So the answer is $A$ is either empty or uncountable ,with either option being satisfiable. $\endgroup$ Jul 11, 2021 at 18:39
  • 1
    $\begingroup$ Sorry, one equation in my above comment was wrong, I meant to write $b_{i + N} \neq \alpha^{i + N}_{i + N}$, where the $\alpha$ are as given in your part $a$ $\endgroup$ Jul 11, 2021 at 18:49
  • 1
    $\begingroup$ I think this is a textbook problem from An Introduction to Abstract Mathematics by Bond and Keane. That context could help. $\endgroup$
    – Mark S.
    Jul 11, 2021 at 19:37

1 Answer 1

2
$\begingroup$

Your proof of part (a) is correct, a nice application of diagonal argument.

For part (b), you can consider it as follows: $$\left|\prod_{i=0}^{\infty}{A_i}\right|=\left|\prod_{i=0}^{N}{A_i}\right|\cdot\left|\prod_{i=N+1}^{\infty}{A_i}\right|$$

You argument in part (a) has already shown that the second term on the RHS is uncountable. Since each $A_i$ is nonempty, the whole product must be uncountable. To illustrate this idea clearly, you can take the argument given by @user2628206 in the comment.

For part (c), the term $\displaystyle\prod_{i=N+1}^{\infty}{A_i}$ is a singleton since it is assumed that $|A_i|=1$ for $i>N$, so $$\left|\prod_{i=0}^{\infty}{A_i}\right|=\left|\prod_{i=0}^{N}{A_i}\right|=\prod_{i=0}^{N}{|A_i|}.$$ The answer is then undetermined:

  1. If each $A_i$ is at most countable (i.e., finite or countably infinite), then the product is at most countable.

  2. If there is one uncountable $A_i$, then the product is uncountable, e.g., $\Bbb R\times\Bbb Q$.

The only difference between part (d) and part (c) is the injection $f:\Bbb N\to A$. This suggests that $A$ must be infinite. Thus again,

  1. If no $A_i$ is uncountable, then the product is countably infinite;

  2. If at least one $A_i$ is uncountable, then the product is uncountable.

$\endgroup$

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.