Logika Benny: Mila, Saizou, Eta, : ), ktoś z Was będzie miał chwilkę czasu poświęcić na logikę(mój ulubiony przedmiot)?

Saizou : Ja będę mieć, ale tak kolo 17 dopiero.

Benny: Ok, ja możliwe, że też będę wtedy

Saizou : a co konkretnego czy tak ogólnikowo ?

Saizou : prawdopodobnie będę dzisiaj o 17, a jak nie to jutro na 100% (w sumie to jutro cały dzień)

Benny: Pokaż, że zbiory ℕ i ℕ^k dla pewnego, ustalonego k∊ℕ są równoliczne i skonstruuj odpowiednią bijekcję.

Saizou : Zobacz sobie dowód lematu 2.6 http://smurf.mimuw.edu.pl/node/628

Benny: Nie ogarniam jak oni te funkcje definiują.

Benny: Jest na to jakiś sposób czy trikowo?

Saizou : na razie nie mam pojęcia jak coś wykombinuję to dam znać xd

Benny: ok

Saizou : to taka luźna propozycja można pokazać że N~N² skorzystać z faktu że jeśli A₁~B₁ oraz A₂~B₂ to A=A₁ x A₂~B₁ x B₂=B i powtarzając tę czynność k razy mamy pokazane że N^k~N

zombi: Żeby pokazać, że ℕ∼ℕ², wystarczy to zrobić jak dla liczb wymiernych. W przypadku liczb wymiernych pisaliśmy je w "tablicy" w takiej postaci

1		1		1		1
							...
1		2		3		4

2		2		2		2
							...
1		2		3		4

3		3		3		3
							...
1		2		3		4

4		4		4		4
							...
1		2		3		4

. . .

	1		1		2		3		2		1
Szliśmy po przekątnych		→		→		→		→		→		...
	1		2		1		1		2		3

Dowód na równoliczność N i N² robimy analogicznie tylko 1. nie wykreślamy powtarzających się liczb, 2. nie rozpatrujemy ułamków tylko pary uporządkowane. Więc będziemy iść <1,1> → <1,2> → <2,1> → <3,1> → <2,2> → <1,3> ... Równoliczność dla N^k pokazujemy przez prostą indukcję.

Benny: Nie wiem czy takie wypisanie coś da, myślę, że to musi być dowód formalny.

zombi: To jest dowód formalny Zbiór jest przeliczalny, jeśli jego elementy możemy ustawić w ciąg. Jeśli mi nie wierzysz to może prof. Newelskiemu uwierzysz https://www.math.uni.wroc.pl/~newelski/dydaktyka/wdm-A/skrypt3/skrypt/node12.html Przykład 2. prawie na samym dole.

zombi: Czasami znalezienie odpowiedniej bijekcji wcale nie jest takie proste, więc wykorzystuje się metodę przekątniową albo tw. Cantora−Bernsteina.

Benny: To jest tak trochę nieintuicyjne. Układamy liczby wymierne w nieskończony ciąg i mówimy, że jest on przeliczalny.

Benny: http://home.agh.edu.pl/~zygmunt/kolo_2_Wstep_2015_schemat.pdf do tych zadań będę się odwoływał + parę z zestawu

fffff: f(x,x) → x² f(x,y), x<y → y²−x+1 f(x,y), x>y → (x−1)²+y W tabelce jest kolejność par uporządkowanych, na podstawie której tworzone są funkcje. Oczywiście ta tabelka to tylko fragment, żeby pokazać zasadę porządkowania. Powyższy zapis to dowód dla ℕ ~ ℕ² Dla ℕ ~ ℕ^k będzie funkcja: f_k(a₁,a₂,...,a_k)=f₂(f_k−1(a₁,a₂,...,a_k−1),a_k) O to chodziło w tym zadaniu?