W zbiorze \(\displaystyle{ \mathbb{N} \rightarrow \mathbb{N}}\) wszystkich funkcji z \(\displaystyle{ \mathbb{N}}\) do \(\displaystyle{ \mathbb{N}}\) określono relację \(\displaystyle{ \le }\) w ten sposób, że
\(\displaystyle{ f \le g \Leftrightarrow \forall n.f(n) \le g(n)}\).
Udowodnić, że \(\displaystyle{ \le }\) jest częściowym porządkiem. Wskazać wszystkie elementy minimalne,
najmniejsze, maksymalne, największe. Podać przykład nieskończonego łańcucha i nieskończonego antyłańcucha. Czy jest to porządek liniowy? Czy jest gęsty?
Dodano po 9 minutach 34 sekundach:
Dowód tego, że \(\displaystyle{ \le }\) jest częściowym porządkiem:
- Zwrotna: oczywiście, że \(\displaystyle{ f(n) \le f(n)}\).
- Antysymetryczna: jeżeli \(\displaystyle{ g(n) \le f(n)}\) i \(\displaystyle{ f(n) \le g(n)}\), to \(\displaystyle{ g(n) = f(n)}\).
- Przechodnia: dla dowolnych \(\displaystyle{ f(n), g(n), h(n)}\) jeżeli \(\displaystyle{ f(n) \le g(n) }\) i \(\displaystyle{ g(n) \le h(n)}\), to, oczywiście \(\displaystyle{ f(n) \le h(n)}\).
Augustyn Kaczmarek pisze: ↑15 gru 2023, o 21:30
Dowód tego, że \(\displaystyle{ \le }\) jest częściowym porządkiem:
- Zwrotna: oczywiście, że \(\displaystyle{ f(n) \le f(n)}\).
- Antysymetryczna: jeżeli \(\displaystyle{ g(n) \le f(n)}\) i \(\displaystyle{ f(n) \le g(n)}\), to \(\displaystyle{ g(n) = f(n)}\).
- Przechodnia: dla dowolnych \(\displaystyle{ f(n), g(n), h(n)}\) jeżeli \(\displaystyle{ f(n) \le g(n) }\) i \(\displaystyle{ g(n) \le h(n)}\), to, oczywiście \(\displaystyle{ f(n) \le h(n)}\).
Wypadałoby jednak dodać, czym jest \(\displaystyle{ n}\), a dokładniej - uwzględnić w rozumowaniu kwantyfikator ogólny z definicji porządku.
Augustyn Kaczmarek pisze: ↑15 gru 2023, o 21:30
Nie wiem, jak zrobić inne pytania.
A próbowałeś? Elementy wyróżnione są proste - wystarczy wziąć definicje i zrozumieć, co oznaczają w tym konkretnym porządku. Czym byłby np. element najmniejszy?
Na przykład, niech \(\displaystyle{ f(n_1) = 1}\), a \(\displaystyle{ g(n_1) = 2}\). Wtedy \(\displaystyle{ f(n_1) \le g(n_1)}\), ale \(\displaystyle{ g(n_1) \nleq f(n_1)}\).
Czy mój dowód jest poprawny? Dodano po 41 minutach 15 sekundach:
Przepraszam, nie zauważyłem \(\displaystyle{ \vee}\)
Wtedy nie będzie, bo możemy wskazać antyłańcuch. Dobrze?
Ten porządek na funkcjach z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) nie jest liniowy, bo wykres jednej takiej funkcji w jednym punkcie może leżeć poniżej niż wykres drugiej funkcji, a w innym punkcie wykres takiej funkcji może leżeć powyżej niż wykres drugiej funkcji w tym punkcie. Oznacza to, że żadna z tych dwóch funkcji nie jest mniejsza, i ten porządek na funkcjach nie jest liniowy.
Ta "definicja" wygląda bardzo źle, bo \(\displaystyle{ f(n),g(n)}\) to nie funkcje, tylko wartości funkcji (czyli liczby). Powinno być:
\(\displaystyle{ \forall f,g\in\NN^\NN (f \le g \vee g \le f).}\)
Augustyn Kaczmarek pisze: ↑17 gru 2023, o 22:04Na przykład, niech \(\displaystyle{ f(n_1) = 1}\), a \(\displaystyle{ g(n_1) = 2}\). Wtedy \(\displaystyle{ f(n_1) \le g(n_1)}\), ale \(\displaystyle{ g(n_1) \nleq f(n_1)}\).
Czy mój dowód jest poprawny?
Nie, bo nie wiadomo, co znaczy. Nie wiadomo, co to jest \(\displaystyle{ n_1}\), nie są też zdefiniowane funkcje, które miałyby być kontrprzykładem.
Augustyn Kaczmarek pisze: ↑17 gru 2023, o 22:04Przepraszam, nie zauważyłem \(\displaystyle{ \vee}\)
Wtedy nie będzie, bo możemy wskazać antyłańcuch. Dobrze?
Po pierwsze, deklaracja, że coś można zrobić nie jest dowodem.
Po drugie, wystarczy wskazać dwie nieporównywalne funkcje. Ale trzeba je porządnie zdefiniować (i pokazać, że są nieporównywalne).
