Sayılabilir iki kümenin birleşiminin kanıtı sayılabilir [kapalı]

Dec 25 2020

Sanırım iki ayrık sayılabilir küme için bunu nasıl kanıtlayacağıma dair bazı ipuçlarım var, ancak iki sıradan sayılabilir kümeyle nasıl başa çıkacağımı bilmiyorum. Bir tavsiye almak istiyorum. Teşekkürler. Ayrıca kesin bir kanıta sahip olmak güzel olurdu.

Yanıtlar

4 Александр Dec 25 2020 at 11:17

Güzel sorun. Bu problem birçok problemin çözümünün temelini oluşturuyor, bu yüzden çok detaylı bir çözüm yazacağım.

Anlaşarak başlayalım.

Tanım 1: Setin$A$ set ile aynı temelliğe sahiptir $B$ var mı $f: A \to B$bu bire bir ve üzerine. Bu durumda yazıyoruz$A\sim B$.

Tanım 2: Bunu söylüyoruz$A$ sayılabilir eğer $\mathbb{N}\sim A$. Sayılamayan sonsuz kümeye sayılamayan küme denir.

Örneğin şunu görebiliriz:

Set $\mathbb{Q}$ sayılabilir ama set $\mathbb{R}$ sayılamaz.

Sorunu şu şekilde yazabiliriz:

İzin Vermek $A$ ve $B$sayılabilir küme. Kanıtla$A\cup B$ sayılabilir.

İspat: Tanıma göre$\color{blue}{(2)}$bunu göstermemiz gerek $\mathbb{N}\sim A\cup B$yani tanımı gereği $\color{blue}{(1)}$ bunu kanıtlamamız gerekiyor $\color{blue}{\text{there exists}}$ bir işlev $f: \mathbb{N}\to A\cup B$ ve şu $f$ bir işlev $\color{blue}{\text{one-to-one}}$ ve $\color{blue}{\text{onto}}$.

Matematikte, yukarıda yaptığım gibi, kullanmak istediğiniz sonuçlar açısından ispatlamanız gerekenleri yazmak önemlidir. Şimdi problemin hipotezlerine geri dönelim.

O zamandan beri $A$ sayılabilir küme, yani $\color{blue}{\text{there exists}}$ bir işlev $g: \mathbb{N}\to A$ öyle ki $g$ bir işlevdir $\color{blue}{\text{one-to-one}}$ ve $\color{blue}{\text{onto}}$. Benzer, ondan beri$B$ sayılabilir küme, yani $\color{blue}{\text{there exists}}$ bir işlev $h: \mathbb{N}\to B$ öyle ki $h$ bir işlev $\color{blue}{\text{one-to-one}}$ ve $\color{blue}{\text{onto}}$.

Matematikte yaygın olan bir şey, yeni ispatlar oluşturmak için modeller olarak zaten kanıtlanmış teoremlerin kanıtlarını kullanmaya çalışmaktır. Doğalların sayılabilir olduğunu daha önce kanıtladıysanız, "tek ve çift sayıları ayırın ve sonra bunları bir yazışma kuralı (bir işlev) ile birleştirin" gibi bir şeyin yapıldığını hatırlayacaksınız.

İzin Vermek, $$f: \mathbb{N}\to A\cup B$$ tarafından tanımlandı $$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.$$

Açık ki $f$ bir işlev $\color{blue}{\text{one-to-one}}$ ve $\color{blue}{\text{onto}}$.

Şimdi, çalışma zamanın geldi. İspat etmelisiniz ki fonksiyon$f$ gerçek $\color{blue}{\text{one-to-one}}$ ve $\color{blue}{\text{onto}}$.