Wykazać zbiory przeliczalne

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
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

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski » 6 cze 2010, o 19:01

Tak.

JK
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

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 » 6 cze 2010, o 19:03

i pozostało chyba
najtrudniejsze to \(\displaystyle{ |\mathbb{Q}_+|=|\mathbb{Q}|}\)
prosiłbym o wskazówki do tego?

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

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski » 6 cze 2010, o 19:09

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 » 6 cze 2010, o 19:14

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

dobrze?

Awatar użytkownika
miki999
Gość Specjalny
Gość Specjalny
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 » 7 cze 2010, o 14:41

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: 25991
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4350 razy

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski » 7 cze 2010, o 15:20

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
Gość Specjalny
Gość Specjalny
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 » 7 cze 2010, o 15:53

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 » 7 cze 2010, o 19:02

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 » 24 sty 2020, o 10:56

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: 631
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 20 razy
Pomógł: 46 razy

Re: Wykazać zbiory przeliczalne

Post autor: Jakub Gurak » 24 sty 2020, o 14:51

Mozesz też zobaczyć tu: //matematyka.pl/viewtopic.php?f=56&t=413967

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: 25991
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4350 razy

Re: Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski » 24 sty 2020, o 16:45

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:56
1. Liczbę wymierną możemy przedstawić jako dzielnik dwóch liczb całkowitych.
Nie "dzielnik" tylko "iloraz".
Strunowiec pisze:
24 sty 2020, o 10:56
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 ?
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