Matematyka.pl

Dzień dobry,
Mam problem z następującym zadaniem:
W zbiorze \(\displaystyle{ \mathbb{N}^{\mathbb{N}}}\) określamy relację równoważności:
\(\displaystyle{ f\equiv g \Leftrightarrow f^{-1}[\mathbb{N}\setminus \left \{ 0,1\right \}]=g^{-1}[\mathbb{N}\setminus \left \{ 0,1\right \}]}\)
(a) Rozstzrygnij, czy istnieje funkcja \(\displaystyle{ f \in [\mathbb{N}^{\mathbb{N}}]}\) taka, że jej klasa abstrakcji \(\displaystyle{ [f]_{\equiv }}\) jest co najwyzej przeliczalna?
(b) Znajdź moc zbioru ilorazowego relacji \(\displaystyle{ \equiv}\).

Ad a) Klasy abstrakcji to funkcje, których przeciwobrazy są równe dla wszystkich naturalnych bez \(\displaystyle{ \{0,1\}}\). Czyli wszystkie funkcje z \(\displaystyle{ \mathbb{N}^{\mathbb{N}}}\), których jest continuum. Wydaje mi się, że nie istnieje przeliczalna klasa abstrakcji.
Ad b) Moc zbioru ilorazowego będzie continuum, tylko nie wiem jak to formalnie udowodnić.

Bardzo proszę o wskazówki.

Krystian_55 pisze:Ad a) Klasy abstrakcji to funkcje, których przeciwobrazy są równe dla wszystkich naturalnych bez \(\displaystyle{ \{0,1\}}\).

Klasy abstrakcji to nie funkcje, tylko zbiory funkcji.

Krystian_55 pisze:Czyli wszystkie funkcje z \(\displaystyle{ \mathbb{N}^{\mathbb{N}}}\), których jest continuum. Wydaje mi się, że nie istnieje przeliczalna klasa abstrakcji.

Udowodnij, że każda klasa abstrakcji jest mocy continuum. Postaraj się w tym celu dobrze zrozumieć, kiedy dwie funkcje są równoważne.

Krystian_55 pisze:Ad b) Moc zbioru ilorazowego będzie continuum, tylko nie wiem jak to formalnie udowodnić.

Z tw. Cantora-Bernsteina. Oszacowanie z góry jest proste, by dostać oszacowanie z dołu musisz wskazać continuum parami nierównoważnych funkcji.

JK

Z definicji klasy abstrakcji: \(\displaystyle{ [f]_{\equiv }= \left\{ g \in \mathbb{N}^{\mathbb{N}}:g\equiv f\right \}= \{ f^{-1}[\mathbb{N}\setminus\left \{ 0,1 \right\}]=g^{-1}[\mathbb{N}\setminus\left \{ 0,1 \right\}] \}}\)
A z definicji przeciwobrazu: \(\displaystyle{ f^{-1}[\mathbb{N}\setminus\left \{ 0,1 \right \}]=\left \{ x\in f:f(x)\in \mathbb{N}\setminus\left \{ 0,1 \right \} \right \}}\).

Czyli klasa abstrakcji tj zbiór elementów (funkcji), z którymi f jest w relacji \(\displaystyle{ \equiv}\) tzn ma takie same przeciwobrazy dla zbioru \(\displaystyle{ \mathbb{N}\setminus\left \{ 0,1 \right \}}\). A wiemy, że wszystkie zbiory funkcj (np funkcje rosnące, zbieżne itd) z \(\displaystyle{ \mathbb{N} \mapsto \mathbb{N}}\) spełniaja ten warunek.

Moc zbiru ilorazowego jest continuum, bo z góry:
\(\displaystyle{ \left | \mathbb{N}^{\mathbb{N}}/_{\equiv } \right |\leq \left | \mathbb{N}^{\mathbb{N}} \right |}\).
Z dołu napisał Pan, żeby wskazać continuum parami nierównowaznuch funkcji, więc myśle ze funkcje z \(\displaystyle{ \mathbb{N}\rightarrow \left \{ 0,1 \right \}}\), jest ich continuum.
Czy poprawnie myślę?

Źle, przeciwobraz każdej takiej funkcji z zadania jest pusty.

W takim razie jak znaleźć ograniczenie dolne?

Krystian_55 pisze:Z definicji klasy abstrakcji: \(\displaystyle{ [f]_{\equiv }= \left\{ g \in \mathbb{N}^{\mathbb{N}}:g\equiv f\right\}= \red{ \left\{ f^{-1}[\mathbb{N}\setminus\left\{ 0,1 \right\}]=g^{-1}[\mathbb{N}\setminus\left\{ 0,1 \right\}] \right \}}}\)

Fragment na czerwono jest bez sensu.

Krystian_55 pisze:A z definicji przeciwobrazu: \(\displaystyle{ f^{-1}[\mathbb{N}\setminus\left \{ 0,1 \right \}]=\red{\left\{ x\in f:f(x)\in \mathbb{N}\setminus\left \{ 0,1 \right \} \right \}}}\).

To nie jest poprawnie zastosowana definicja.

Krystian_55 pisze:Czyli klasa abstrakcji tj zbiór elementów (funkcji), z którymi f jest w relacji \(\displaystyle{ \equiv}\) tzn ma takie same przeciwobrazy dla zbioru \(\displaystyle{ \mathbb{N}\setminus\left \{ 0,1 \right \}}\). A wiemy, że wszystkie zbiory funkcj (np funkcje rosnące, zbieżne itd) z \(\displaystyle{ \red{\mathbb{N} \mapsto \mathbb{N}}}\) spełniaja ten warunek.

Stwierdzenie na czerwono jest bez sensu. Nie znasz funkcji \(\displaystyle{ f}\), a twierdzisz, że coś jest z nią w relacji. Co więcej, twierdzisz, że w relacji z nią są zbiory funkcji, a przecież w relacji z funkcją mogą być tylko funkcje itd.

Postaraj się porządnie formułować swoje myśli.

Krystian_55 pisze:Moc zbiru ilorazowego jest continuum, bo z góry:
\(\displaystyle{ \left | \mathbb{N}^{\mathbb{N}}/_{\equiv } \right |\leq \left | \mathbb{N}^{\mathbb{N}} \right |}\).

To oszacowanie jest w porządku.

Krystian_55 pisze:Z dołu napisał Pan, żeby wskazać continuum parami nierównowaznuch funkcji, więc myśle ze funkcje z \(\displaystyle{ \mathbb{N}\rightarrow \left \{ 0,1 \right \}}\), jest ich continuum.
Czy poprawnie myślę?

Nie. Nie jest prawdą, że dowolne dwie różne funkcje z \(\displaystyle{ \{0,1\}^\NN}\) są ze sobą nierównoważne. Jest nawet bardzo nieprawdą. Żeby znaleźć rodzinę takich funkcji trzeba najpierw zrozumieć tę relację, zrozumieć jakie funkcje utożsamia (nie chodzi o przeczytanie definicji), a to najwyraźniej jeszcze Ci się nie udało. Weź sobie konkretną funkcję z \(\displaystyle{ \NN^\NN}\), znajdź kilka funkcji z nią równoważnych, powtórz to z inną funkcją. Może pomoże.

JK

\(\displaystyle{ g\left( x\right)=2x}\) i \(\displaystyle{ h\left( x\right) =3x}\), gdzie \(\displaystyle{ x \in \mathbb{N}}\) czyli funkcje rosnące z \(\displaystyle{ \mathbb{N}^{\mathbb{N}}}\) są równoważne,bo ich przeciwobrazy to \(\displaystyle{ \mathbb{N}\setminus \left \{ 0 \right \}}\)

Funkcja identycznościowa czyli \(\displaystyle{ f\left( x\right)=x}\); jej przeciwobraz to zbiór \(\displaystyle{ \mathbb{N} \setminus \left\{ 0,1\right\}}\)

Jeśli wezmę funkcę stałą równą np 5 to przeciwobraz dla zbioru z zadania czyli \(\displaystyle{ f ^{-1} [\mathbb{N}\setminus\left\{ 0,1\right\}]}\) to całe \(\displaystyle{ \mathbb{N}}\)

Klasy abstrakcji to podziały tej relacji. Wydaje mi się, że funkcja rosnące takie jak \(\displaystyle{ f\left( x\right)=kx}\), gdzie \(\displaystyle{ k\in \mathbb{N} \wedge k \ge 2}\) tworzą jedną z klas abstrakcji.

Funkcje stałe różne od \(\displaystyle{ \left\{ 0,1\right\}}\) tworzą kolejną klasę abstrakcji. Funkcji stałych/ rosnących jest więcej niż przeliczalnie wiele.

W zadaniu pytają czy istnieje taka klasa abstrakcji, która jest co najwyżej przeliczalna. Więc można założyć nie wprost że istnieje. Wtedy nalezy pokazać, ze istnieje zbiór funkcji, których jest przeliczalnie wiele i są w relacji równoważności z f tzn. mają równw przeciwobrazy dla zbioru \(\displaystyle{ B=\mathbb{N}\setminus\left\{ 0,1\right\}}\). I tutaj nie wiem co dalej...

Wskazówka: z każdą klasą abstrakcji można związać podzbiór \(\displaystyle{ \mathbb N}\), a tych jest...?

\(\displaystyle{ \left| P\left( \mathbb{N}\right) \right|=continuum}\)
Czyli podpunkt (b)

\(\displaystyle{ \mathbb{N}/ _{\equiv}}\)\(\displaystyle{ \rightarrow P\left( \mathbb{N}\right)}\)

Ta funkcja jest na, czyli moc zbioru ilorazowego jest większa od \(\displaystyle{ continuum}\). Z twierdzenia C-B mamy, że zbiór ilorazowy jest mocy \(\displaystyle{ continuum}\)?

Krystian_55 pisze:Klasy abstrakcji to podziały tej relacji.

Krystian_55 pisze:Wydaje mi się, że funkcja rosnące takie jak \(\displaystyle{ f\left( x\right)=kx}\), gdzie \(\displaystyle{ k\in \mathbb{N} \wedge k \ge 2}\) tworzą jedną z klas abstrakcji.

Nieprawda. Są w jednej klasie abstrakcji, ale nie tworzą jej - tam jest jeszcze dużo innych funkcji.

Krystian_55 pisze:Funkcje stałe różne od \(\displaystyle{ \left\{ 0,1\right\}}\) tworzą kolejną klasę abstrakcji.

Jak wyżej - są w jednej klasie, ale nie tworzą jej.

Krystian_55 pisze:Funkcji stałych/ rosnących jest więcej niż przeliczalnie wiele.

Naprawdę uważasz, że funkcji stałych jest więcej niż przeliczalnie wiele? Co do funkcji rosnących to mam wątpliwość, co przez to rozumiesz.

Krystian_55 pisze:W zadaniu pytają czy istnieje taka klasa abstrakcji, która jest co najwyżej przeliczalna. Więc można założyć nie wprost że istnieje. Wtedy nalezy pokazać, ze istnieje zbiór funkcji, których jest przeliczalnie wiele i są w relacji równoważności z f tzn.

To nie ma sensu. Masz przecież pokazać coś wręcz przeciwnego - że takich funkcji jest nieprzeliczalnie wiele.

Krystian_55 pisze:\(\displaystyle{ \mathbb{N}/ _{\equiv}}\)\(\displaystyle{ \rightarrow P\left( \mathbb{N}\right)}\)

Ta funkcja jest na, czyli moc zbioru ilorazowego jest większa od \(\displaystyle{ continuum}\).

Po pierwsze, tu nie ma żadnej funkcji. Narysowałeś kilka znaczków, ale funkcji nie ma tu żadnej.
Po drugie, gdyby jednak pojawiła się jakaś funkcja "na", to na pewno nie znaczyłoby to, że moc zbioru ilorazowego jest większa od \(\displaystyle{ \mathfrak{c}}\).

JK

Z każdą klasą abstrakcji powiążmy podzbiór \(\displaystyle{ \mathbb{N}}\), w ten sposób, że do jednej klasy abstrakcji trafiają funkcje, których przeciwobraz jest jednoelementowy. Do tej klasy należy np funkcja, która dla \(\displaystyle{ x=1}\) przyjmuje wartość 5, a dla pozostałych argumentów jest równa 0. Czy to jest klasa abstrakcji?

Klasa abstrakcji: zbiór funkcji, których przeciwobraz jest zbiorem jednoelementowym/ dwuelementowym itd.

Krystian_55 pisze:Z każdą klasą abstrakcji powiążmy podzbiór \(\displaystyle{ \mathbb{N}}\), w ten sposób, że do jednej klasy abstrakcji trafiają funkcje, których przeciwobraz jest jednoelementowy.

Ja nie rozumiem tego powiązania - pierwszy człon tego zdania złożonego nie ma żadnego związku z drugim.
Najpierw deklarujesz, że chcesz z każdą klasą abstrakcji w jakiś sposób związać podzbiór \(\displaystyle{ \NN}\), po czym nagle (zamiast opisać, na czym polega to związanie) wskazujesz jakiś zbiór funkcji.

Krystian_55 pisze:Do tej klasy należy np funkcja, która dla \(\displaystyle{ x=1}\) przyjmuje wartość 5, a dla pozostałych argumentów jest równa 0.

Ta funkcja należy do opisanego poprzednio zbioru funkcji.

Krystian_55 pisze:Czy to jest klasa abstrakcji?

Nie.

Ale niezależnie od tego, czym jest ten zbiór funkcji, jaki to ma związek z zadaniem?

JK

Medea 2 pisze:Wskazówka: z każdą klasą abstrakcji można związać podzbiór \(\displaystyle{ \mathbb N}\), a tych jest...?

Można zapytać w jaki sposób związać klasy abstrkcji z podzbiorem \(\displaystyle{ \mathbb N}\)?

Musisz zacząć od zrozumienia tej relacji, wtedy będziesz wiedział, jaka jest odpowiedź na Twoje pytanie.

Kiedy dwie funkcje są równoważne? Co jest cechą łącząca funkcje równoważne? Co te funkcje mają wspólnego ze sobą? I nie chodzi o przeczytanie definicji, tylko o jej zrozumienie - spróbuj wypowiedzieć to własnymi słowami.

JK

funkcje są w tej relacji, jeśli ich przeciwobrazy są równe. Przeciwobraz funkcji to zbiór argumentów tej funkcji, który spełnia własność, że wartość funkcji dla tych argumentów nalezy do zadanego zbioru. Zbiory są równe jeśli każdy element zboru pierwszego należy do zbioru drugiego i odwrotnie. Do tych zbiorów argumentów może należeć przeliczalnie wiele argumentów (co najwyżej \(\displaystyle{ \mathbb N}\)). Skoro klasy abstrakcji utożsamiamy z podziałami, to tutaj możemy klasy abstrakcji utożsamić ze zbiorami funkcji, których przeciwobrazy tworzą podzbiory zbioru na którym określamy te funkcje, czyli \(\displaystyle{ \mathbb N}\).

Wydaje mi się, że cecha, która łączy dwie funkcje równoważne to liczba elementów zbioru argumentów. Nie wiem czy ten opis jest prawidłowy. Gdzieś przeczytałem, że na klasy abstrakcji należy popatrzeć z góry. Tzn mam continuum funkcji z \(\displaystyle{ \mathbb N ^{\mathbb N}}\) i zadaną relację. Jedyna cecha jaką widzę to liczba elementów zbioru argumentów, tworzących ten przeciwobraz.