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

Posty: 12532
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:
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 22 maja 2018, o 09:02 
Administrator

Posty: 22651
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 Online
PostNapisane: 22 maja 2018, o 10:15 
Użytkownik

Posty: 12532
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: 22651
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 Online
PostNapisane: 22 maja 2018, o 11:25 
Użytkownik

Posty: 12532
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 
 Liczby wymierne i niewymierne - zadanie 2  lokuero  7
 Wyznacz wszystkie wartości liczby m  wirus1910  3
 działania łączne i przemienne - l. porządkowe i naturaln  Jutrzas  1
 Porównanie liczby podzbiorów  patry93  7
 liczby należące do obu zbiorów  mat1989  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl