szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 22 maja 2018, o 04:25 
Użytkownik

Posty: 12654
Nie udało mi się tego (jak i prawie niczego) rozwiązać na kolokwium (choć zadanie wygląda na bardzo łatwe), bo byłem nieprzygotowany i wolno myślę (a poza tym debil ze mnie), więc chciałbym sprawdzić, czy teraz jestem w stanie napisać poprawne i porządne rozwiązanie poniższego zadania. Będę wdzięczny za wszelkie uwagi, sprostowania, poprawki.

Mamy hierarchię R_{\alpha}:
\begin{cases} R_0=\varnothing \\ R_{\alpha+1}=\mathcal{P}(R_{\alpha})\\ R_{\gamma}= \bigcup_{\xi<\gamma}^{}R_{\xi} \text{ gdy } \mathrm{Lim}(\gamma), \ \gamma\neq 0 \end{cases}

Dla zbioru x definiujemy \mathrm{rank}(x)=\min\left\{ \alpha: x\in R_{\alpha+1}\right\}
Chciałbym pokazać, że dla dowolnej liczby porządkowej \alpha mamy \mathrm{rank}(\alpha)=\alpha
Spróbuję to udowodnić za pomocą indukcji pozaskończonej.
1^{\circ} Dla \alpha=0 sprawa jest prosta: 0\notin 0 oraz 0\in 1, zaś 1=\left\{ \varnothing\right\}=\mathcal{P}(\varnothing)=R_1, a zatem \mathrm{rank}(0)=0.

2^{\circ} Teraz czas na krok następnikowy. Przypuśćmy, że dla pewnej liczby porządkowej \alpha zachodzi \mathrm{rank}(\alpha)=\alpha.
Ponieważ \alpha\in \alpha+1 i R_{\eta} są tranzytywne, zatem \mathrm{rank}(\alpha+1)>\mathrm{rank}(\alpha)=\alpha, czyli
\mathrm{rank}(\alpha+1)\ge \alpha+1. Pokażemy teraz, że \alpha+1\in R_{\alpha+2}, czyli \mathrm{rank}(\alpha+1)\le \alpha+1, co wraz z poprzednim wnioskiem doprowadzi nas do stwierdzenia, że \mathrm{rank}(\alpha+1)=\alpha+1. Mianowicie mamy \alpha+1=\alpha\cup \left\{ \alpha\right\} i z założenia indukcyjnego mamy w szczególności, że \alpha \in R_{\alpha+1}. Ponadto jest R_{\alpha+2}=\mathcal{P}(R_{\alpha+1}), czyli wystarczy pokazać, że
\alpha+1\subset R_{\alpha+1}. Mamy, jak wspomniałem, \alpha+1=\alpha\cup\left\{ \alpha\right\} oraz \alpha\in R_{\alpha+1} z zał. indukcyjnego, a ponadto dla dowolnego \xi \in \alpha mamy \xi \in R_{\alpha+1}, co wynika z tranzytywności R_{\alpha+1}. Zatem istotnie \alpha+1\subset R_{\alpha+1}, czyli
\alpha+1\in \mathcal{P}(R_{\alpha+1})=R_{\alpha+2}, tj. \mathrm{rank}(\alpha+1)\le \alpha+1, co w połączeniu z poprzednim wnioskiem \mathrm{rank}(\alpha+1)\ge \alpha+1 daje nam też \mathrm{rank}(\alpha+1)=\alpha+1 i kończy krok następnikowy.

3^{\circ} Wreszcie przyszła pora na krok graniczny. Niech \gamma będzie liczbą porządkową graniczną i przypuśćmy, że dla każdego \alpha<\gamma jest \mathrm{rank}(\alpha)=\alpha. Wówczas mamy dla dowolnej liczby porządkowej \alpha<\gamma, \ \alpha \subset R_{\alpha} (gdyż \alpha \in R_{\alpha+1}=\mathcal{P}(R_{\alpha})), czyli (ponieważ \mathrm{Lim}(\gamma))
\gamma= \bigcup_{\alpha<\gamma}^{} \alpha\subset  \bigcup_{\alpha<\gamma}^{} R_{\alpha}=R_{\gamma}, a więc \gamma \subset R_{\gamma}, tj.
\gamma \in R_{\gamma+1}=\mathcal{P}(R_{\gamma}).
Wobec tego \mathrm{rank}(\gamma)\le \gamma. Gdyby jednak zaszło \mathrm{rank}(\gamma)<\gamma, to istniałoby takie \eta \in \gamma, że
\gamma\in R_{\eta+1}, tj. \gamma \subset R_{\eta}.
jednak skoro \gamma jest graniczna i \eta\in \gamma, to także
\eta+1\in \gamma i z tranzytywności \eta+1\in R_{\eta+1}, ale z założenia indukcyjnego \mathrm{rank}(\eta+1)=\eta+1, w szczególności \eta+1\notin R_{\eta+1}. Sprzeczność.
Zatem \mathrm{rank}(\gamma)\le \gamma i \neg\left( \mathrm{rank}(\gamma)<\gamma\right), czyli \mathrm{rank}(\gamma)=\gamma, co kończy dowód.



Czy coś jest źle? A może coś da się zrobić sprawniej, lepiej, zgrabniej? Najbardziej obawiam się, że gdzieś niejawnie założyłem tezę, ponieważ nie rozumiem tej piekielnej matematyki.

BTW Nie wiem, co mi odbiło, że wybrałem ten kurs… Ech, jak taki troglodyta jak ja ma to zdać? Rynek zweryfikuje. :lol:
Góra
Mężczyzna Offline
PostNapisane: 22 maja 2018, o 09:02 
Administrator

Posty: 22914
Lokalizacja: Wrocław
Premislav napisał(a):
Teraz czas na krok następnikowy. Przypuśćmy, że dla pewnej liczby porządkowej \alpha zachodzi \mathrm{rank}(\alpha)=\alpha.
Ponieważ \alpha\in \alpha+1 i R_{\eta} są tranzytywne, zatem \mathrm{rank}(\alpha+1)>\mathrm{rank}(\alpha)=\alpha,

Tu zadałbym oczywiście pytanie "Dlaczego?" - jak dokładnie z tej tranzytywności ma wynikać \mathrm{rank}(\alpha+1)>\mathrm{rank}(\alpha) ?

To pytanie nie pojawiłoby się natomiast, gdyby powołano się na fakt uzasadniony na ćwiczeniach: x\in y \Rightarrow \mathrm{rank}(x)<\mathrm{rank}(y).

Premislav napisał(a):
Pokażemy teraz, że \alpha+1\in R_{\alpha+2}, czyli \mathrm{rank}(\alpha+1)\le \alpha+1, co wraz z poprzednim wnioskiem doprowadzi nas do stwierdzenia, że \mathrm{rank}(\alpha+1)=\alpha+1. Mianowicie mamy \alpha+1=\alpha\cup \left\{ \alpha\right\} i z założenia indukcyjnego mamy w szczególności, że \alpha \in R_{\alpha+1}. Ponadto jest R_{\alpha+2}=\mathcal{P}(R_{\alpha+1}), czyli wystarczy pokazać, że
\alpha+1\subset R_{\alpha+1}. Mamy, jak wspomniałem, \alpha+1=\alpha\cup\left\{ \alpha\right\} oraz \alpha\in R_{\alpha+1} z zał. indukcyjnego, a ponadto dla dowolnego \xi \in \alpha mamy \xi \in R_{\alpha+1}, co wynika z tranzytywności R_{\alpha+1}. Zatem istotnie \alpha+1\subset R_{\alpha+1}, czyli
\alpha+1\in \mathcal{P}(R_{\alpha+1})=R_{\alpha+2}, tj. \mathrm{rank}(\alpha+1)\le \alpha+1, co w połączeniu z poprzednim wnioskiem \mathrm{rank}(\alpha+1)\ge \alpha+1 daje nam też \mathrm{rank}(\alpha+1)=\alpha+1 i kończy krok następnikowy.

Dobrze (choć zauważam pewną skłonność do powtórzeń...).

Premislav napisał(a):
3^{\circ} Wreszcie przyszła pora na krok graniczny. Niech \gamma będzie liczbą porządkową graniczną i przypuśćmy, że dla każdego \alpha<\gamma jest \mathrm{rank}(\alpha)=\alpha. Wówczas mamy dla dowolnej liczby porządkowej \alpha<\gamma, \ \alpha \subset R_{\alpha} (gdyż \alpha \in R_{\alpha+1}=\mathcal{P}(R_{\alpha})), czyli (ponieważ \mathrm{Lim}(\gamma))
\gamma= \bigcup_{\alpha<\gamma}^{} \alpha\subset  \bigcup_{\alpha<\gamma}^{} R_{\alpha}=R_{\gamma}, a więc \gamma \subset R_{\gamma}, tj.
\gamma \in R_{\gamma+1}=\mathcal{P}(R_{\gamma}).
Wobec tego \mathrm{rank}(\gamma)\le \gamma. Gdyby jednak zaszło \mathrm{rank}(\gamma)<\gamma, to istniałoby takie \eta \in \gamma, że
\gamma\in R_{\eta+1}, tj. \gamma \subset R_{\eta}.
jednak skoro \gamma jest graniczna i \eta\in \gamma, to także
\eta+1\in \gamma i z tranzytywności \eta+1\in R_{\eta+1}, ale z założenia indukcyjnego \mathrm{rank}(\eta+1)=\eta+1, w szczególności \eta+1\notin R_{\eta+1}. Sprzeczność.
Zatem \mathrm{rank}(\gamma)\le \gamma i \neg\left( \mathrm{rank}(\gamma)<\gamma\right), czyli \mathrm{rank}(\gamma)=\gamma, co kończy dowód.

Dobrze.

Premislav napisał(a):
Nie wiem, co mi odbiło, że wybrałem ten kurs…

Hmmm...

Premislav napisał(a):
Ech, jak taki troglodyta jak ja ma to zdać? Rynek zweryfikuje.

Zdać nie jest aż tak trudno, trochę trzeba napracować się na czwórkę. Na ustnym na pewno będzie lepiej... :)

JK
Góra
Mężczyzna Offline
PostNapisane: 22 maja 2018, o 10:15 
Użytkownik

Posty: 12654
Jan Kraszewski napisał(a):
Dlaczego?

Gdyby dla pewnej liczby porządkowej \alpha zachodziło
\mathrm{rank}(\alpha+1)< \mathrm{rank}(\alpha), to istniałaby taka liczba porządkowa \beta< \mathrm{rank}(\alpha), że \alpha+1\in  R_{\beta+1}, a wówczas, z uwagi na \alpha\in \alpha+1 i na tranzytywność R_{\eta} także
\alpha\in R_{\beta+1}, czyli
\mathrm{rank}(\alpha)\le \beta <\mathrm{rank}(\alpha)
a to jest ewidentna sprzeczność, zatem \mathrm{rank}(\alpha+1)\ge \mathrm{rank}(\alpha).
Równości być nie może, ponieważ jeśli \alpha\cup \left\{ \alpha\right\}= \alpha+1\in R_{\gamma+1}=\mathcal{P}(R_{\gamma}) dla pewnej liczby porządkowej \gamma, to \alpha\in R_{\gamma}.
Ale faktycznie była to poważna luka.
Jan Kraszewski napisał(a):
To pytanie nie pojawiłoby się natomiast, gdyby powołano się na fakt uzasadniony na ćwiczeniach: x\in y \Rightarrow \mathrm{rank}(x)<\mathrm{rank}(y).

Słusznie, pojawił się taki fakt, nawet o nim pamiętałem (teraz, nie na kolokwium, wtedy imienia nie pamiętałem), faktycznie lepiej z niego skorzystać.

Dziękuję bardzo.
Góra
Mężczyzna Offline
PostNapisane: 22 maja 2018, o 11:13 
Administrator

Posty: 22914
Lokalizacja: Wrocław
Teraz dobrze, choć prościej byłoby stwierdzić, że gdyby \mathrm{rank}(\alpha+1)\le\alpha, to \alpha+1=\alpha\cup\{{\red \alpha}\} \subseteq R_{\alpha}, czyli {\red \alpha}\in R_\alpha, co stoi w sprzeczności z \mathrm{rank}(\alpha)=\alpha.

JK
Góra
Mężczyzna Offline
PostNapisane: 22 maja 2018, o 11:25 
Użytkownik

Posty: 12654
Racja, tak znacznie szybciej. Jeszcze raz dziękuję.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zbiór a liczby rzeczywiste  andrzej2208  6
 liczby należące do obu zbiorów  mat1989  2
 Podzielność zbioru przez liczby.  Michal663  5
 Wielokrotność liczby alef-zero  KisielPoObiedzie  11
 Liczby porządkowe - zadanie z iloczynem  filut  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl