Bukti penyatuan dua set yang dapat dihitung dapat dihitung [ditutup]

Question

Saya pikir saya punya beberapa petunjuk untuk bagaimana membuktikan itu untuk dua set yang dapat dihitung yang terputus-putus, tetapi saya tidak tahu bagaimana menangani dua set yang dapat dihitung biasa. Saya ingin meminta beberapa nasihat. Terima kasih. Ini juga akan menyenangkan untuk memiliki bukti yang kuat.

Answer 1

Masalah bagus. Masalah ini meletakkan dasar untuk menyelesaikan banyak masalah, jadi saya akan menulis solusi yang sangat rinci.

Mari kita mulai dengan menyetujui.

Definisi 1: Kami mengatakan bahwa himpunan$A$ memiliki kardinalitas yang sama dengan himpunan $B$ apakah ada $f: A \to B$itu satu-ke-satu dan ke atas. Dalam hal ini, kami menulis$A\sim B$.

Definisi 2: Kami mengatakan itu$A$ dapat dihitung jika $\mathbb{N}\sim A$. Himpunan tak hingga yang tak terhitung disebut himpunan tak terhitung.

Misalnya, kita dapat melihat bahwa:

Set $\mathbb{Q}$ bisa dihitung tapi set $\mathbb{R}$ tidak terhitung.

Masalah Anda, kami dapat menulis sebagai:

Membiarkan $A$ dan $B$set yang dapat dihitung. Buktikan itu$A\cup B$ dapat dihitung.

Bukti: Menurut definisi$\color{blue}{(2)}$, kami perlu menunjukkannya $\mathbb{N}\sim A\cup B$, jadi menurut definisi $\color{blue}{(1)}$ kita perlu membuktikannya $\color{blue}{\text{there exists}}$ sebuah fungsi $f: \mathbb{N}\to A\cup B$ dan itu $f$ adalah sebuah fungsi $\color{blue}{\text{one-to-one}}$ dan $\color{blue}{\text{onto}}$.

Dalam matematika itu penting, seperti yang telah saya lakukan di atas untuk menulis apa yang harus Anda buktikan dalam kaitannya dengan hasil yang ingin Anda gunakan. Sekarang, mari kita kembali ke hipotesis masalahnya.

Sejak itu $A$ adalah set yang dapat dihitung, jadi $\color{blue}{\text{there exists}}$ sebuah fungsi $g: \mathbb{N}\to A$ seperti yang $g$ adalah sebuah fungsi $\color{blue}{\text{one-to-one}}$ dan $\color{blue}{\text{onto}}$. Mirip, sejak itu$B$ adalah set yang dapat dihitung, jadi $\color{blue}{\text{there exists}}$ sebuah fungsi $h: \mathbb{N}\to B$ seperti yang $h$ adalah sebuah fungsi $\color{blue}{\text{one-to-one}}$ dan $\color{blue}{\text{onto}}$.

Sesuatu yang umum dalam matematika adalah mencoba menggunakan bukti dari teorema yang sudah terbukti, sebagai model untuk membangun bukti baru. Jika Anda pernah membuktikan bahwa alam dapat dihitung, maka Anda akan ingat bahwa sesuatu seperti "pisahkan bilangan ganjil dan genap dan kemudian gabungkan dengan aturan korespondensi (fungsi)" telah dilakukan.

Membiarkan, $$f: \mathbb{N}\to A\cup B$$ didefinisikan oleh $$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.$$

Jelas itu $f$ adalah sebuah fungsi $\color{blue}{\text{one-to-one}}$ dan $\color{blue}{\text{onto}}$.

Sekarang, saatnya Anda bekerja. Anda harus membuktikan bahwa fungsinya$f$ benar-benar $\color{blue}{\text{one-to-one}}$ dan $\color{blue}{\text{onto}}$.