Two Analysis Problems

Recently I heard two problems in analysis, both I think are interesting, and they do not require too deep knowledge in analysis, which is the kind of questions I like most. Share here.

1) Suppose converges. Also, for each positive integer k, it is known that (just to avoid confusion, allow me clarify here that jk means "j times k"). Prove that for all positive integers i.

2) S contains all elements such that for any , there exists a rational number (where p,q are positive integers) satisfying . Prove that S is uncountable.

Two Problems about Countability

Recently I heard two related problems about countability. They should be good exercises for mathematial analysis amateur.

Below N denotes the set of natural numbers.

The first question is, is there exists an uncountable collection of finite subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?

The second question is, is there exists an uncountable collection of subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?

------

The first question is very easy. The second question is a bit tricky.

可數性（countability）

大家知道，如果一個集的元素可以和正整數集 N 的元素一一對應的話，那麼這個集稱為可數的（countable）。例如：整數集 Z 是可數的，因為它可以和 N 作一一對應：

1←→0、2←→1、3←→ -1、4←→2、5←→ -2、6←→3、7←→ -3、……

換句話說，如果一個集的所有元素可以「順序列出來」，則它是可數的：

0、1、-1、2、-2、3、-3、……

以下是兩個「證明」，大家看看有甚麼問題：

(1) 0 和 1 之間的所有實數（不包括 0 和 1）是可數的

證明：我們只需把 0 和 1 之間的所有實數「順序列出來」即可：

0.1, 0.2, 0.3, ..., 0.9, 0.01, 0.02, ..., 0.99, 0.001, 0.002, ..., 0.999, 0.0001, ...

(2) 所有以整數為系數的多項式是不可數的

證明：假設所有以整數為系數的多項式是可數的，則存在一一對應

1 ←→ a₁₀ + a₁₁x + a₁₂x² + a₁₃x³ + ...
2 ←→ a₂₀ + a₂₁x + a₂₂x² + a₂₃x³ + ...
3 ←→ a₃₀ + a₃₁x + a₃₂x² + a₃₃x³ + ...
4 ←→ a₄₀ + a₄₁x + a₄₂x² + a₄₃x³ + ...
......

考慮 f(x) = (a₁₀+1) + (a₂₁+1)x + (a₃₂+1)x² + (a₄₃+1)x³ + ...，則顯然 f(x) 不等於以上任何一個多項式，這跟一一對應的意義矛盾，因此所有以整數為系數的多項式是不可數的。

Mission Impossible?

哈，今日又聽到一條看似"mission impossible"的問題。我想這題用英文會好理解一點：

There is a submarine which is located at some integer point on the real axis at the 0th second. It moves with uniform velocity k units / sec, where k is an integer (possibly negative). As the submarine is deep under the water, you cannot see it. Every second you are allowed to fire a missile at some integer point. Find a way to fire the missiles so that you are guaranteed to fire at the submarine.