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.

Ilustracja funkcji za pomocą grafu

Przypomnijmy intuicję ze szkoły, że funkcja pomiędzy dwoma zbiorami, to przyporządkowanie każdemu elementowi pierwszego zbioru dokładnie jednego elementu drugiego zbioru. U nas rolę przyporządkowania w sposób ścisły pełni relacja pomiędzy tymi zbiorami. Każda funkcja jest zatem zbiorem par uporządkowanych. Spróbujemy jednak zilustrować funkcję za pomocą grafu. Wiemy, że funkcja jest zbiorem par, a każdy zbiór jest (sam w sobie) nieuporządkowany. Możemy zatem te pary ustawić w takiej kolejności jak chcemy. Weźmy element dziedziny [math]x \in X[/math], z definicji funkcji jest mu przypisany dokładnie jeden element [math]y\in Y[/math]. Łączymy te elementy, łączymy wszystkie elementy dziedziny którym jest przypisana wartość [math]y[/math] z elementem [math]y[/math]. Bierzemy kolejny inny element dziedziny funkcji [math]x _{1}[/math], przypisany jest mu jeden element [math]y _{1}[/math]. Łączymy te elementy, łączymy wszystkie elementy dziedziny którym jest przypisana wartość [math]y_{1}[/math] z elementem [math]y _{1}[/math]. Bierzemy kolejny inny element dziedziny funkcji [math]x _{2}[/math], robimy ten proces aż się wyczerpią elementy dziedziny(u nas cztery serie- zobacz ilustrację obok).