Dowód indukcyjny o mocy zbioru potęgowego

[hack2yrjoy]

Mamy do wykazania indukcyjnie, że jeżeli zbiór \(\displaystyle{ A}\) ma \(\displaystyle{ n}\) elementów, to wszystkich podzbiorów zbioru \(\displaystyle{ A}\) jest \(\displaystyle{ 2^{n}}\), tzn. \(\displaystyle{ \left|P(A)\right| = 2^{n}}\).
Zacznijmy od sprawdzenia czy jest to prawdziwe dla \(\displaystyle{ n = 0}\). Oczywiście zbiór \(\displaystyle{ A = \emptyset}\), więc \(\displaystyle{ P(A) = \{\emptyset\}}\), czyli \(\displaystyle{ \left| P(A) \right| = 1 = 2^{0}}\). Czyli jest to prawda dla \(\displaystyle{ n = 0}\).
Załóżmy teraz, że prawdą jest, że jeżeli zbiór \(\displaystyle{ S}\) ma \(\displaystyle{ k}\) elementów dla jakiegoś \(\displaystyle{ k \geq 0}\), to \(\displaystyle{ \left|P(S)\right| = 2^{k}}\). Sprawdzimy, czy jest to także prawda dla \(\displaystyle{ k + 1}\). Stwórzmy nowy zbiór \(\displaystyle{ T = S \cup \{ t \}}\), gdzie \(\displaystyle{ t}\) jest inny od dowolnego \(\displaystyle{ s \in S}\)(tzn \(\displaystyle{ S \cap \{ t \} = \emptyset}\)). W ten sposób \(\displaystyle{ \left| T \right| = k + 1}\). Weźmy funkcję \(\displaystyle{ f: P(T) \rightarrow P(S)}\), o wzorze \(\displaystyle{ f(K) = K \setminus \{ t \}}\). W ten sposób utworzyliśmy funkcję która jest dwa do jednego. Ponieważ, jeżeli wieźmiemy dowolny element \(\displaystyle{ R \in P(S)}\), wtedy odpowiada on tożsamemu elementowi \(\displaystyle{ K = R}\) oraz elementowi \(\displaystyle{ R \cup \{ t \}}\). Jest to oczywiście surjekcja, odkąd \(\displaystyle{ P(S) \subset P(T)}\). Skoro \(\displaystyle{ \left|P(S)\right| = 2^{k}}\)(z założenia), a elementów zbioru \(\displaystyle{ P(T)}\) jest dwa razy więcej, to \(\displaystyle{ \left|P(T)\right| = 2\left|P(S)\right| = 2 \times 2^k = 2^{k + 1}}\) co kończy dowód. Tak więc prawdą jest, że jeżeli \(\displaystyle{ \left| A \right| = n}\) dla dowolnego \(\displaystyle{ n \geq 0}\), to ma on \(\displaystyle{ 2^{n}}\) podzbiorów.
Czy jest to dowód przeprowadzony poprawnie? Nie jestem pewny czy koniecznie muszę jakoś szczególnie dowodzić, że funkcja \(\displaystyle{ f}\) jest "na"(choć wydaje mi się, że to co napisałem jest wystarczające).

[Jan Kraszewski]

Ten dowód nie jest dobry (choć opiera się na dobrym pomyśle), bo nawet sformułowanie twierdzenia nie jest poprawne. Dokładniej - nie wiadomo, jak wygląda teza, którą próbujesz udowodnić indukcyjnie. A bez tego nie da się poprawnie przeprowadzić dowodu kroku indukcyjnego.

Poprawnie sformułowane twierdzenie wygląda tak:

\(\displaystyle{ (\forall n\in\NN)(\forall A)(|A|=n \Rightarrow |P(A)|=2^n).}\)

JK

[hack2yrjoy]

Ten dowód nie jest dobry (choć opiera się na dobrym pomyśle), bo nawet sformułowanie twierdzenia nie jest poprawne. Dokładniej - nie wiadomo, jak wygląda teza, którą próbujesz udowodnić indukcyjnie. A bez tego nie da się poprawnie przeprowadzić dowodu kroku indukcyjnego.

Poprawnie sformułowane twierdzenie wygląda tak:

\(\displaystyle{ (\forall n\in\NN)(\forall A)(|A|=n \Rightarrow |P(A)|=2^n).}\)

JK

Co jest konkretnie złego w powyższym dowodzie? Jeżeli chodzi o tezę, to ma pan na myśli że przeszedłem do dowodzenia bez konkretnego nakreślenia co właściwie dowodzę?

[Jan Kraszewski]

Jak chcesz rozważać poprawność dowodu nie mając porządnie określone, co dowodzisz?

Zasada Indukcji Matematycznej (ZIM) mówi, że jeśli masz formułę \(\displaystyle{ \varphi(n)}\), gdzie \(\displaystyle{ n\in\NN}\), taką że \(\displaystyle{ \varphi(0)}\) i \(\displaystyle{ (\forall n\in\NN)(\varphi(n) \Rightarrow \varphi(n+1))}\), to wówczas \(\displaystyle{ (\forall n\in\NN)\varphi(n)}\). Zatem jeżeli chcesz przeprowadzić dowód, w którym stosujesz ZIM, to musisz najpierw określić, czym jest \(\displaystyle{ \varphi(n)}\).

W Twoim rozumowaniu nie wiadomo, czym jest \(\displaystyle{ \varphi(n)}\), więc nie wiadomo, co dowodzisz.

JK

[janusz47]

Przykład

Niech \(\displaystyle{ X = \{1, 2\}}\) wtedy \(\displaystyle{ |P(X)| = 2^2 = 4}\) elementy

\(\displaystyle{ P(X) = \{ \emptyset, \{1\}, \{2\}, X \}.}\)

Niech \(\displaystyle{ Y = X \cup \{3\}}\) wtedy \(\displaystyle{ |P(Y)| = |X \cup \{3\}| = 2^{2}+ 2^{2} = 2\cdot 2^2 = 8}\) -elementów.

Tabelka
\(\displaystyle{ \begin{tabular}{|c|c|} \hline
Podzbiory zbioru X & Nowe podzbiory \\ \hline
\emptyset & \{3\} \\ \hline
\{1\} & \{1, 3\} \\ \hline
\{2\} & \{2, 3\} \\ \hline
X & Y \\ \hline
\end{tabular}}\)

[Jan Kraszewski]

janusz47, ale co to ma do rzeczy? Twój przykład niczego nie wnosi.

Pomysł hack2yrjoy był (w jakimś sensie) dobry, tylko strona formalna była zła.

JK

[janusz47]

Przykłady wnoszą wiele do dowodu, zwłaszcza wtedy, gdy dowód się komplikuje.

Mam pytanie Panie Kraszewski, co Pan edytował w moim poście?

[Jan Kraszewski]

Mam pytanie Panie Kraszewski, co Pan edytował w moim poście?

Było "Niech \(\displaystyle{ Y = X \cup {3}}\)" - nie zakodowałeś klamer.

Nawiasem mówiąc, to co napisałeś

wtedy \(\displaystyle{ |P(Y)| \red= |X \cup \{3\}|\black = 2^{2}+ 2^{2} = 2\cdot 2^2 = 8}\) -elementów.

też jest niepoprawne, bo zgubiłeś \(\displaystyle{ P}\).

JK

[Bran]

Skorzystajmy z zaproponowanej wcześniej formy twierdzenia:

Poprawnie sformułowane twierdzenie wygląda tak:

\(\displaystyle{ (\forall n\in\NN)(\forall A)(|A|=n \Rightarrow |P(A)|=2^n).}\)

Dowód indukcyjny.

Pierwszy krok:
Sprawdzamy czy twierdzenie jest prawdziwe dla \(\displaystyle{ n = 0}\).
Jeżeli \(\displaystyle{ |A| = 0}\), to oznacza, że żaden element nie należy do tego zbioru, zatem zbiór \(\displaystyle{ A = \emptyset}\). Zbiór potęgowy zbioru \(\displaystyle{ A}\), tj. \(\displaystyle{ P(A) = {\emptyset}}\) ma jeden element (jak widać).
Zatem prawdą jest, że jeśli \(\displaystyle{ |A| = 0}\), to \(\displaystyle{ P(A) = 2^0 = 1}\).

Ukryta treść:    

Tak jak zauważyłeś w swoim głównym poście.

Założenie indukcyjne:
Weźmy dowolną liczbę \(\displaystyle{ n}\) i załóżmy, że \(\displaystyle{ |A| = n \Rightarrow |P(A)| = 2^n.}\)

Drugi krok:
Sprawdźmy, czy prawdą jest \(\displaystyle{ |T| = n+1 \Rightarrow |P(T)| = 2^{n+1}.}\)

Ukryta treść:    

Idąc za Twoim pomysłem.

Niech zbiór \(\displaystyle{ T = A \cup \left\{ t\right\}}\), gdzie \(\displaystyle{ t \notin A}\).
Zbiór \(\displaystyle{ T}\) ma zatem \(\displaystyle{ n + 1}\) elementów.

Weźmy funkcję \(\displaystyle{ f: P(T) \rightarrow P(A)}\) zadaną wzorem: \(\displaystyle{ f(K) = K \setminus \left\{ t\right\}.}\)

Weźmy dowolny element \(\displaystyle{ K}\) zbioru \(\displaystyle{ P(A)}\). Wiemy, że \(\displaystyle{ t \notin A}\), zatem nie może również należeć do \(\displaystyle{ P(A)}\), tym bardziej więc do \(\displaystyle{ K.}\)
Skoro więc \(\displaystyle{ f(K) = K \setminus \left\{ t\right\}}\), to \(\displaystyle{ f(K) = K.}\)
Wiemy jednocześnie, że \(\displaystyle{ f(K \cup \left\{ t\right\} ) = K}\), bo ze wzoru funkcji mamy \(\displaystyle{ f(K \cup \left\{ t\right\} ) = \left( K \cup \left\{ t\right\}\right) \setminus \left\{ t\right\} = K.}\)

Zatem dokładnie dwa zbiory z \(\displaystyle{ P(T)}\) (\(\displaystyle{ K}\) i \(\displaystyle{ K \cup \left\{ t\right\}}\)) odpowiadają jednemu zbiorowi z \(\displaystyle{ P(A)}\) (\(\displaystyle{ K}\)).

A ponieważ mamy suriekcję, to \(\displaystyle{ \left| P(T)\right| = 2 \left| P(A)\right|.}\)
Co za tym idzie \(\displaystyle{ \left| P(T)\right| = 2 \cdot 2^n = 2^{n+1}.}\)
Ponieważ \(\displaystyle{ |T| = n + 1}\), to powyższy wynik kończy dowód.

[Janusz Tracz]

Bran powinno być (bo wcięło klamry):

Zbiór potęgowy zbioru \(\displaystyle{ A=\emptyset}\), tj. \(\displaystyle{ P(A) = \left\{ \emptyset\right\}}\)

Jeśli chodzi o dalszy dowód to nie powinno zakładać się tezy

Weźmy dowolną liczbę \(\displaystyle{ n}\) i załóżmy, że \(\displaystyle{ |A| = n}\) \(\displaystyle{ \Rightarrow}\) \(\displaystyle{ |P(A)| = 2^n}\).

Mimo, że bierzesz dowodną liczbę \(\displaystyle{ n}\) to nie zakładasz tezy a raczej robisz to przy ustalonej liczbie \(\displaystyle{ n}\). Poza tym ustalenie \(\displaystyle{ n}\) to za mało jeszcze trzeba ustać \(\displaystyle{ A}\). Można ustalić takie \(\displaystyle{ n\in\NN}\) oraz zbiór \(\displaystyle{ A}\) takie, że \(\displaystyle{ |A| = n \Rightarrow |P(A)| = 2^n}\). Takie ustalanie wynika z dwóch kwantyfikatorów które trzeba obsłużyć w tezie sformowanej przez Jan Kraszewski

\(\displaystyle{ (\forall n\in\NN)(\forall A)(|A|=n \Rightarrow |P(A)|=2^n).}\)

Jak mamy już w ręce obiekty na których pracujemy czyli \(\displaystyle{ A}\) takie, że \(\displaystyle{ \left| A\right|=n}\) to można zbiór \(\displaystyle{ A}\) powiększyć o jeden element \(\displaystyle{ t}\) (oczywiście taki, że \(\displaystyle{ t\not\in A}\)). Można to zapisać \(\displaystyle{ T = A \cup \left\{ t\right\}}\) oczywiście \(\displaystyle{ \left| T\right|=n+1}\). By policzyć ilość elementów \(\displaystyle{ P(T)}\) rozważmy dwie rozłącznie sytuacje:

\(\displaystyle{ \bullet}\) Ile jest podzbiorów \(\displaystyle{ T}\) w których nie ma \(\displaystyle{ t}\) ? Jest to pytanie o podzbiory zbioru \(\displaystyle{ A}\) których jest \(\displaystyle{ 2^n}\)

\(\displaystyle{ \bullet}\) Ile jest podzbiorów \(\displaystyle{ T}\) w których jest \(\displaystyle{ t}\) ? Jest to pytanie o podzbiory zbioru \(\displaystyle{ A}\) do których "dorzucimy" dodamy nowy element \(\displaystyle{ t}\). Dodanie \(\displaystyle{ t}\) do każdego podzbiory nie zmieni faktu, że jest ich dalej \(\displaystyle{ 2^n}\)

Zatem \(\displaystyle{ \left| P(T)\right|=2^n+2^n=2^{n+1}}\). Na mocy zasady indukcji matematycznej pokazaliśmy, że prawdą jest \(\displaystyle{ |T| = n+1 \Rightarrow |P(T)| = 2^{n+1}}\) a tym samym prawdą jest, że:

\(\displaystyle{ (\forall n\in\NN)\varphi(n)}\)

Czyli tu oznacza to tyle, że liczebność zbioru potęgowego zbioru o \(\displaystyle{ n}\) elementach wynosi \(\displaystyle{ 2^n}\). Takie podejście wydaje mi się dużo bardziej przejrzyste (szczególnie jak zrozumie się dwa powyższe podpunktu oznaczone \(\displaystyle{ \bullet}\) staje się to jasne) niż bawienia się w rozwalanie dość sztucznie definiowanych funkcji.-- 15 lip 2019, o 09:10 --PS Teraz zauważyłem, że podobny podział zaproponował janusz47. Uważam, że ta tabelka dużo wnosi bo pokazuje rozbicie \(\displaystyle{ P(T)}\) (dla \(\displaystyle{ n=3}\)) i które ja zaproponowałem w ogólnym przypadku. Podzbiory "stare" czyli bez \(\displaystyle{ t}\) i "nowe" z \(\displaystyle{ t}\).

[janusz47]

Jeśli zbiór \(\displaystyle{ A}\) jest skończony i ma \(\displaystyle{ n}\) elementów, to zbiór potęgowy \(\displaystyle{ \mathcal{P}(A)}\) ma \(\displaystyle{ 2^{n}}\) - elementów.

Dowód tego twierdzenia wynika z zasad kombinatoryki.

Istnieje bowiem wzajemnie jednoznaczne przyporządkowanie \(\displaystyle{ \mathcal{P}(A) \ni A \rightarrow \kappa(A)}\)

gdzie

\(\displaystyle{ \kappa(A) = \begin{cases} 1 \ \ \mbox{gdy} \ \ x\in{A}\\ 0 \ \ \mbox{gdy}\ \ x\notin A \end{cases}}\)

jest funkcją charakterystyczną zbioru \(\displaystyle{ A.}\)

Istotnie podzbiór zbioru \(\displaystyle{ A}\) można określić, przyporządkowując jego elementom liczby \(\displaystyle{ 1}\) bądź \(\displaystyle{ 0}\) w zależności od tego, czy zaliczamy dany element do definiowanego zbioru czy nie.

Zliczając podzbiory zbioru \(\displaystyle{ n}\) - elementowego według ich liczności, innymi słowy korzystając z faktu iż

\(\displaystyle{ \mathcal{P}(A) = \mathcal{P}_{0}(A) \cup \mathcal{P}_{1}(A) \cup ... \cup \mathcal{P}_{n}(A)}\),

otrzymujemy

\(\displaystyle{ \sum_{k=0}^{n}{n \choose k} = 2^{n}.}\)


Podzbiorów zbioru \(\displaystyle{ n}\) elementowego jest tyle, ile wariacji z powtórzeniami zbioru dwuelementowego po \(\displaystyle{ n.}\)

Stąd też oznaczenie zbioru potęgowego \(\displaystyle{ 2^{A}.}\)

[Jan Kraszewski]

Założenie indukcyjne:
Weźmy dowolną liczbę \(\displaystyle{ n}\) i załóżmy, że \(\displaystyle{ |A| = n \Rightarrow |P(A)| = 2^n.}\)

Drugi krok:
Sprawdźmy, czy prawdą jest \(\displaystyle{ |T| = n+1 \Rightarrow |P(T)| = 2^{n+1}.}\)

Przykro mi, ale oba te stwierdzenia nie są dobre. W szczególności to drugie, co znów "kładzie" dowód.

Po pierwsze, "założenie indukcyjne" wcale tak nie wygląda. Takie sformułowanie wynika z niezrozumienia, czym jest "założenie indukcyjne". Częściowo wyjaśnił to Janusz Tracz

Mimo, że bierzesz dowodną liczbę \(\displaystyle{ n}\) to nie zakładasz tezy a raczej robisz to przy ustalonej liczbie \(\displaystyle{ n}\). Poza tym ustalenie \(\displaystyle{ n}\) to za mało jeszcze trzeba ustać \(\displaystyle{ A}\). Można ustalić takie \(\displaystyle{ n\in\NN}\) oraz zbiór \(\displaystyle{ A}\) takie, że \(\displaystyle{ |A| = n \Rightarrow |P(A)| = 2^n}\). Takie ustalanie wynika z dwóch kwantyfikatorów które trzeba obsłużyć w tezie sformowanej przez Jan Kraszewski.

ale też nie zrobił tego poprawnie. Dowód kroku indukcyjnego powinien zacząć się od tego, że zakładamy, iż dla dowolnie ustalonego \(\displaystyle{ n\in\NN}\) prawdą jest, że każdy zbiór \(\displaystyle{ n}\)-elementowy ma \(\displaystyle{ 2^n}\) podzbiorów. Ustalanie zbioru \(\displaystyle{ A}\) to zdecydowanie nie jest dobry pomysł.

Ale gorzej jest później. Otóż chcemy pokazać, że dla ustalonego wcześniej \(\displaystyle{ n}\) zachodzi teza indukcyjna. Ale to oznacza, że dowolny zbiór \(\displaystyle{ n+1}\)-elementowy ma \(\displaystyle{ 2^{n+1}}\) elementów. W związku z tym wszystkie "konstrukcje" postaci \(\displaystyle{ A\cup\{t\}}\) nie są dobre, bo nie dają pewności, że dostaniemy wszystkie zbiory \(\displaystyle{ n+1}\)-elementowe. Trzeba zacząć inaczej - od ustalenia dowolnego zbioru \(\displaystyle{ n+1}\)elementowego \(\displaystyle{ S}\). A potem odejmujemy, żeby móc skorzystać z założenia indukcyjnego.

\(\displaystyle{ (\forall n\in\NN)\varphi(n)}\)

Czyli tu oznacza to tyle, że liczebność zbioru potęgowego zbioru o \(\displaystyle{ n}\) elementach wynosi \(\displaystyle{ 2^n}\).

Nie. Tu oznacza, że liczebność dowolnego zbioru potęgowego zbioru o \(\displaystyle{ n}\) elementach wynosi \(\displaystyle{ 2^n}\).

Dowód tego twierdzenia wynika z zasad kombinatoryki.

Oczywiście, ale hack2yrjoy chciał indukcyjnie.

Stąd też oznaczenie zbioru potęgowego \(\displaystyle{ 2^{A}}\).

Można dodać, że obecnie raczej już nieużywane.

JK

[Bran]

Jan Kraszewski, treść mojego założenia indukcyjnego była sformułowana bardzo niefrasobliwie i faktycznie wyszło jakbym zakładał tezę (czego zrobić nie chciałem). Mój błąd!

Natomiast nie bardzo rozumiem dlaczego:

\(\displaystyle{ |T| = n+1 \Rightarrow |P(T)| = 2^{n+1}}\)

to błąd?

[Jan Kraszewski]

Natomiast nie bardzo rozumiem dlaczego:

\(\displaystyle{ |T| = n+1 \Rightarrow |P(T)| = 2^{n+1}}\)

to błąd?

A cóż to jest \(\displaystyle{ T}\)? Używasz symbolu, który nigdy wcześniej nie pojawił się.

Cały czas nie zauważasz, że formuła, której prawdziwość starasz się pokazać indukcyjnie, zaczyna się od kwantyfikatora ogólnego, kwantyfikującego po wszystkich zbiorach.

JK