Moc zbioru

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Nuna
Użytkownik
Użytkownik
Posty: 40
Rejestracja: 7 gru 2019, o 19:36
Płeć: Kobieta
wiek: 19
Podziękował: 17 razy

Moc zbioru

Post autor: Nuna » 15 sty 2020, o 22:09

Pokaż, że moc zbioru \(\displaystyle{ Z = \left\{ x \in \RR: (\exists n \in \NN) ( x ^{n} \in \QQ) \right\} = \aleph_0}\).
Zaczęłam od ograniczenia od dołu, tzn. wzięłam sobie podzbiór \(\displaystyle{ A \subseteq Z}\), że \(\displaystyle{ x \in \NN}\), wówczas \(\displaystyle{ (\forall x \in \NN)(\exists n \in \NN)(x ^{n} \in \QQ) }\), zatem \(\displaystyle{ \left| A\right|=\left| \NN\right| = \aleph_0 }\), stąd \(\displaystyle{ \left| \NN\right| \le \left| Z\right| }\). Nie wiem jak ograniczyć ten zbiór z góry, a może trzeba to zrobić kompletnie inaczej?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 2553
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 68 razy
Pomógł: 793 razy

Re: Moc zbioru

Post autor: Janusz Tracz » 15 sty 2020, o 22:22

Z góry można by ograniczyć przez \(\displaystyle{ \text{liczby algebraiczne}}\) wszak \(\displaystyle{ Z \subseteq \text{liczby algebraiczne}}\) a \(\displaystyle{ \left| \text{liczby algebraiczne}\right|= \aleph_0}\) co dowodzi tezy.

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

Re: Moc zbioru

Post autor: Jan Kraszewski » 15 sty 2020, o 22:35

Nuna pisze:
15 sty 2020, o 22:09
Pokaż, że moc zbioru \(\displaystyle{ Z = \left\{ x \in \RR: (\exists n \in \NN) ( x ^{n} \in \QQ) \right\} = \aleph_0}\)
.
Jak zbiór, to zbiór, jak moc zbioru, to moc zbioru, ale nie jedno z drugim. Czyli \(\displaystyle{ Z = \left\{ x \in \RR: (\exists n \in \NN) ( x ^{n} \in \QQ) \right\} }\) i \(\displaystyle{ \left| Z\right| = \aleph_0}\).
Nuna pisze:
15 sty 2020, o 22:09
Zaczęłam od ograniczenia od dołu, tzn. wzięłam sobie podzbiór \(\displaystyle{ A \subseteq Z}\), że \(\displaystyle{ x \in \NN}\), wówczas \(\displaystyle{ (\forall x \in \NN)(\exists n \in \NN)(x ^{n} \in \QQ) }\), zatem \(\displaystyle{ \left| A\right|=\left| \NN\right| = \aleph_0 }\),
.
Nie rozumiem. Używasz jakiegoś zbioru \(\displaystyle{ A}\), ale domyślić się co to za zbiór nie jest łatwo.

No i prościej jest zauważyć po prostu, że \(\displaystyle{ \NN \subseteq Z}\)...
Janusz Tracz pisze:
15 sty 2020, o 22:22
Z góry można by ograniczyć przez \(\displaystyle{ \text{liczby algebraiczne}}\) wszak \(\displaystyle{ Z \subseteq \text{liczby algebraiczne}}\) a \(\displaystyle{ \left| \text{liczby algebraiczne}\right|= \aleph_0}\) co dowodzi tezy.
Po pierwsze tezy dowodzi dopiero zastosowanie tw. Cantora-Bernsteina. Po drugie, musisz móc korzystać z faktu, że zbiór liczb algebraicznych jest przeliczalny.

JK

Nuna
Użytkownik
Użytkownik
Posty: 40
Rejestracja: 7 gru 2019, o 19:36
Płeć: Kobieta
wiek: 19
Podziękował: 17 razy

Re: Moc zbioru

Post autor: Nuna » 15 sty 2020, o 22:47

Dziękuję bardzo za odpowiedzi, rzeczywiście na samym początku popełniłam gafę, przyrównując zbiór do \(\displaystyle{ \aleph_0}\), no i naturalnie, można było od razu napisać \(\displaystyle{ \NN \subseteq Z}\)... Czy mogę używać faktu, że liczby algebraiczne są przeliczalne nie wiem, na wykładzie/ ćwiczeniach w ogóle one się nie pojawiły, ale zadanie robię dla własnego treningu, więc co potrzebuję, doczytam ;)

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 2553
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 68 razy
Pomógł: 793 razy

Re: Moc zbioru

Post autor: Janusz Tracz » 15 sty 2020, o 23:11

Po pierwsze tezy dowodzi dopiero zastosowanie tw. Cantora-Bernsteina.
Skrót myślowy na który sobie pozwoliłem widząc, że Nuna orientuje się w tym co piszę i szuka ograniczenia górnego niejako dążąc do zastosowania tw. Cantora-Bernsteina niemniej jednak fakt faktem dopiero powołując się na tw. Cantora-Bernsteina dowód zostaje zakończony. Zatem uwaga jest jak najbardziej słuszna, dziękuję.
Po drugie, musisz móc korzystać z faktu, że zbiór liczb algebraicznych jest przeliczalny.
Założyłem, że mogę 8-) Ale skoro...
Czy mogę używać faktu, że liczby algebraiczne są przeliczalne nie wiem, na wykładzie/ ćwiczeniach w ogóle one się nie pojawiły
to chętnie doprecyzuję. Liczby algebraiczne to zbiór takich liczb dla których istnieje wielomian o współczynnikach całkowitych który znika (zeruje się) na nich (oczywiście nie na wszystkich na raz tylko dla każdej liczby z ów zbiory istnieje odpowiedni wielomian). Formalną definicję znajdziesz https://pl.wikipedia.org/wiki/Liczby_algebraiczne. Więc generalnie idea pokazania nieprzeliczalności liczb algebraicznych opiera się na pokazaniu, że jest przeliczalnie wiele wielomianów z całkowitymi współczynnikach. A idee tego dowodu można z kolei oprzeć na przeliczalnej ilości wielomianów o współczynnikach naturalnych rozważając odwzorowanie ze zbioru wielomianów w \(\displaystyle{ \NN}\) daje jako:

\(\displaystyle{ a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0\mapsto 2^{a_0}3^{a_{1}} \cdot ... \cdot p_{n+1}^{a_n}}\)

korzystając z jednoznaczności rozkładu dostajemy jednoznaczne przypisanie wielomianu o naturalnych współczynnikach do liczby naturalnej. Oczywiście niedogodnością jest fakt, że są to jedynie wielomiany o naturalnych współczynnikach a nie całkowitych. Są to jednak niedogodności które stosunkowo łatwo naprawić np. kodując informację o znaku liczb \(\displaystyle{ a_i}\). Dokładniej jest to opisane https://www.math.arizona.edu/~glickenstein/math323s13/hw10sol.pdf

PS Nie wykluczam, że przedstawiony szkic rozwiązania zadanie nie jest "najładniejszy" choć innego nie widzę. Być może istnieje rozwiązanie szybsze i łatwiejsze. A może nawet jawnie by się znalazła bijekcja \(\displaystyle{ \phi:Z \rightarrow \NN}\)

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

Re: Moc zbioru

Post autor: Jan Kraszewski » 15 sty 2020, o 23:18

Janusz Tracz pisze:
15 sty 2020, o 23:11
Więc generalnie idea pokazania nieprzeliczalności liczb algebraicznych opiera się na pokazaniu, że jest przeliczalnie wiele wielomianów i całkowitych współczynnikach.
Ups!
Janusz Tracz pisze:
15 sty 2020, o 23:11
PS Nie wykluczam, że przedstawiony szkic rozwiązania zadanie nie jest "najładniejszy" choć innego nie widzę. Być może istnieje rozwiązanie szybsze i łatwiejsze.
A nie prościej pokazać, że zbiór wielomianów o współczynnikach całkowitych rozbija się na przeliczalną sumę zbiorów, z których każdy składa się z wielomianów stopnia co najwyżej \(\displaystyle{ n}\) dla kolejnych liczb naturalnych \(\displaystyle{ n}\)? Z kolei taki pojedynczy zbiór wielomianów jest w prosty sposób bijektywny z \(\displaystyle{ \ZZ^{n+1}}\) poprzez naturalne utożsamienie wielomianu z ciągiem współczynników (ew. dopisując zera z przodu), a zbiór \(\displaystyle{ \ZZ^{n+1}}\) jest przeliczalny jako skończony produkt zbiorów przeliczalnych?

JK

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

Re: Moc zbioru

Post autor: Jan Kraszewski » 15 sty 2020, o 23:38

Nuna pisze:
15 sty 2020, o 22:47
Czy mogę używać faktu, że liczby algebraiczne są przeliczalne nie wiem, na wykładzie/ ćwiczeniach w ogóle one się nie pojawiły
Właśnie o to chodzi. Dowód, że zbiór liczb algebraicznych jest przeliczalny jest dość nietrywialny, więc gdyby okazało się, że musisz najpierw pokazać przeliczalność zbioru liczb algebraicznych, to może okazać się, że to gra niewarta świeczki i lepiej poszukać prostszego oszacowania z góry.

Wersja (wg mnie) prostsza:

Zauważ, że \(\displaystyle{ Z= \bigcup_{n\in\NN} Z_n}\), gdzie \(\displaystyle{ Z_n=\left\{ x \in \RR: x ^{n} \in \QQ \right\}}\). Wystarczy zatem pokazać, że \(\displaystyle{ \left| Z_n\right|=\aleph_0 }\) dla \(\displaystyle{ n\in\NN}\) i skorzystać z tw. o sumie przeliczalnie wielu zbiorów przeliczalnych. Z kolei nie jest trudno pokazać, że funkcja

\(\displaystyle{ \varphi_n:Z_n\to\QQ,\ \varphi_n(x)=x^{n}}\)

jest bijekcją dla nieparzystych \(\displaystyle{ n}\), więc \(\displaystyle{ \left| Z_n\right|=\aleph_0 }\) dla nieparzystych \(\displaystyle{ n}\). Z kolei dla \(\displaystyle{ n}\) parzystych funkcje

\(\displaystyle{ \psi^1_n:Z_n\cap[0,+\infty)\to\QQ\cap[0,+\infty),\ \varphi_n(x)=x^{n}\\
\psi^2_n:Z_n\cap(-\infty,0]\to\QQ\cap[0,+\infty),\ \varphi_n(x)=x^{n}}\)


są bijekcjami, więc zbiór \(\displaystyle{ Z_n}\) jest sumą dwóch zbiorów przeliczalnych i także dla \(\displaystyle{ n}\) parzystych mamy \(\displaystyle{ \left| Z_n\right|=\aleph_0 }\).

JK

ODPOWIEDZ