-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dowod Unikalnosci Elementow Zbioru Rodziny Zbiorow Nietautologii.tex
54 lines (43 loc) · 3.37 KB
/
Dowod Unikalnosci Elementow Zbioru Rodziny Zbiorow Nietautologii.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
Niech $\mathbb{X} \subseteq \mathbb{N}$ taki, że:
\begin{itemize}
\item $1 \in \mathbb{X}$, oraz
\item $2 \in \mathbb{X}$, oraz
\item $3 \in \mathbb{X}$, oraz
\item dla dowolnego $n \in \mathbb{N}$, $n \geq 2$, jeśli $n \in \mathbb{X}$ oraz $(n + 1) \in \mathbb{X}$, to $(n + 2) \in \mathbb{X}$
\end{itemize}
Wtedy $\mathbb{X} = \mathbb{N}$
\n
\noindent
Niech $\mathbb{X} = \{n \in \mathbb{N} | \mathbb{NT}_n$ zawiera unikalne wartości$\}$
\n
\noindent
W dowodzie skorzystamy z powyższej zasady indukcji.
\n
\noindent
Dowód indukcyjny:
\n
\noindent
Podstawa indukcji:
\begin{itemize}
\item $1 \in \mathbb{X}$, bo $\mathbb{NT}_1 = \{0, 1\}$
\item $2 \in \mathbb{X}$, bo $\mathbb{NT}_2 = \{01, 10\}$
\item $3 \in \mathbb{X}$, bo $\mathbb{NT}_3 = \{101, 010, 000, 001, 110, 111\}$
\end{itemize}
\noindent
Krok indukcyjny:
\n
\noindent
Weźmy dowolne $n \in \mathbb{N}, n \geq 2$. Załóżmy, że $n \in \mathbb{X}$ i $(n + 1) \in \mathbb{X}$. Pokażemy, że $(n + 2) \in \mathbb{X}$.
\n
\noindent
Załóżmy nie wprost, że $\mathbb{NT}_{n + 2}$ zawiera duplikaty. Zatem istnieją takie $i, j$, że $i \neq j$ i $\mathbb{NT}_{n + 2, i} = \mathbb{NT}_{n + 2, j}$. Rozważmy wszystkie przypadki, w jaki sposób mogliśmy stworzyć elementy $\mathbb{NT}_{n + 2, i}$ i $\mathbb{NT}_{n + 2, j}$:
\begin{itemize}
\item Elementy $\mathbb{NT}_{n + 2, i}$, $\mathbb{NT}_{n + 2, j}$ powstały z elementów zbioru $\mathbb{NT}_n$ poprzez dodanie $"00"$ lub $"11"$. Zauważmy, że skoro $\mathbb{NT}_{n + 2, i} = \mathbb{NT}_{n + 2, j}$, to w całości są takie same, więc w szczególności ostatnia operacja była taka sama i elementy, z których powstały elementy $\mathbb{NT}_{n + 2, i}$ i $\mathbb{NT}_{n + 2, j}$ też były. Czyli istnieją $i\prime, j\prime$ takie, że $i\prime \neq j\prime$ i $\mathbb{NT}_{n, i\prime} = \mathbb{NT}_{n, j\prime}$. Sprzeczność \lightning (bo z założenia indukcyjnego $\mathbb{NT}_n \in X$, czyli zbiór $\mathbb{NT}_n$ nie zawiera duplikatów).
\item Elementy $\mathbb{NT}_{n + 2, i}$, $\mathbb{NT}_{n + 2, j}$ powstały z elementów zbioru $\mathbb{NT}_{n + 1}$ poprzez dodanie "przeciwnej cyfry". Zauważmy, że skoro $\mathbb{NT}_{n + 2, i} = \mathbb{NT}_{n + 2, j}$, to w całości są takie same, więc w szczególności ostatnia operacja była taka sama i elementy, z których powstały elementy $\mathbb{NT}_{n + 2, i}$ i $\mathbb{NT}_{n + 2, j}$ też były. Czyli istnieją $i\prime, j\prime$ takie, że $i\prime \neq j\prime$ i $\mathbb{NT}_{n + 1, i\prime} = \mathbb{NT}_{n + 1, j\prime}$. Sprzeczność \lightning (bo z założenia indukcyjnego $\mathbb{NT}_{n + 1} \in X$, czyli zbiór $\mathbb{NT}_{n + 1}$ nie zawiera duplikatów).
\item BSO: Załóżmy, że $\mathbb{NT}_{n + 2, i}$ został stworzony z elementu zbioru $\mathbb{NT}_n$, a $\mathbb{NT}_{n + 2, j}$ został stworzony z elementu zbioru $\mathbb{NT}_{n + 1}$. Zauważmy, że skoro $\mathbb{NT}_{n + 2, i} = \mathbb{NT}_{n + 2, j}$, to w całości są takie same, więc w szczególności pierwsze 2 znaki są takie same. Sprzeczność \lightning (bo pierwsze 2 znaki $\mathbb{NT}_{n + 2, i} \in \{"00", "11"\}$, a pierwsze 2 znaki $\mathbb{NT}_{n + 2, j} \in \{"01", "10"\}$).
\end{itemize}
\noindent
We wszystkich przypadkach otrzymaliśmy sprzeczność, zatem $(n + 2) \in \mathbb{X}$.
\n
\noindent
To znaczy, że na mocy tw. o indukcji $\mathbb{X} = \mathbb{N}$, czyli $\mathbb{NT}_n$ zawiera unikalne wartości.