2つの可算集合の和集合の証明は可算です[クローズ]

いい問題です。この問題は多くの問題を解決するための基礎を築くので、私は非常に詳細な解決策を書きます。

同意することから始めましょう。

定義1：セットと言う$A$ セットと同じカーディナリティを持っています $B$ 存在しますか $f: A \to B$それは1対1であり、上にあります。この場合、$A\sim B$。

定義2：私たちはそれを言います$A$ 次の場合は可算です $\mathbb{N}\sim A$。可算でない無限集合は、非可算集合と呼ばれます。

たとえば、次のことがわかります。

セット $\mathbb{Q}$ 可算ですが、セット $\mathbb{R}$ 数えられないです。

あなたの問題、私たちは次のように書くことができます：

しましょう $A$ そして $B$可算集合。証明してください$A\cup B$ 可算です。

証明：定義上$\color{blue}{(2)}$、それを示す必要があります $\mathbb{N}\sim A\cup B$、定義上 $\color{blue}{(1)}$ それを証明する必要があります $\color{blue}{\text{there exists}}$ 機能 $f: \mathbb{N}\to A\cup B$ そしてそれ $f$ 関数です $\color{blue}{\text{one-to-one}}$ そして $\color{blue}{\text{onto}}$。

数学では、上で行ったように、使用したい結果に関して証明しなければならないことを書くことが重要です。それでは、問題の仮説に戻りましょう。

それ以来 $A$ 可算集合なので $\color{blue}{\text{there exists}}$ 機能 $g: \mathbb{N}\to A$ そのような $g$ は関数です $\color{blue}{\text{one-to-one}}$ そして $\color{blue}{\text{onto}}$。同様に、それ以来$B$ 可算集合なので $\color{blue}{\text{there exists}}$ 機能 $h: \mathbb{N}\to B$ そのような $h$ 関数です $\color{blue}{\text{one-to-one}}$ そして $\color{blue}{\text{onto}}$。

数学で一般的なことは、新しい証明を構築するためのモデルとして、すでに証明された定理の証明を使用しようとすることです。ナチュラルが可算であることを証明したことがあるなら、「奇数と偶数を分けて、対応規則（関数）でそれらを結合する」のようなことが行われたことを覚えているでしょう。

しましょう、 $$f: \mathbb{N}\to A\cup B$$ によって定義されます $$f(x):=\left\{\begin{aligned}h\left( \frac{n}{2}\right), \quad \text{n is even}\\ g\left( \frac{n+1}{2}\right), \quad \text{n is odd} \end{aligned} \right.$$

それは明らかです $f$ 関数です $\color{blue}{\text{one-to-one}}$ そして $\color{blue}{\text{onto}}$。

さあ、あなたが働く時が来ました。あなたはその機能が$f$ 本当に $\color{blue}{\text{one-to-one}}$ そして $\color{blue}{\text{onto}}$。