We have a set that contains sequences of integers, so that every sequence of integers has a subsequence that is in this set. Is this uncountable? If so, could you prove it?
I know that set of all sequences of integers is uncountable. Now, I want to prove that the set I was taking about, let call it S is uncountable. Let it be countable (proof by contradiction). Know, I don't know how I should define function from set of natural numbers to this set. This is where I stuck.
Lemma. Let $\mathcal P_\infty(\Bbb N)$ denote the set of all infinite subsets of $\Bbb N$. Suppose $A_1,A_2,A_3,\ldots $ are countably many elements of $\mathcal P_\infty(\Bbb N)$. Then there exists $X\in \mathcal P_\infty(\Bbb N)$ such that $\forall k\in\Bbb N, A_k\not\subseteq X$.
Proof. Let $a_k:=\min\{\,x\in A_k\mid x>2k\,\}$ (possible because $A_k$ is infnite) and $X=\Bbb N\setminus\{\,a_k\mid k\in\Bbb N\,\}$. Then $X$ is infnite because it lacks at most $n$ of the numbers $\{1,\ldots, 2n\}$. And clearly, $a_k\in A_k\setminus X$. $\square$
Now for the original problem: Let $S$ be a set of sequences such that every sequence of ontegers has a subsequence that is in $S$. If we pick a strictly increasing sequence of integers, any subsequence will also be strictly increasing, and a strictly increasing sequence $x_1,x_2,x_3,\ldots$ is a subsequence of a strictly increasing sequence $y_1,y_2,y_3,\ldots$ if and only if $\{x_1,x_2,\ldots\}\subseteq \{y_1,y_2,\ldots\}$. Thus from the lemma, we conclude that $S$ is uncountable (already the strictly increasing sequences must be uncountably many).