Dalsze zagadnienia

Będę tu prezentował dodatkowe, raczej proste zadania( bo były fajne zadania, które zostawiłem na potem). Będą to raczej proste problemy.

Uzasadnimy najpierw, że dla dwóch rodzin zbiorów [math]\mathbb{X}, \mathbb{Y}[/math] nie zawsze zachodzi równość zbiorów:

[math]\bigcap\left( \mathbb{X} \cap \mathbb{Y}\right)= \bigcap \mathbb{X} \cap \bigcap \mathbb{Y}.[/math]

Jako kontrprzykład dla tej równości połóżmy [math]X=\left\{ 1,2\right\} [/math] [math]Y=\left\{ 2,3\right\}[/math] oraz [math]\mathbb{X}=\left\{ X\right\}, \mathbb{Y}=\left\{ Y\right\}.[/math]

Wtedy [math]\bigcap \mathbb{X}=X[/math], podobnie [math]\bigcap \mathbb{Y}=Y[/math], zatem [math]\bigcap \mathbb{X} \cap \bigcap \mathbb{Y}=X\cap Y=\left\{ 2\right\}.[/math]

Podczas gdy [math]\mathbb{X} \cap \mathbb{Y}=\emptyset[/math], bo zbiory [math]X\neq Y[/math], zatem [math]\bigcap\left( \mathbb{X} \cap \mathbb{Y}\right)=\bigcap\emptyset=\emptyset\neq\left\{ 2\right\}[/math], równość więc nie jest prawdą.

Zastanówmy się nad inkluzjami dla rodziny zbiorów [math]\mathbb{X}[/math]: [math]\bigcup\mathbb{X}\subset \mathbb{X}[/math], oraz [math]\bigcup\mathbb{X}\supset \mathbb{X}.[/math] Otóż, wbrew pozorom, ta ostatnia inkluzja jest o wiele bardziej nietypowa. Pierwsza inkluzja mówi, że elementy [math]\bigcup\mathbb{X}[/math] są elementami [math]\mathbb{X}[/math], czyli elementy elementów [math]\mathbb{X}[/math] (zbiorów rodziny [math]\mathbb{X}[/math]) są elementami [math]\mathbb{X}[/math]- są to tzw. zbiory(rodziny zbiorów) przechodnie. Równoważnie to możemy określić warunkiem [math]\mathbb{X}\subset P\left( \mathbb{X}\right)[/math], bo ten warunek oznacza, że zbiory rodziny [math]\mathbb{X}[/math] są elementami [math]P\left( \mathbb{X}\right)[/math], czyli są podzbiorami [math]\mathbb{X}[/math], w związku z czym ich elementy są elementami [math]\mathbb{X}[/math], czyli to oznacza, że elementy elementów [math]\mathbb{X}[/math] są elementami [math]\mathbb{X}[/math]. O takich zbiorach przechodnich będziemy jeszcze pisać.

Natomiast inkluzja [math]\bigcup\mathbb{X}\supset \mathbb{X}.[/math] jest o wiele dziwniejsza. Mówi ona, że zbiory rodziny [math]\mathbb{X}[/math] są elementami [math]\bigcup\mathbb{X}[/math], a więc elementów tych zbiorów. A to przecież elementy zbiorów rodziny [math]\mathbb{X}[/math] są elementami odpowiednich zbiorów. Jednak taka dziwaczna inkluzja jest możliwa. Niech [math]\mathbb{X}[/math] będzie dowolną rodziną induktywną (tzn. spełniającą aksjomat nieskończoności). Wykażemy, że wtedy [math]\bigcup\mathbb{X}\supset \mathbb{X}.[/math]

Niech [math]A\in\mathbb{X}.[/math] Pokażemy, że [math]A\in\bigcup\mathbb{X}.[/math] Ponieważ [math]\mathbb{X}[/math] jest zbiorem induktywnym, to [math]A'=A\cup\left\{ A\right\}\in\mathbb{X}[/math], ponieważ [math]A\in A\cup\left\{ A\right\}\in\mathbb{X}[/math], to [math]A\in\bigcup\mathbb{X}. \square[/math]

Zastanówmy się teraz uważnie nad pytaniem: Czy istnieje więcej niż jeden zbiór(rodzina zbiorów) [math]\mathbb{X}[/math] taka, że [math]\bigcap \mathbb{X} = \bigcup \mathbb{X}[/math]?

Otóż wiemy, że dla dowolnego zbioru [math]X[/math] mamy [math]\bigcap \left\{X\right\}=X=\bigcup \left\{X\right\},[/math] a więc istnieje przynajmniej jedna taka rodzina zbiorów. Biorąc teraz dwa różne zbiory [math]A,B[/math], zauważamy, że wtedy rodziny zbiorów [math]\left\{A\right\}, \left\{B\right\}[/math] są różne (bo zbiory [math]A,B[/math] są różne). Zgodnie z przytoczonym faktem [math]\bigcap \left\{A\right\}=A=\bigcup \left\{A\right\},[/math] oraz [math]\bigcap \left\{B\right\}=B=\bigcup \left\{B\right\}[/math], wobec czego istnieją co najmniej dwie rodziny zbiorów [math]\mathbb{X}[/math], takie,że iloczyn rodziny [math]\mathbb{X}[/math] jest równy sumie rodziny [math]\mathbb{X}[/math].

Dla dowolnego zbioru [math]X[/math], mamy: [math]\bigcup P\left( X\right)=X.[/math]

Dowód: Aby pokazać, że [math]\bigcup P\left( X\right)=X,[/math] pokazujemy dwa zawierania.

Inkluzja w prawo: Suma rodziny wszystkich podzbiorów [math]X[/math], a więc suma szczególnej rodziny podzbiorów [math]X[/math] musi być podzbiorem [math]X[/math].

Inkluzja w lewo: Wiemy,że suma dowolnej rodziny zbiorów jest nadzbiorem każdego zbioru tej rodziny, więc suma rodziny wszystkich podzbiorów [math]X[/math] jest nadzbiorem [math]X[/math] (bo [math]X \subset X[/math], a więc [math]X\in P\left( X\right)[/math]).

A więc [math]\bigcup P\left( X\right)=X.\square[/math]

Dla dowolnej rodziny zbiorów [math]\mathbb{X}[/math] mamy:

[math]\mathbb{X}\subset P\left( \bigcup \mathbb{X}\right).[/math]

Dowód: Niech [math]A\in\mathbb{X}[/math]. Skoro [math]A[/math] jest zbiorem z rodziny [math]\mathbb{X}[/math], to z własności sumy [math]A[/math] jest podzbiorem sumy tej rodziny, czyli [math]A\subset \bigcup \mathbb{X}.[/math] To z kolei oznacza, że [math]A\in P\left( \bigcup \mathbb{X}\right)[/math], i z dowolności [math]A[/math], otrzymujemy [math]\mathbb{X}\subset P\left( \bigcup \mathbb{X}\right).\square[/math]

Jednak inkluzja w drugą stronę nie zawsze zachodzi. Kontrprzykładem będzie rodzina [math]\mathbb{X}= \{\{\emptyset\}\}.[/math] Wtedy:

[math]\mathcal{P}(\bigcup\{\{\emptyset\}\} \ \ )= \mathcal{P}(\{\emptyset\}) = \{\emptyset,\{\emptyset\}\}\neq \{\{\emptyset\}\}=\mathbb{X},[/math] bo [math]\emptyset\notin \{\{\emptyset\}\}[/math], bo [math]\emptyset\neq \{\emptyset\}.[/math] Zatem tutaj [math]\mathbb{X}\neq P\left( \bigcup \mathbb{X}\right).[/math]

Jeśli mamy funkcję [math]f:X\rightarrow X[/math], to element [math]x\in X[/math] nazywamy punktem stałym funkcji [math]f[/math], gdy [math]f(x)=x.[/math]

Niech [math]X[/math] będzie zbiorem. Rozważmy funkcję [math]f:P\left( P\left( X\right) \right) \rightarrow P\left( P\left( X\right) \right),[/math] określoną jako:

[math]f\left( x\right)=\left\{ \bigcup x, \bigcap x\right\} .[/math]

Czyli funkcja [math]f[/math] dostaje jako argument rodzinę podzbiorów [math]X[/math], i przypisuje jej rodzinę złożoną z dwóch zbiorów- zbioru będącego sumą tej rodziny oraz zbioru będącego iloczynem tej rodziny. Podamy kilka przykładów punktów stałych dla tej funkcji.

Dla dowolnego zbioru [math]A\subset X[/math], mamy [math]f\left( \left\{ A\right\} \right)=\left\{ \bigcup \left\{ A\right\} , \bigcap \left\{ A\right\} \right\}=\left\{ A,A\right\} =\left\{ A\right\} .[/math] A więc rodzina [math]\left\{ A\right\}[/math] jest punktem stałym. Kolejne przykłady:

Dla dowolnego zbioru [math]A \subset X[/math], mamy [math]f\left( \left\{ A,\emptyset \right\} \right)=\left\{ \bigcup\left\{ A,\emptyset \right\}, \bigcap\left\{ A,\emptyset \right\} \right\}=\left\{ A \cup \emptyset, A \cap \emptyset \right\}=\left\{ A,\emptyset \right\}.[/math]

Dla dowolnych zbiorów [math]A,B \subset X[/math], takich, że [math]A \subset B[/math] mamy: [math]f\left( \left\{ A,B\right\} \right)=\left\{ A \cup B, A \cap B\right\}=\left\{ B,A\right\}=\left\{ A,B\right\},[/math] gdzie przedostatnia równość pochodzi z założenia, że [math]A \subset B.[/math]

Zwróćmy uwagę, że istnieją funkcje, które nie mają punktów stałych. Prostym przykładem może być funkcja [math]f:\left\{ 0,1\right\} \rightarrow \left\{ 0,1\right\},[/math] daną jako [math]f=\left\{ \left( 0,1\right),\left( 1,0\right) \right\}.[/math]

Kolejny przykład. Niech [math]X[/math] będzie niepustym zbiorem. Wykażemy, że dla funkcji [math]f:P\left( X\right) \rightarrow P\left( X\right),[/math] określonej jako [math]f\left( A\right)=X \setminus A[/math], nie istnieje punkt stały.

Przypuśćmy, że istnieje punkt stały, nazwijmy go [math]A[/math]. Wtedy [math]f\left( A\right)=A.[/math] Z drugiej strony, z definicji tej funkcji mamy [math]f\left( A\right)=X \setminus A.[/math] Wnioskujemy, że [math]A=X \setminus A.[/math] Ponieważ zbiór [math]X[/math] jest niepusty, więc istnieje element [math]x \in X,[/math] ustalamy taki element. Rozstrzygnijmy problem czy [math]x \in A.[/math] Jeśli tak, to z tej równości wynika, że [math]x \in X \setminus A[/math], a więc z definicji różnicy zbiorów [math]x \notin A[/math]- sprzeczność. Jeśli [math]x\notin A[/math], to [math]x \in X \setminus A,[/math] a więc z tej równości wynika, że [math]x \in A[/math], i również otrzymujemy sprzeczność, co kończy ten prosty dowód.[math]\square[/math]

Dla funkcji [math]f:P\left( X\right) \rightarrow P\left( X\right),[/math] zbiór [math]A \subset X[/math] nazywamy najmniejszym punktem stałym, gdy [math]f\left( A\right)=A,[/math] (czyli [math]A[/math] jest punktem stałym) oraz dla dowolnego zbioru [math]B \subset X[/math] spełniony jest warunek [math]f\left( B\right)=B \rightarrow A \subset B.[/math] Czyli gdy każdy punkt stały [math]B[/math] jest większy pod względem inkluzji od [math]A[/math]- od tego najmniejszego punktu stałego, czyli zbiór [math]B[/math] jest nadzbiorem zbioru [math]A[/math].

Podobnie dla funkcji [math]f:P\left( X\right) \rightarrow P\left( X\right),[/math] zbiór [math]A \subset X[/math] nazwiemy największym punktem stałym, gdy jest punktem stałym, oraz każdy zbiór [math]B \subset X[/math] będący punktem stałym jest podzbiorem [math]A[/math], czyli wtedy zbiór [math]A[/math] jest większy pod względem inkluzji od [math]B[/math].

Poniższy przykład pokazuje, że dla funkcji może się zdarzyć, że mimo, że istnieją punkty stałe, ale nie istnieje największy punkt stały.

Niech [math]X[/math] będzie niepustym zbiorem. Rozważmy funkcję [math]f:P\left( P\left( X\right) \right) \rightarrow P\left( P\left( X\right) \right)[/math], określoną jako [math]f\left( \mathbb{A}\right)= \left\{ \bigcup \mathbb{A} \right\},[/math] czyli funkcja [math]f[/math] dostaje jako argument rodzinę podzbiorów [math]X[/math], i przypisuje jej zbiór jednoelementowy złożony z sumy tej rodziny. Jeśli [math]\mathbb{A}[/math] jest rodziną podzbiorów [math]X[/math], która jest punktem stałym, to wtedy [math]f\left( \mathbb{A}\right)=\mathbb{A}= \left\{ \bigcup \mathbb{A} \right\}.[/math] Widać więc, że punktami stałymi mogą być tylko rodziny jednozbiorowe (jednoelementowe)- bo zbiór [math]\left\{ \bigcup \mathbb{A} \right\}[/math] jest jednoelementowy. Wykażemy teraz, że każda rodzina jednozbiorowa jest punktem stałym. Niech [math]A \subset X.[/math] Pokazujemy, że [math]\left\{ A\right\}[/math] jest punktem stałym. Z określenia funkcji mamy [math]f\left( \left\{ A\right\} \right)= \left\{ \bigcup \left\{ A\right\} \right\}=\left\{ A\right\}.[/math] Zatem [math]\left\{ A\right\}[/math] jest punktem stałym. Zatem dla tej funkcji punktami stałymi są dokładnie rodziny jednozbiorowe. Ponieważ [math]X[/math] jest niepusty, więc ma co najmniej dwa różne podzbiory [math]A,B[/math] (np. [math]\emptyset[/math] i [math]X[/math]). Ustalmy dwa takie różne podzbiory [math]A,B.[/math] Wtedy rodziny zbiorów [math]\left\{ A\right\},\left\{ B\right\}[/math] są różne ( bo zbiory [math]A,B[/math] są różne). Zgodnie z udowodnioną własnością rodziny zbiorów [math]\left\{ A\right\},\left\{ B\right\}[/math] są punktami stałymi. Gdyby istniał tu największy punkt stały, to musiałby być nadzbiorem [math]\left\{ A\right\}[/math] oraz [math]\left\{ B\right\},[/math] zatem musiałby mieć co najmniej dwa elementy ([math]A,B[/math]). A ponieważ jest to punkt stały, i punktami stałymi są dokładnie rodziny jednozbiorowe otrzymujemy sprzeczność. Wobec czego tu nie istnieje największy punkt stały ( choć istnieją co najmniej dwa punkty stałe).

Jednak każda funkcja [math]f:P\left( X\right) \rightarrow P\left( X\right)[/math], która jest monotoniczna ze względu na inkluzję, posiada najmniejszy punkt stały oraz ma największy punkt stały.

Monotoniczna pod względem inkluzji, tzn. spełnia warunek dla dowolnych zbiorów [math]A,B \subset X[/math]:

[math]A \subset B \rightarrow f\left( A\right) \subset f\left( B\right).[/math]

Warunek ten mówi, że jeśli na argumentach funkcji zachodzi inkluzja (przypominamy,że argumentami i wartościami funkcji są tu podzbiory zbioru [math]X[/math]), to na odpowiadających im wartościach również zachodzi (zgodna) inkluzja. Funkcję monotoniczne ze względu na inkluzję zachowują relację inkluzji pomiędzy przekształcanymi zbiorami.