Dowód połączenia dwóch policzalnych zbiorów jest policzalny [zamknięty]

Dec 25 2020

Myślę, że mam kilka wskazówek, jak to udowodnić dla dwóch rozłącznych policzalnych zestawów, ale nie wiem, jak sobie radzić z dwoma zwykłymi policzalnymi zestawami. Chciałbym prosić o radę. Dzięki. Byłoby też miło mieć rygorystyczny dowód.

Odpowiedzi

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

Niezły problem. Ten problem stanowi podstawę do rozwiązania wielu problemów, dlatego napiszę bardzo szczegółowe rozwiązanie.

Zacznijmy od zgody.

Definicja 1: Mówimy, że zbiór$A$ ma taką samą liczność jak zbiór $B$ czy istnieje $f: A \to B$to jest jeden do jednego i na. W takim przypadku piszemy$A\sim B$.

Definicja 2: Tak mówimy$A$ jest policzalne, jeśli $\mathbb{N}\sim A$. Nieskończony zbiór, którego nie można policzyć, nazywa się zbiorem niepoliczalnym.

Na przykład widzimy, że:

Zestaw $\mathbb{Q}$ jest policzalne, ale zbiór $\mathbb{R}$ jest niepoliczalna.

Twój problem możemy napisać jako:

Pozwolić $A$ i $B$policzalny zestaw. Udowodnij to$A\cup B$ jest policzalna.

Dowód: z definicji$\color{blue}{(2)}$, musimy to pokazać $\mathbb{N}\sim A\cup B$, więc z definicji $\color{blue}{(1)}$ musimy to udowodnić $\color{blue}{\text{there exists}}$ funkcja $f: \mathbb{N}\to A\cup B$ i to $f$ jest funkcją $\color{blue}{\text{one-to-one}}$ i $\color{blue}{\text{onto}}$.

W matematyce ważne jest, tak jak zrobiłem powyżej, aby napisać, co musisz udowodnić pod względem wyników, których chcesz użyć. Wróćmy teraz do hipotez problemu.

Od tego czasu $A$ jest policzalny zbiorem, więc $\color{blue}{\text{there exists}}$ funkcja $g: \mathbb{N}\to A$ takie że $g$ jest funkcją $\color{blue}{\text{one-to-one}}$ i $\color{blue}{\text{onto}}$. Podobnie, od tego czasu$B$ jest policzalny zbiorem, więc $\color{blue}{\text{there exists}}$ funkcja $h: \mathbb{N}\to B$ takie że $h$ jest funkcją $\color{blue}{\text{one-to-one}}$ i $\color{blue}{\text{onto}}$.

Coś powszechnego w matematyce to próba wykorzystania dowodów już udowodnionych twierdzeń jako modeli do budowania nowych dowodów. Jeśli kiedykolwiek udowodniłeś, że liczby naturalne są policzalne, to pamiętasz, że coś w rodzaju „oddziel liczby nieparzyste i parzyste, a następnie połącz je zgodnie z regułą korespondencji (funkcją)”.

Pozwolić, $$f: \mathbb{N}\to A\cup B$$ określony przez $$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.$$

Jest oczywiste, że $f$ jest funkcją $\color{blue}{\text{one-to-one}}$ i $\color{blue}{\text{onto}}$.

Teraz czas na pracę. Musisz udowodnić, że funkcja$f$ jest naprawdę $\color{blue}{\text{one-to-one}}$ i $\color{blue}{\text{onto}}$.