szukanie zaawansowane
 [ Posty: 18 ]  Przejdź na stronę 1, 2  Następna strona
Autor Wiadomość
Mężczyzna
PostNapisane: 9 sie 2019, o 01:39 
Użytkownik

Posty: 560
Lokalizacja: Rzeszów
Wykażemy teraz, ze obraz przez funkcję dowolnego zbioru skończonego jest zawsze skończony.

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

Dowód (indukcyjny):

Jeśli n=\emptyset, to jedynym podzbiorem zbioru pustego jest on sam, czyli musi być B=\emptyset, i wtedy dla dowolnej funkcji f:\emptyset \rightarrow A mamy \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 0=\emptyset ). A więc spełniona jest podstawa indukcji.

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

\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 \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 n obraz każdego podzbioru zbioru n jest zbiorem skończonym. Lemat jest więc udowodniony.

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

Posty: 16716
Lokalizacja: Bydgoszcz
W dowodzie korzystasz z "faktu", że suma zbiorów skończonych jest zbiorem skończonym. A skąd to wiesz?
Góra
Mężczyzna
PostNapisane: 9 sie 2019, o 18:17 
Użytkownik

Posty: 560
Lokalizacja: Rzeszów
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).
Góra
Mężczyzna
PostNapisane: 9 sie 2019, o 18:42 
Użytkownik

Posty: 16716
Lokalizacja: Bydgoszcz
Jakub Gurak napisał(a):
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ć..
Góra
Mężczyzna
PostNapisane: 12 sie 2019, o 04:51 
Użytkownik
Avatar użytkownika

Posty: 46
Lokalizacja: Oulu
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.
Góra
Mężczyzna
PostNapisane: 12 sie 2019, o 10:14 
Moderator
Avatar użytkownika

Posty: 8453
Lokalizacja: Wrocław
Przy dowodzeniu tak podstawowej własności niezbędne jest zdefiniowanie zbioru skończonego, bo możliwości jest multum 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 n, zbioru A i funkcji f : n \to A, zbiór f[n] jest skończony.
Góra
Mężczyzna
PostNapisane: 13 sie 2019, o 12:42 
Użytkownik

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

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

Skończoność A/R wynika z faktu, że klasy równoważności są niepuste.
Góra
Mężczyzna
PostNapisane: 13 sie 2019, o 21:06 
Użytkownik

Posty: 426
Lokalizacja: Wrocław
a4karo napisał(a):
Skończoność 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 A/R jest skończony, nie jest natychmiastowy.
Natomiast oczywiście dla każdego konkretnego zbioru skończonego A i każdej relacji równoważności R na tym zbiorze łatwo pokazać, że zbiór 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 A i każdej relacji równoważności R na tym zbiorze, zbiór ilorazowy A/R jest skończony".
Góra
Mężczyzna
PostNapisane: 13 sie 2019, o 21:25 
Użytkownik

Posty: 16716
Lokalizacja: Bydgoszcz
A czy to nie wynika wprost z aksjomatu wyboru?
Góra
Mężczyzna
PostNapisane: 13 sie 2019, o 21:48 
Użytkownik

Posty: 426
Lokalizacja: Wrocław
Z pewnika wyboru dostaniesz, że zbiór ilorazowy A/R jest równoliczny z pewnym podzbiorem A' zbioru 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 ZF.
Góra
Mężczyzna
PostNapisane: 13 sie 2019, o 23:33 
Użytkownik

Posty: 16716
Lokalizacja: Bydgoszcz
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 :)
Góra
Mężczyzna
PostNapisane: 14 sie 2019, o 11:46 
Użytkownik

Posty: 426
Lokalizacja: Wrocław
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.
Góra
Mężczyzna
PostNapisane: 15 sie 2019, o 20:37 
Użytkownik

Posty: 560
Lokalizacja: Rzeszów
a4karo napisał(a):
wykazanie, że podzbiór zbioru skończonego jest skończony jest dość łatwe.
a4karo napisał(a):
Może dlatego Benedykt Chmielowski miał rację pisząc: koń, jaki jest, każdy widzi :)
Zgadzam się, dlatego dziwi mnie ta odpowiedź:
krl napisał(a):
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 f:X \rightarrow Y jej zbiór wartości f_P jest mocy nie większej niż dziedzina 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 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 X musi być liczniejsza niż zbiór wartości.

Formalnie- trzeba to pokazać, definiując funkcję różnowartościową ze zbioru f_{P} w zbiór X. Wystarczy elementowi y\in f_P przypisać element jego przeciwobrazu \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 \left| f_P\right| \le \left| f_L=X\right|.

W szczególności dla dowolnej funkcji f;X \rightarrow Y,i jeśli zbiór X jest skończony, to obraz \stackrel{ \rightarrow }{f  } \left( X\right) jest zbiorem wartości, mocy nie większej niż dziedzina X- zbiór skończony, więc "tym bardziej" ( zaznaczam " " gdyż to nieformalne ) \stackrel{ \rightarrow }{f  } \left( X\right) jest zbiorem skończonym.
Góra
Mężczyzna
PostNapisane: 15 sie 2019, o 23:19 
Użytkownik

Posty: 1737
Lokalizacja: Sosnowiec
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 A_n=\{1,\ldots, n\} dla pewnego n\in\NN. Formalnie mam zdefiniowany ciąg zbiorów (A_n)_{n\in\NN} taki, że A_0=\emptyset, A_{n+1}=A_n\cup\{n+1\} dla n\in\NN. Definicja liczb naturalnych nie ma tu znaczenia, nie odwołuję się nigdzie do konstrukcji von Neumanna.

Przejdźmy do dowodu:

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

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

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 a_n=\infty, to a_m=\infty dla m\geq n.

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

(3) a_N=\infty

po czym definiujemy n_0:=\min\{n\in\NN: a_n=\infty\} i dowodzimy, że funkcja a zawężona do A_{n_0} jest bijekcją na zbiór A.
Góra
Mężczyzna
PostNapisane: 16 sie 2019, o 00:35 
Administrator

Posty: 24832
Lokalizacja: Wrocław
Jakub Gurak napisał(a):
oczywiste przecież, że podzbiór zbioru skończonego jest skończony.

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

JK
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 18 ]  Przejdź na stronę 1, 2  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Jak udowodnic ze dzialanie jest laczne....  merneith  7
 Wykazac ze zbior jest nieprzeliczalny...  ruben  12
 [Dowod] kres gorny oraz dolny zbioru  tęcza  2
 Elementy zbioru  mike  1
 czego jest więcej: liczb R czy R+?  matemateusz  11
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl