Zbiory nieprzeliczalne

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
matmatmm
Użytkownik
Użytkownik
Posty: 2045
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 77 razy
Pomógł: 307 razy

Re: Zbiory nieprzeliczalne

Post autor: matmatmm » 29 paź 2019, o 16:34

Jan Kraszewski pisze:
29 paź 2019, o 16:17
matmatmm pisze:
29 paź 2019, o 14:52
bo pod założeniem zaprzeczenia hipotezy continuum \(\displaystyle{ \aleph_1<\mathfrak{c}}\).
A Ty chyba nie wiesz, co to jest hipoteza continuum.
Co napisałem nie tak? Przecież zawsze \(\displaystyle{ \aleph_1\leq \mathfrak{c}}\)

@Borneq
\(\displaystyle{ \omega^{\omega}}\) jest liczbą porządkową przeliczalną, a więc jest elementem \(\displaystyle{ \aleph_1}\) (Podobnie jak na przykład \(\displaystyle{ \omega^{\omega^{\omega}}}\), czy nawet \(\displaystyle{ \epsilon_0}\)). Ta notacja może być myląca, gdyż moc zbioru \(\displaystyle{ \omega^{\omega}}\) nie jest równa \(\displaystyle{ \aleph_0^{\aleph_0}}\) mimo, że moc \(\displaystyle{ \omega}\) jest równa \(\displaystyle{ \aleph_0}\).
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Jan Kraszewski
Administrator
Administrator
Posty: 27905
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4643 razy

Re: Zbiory nieprzeliczalne

Post autor: Jan Kraszewski » 29 paź 2019, o 16:40

matmatmm pisze:
29 paź 2019, o 16:34
Co napisałem nie tak? Przecież zawsze \(\displaystyle{ \aleph_1\leq \mathfrak{c}}\)
Nic. To ja przeczytałem nie tak (dokładniej: mój wzrok ominął "zaprzeczenia"). Przepraszam.

JK

Awatar użytkownika
Borneq
Użytkownik
Użytkownik
Posty: 221
Rejestracja: 23 lip 2010, o 07:50
Płeć: Mężczyzna
Lokalizacja: geo:lat=0 geo:lon=0
Podziękował: 13 razy

Re: Zbiory nieprzeliczalne

Post autor: Borneq » 29 paź 2019, o 16:49

C o mnie myli: liczby porządkowe mają nieskończoną a nawet nieprzeliczalną lizczbę "punktów nieciągłości", chodzi o to że z liczby 2 nie dojdzie się nigdy do liczby \(\displaystyle{ \omega+1}\). Mamy jakby odwrócony na nice przypadek \(\displaystyle{ \RR}\) bo w \(\displaystyle{ \RR}\) nie ma sąsiednich, ale tu są sąsiednie w każdym kawałku, tyle że tych kawałków jest potwornie duzo. W jednym takim kawałku musi być \(\displaystyle{ \aleph_0}\), w skończonej ich liczbie też. Natomiast \(\displaystyle{ \omega^2}\) powinna mieć \(\displaystyle{ \aleph_0*\aleph_0=\aleph_0}\) i tak dalej, lecz gdy mamy \(\displaystyle{ \omega^{\omega}}\) to już powinniśmy mieć continuum, a to nie jest koniec tego zbioru.

Jan Kraszewski
Administrator
Administrator
Posty: 27905
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4643 razy

Re: Zbiory nieprzeliczalne

Post autor: Jan Kraszewski » 29 paź 2019, o 17:03

Borneq pisze:
29 paź 2019, o 16:49
lecz gdy mamy \(\displaystyle{ \omega^{\omega}}\) to już powinniśmy mieć continuum
No nie. Przede wszystkim nie rozumiesz, czym jest \(\displaystyle{ \omega^{\omega}}\) (potęgowanie porządkowe). Cały czas odnosisz się do swoich wyobrażeń, a nie do definicji.

JK

Jakub Gurak
Użytkownik
Użytkownik
Posty: 872
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 28 razy
Pomógł: 55 razy

Re: Zbiory nieprzeliczalne

Post autor: Jakub Gurak » 29 sty 2021, o 20:47

Twierdzenie, że każde dwa zbiory są porównywalne na moc można wykorzystać aby udowodnić, że jeśli \(\displaystyle{ X}\) jest dowolnym zbiorem nieskończonym a \(\displaystyle{ Y}\) dowolnym zbiorem skończonym, to \(\displaystyle{ \left| X\right|>\left| Y\right|.}\) :mrgreen:

PROSTY DOWÓD:

Z Lematu Zorna otrzymujemy, że każde dwa zbiory są porównywalne na moc, więc również \(\displaystyle{ \left| X\right| \ge \left| Y\right|}\) lub \(\displaystyle{ \left| Y\right| \ge \left| X\right|. }\) Jeśli \(\displaystyle{ \left| X\right| \ge \left| Y\right|}\) , to \(\displaystyle{ X\not\sim Y}\) ( w przeciwnym razie, ponieważ gdyż \(\displaystyle{ X}\) jest zbiorem nieskończonym, a \(\displaystyle{ Y}\) zbiorem skończonym, więc \(\displaystyle{ Y}\) jako zbiór równoliczny ze zbiorem nieskończonym byłby nieskończony- sprzeczność), a zatem \(\displaystyle{ X\not\sim Y}\), więc \(\displaystyle{ \left| X\right|>\left| Y\right|}\), co należało pokazać. Jeśli \(\displaystyle{ \left| Y\right| \ge \left| X\right|}\) doprowadzimy ten przypadek do sprzeczności co oznaczać będzie, że on jest niemożliwy, co zakończy dowód. W takim wypadku \(\displaystyle{ Y}\) jako zbiór większej lub równej mocy niż zbiór nieskończony byłby również nieskończony, a \(\displaystyle{ Y}\) jest zbiorem skończonym- sprzeczność.\(\displaystyle{ \square }\):lol:

Aha muszę dodać,
NIE CAŁKIEM OCZYWISTY FAKT:    

Jakub Gurak
Użytkownik
Użytkownik
Posty: 872
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 28 razy
Pomógł: 55 razy

Re: Zbiory nieprzeliczalne

Post autor: Jakub Gurak » 12 lut 2021, o 21:03

Kilka dni po przeprowadzeniu tego dowodu dostrzegłem, że chyba przesadziłem, nie trzeba tu Lematu Zorna- wystarczą same elementarne fakty, co wczoraj udowodniłem. Udowodnimy najpierw pewien lemat, którego dowód jest analogiczny do dowodu z ważniaka, że jeśli zbiór \(\displaystyle{ X}\) jest nieskończony, to dla dowolnej liczby naturalnej von Neumanna \(\displaystyle{ n}\), mamy \(\displaystyle{ |n|\le |X|}\), więc analogicznie udowodniłem to dla dowolnych zbiorów skończonych. A z niego łatwo będzie wynikać nasza teza. Przedstawię teraz rezultat.

Lemat:

Dla dowolnego zbioru nieskończonego \(\displaystyle{ X}\), dla dowolnej liczby naturalnej von Neumanna \(\displaystyle{ n}\), dla dowolnego zbioru \(\displaystyle{ Y\sim n}\), mamy \(\displaystyle{ |Y| \le \left| X\right|.}\)

Dowód:

Niech \(\displaystyle{ X}\) będzie zbiorem nieskończonym. Niech \(\displaystyle{ n\in\mathbb{N}.}\) Dalej prowadzimy dowód indukcyjnie, ze względu na \(\displaystyle{ n}\).

Jeśli \(\displaystyle{ n=0=\emptyset}\), to jedynym zbiorem równolicznym ze zbiorem pustym jest zbiór pusty (wynika to stąd, że zbiór równoliczny ze zbiorem niepustym musi być niepusty- to nawet każda funkcja na zbiorze niepustym prowadzi w zbiór niepusty, więc stąd to wynika, oraz z symetrii równoliczności).

A wtedy funkcja pusta \(\displaystyle{ f:\emptyset \rightarrow X}\) jest różnowartościowa, formalnie rzecz biorąc. A zatem \(\displaystyle{ |Y|=|\emptyset| \le \left| X\right|.}\)

Przypuśćmy teraz, że twierdzenie zachodzi dla \(\displaystyle{ n}\). Rozważmy \(\displaystyle{ n'}\), oraz zbiór \(\displaystyle{ Y\sim n'}\). Pokażemy, że \(\displaystyle{ \left| Y\right| \le \left| X\right|}\). Ponieważ \(\displaystyle{ Y\sim n'}\), więc istnieje bijekcja \(\displaystyle{ f:n' \rightarrow Y .}\) A zatem jej zawężenie \(\displaystyle{ f_{|n}:n \rightarrow Y \setminus \left\{ f(n)\right\} }\), jest nadal bijekcją, gdyż jest taki prosty fakt, że jak z bijekcji wyrzucimy jedną parę złożoną z elementu dziedziny i odpowiadającej jej wartości, to będzie to nadal bijekcja. Wobec czego \(\displaystyle{ f_{|n}}\) jest bijekcją z \(\displaystyle{ n}\) w \(\displaystyle{ Y \setminus\left\{ f(n)\right\} .}\) Teraz do \(\displaystyle{ n}\) i zbioru \(\displaystyle{ Y \setminus \left\{ f(n)\right\} }\) możemy zastosować założenie indukcyjne, i otrzymać, że \(\displaystyle{ \left| Y \setminus \left\{ f(n)\right\} \right| \le \left| X\right| }\). A zatem istnieje funkcja różnowartościowa \(\displaystyle{ g:Y \setminus \left\{ f(n)\right\} \rightarrow X}\). Zauważmy teraz, że \(\displaystyle{ g}\) nie może być bijekcją. W przeciwnym razie złozenie \(\displaystyle{ f_{|n}\circ g: n \rightarrow X}\) jako złożenie bijekcji byłoby bijekcją, a zatem \(\displaystyle{ n\sim X}\), a zatem zbiór \(\displaystyle{ X}\) byłby skończony, a on jest naszym zbiorem nieskończonym- sprzeczność. Wobec czego \(\displaystyle{ g}\) nie jest bijekcją, ale jest różnowartościowa, zatem otrzymujemy, że \(\displaystyle{ g}\) nie jest 'na'. A zatem zbiór wartości \(\displaystyle{ g_P \neq X}\), ale \(\displaystyle{ g_P\subset X}\), zatem \(\displaystyle{ g_P}\) jest istotnym podzbiorem zbioru \(\displaystyle{ X}\), zatem istnieje element \(\displaystyle{ a\not\in g_P }\) spoza tego podzbioru, (element, który: \(\displaystyle{ a\in X}\)). Ustalmy taki element \(\displaystyle{ a}\). A wtedy \(\displaystyle{ h=g \cup \left\{ \left( f(n),a\right) \right\}}\) jest oczywiście funkcją z \(\displaystyle{ \left( Y \setminus \left\{ f(n)\right\} \ \right) \cup \left\{ f(n)\right\}=Y}\) do \(\displaystyle{ X}\) (\(\displaystyle{ a\in X}\)), a ponieważ \(\displaystyle{ g}\) jest różnowartościowa i \(\displaystyle{ a\not\in g_P}\)- element \(\displaystyle{ a}\) nie jest w zbiorze wartości \(\displaystyle{ g}\), to \(\displaystyle{ h}\) nadal jest różnowartościowa, a zatem \(\displaystyle{ \left| Y\right| \le \left| X\right|}\). Dowolność tego zbioru kończy dowód kroku indukcyjnego. Na mocy zasady indukcji matematycznej lemat jest udowodniony. \(\displaystyle{ \square}\)

Łatwo będzie teraz udowodnić, że jeśli \(\displaystyle{ X}\) jest dowolnym zbiorem nieskończonym, a \(\displaystyle{ Y}\) dowolnym zbiorem skończonym, to \(\displaystyle{ \left| Y\right|<|X|.}\)

Prosty dowód:

Ponieważ \(\displaystyle{ Y}\) jest zbiorem skończonym, to \(\displaystyle{ Y\sim n}\), dla pewnego \(\displaystyle{ n\in \NN}\). Mamy zatem zbiór nieskończony \(\displaystyle{ X, n\in\mathbb {N}}\), i zbiór \(\displaystyle{ Y\sim n}\), stosując lemat otrzymujemy \(\displaystyle{ |Y| \le \left| X\right|}\). Pozostaje wykazać, że zbiór \(\displaystyle{ Y}\) nie może być równoliczny ze zbiorem \(\displaystyle{ X}\). Ale gdyby \(\displaystyle{ Y}\) był równoliczny z \(\displaystyle{ X}\)-zbiorem nieskończonym, to \(\displaystyle{ Y}\) byłby nieskończony, a \(\displaystyle{ Y}\) jest skończony- sprzeczność. Zatem \(\displaystyle{ Y\not\sim X}\), a więc \(\displaystyle{ |Y|<|X|.\square }\) :D 8-) :lol:

Jakub Gurak
Użytkownik
Użytkownik
Posty: 872
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 28 razy
Pomógł: 55 razy

Re: Zbiory nieprzeliczalne

Post autor: Jakub Gurak » 12 maja 2021, o 13:09

Udowodniłem przed chwilą, że jeśli \(\displaystyle{ A}\) jest zbiorem nieprzeliczalnym, a \(\displaystyle{ B}\) zbiorem co najwyżej przeliczalnym, to różnica symetryczna \(\displaystyle{ A\oplus B}\) jest dalej równoliczna ze zbiorem nieprzeliczalnym \(\displaystyle{ A}\). Łatwo to udowodniłem. Przedstawię teraz ten prosty dowód:

Przypominam zbiory nieprzeliczalne są odporne na dodawanie i ujmowanie zbiorów co najwyżej przeliczalnych, o czym można poczytać w pierwszym poście tego wątku (tzn. po dodaniu zbioru do sumy otrzymujemy zbiór tej samej mocy, podobnie po odjęciu zbioru jako różnicy otrzymujemy zbiór tej samej mocy). Będziemy z tego korzystać. Przejdźmy zatem do naszego dowodu.

PROSTY DOWÓD:

Mamy \(\displaystyle{ A\oplus B= (A \setminus B) \cup \left( B \setminus A\right) .}\) Ponieważ \(\displaystyle{ A}\) jest zbiorem nieprzeliczalnym, \(\displaystyle{ B}\) jest zbiorem co najwyżej przeliczalnym, i zbiory nieprzeliczalne są odporne na ujmowanie zbiorów co najwyżej przeliczalnych, więc \(\displaystyle{ A \setminus B\sim A}\). Popatrzmy na drugi składnik tej sumy- ponieważ zbiór \(\displaystyle{ B}\) jest co najwyżej przeliczalny, więc jego podzbiór \(\displaystyle{ B \setminus A}\) jest co najwyżej przeliczalny. Mamy, że \(\displaystyle{ A \setminus B}\) jako zbiór równoliczny ze zbiorem nieprzeliczalnym \(\displaystyle{ A}\) jest nieprzeliczalny, więc po dodaniu co najwyżej przeliczalnego zbioru \(\displaystyle{ B \setminus A}\) otrzymujemy:

\(\displaystyle{ A\oplus B=\left( A \setminus B\right) \cup \left( B \setminus A\right) \sim A \setminus B\sim A}\), a więc \(\displaystyle{ A\oplus B\sim A. \square}\) :lol:

a4karo
Użytkownik
Użytkownik
Posty: 19428
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 7 razy
Pomógł: 3284 razy

Re: Zbiory nieprzeliczalne

Post autor: a4karo » 12 maja 2021, o 15:15

A nie wystarczy \(\displaystyle{ A\oplus B= (A \setminus B) \cup \left( B \setminus A\right)\supset A\setminus B}\) ?

ODPOWIEDZ