Pomocy kot: Witam. Za zadanie mam wykazać że zbiór ℕ x ℕ jest równej mocy ze zbiorem ℕ. Jak do tej pory wpadłem na to że trzeba znaleźć bijekcję między tymi zbiorami. Dodatkowo w założeniach zadania miałem podaną taką funkcję f: ℕxℕ → ℕ, f(x,y) = 2^x(2y + 1) − 1 Mógłby mnie ktoś naprowadzić na dobre tory ?

Maslanek: Wziąłbym funkcję: f(x,y)=2^x−1(2y−1)−1, bo inaczej te założenia nie są spełnione ^^ (chyba, że N traktujemy z 0) Niewątpliwie bijekcja, bo dla f(1,y) otrzymujemy liczby parzyste. Dla f(2, y) otrzymamy nieparzyste. Trzeba jeszcze pokazać, że f(x,y) jest iniekcją. Weźmy f(a,b)=2^a−1(2b−1)−1 oraz f(c,d)=2^d−1(2c−1)−1 Mamy: f(a,b)=f(c,d) ⇔ 2^a−1(2b−1)=2^d−1(2c−1) Z jednoznaczności rozkładu na czynniki pierwsze: a=d i b=c. Zatem bijekcja, więc równoliczność

Maslanek: Albo inaczej: Stwórzmy tablicę: (1,1) (1,2) (1,3) (1,4) ... (2,1) (2,2) (2,3) (2,4) ... (3,1) (3,2) (3,3) (3,4) ... (4,1) (4,2) (4,3) (4,4) ... ... ... ... ... Przyporządkowanie f: N→(N x N) takie, że kolejnym n przyporządkowujemy wyrazy leżące na kolejnych przekątnych Czyli: f(1)=(1,1) f(2)=(1,2) f(3)=(2,1) f(4)=(1,3) itd. Podobnie dostajemy bijekcję, więc równoliczność

kot: Aby funkcja była bijekcją musi być suriekcją i iniekcją. W pierwszej części udowodniłeś że to jest suriekcja ? 'Niewątpliwie bijekcja, bo dla f(1,y) otrzymujemy liczby parzyste. Dla f(2, y) otrzymamy nieparzyste.' Pytam ponieważ chce się tylko upewnić

Maslanek: Tak, tak Nie wiem, czemu tak napisałem Chyba chciałem skoczyć krok dalej

kot: Jeszcze mam pytanie odnośnie tej tablicy. Czy dobrze rozumiem że dla f(5) = (2,2), f(6) = (3,1) etc. ? Sądzisz że skonstruowanie takiej tablicy może być dowodem ?

Maslanek: Jest dowodem nawet Na pewno jest różnowartościowa, a co więcej dla każdej pary (x,y) znajdziemy odpowiednie n ze względu na taką konstrukcję funkcji f. Czyli mamy bijekcję

Maslanek: I tak własnie jest jak piszesz

kot: Wszystko jasne dzięki bardzo za pomoc

Maslanek: Proszę bardzo, wpadaj częściej Dowody sobie przypominam i, o dziwo, własnie zrozumiałem ten 1 sposób

kot: Mówisz o tym sposobie który podałeś jako pierwszy bez tablicy ? Możesz go trochę bardziej objaśnić jak masz chwilkę

Maslanek: Ogólnie z definicji różnowartościowości, jeżeli pokażemy, że f(x₁)=f(x₂)⇒x₁=x₂, to funkcja jest różnowartościowa. Mamy rozkład na czynniki pierwsze liczb po lewej i po prawej. Czyli: 2^a−1(2b−1)=2^c−1(2d−1) (z równości wartości funkcji dla róznych argumentów x₁, x₂) Rozpatrzmy przypadki: (1) f(x₁)=f(x₂) jest liczbą nieparzystą Wtedy a=1, c=1 i musiałoby być (2b−1)=(2d−1) Tutaj przydałoby się zajrzeć do algebry i rozkładu na czynniki pierwsze. Że jest jednoznaczny. Więc jeśli w rozkładzie f(x₁)=f(x₂) to ich rozkład jest taki sam (mamy już tą samą liczbę dwójek, równą 0), więc b=d. (2) f(x₁)=f(x₂) jest liczbą parzystą Wtedy a,b>1 i musiałoby być 2^a−1(2b−1)=2^c−1(2d−1) Przypuśćmy teraz, że po lewej stronie występuje nieparzysta liczba dwójek, a po prawej parzysta (lub po prostu inna liczba dwójek). Drugi czynnik w iloczynach jest liczbą nieparzystą, więc w jego rozkładzie nie występują dwójki. Ale f(x₁) ma jednoznaczny rozkład, więc sytuacja taka nie może zachodzić. Czyli a=c i podobnie jak wyżej b=d.