La preuve de l'union de deux ensembles dénombrables est dénombrable [fermé]

Question

Je pense que j'ai quelques indices sur la façon de prouver cela pour deux ensembles dénombrables disjoints, mais je ne sais pas comment gérer deux ensembles dénombrables ordinaires. Je voudrais demander quelques conseils. Merci. Ce serait également bien d'avoir une preuve rigoureuse.

Answer 1

Joli problème. Ce problème jette les bases de la résolution de nombreux problèmes, je vais donc écrire une solution très détaillée.

Commençons par être d'accord.

Définition 1: On dit que l'ensemble$A$ a la même cardinalité que set $B$ existe-t-il $f: A \to B$c'est un à un et sur. Dans ce cas, nous écrivons$A\sim B$.

Définition 2: Nous disons que$A$ est dénombrable si $\mathbb{N}\sim A$. Un ensemble infini qui n'est pas dénombrable est appelé un ensemble indénombrable.

Par exemple, nous pouvons voir que:

L'ensemble $\mathbb{Q}$ est dénombrable mais l'ensemble $\mathbb{R}$ est indénombrable.

Votre problème, nous pouvons écrire comme:

Laisser $A$ et $B$ensemble dénombrable. Prouve-le$A\cup B$ est dénombrable.

Preuve: Par définition$\color{blue}{(2)}$, nous devons montrer que $\mathbb{N}\sim A\cup B$, donc par définition $\color{blue}{(1)}$ nous devons prouver que $\color{blue}{\text{there exists}}$ une fonction $f: \mathbb{N}\to A\cup B$ et cela $f$ est une fonction $\color{blue}{\text{one-to-one}}$ et $\color{blue}{\text{onto}}$.

En mathématiques, il est important, comme je l'ai fait plus haut, d'écrire ce que vous devez prouver en fonction des résultats que vous souhaitez utiliser. Revenons maintenant aux hypothèses du problème.

Depuis que $A$ est un ensemble dénombrable, donc $\color{blue}{\text{there exists}}$ une fonction $g: \mathbb{N}\to A$ tel que $g$ est une fonction $\color{blue}{\text{one-to-one}}$ et $\color{blue}{\text{onto}}$. Similaire, depuis que$B$ est un ensemble dénombrable, donc $\color{blue}{\text{there exists}}$ une fonction $h: \mathbb{N}\to B$ tel que $h$ est une fonction $\color{blue}{\text{one-to-one}}$ et $\color{blue}{\text{onto}}$.

Une chose courante en mathématiques est d'essayer d'utiliser des preuves de théorèmes déjà éprouvés, comme modèles pour construire de nouvelles preuves. Si vous avez déjà prouvé que les naturels sont dénombrables, alors vous vous souviendrez que quelque chose comme "séparer les nombres pairs et impairs puis les joindre par une règle de correspondance (une fonction)" a été fait.

Laisser, $$f: \mathbb{N}\to A\cup B$$ Défini par $$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.$$

Il est clair que $f$ est une fonction $\color{blue}{\text{one-to-one}}$ et $\color{blue}{\text{onto}}$.

Maintenant, il est temps pour vous de travailler. Vous devez prouver que la fonction$f$ est vraiment $\color{blue}{\text{one-to-one}}$ et $\color{blue}{\text{onto}}$.