Wykazać zbiory przeliczalne

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski »

Tak.

JK
robin5hood
Użytkownik
Użytkownik
Posty: 1676
Rejestracja: 2 kwie 2007, o 14:43
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 178 razy
Pomógł: 17 razy

Wykazać zbiory przeliczalne

Post autor: robin5hood »

i pozostało chyba
najtrudniejsze to \(\displaystyle{ |\mathbb{Q}_+|=|\mathbb{Q}|}\)
prosiłbym o wskazówki do tego?
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski »

E tam.
1. \(\displaystyle{ |\mathbb{Q}_-|=|\mathbb{Q}_+|}\) - prosto.
2. \(\displaystyle{ \mathbb{Q}=\mathbb{Q}_-\cup\mathbb{Q}_+\cup\{0\}}\) i korzystasz z twierdzenia o sumie zbiorów przeliczalnych (w którejś z wersji).

JK
robin5hood
Użytkownik
Użytkownik
Posty: 1676
Rejestracja: 2 kwie 2007, o 14:43
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 178 razy
Pomógł: 17 razy

Wykazać zbiory przeliczalne

Post autor: robin5hood »

1. \(\displaystyle{ g(k)=-k}\)
2. suma zbiorów przeliczalnych jest zbiorem przeliczalnym

dobrze?
Awatar użytkownika
miki999
Użytkownik
Użytkownik
Posty: 8691
Rejestracja: 28 lis 2007, o 18:10
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 36 razy
Pomógł: 1001 razy

Wykazać zbiory przeliczalne

Post autor: miki999 »

dobrze?
Tak.


Jeżeli uprzednio udowodniłeś, że \(\displaystyle{ |\mathbb{Q}|=\aleph _0}\), to można też to zrobić inaczej. Sprawdzenie, że \(\displaystyle{ |\mathbb{Q}_+|=|\mathbb{Q}|}\) jest prostym wnioskiem wynikającym z inkluzji: \(\displaystyle{ \mathbb{N}_+ \subset \mathbb{Q}_+ \subset \mathbb{Q}}\).



Pozdrawiam.
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski »

miki999 pisze:Jeżeli uprzednio udowodniłeś, że \(\displaystyle{ |\mathbb{Q}|=\aleph _0}\), to można też to zrobić inaczej.
Miki, my właśnie to dowodzimy...

JK
Awatar użytkownika
miki999
Użytkownik
Użytkownik
Posty: 8691
Rejestracja: 28 lis 2007, o 18:10
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 36 razy
Pomógł: 1001 razy

Wykazać zbiory przeliczalne

Post autor: miki999 »

Rzeczywiście, myślałem, że to jakiś inny (któryś z kolei) podpunkt.



Pozdrawiam.
robin5hood
Użytkownik
Użytkownik
Posty: 1676
Rejestracja: 2 kwie 2007, o 14:43
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 178 razy
Pomógł: 17 razy

Wykazać zbiory przeliczalne

Post autor: robin5hood »

a jak najlepiej pokazac ze \(\displaystyle{ f:N\times N\to N, f(n,k)=2^n(2k+1)-1}\) jest różnowartościowa
Strunowiec
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 23 sty 2020, o 18:45
Płeć: Mężczyzna
wiek: 47
Podziękował: 2 razy

Re: Wykazać zbiory przeliczalne

Post autor: Strunowiec »

gg1985 pisze: 18 lis 2006, o 15:48 Witam

1. Używając metody przekątniowej, wykazać że iloczyn kartezjański dwóch zbiorów przeliczalnych jest zbiorem przeliczalnym.

2. Wykazać, że zbiór liczb wymiernych jest zbiorem przeliczalnym

Pozdrawiam

ad.2.
Zastanawiałem się kiedyś nad takim dowodzeniem przeliczalności zbioru liczby wymiernych.

1. Liczbę wymierną możemy przedstawić jako dzielnik dwóch liczb całkowitych.
2. Każdą liczbę całkowitą możemy wypowiedzieć i zapisać jednoznacznie wyrazami o skończonej liczbie głosek (liter). (np. "Sto dwadzieścia pięć miliardów dwieście cztery").
3. Więc także każdy dzielnik możemy wypowiedzieć i zapisać jednoznacznie (np. "szesnaście tysięcy pięćset cztery podzielić na dwadzieścia osiem").
4. Wyrazy i zdania można posortować jednoznacznie alfabetycznie i jest to porządek, bez powtórzeń. Tutaj oczywiście potrzebny jest lemat o porządku alfabetycznym.
5. Uporządkowana alfabetycznie lista zdań opisujących liczby wymierne jest przeliczalna.

Czego brakuje takiemu dowodowi ?
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Wykazać zbiory przeliczalne

Post autor: Jakub Gurak »

Mozesz też zobaczyć tu:

Stąd \(\displaystyle{ \left| \NN \times \NN\right| \le \left| \NN\right| .}\)

Nierówność mocy w drugą drugą stronę jest oczywista, gdyż \(\displaystyle{ \left| \NN \times \NN\right| \ge \left| \NN \times \left\{ 0\right\} \right|=\left| \NN\right|. }\)

A zatem \(\displaystyle{ \NN \times \NN\sim\NN.}\)

A zatem również iloczyn kartezjański dwóch zbiorów przeliczalnych (równolicznych z \(\displaystyle{ \NN}\) ) jest przeliczalny, gdyż jeśli zbiory \(\displaystyle{ A,B}\) są przeliczalne, czyli równoliczne z \(\displaystyle{ \NN}\), to \(\displaystyle{ A\times B\sim \NN \times \NN\sim\NN,}\) a więc zbiór \(\displaystyle{ A \times B}\) jest równoliczny z \(\displaystyle{ \NN}\), czyli przeliczalny.\(\displaystyle{ \square}\) :lol:
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski »

Jakub Gurak, przecież post Strunowca nie dotyczył tego, jak udowodnić przeliczalność zbioru liczb wymiernych. Chodziło o to, by ocenić konkretny pomysł dowodowy.
Strunowiec pisze: 24 sty 2020, o 10:561. Liczbę wymierną możemy przedstawić jako dzielnik dwóch liczb całkowitych.
Nie "dzielnik" tylko "iloraz".
Strunowiec pisze: 24 sty 2020, o 10:562. Każdą liczbę całkowitą możemy wypowiedzieć i zapisać jednoznacznie wyrazami o skończonej liczbie głosek (liter). (np. "Sto dwadzieścia pięć miliardów dwieście cztery").
3. Więc także każdy dzielnik możemy wypowiedzieć i zapisać jednoznacznie (np. "szesnaście tysięcy pięćset cztery podzielić na dwadzieścia osiem").
4. Wyrazy i zdania można posortować jednoznacznie alfabetycznie i jest to porządek, bez powtórzeń. Tutaj oczywiście potrzebny jest lemat o porządku alfabetycznym.
5. Uporządkowana alfabetycznie lista zdań opisujących liczby wymierne jest przeliczalna.

Czego brakuje takiemu dowodowi ?
Dokładności formalnej. Pomysł ogólnie jest dobry, ale na poziomie szczegółów są kłopoty. Nie jest prawdą np., że każdy iloraz możemy zapisać jednoznacznie, bo np. "Jeden podzielić na dwa", "Dwa podzielić na cztery" itd. zapisują tę samą liczbę wymierną. Co więcej, każda liczba wymierna jest zapisana na nieskończenie wiele sposobów. Trzeba to jakoś poprawić. Dalej, stwierdzenie "Uporządkowana alfabetycznie lista zdań opisujących liczby wymierne jest przeliczalna." wymaga uzasadnienia. A jak zaczniesz doprecyzowywać te kwestie i dowodzić brakujące lematy, to okaże się, że dowód jest dość skomplikowany...

JK
ODPOWIEDZ