Obraz zbioru skończonego jest skończony.

[Jakub Gurak]

Wykażemy teraz, ze obraz przez funkcję dowolnego zbioru skończonego jest zawsze skończony.

Lemat: Niech \(\displaystyle{ n}\) będzie liczbą naturalną w sensie von Neumanna, niech zbiór \(\displaystyle{ B \subset n,}\) niech \(\displaystyle{ A}\) będzie zbiorem, niech \(\displaystyle{ f: n \rightarrow A}\) Wykażemy najpierw, że \(\displaystyle{ \stackrel { \rightarrow }{f}\left( B\right)}\) jest zbiorem skończonym. Czyli dla dowolnej liczby naturalnej von Neumanna \(\displaystyle{ n}\) obraz każdego podzbioru \(\displaystyle{ n}\) jest skończony.

Dowód (indukcyjny):

Jeśli \(\displaystyle{ n=\emptyset,}\) to jedynym podzbiorem zbioru pustego jest on sam, czyli musi być \(\displaystyle{ B=\emptyset,}\) i wtedy dla dowolnej funkcji \(\displaystyle{ f:\emptyset \rightarrow A}\) mamy \(\displaystyle{ \stackrel { \rightarrow }{f}\left( B\right)= \stackrel { \rightarrow }{f}\left( \emptyset \right) =\emptyset,}\) a więc jest zbiorem skończonym(nie podoba mi się to, ale ściśle rzecz biorąc zbiór pusty jest skończony, bo jest równoliczny z samym sobą, czyli liczbą naturalną von Neumanna \(\displaystyle{ 0=\emptyset}\) ). A więc spełniona jest podstawa indukcji.

Weźmy \(\displaystyle{ n \in \NN,}\) I załóżmy, że obraz każdego podzbioru \(\displaystyle{ n}\) jest skończony. Rozważmy \(\displaystyle{ n'=n \cup\left\{ n\right\},}\) oraz dowolny zbiór \(\displaystyle{ B \subset n'=n \cup \left\{ n\right\},}\) oraz dowolną funkcję \(\displaystyle{ f:n' \rightarrow A.}\) Wykażemy, że \(\displaystyle{ \stackrel { \rightarrow }{f}\left( B\right)}\) jest zbiorem skończonym.
Jeśli \(\displaystyle{ n\not\in B}\), a wiemy, że \(\displaystyle{ B \subset n \cup \left\{ n\right\},}\) więc \(\displaystyle{ B \subset n,}\) więc z założenia indukcyjnego \(\displaystyle{ \stackrel { \rightarrow }{f}\left( B\right)}\) jest zbiorem skończonym. Jeśli \(\displaystyle{ n \in B}\), to \(\displaystyle{ B \setminus \left\{ n\right\} \subset n,}\) a więc z założenia indukcyjnego \(\displaystyle{ \stackrel { \rightarrow }{f}\left( B \setminus \left\{ n\right\} \right)}\) jest skończony. Wtedy:

\(\displaystyle{ \stackrel { \rightarrow }{f}\left( B \right) =\stackrel { \rightarrow }{f}\left( B \setminus \left\{ n\right\} \cup \left\{ n\right\} \right)= \stackrel { \rightarrow }{f}\left( B \setminus \left\{ n\right\} \right) \cup \stackrel { \rightarrow }{f}\left\{ n\right\}= \stackrel { \rightarrow }{f}\left( B \setminus \left\{ n\right\} \right) \cup \left\{ f\left( n\right) \right\} ,}\) więc \(\displaystyle{ \stackrel { \rightarrow }{f}\left( B \right)}\) jako suma dwóch zbiorów skończonych (a dokładniej zbioru skończonego i jednoelementowego ) jest zbiorem skończonym. Krok indukcyjny został dowiedziony.

Na mocy zasady indukcji matematycznej, dla dowolnej liczby naturalnej von Neumanna \(\displaystyle{ n}\) obraz każdego podzbioru zbioru \(\displaystyle{ n}\) jest zbiorem skończonym. Lemat jest więc udowodniony.

Aby dowieść twierdzenie ustalmy dowolny zbiór skończony \(\displaystyle{ A}\), oraz dowolną funkcję \(\displaystyle{ f:A \rightarrow B.}\) Wykażemy, że \(\displaystyle{ \stackrel { \rightarrow }{f}\left( A \right)}\) jest zbiorem skończonym. Ponieważ zbiór \(\displaystyle{ A}\) jest skończony, więc \(\displaystyle{ A\sim n}\) dla pewnego \(\displaystyle{ n \in \NN.}\) Istnieje więc bijekcja \(\displaystyle{ g:n \rightarrow A,}\) ustalmy ją. W szczególności \(\displaystyle{ g}\) jest "na" A, również \(\displaystyle{ f: A \rightarrow \stackrel { \rightarrow }{f}\left( A \right)}\) jest " na ". Zatem również ich złożenie \(\displaystyle{ f\circ g:n \rightarrow \stackrel { \rightarrow }{f}\left( A \right)}\) jest "na" zbiór \(\displaystyle{ \stackrel { \rightarrow }{f}\left( A\right).}\) Stosujemy udowodniony lemat do funkcji \(\displaystyle{ f\circ g}\) oraz do zbioru \(\displaystyle{ B=n \subset n,}\) dostając, że \(\displaystyle{ \stackrel { \rightarrow }{f\circ g}\left( n \right)}\) jest zbiorem skończonym, zbiorem równym \(\displaystyle{ \stackrel { \rightarrow }{f}\left( A \right)}\), czyli \(\displaystyle{ \stackrel { \rightarrow }{f}\left( A \right)}\) jest zbiorem skończonym. \(\displaystyle{ \square}\)

[a4karo]

W dowodzie korzystasz z "faktu", że suma zbiorów skończonych jest zbiorem skończonym. A skąd to wiesz?

[Jakub Gurak]

W zasadzie korzystam jedynie z tego, że suma zbioru skończonego i jednoelementowego jest zbiorem skończonym, co wydaje się bardzo prostym.

Uczciwie przyznam, że nie tylko tego nie uzasadniałem, takich bardzo prostych faktów. Np. skorzystałem z faktu, że złożenie funkcji " na" jest "na"( z tego co kojarzę, to jest to bardzo proste, wręcz wzorcowe zadanie ze wstępu do matematyki).

[a4karo]

W zasadzie korzystam jedynie z tego, że suma zbioru skończonego i jednoelementowego jest zbiorem skończonym, co wydaje się bardzo prostym.

Wydaje się tak samo prostym jak teza Twojego dowodu. Przy zabawie takimi elementarnymi rzeczami precyzja jest bardzo ważna. Po prostu musisz dokładnie wiedzieć z czego wolno korzystać..

[Gosda]

Chciałbym zobaczyć dowód, który nie korzysta (najlepiej wcale) z indukcji matematycznej czyli tego, że zbiór liczb naturalnych istnieje i jest dobrze uporządkowany.

[Dasio11]

Przy dowodzeniu tak podstawowej własności niezbędne jest zdefiniowanie zbioru skończonego, bo

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Zbi%C3%B3r_sko%C5%84czony#Definicje_formalne

a równoważność między nimi niekoniecznie jest bardziej podstawowa niż ów fakt, którego dowodzimy. Wprawdzie Jakub Gurak nie podał takiej definicji, jednak z dowodu można odczytać, że chodzi o definicję naturalną, czyli: zbiór jest skończony, gdy jest równoliczny z pewną liczbą naturalną (w sensie von Neumanna).

Przyjmując taką definicję, rzeczonego faktu nie da się udowodnić, nie stosując - choćby pośrednio - zasady indukcji dla zbioru liczb naturalnych, bo (na gruncie ATM) jest to jego najbardziej podstawowa własność. W szczególności: to z indukcji wynika dobre uporządkowanie, nie na odwrót.

A jeśli chciałbyś zobaczyć ten dowód dla innej definicji skończoności, to powinieneś określić której.

Inna sprawa, że w powyższym dowodzie teza indukcyjna jest niepotrzebnie skomplikowana, bo łatwiej jest od razu dowodzić, że dla każdej liczby naturalnej \(\displaystyle{ n}\), zbioru \(\displaystyle{ A}\) i funkcji \(\displaystyle{ f : n \to A}\), zbiór \(\displaystyle{ f[n]}\) jest skończony.

[a4karo]

Przypuśćmy, że \(\displaystyle{ A}\) jest zbiorem skończonym i \(\displaystyle{ f:A\to X}\).
Relacja \(\displaystyle{ R\subset A\times A}\) określona następująco: \(\displaystyle{ aRb \Leftrightarrow f(a)=f(b)}\) jest relacją równoważności.

Odwzorowanie \(\displaystyle{ F:A/R\to X}\) dane wzorem \(\displaystyle{ F([x])=f(x)}\) jest bijekcją między \(\displaystyle{ A/R}\) i \(\displaystyle{ f(A)}\).

Skończoność \(\displaystyle{ A/R}\) wynika z faktu, że klasy równoważności są niepuste.

[krl]

Skończoność \(\displaystyle{ A/R}\) wynika z faktu, że klasy równoważności są niepuste.

Intuicyjnie rzecz biorąc, masz rację. Ale jeśli już dzielimy włos na czworo, to takie intuicje nie wystarczają. Dowód, że zbiór ilorazowy \(\displaystyle{ A/R}\) jest skończony, nie jest natychmiastowy.
Natomiast oczywiście dla każdego konkretnego zbioru skończonego \(\displaystyle{ A}\) i każdej relacji równoważności \(\displaystyle{ R}\) na tym zbiorze łatwo pokazać, że zbiór \(\displaystyle{ A/R}\) jest skończony, bez odwoływania się do dobrego uporządkowania zbioru liczb naturalnych.
No ale to nie jest to samo, co dowód zdania, że:
"Dla każdego zbiory skończonego \(\displaystyle{ A}\) i każdej relacji równoważności \(\displaystyle{ R}\) na tym zbiorze, zbiór ilorazowy \(\displaystyle{ A/R}\) jest skończony".

[a4karo]

A czy to nie wynika wprost z aksjomatu wyboru?

[krl]

Z pewnika wyboru dostaniesz, że zbiór ilorazowy \(\displaystyle{ A/R}\) jest równoliczny z pewnym podzbiorem \(\displaystyle{ A'}\) zbioru \(\displaystyle{ A}\). No, ale wtedy jeszcze musisz pokazać, że podzbiór zbioru skończonego jest skończony.

Jednak pewnik wyboru nie jest potrzebny, by pokazać, że obraz zbioru skończonego jest skończony. Bo zbiór liczb naturalnych jest dobrze uporządkowany już w \(\displaystyle{ ZF}\).

[a4karo]

Przyjmując definicję, że zbiór nieskończony to zbiór równoliczny ze swoim właściwym podzbiorem, wykazanie, że podzbiór zbioru skończonego jest skończony jest dość łatwe. Ale fakt, bawiąc się takim elementarzem trzeba dokładnie sprecyzować z czego wolno korzystać.

Może dlatego Benedykt Chmielowski miał rację pisząc: koń, jaki jest, każdy widzi

[krl]

W tej kwestii nie istnieje jedna racja. Różni matematycy w różny sposób patrzą na matematykę, również w praktycznej swojej działalności. Nawet jeśli przyznają (zapewne pod wpływem prania mózgów na studiach), że "teoria mnogości jest podstawą matematyki, która się do niej redukuje" (redukcjonizm zbliżony do logicyzmu), to w praktyce badawczej często tak nie postępują (chyba że zajmują się teorią mnogości lub logiką matematyczną).
Niedawno zauważyłem w podstawach informatyki próby grzebania w podstawach teorii zbiorów, motywowane jednak konkretnymi zastosowaniami w informatyce.

[Jakub Gurak]

wykazanie, że podzbiór zbioru skończonego jest skończony jest dość łatwe.

Może dlatego Benedykt Chmielowski miał rację pisząc: koń, jaki jest, każdy widzi

Zgadzam się, dlatego dziwi mnie ta odpowiedź:

W tej kwestii nie istnieje jedna racja.

Czyli podzbiór zbioru skończonego nie musi być skończony Rozumiem niechęć mówienia o pustym podzbiorze, że jest skończony, ale gdy jest niepusty, to oczywiste przecież, że podzbiór zbioru skończonego jest skończony.

Akurat zakładając temat nie zastanawiałem się zbytnio czy to intuicyjnie oczywiste czy nie( myślałem, fajny dowód mam na kartce- podzielę się) ale jakby się zastanowić, to łatwo można zauważyć więcej: dla dowolnej funkcji \(\displaystyle{ f:X \rightarrow Y}\) jej zbiór wartości \(\displaystyle{ f_P}\) jest mocy nie większej niż dziedzina \(\displaystyle{ X}\).

Zaobserwować jest to bardzo łatwo( choć takie twierdzenie chyba jest = w książce Kuratowski,Mostowski. Teoria Mnogości), gdyż każda funkcja przypisuję każdemu elementowi zbioru \(\displaystyle{ X}\) co najwyżej jedną wartość (nie więcej). Wobec czego zamieniamy jeden element na jeden, albo wiele elementów na jeden, więc dziedzina \(\displaystyle{ X}\) musi być liczniejsza niż zbiór wartości.

Formalnie- trzeba to pokazać, definiując funkcję różnowartościową ze zbioru \(\displaystyle{ f_{P}}\) w zbiór \(\displaystyle{ X}\). Wystarczy elementowi \(\displaystyle{ y\in f_P}\) przypisać element jego przeciwobrazu \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y\right\} .}\) Potrzeba tu aksjomatu wyboru na podobnej zasadzie jak tu, co wyjaśniłem. Taka funkcja będzie różnowartościowa, gdyż przeciwobrazy zbiorów jednoelementowych są rozłączne. A więc \(\displaystyle{ \left| f_P\right| \le \left| f_L=X\right|.}\)

W szczególności dla dowolnej funkcji \(\displaystyle{ f;X \rightarrow Y}\),i jeśli zbiór \(\displaystyle{ X}\) jest skończony, to obraz \(\displaystyle{ \stackrel{ \rightarrow }{f } \left( X\right)}\) jest zbiorem wartości, mocy nie większej niż dziedzina \(\displaystyle{ X}\)- zbiór skończony, więc "tym bardziej" ( zaznaczam " " gdyż to nieformalne ) \(\displaystyle{ \stackrel{ \rightarrow }{f } \left( X\right)}\) jest zbiorem skończonym.

[matmatmm]

Dowód, że podzbiór zbioru skończonego jest skończony, chyba nie jest taki natychmiastowy. Podzielę się szkicem swojego dowodu.

Zbiór skończony definiuję jako równoliczny ze zbiorem pustym lub zbiorem \(\displaystyle{ A_n=\{1,\ldots, n\}}\) dla pewnego \(\displaystyle{ n\in\NN}\). Formalnie mam zdefiniowany ciąg zbiorów \(\displaystyle{ (A_n)_{n\in\NN}}\) taki, że \(\displaystyle{ A_0=\emptyset, A_{n+1}=A_n\cup\{n+1\}}\) dla \(\displaystyle{ n\in\NN}\). Definicja liczb naturalnych nie ma tu znaczenia, nie odwołuję się nigdzie do konstrukcji von Neumanna.

Przejdźmy do dowodu:

Niech \(\displaystyle{ X\sim A_N}\) dla pewnego \(\displaystyle{ N\in\NN}\) oraz \(\displaystyle{ Y\subseteq X}\). Niech \(\displaystyle{ f:X\rightarrow A_N}\) będzie bijekcją. Oznaczmy \(\displaystyle{ A:=f[Y]\subseteq A_N}\). Pokażemy, że \(\displaystyle{ A\sim A_{n_0}}\) dla pewnego \(\displaystyle{ n_0\leq N}\).

Określimy indukcyjnie ciąg \(\displaystyle{ (a_n)_{n\in\NN}}\). Ustalmy \(\displaystyle{ n\in\NN}\) i załóżmy, że zdefiniowaliśmy \(\displaystyle{ a_k}\) dla \(\displaystyle{ k<n}\). Niech

\(\displaystyle{ a_n:=\begin{cases}\min\left( A\setminus\{a_0,\ldots,a_{n-1}\}\right) & , A\setminus\{a_0,\ldots,a_{n-1}\}\neq \emptyset \\ \infty & , A\setminus\{a_0,\ldots,a_{n-1}\}=\emptyset \end{cases}}\)

Należy udowodnić, że

(1) Jeśli \(\displaystyle{ a_n=\infty}\), to \(\displaystyle{ a_m=\infty}\) dla \(\displaystyle{ m\geq n}\).

(2) Jeśli \(\displaystyle{ a_n\neq\infty\neq a_m}\) oraz \(\displaystyle{ n<m}\), to \(\displaystyle{ a_n<a_m}\).

(3) \(\displaystyle{ a_N=\infty}\)

po czym definiujemy \(\displaystyle{ n_0:=\min\{n\in\NN: a_n=\infty\}}\) i dowodzimy, że funkcja \(\displaystyle{ a}\) zawężona do \(\displaystyle{ A_{n_0}}\) jest bijekcją na zbiór \(\displaystyle{ A}\).

[Jan Kraszewski]

oczywiste przecież, że podzbiór zbioru skończonego jest skończony.

Trawestując znajomego profesora, "oczywistość" jest kategorią psychologiczną, a nie matematyczną.

JK