\documentclass[12pt,a4paper]{article}
\frenchspacing
\usepackage[nohead]{geometry}
\usepackage{amssymb}
\usepackage{mathtime,array}
\def\boldmath{\relax}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage[polish]{babel}
\geometry{nohead}
\newcommand{\rsym}{\mathrel{\shortstack{$\cdot$\\[-1.4ex]$-$}}}
\newcommand{\p}[1]{\langle#1\rangle}
\usepackage{ntheorem}
\theoremheaderfont{\normalfont\bfseries}
\theoremseparator{.}
\theorembodyfont{\normalfont\upshape}
\theoremstyle{plain}
\newtheorem{zadanie}{Zadanie}
\theoremstyle{nonumberplain}
\newtheorem{rozwiazanie}{Rozwiązanie}
\makeatletter
\newcommand\krok{\@startsection{subparagraph}{5}{\parindent}%
                                       {1ex \@plus.5ex \@minus .2ex}%
                                       {-.5em}%
                                      {\normalfont\normalsize\itshape}}
\makeatother
\begin{document}
\title{Logika dla informatyków}
\author{Egzamin połówkowy z~30 listopada 2002}
\date{Rozwiązania wybranych zadań}
\maketitle

\begin{zadanie}
Niech~$I$ oznacza relację identyczności na zbiorze~$X$.
Udowodnij, że relacja $R\subseteq X\times X$ jest relacją
równoważności wtedy i~tylko wtedy, gdy spełniony jest warunek
\[I\subseteq R \wedge R^{-1}=R \wedge RR\subseteq R.\]
\end{zadanie}

\begin{rozwiazanie}
Jest to bardzo proste zadanie, tak proste, że chciałoby się napisać
tylko, że jest oczywiste. Warunki $I\subseteq R$ i $RR\subseteq R$
są niemal identyczne odpowiednio z~warunkami z~definicji zwrotności
i~symetryczności relacji $R$.
Z~tego powodu przedstawiony dowód
może będzie zbyt szczegółowy.
Weźmy zbiór $X$ i~relację $R\subseteq X\times X$.

\krok{Krok 1.}
Pokażemy, że $R$ jest relacją zwrotną w~zbiorze $X$
wtedy i~tylko wtedy, gdy $I\subseteq R$.
Dowód równoważności składa się oczywiście
z~dowodu dwóch implikacji.

Najpierw załóżmy, że $R$ jest relacją zwrotną w~zbiorze $X$.
Aby dowieść, że $I\subseteq R$, weźmy dowolny element
$p\in I$. Oczywiście, $p$ jest parą uporządkowaną
(ponieważ $I$ jest relacją), obie współrzędne $p$
należą do $X$ (gdyż $I$ jest relacją w~zbiorze $X$)
i~są sobie równe (dlatego, że $I$ jest relacją identyczności).
Tak więc $p=\p{x,x}$ dla pewnego $x\in X$.
Ponieważ $R$ jest zwrotna, więc
$p=\p{x,x}\in R$. W~ten sposób dowód zawierania $I\subseteq R$
został zakończony.

Aby dowieść zwrotność relacji $R$,
wystarczy dla dowolnego elementu $x\in X$ pokazać,
że para $\p{x,x}$ należy do $R$. Oczywiście,
$\p{x,x}\in I$ na podstawie definicji relacji
identycznościowej. Stąd i~z zawierania $I\subseteq R$
otrzymujemy, że $\p{x,x}\in R$.

\krok{Krok 2.}
Teraz pokażemy, że relacja $R$ jest symetryczna
wtedy i~tylko wtedy, gdy $R^{-1}=R$.
Podobnie jak w~kroku 1 udowodnimy dwie implikacje.

Jeżeli relacja $R$ jest symetryczna, to dowolna
para $\p{x,y}$ z~relacji $R$ (a właściwie dowolny element relacji $R$)
należy także do relacji $R^{-1}$. Tak jest, ponieważ
z~warunku $\p{x,y}\in R$ wynika, że $\p{y,x}\in R$, a~to z~kolei
oznacza, że $\p{x,y}\in R^{-1}$.
Przedstawione rozumowanie świadczy o~tym,
że symetryczna relacja $R$ spełnia warunek $R\subseteq R^{-1}$.
Podobnie dowodzimy zawieranie odwrotne:
jeżeli $\p{x,y}\in R^{-1}$, to korzystając z~definicji relacji
odwrotnej otrzymujemy, że $\p{y,x}\in R$, a~jeżeli skorzystamy
jeszcze z~symetryczności $R$,
to otrzymamy, że $\p{x,y}\in R$.
Dla relacji symetrycznej prawdziwe są więc dwa zawierania:
$R\subseteq R^{-1}$ i $R^{-1}\subseteq R$.
Wobec tego, prawdziwa jest też równość $R=R^{-1}$.

W~drugą stronę, relacja spełniają warunek $R=R^{-1}$
spełnia także zawieranie $R\subseteq R^{-1}$.
To zawieranie oznacza, że $R$ jest relacją symetryczną.
Jeżeli bowiem $\p{x,y}\in R$, to na podstawie tego zawierania
mamy, że $\p{y,x}\in R^{-1}$. Jeżeli teraz skorzystamy z~definicji
relacji odwrotnej, to otrzymamy, że $\p{y,x}\in R$.

\krok{Krok 3.}
Pokażemy jeszcze, że przechodniość relacji $R$ jest
równoważna zawieraniu $RR\subseteq R$.

Załóżmy, że $R$ jest relacją przechodnią i $\p{x,y}\in RR$.
Z~definicji złożenia relacji wynika, że istnieje $z$ taki, że
$\p{x,z}\in R$ i  $\p{z,y}\in R$. Jeden z~takich $z$ oznaczmy symbolem $z_0$.
Element $z_0$ ma więc dwie własności: $\p{x,z_0}\in R$ oraz $\p{z_0,y}\in R$.
Z~przechodniości relacji $R$ otrzymujemy, że $\p{x,y}\in R$.
Kończy to dowód zawierania $RR\subseteq R$.

Jeżeli $RR\subseteq R$, to relacja $R$ jest przechodnia.
Aby się o~tym przekonać weźmy $x$, $y$ i $z$
takie, że $\p{x,y}\in R$ i $\p{y,z}\in R$. Z~definicji złożenia relacji
wynika, że $\p{x,z}\in RR$. Założone zawieranie implikuje
więc, że $\p{x,z}\in R$, i~to kończy dowód przechodniości
relacji $R$.

\krok{Krok 4.}
Z~kroków 1, 2 i~3 wynika równoważność z~zadania 1. Aby się o~tym przekonać, wystarczy zauważyć,
że jeżeli zdania $\varphi_i$ są równoważne zdaniom $\psi_i$ dla $i=1,2,3$,
to koniunkcja $
\varphi_1\wedge\varphi_2\wedge\varphi_3$ jest
równoważna koniunkcji $
\psi_1\wedge\psi_2\wedge\psi_3$.
\end{rozwiazanie}

\begin{zadanie}
Pokaż, że
\begin{equation}\label{rown1}
(A_1\cup A_2)\rsym(B_1\cup B_2)\subseteq (A_1\rsym B_1)\cup(A_2\rsym
B_2).
\end{equation}
Czy zawieranie
\begin{equation}\label{rown4}
(A_1\cap A_2)\rsym(B_1\cap B_2)\subseteq (A_1\rsym B_1)\cup(A_2\rsym
B_2)
\end{equation}
jest prawdziwe dla dowolnych zbiorów $A_1$, $A_2$, $B_1$ i $B_2$?

\noindent Odpowiedź uzasadnij.
\end{zadanie}

\begin{rozwiazanie}
Zaczynamy od pierwszej inkluzji.
Zgodnie z~definicją, aby dowieść zawieranie $X\subseteq Y$
powinniśmy wziąć dowolny element $x\in X$ i~o tym elemencie dowieść,
że należy do zbioru $Y$. Weźmy więc
$x\in (A_1\cup A_2)\rsym(B_1\cup B_2)$.
Z~definicji różnicy symetrycznej wiemy, że
element ten spełnia równoważność
\begin{equation}\label{rown2}
x\in (A_1\cup A_2)\Leftrightarrow x\not\in(B_1\cup B_2).
\end{equation}
Na podstawie tej równoważności niewiele potrafimy rozstrzygnąć.
Załóżmy więc dodatkowo, że zachodzi
\krok{Przypadek 1:}
$x\in (A_1\cup A_2)$.
Z~równoważności (\ref{rown2}) otrzymujemy, że
$x\not\in(B_1\cup B_2)$. Wobec tego, zarówno $x\not\in B_1$,
jak i $x\not\in B_2$.
Dalsze rozumowanie też będzie polegać na rozważeniu
kolejnych przypadków.

\krok{Przypadek 1.1:}
$x\in A_1$. Wiemy już, że $x\not\in B_1$.
Zachodzi więc także równoważność
\begin{equation}\label{rown3}
x\in A_1\Leftrightarrow x\not\in B_1,
\end{equation}
np. dlatego, że w~rozważany przypadku
obie strony tej równoważności są prawdziwe,
albo dlatego, że dowodzenie tej równoważności
polega na wykazaniu dwóch implikacji stwierdzających,
że przy pewnych założeniach zachodzą
fakty, których prawdziwość udało nam się wcześniej
ustalić. Równoważność (\ref{rown3}) oznacza, że
$x\in(A_1\rsym B_1)$, i~tym bardziej, $x$ należy do
prawej strony wzoru (\ref{rown1}).

\krok{Przypadek 1.1:}
$x\in A_2$. W~tym przypadku, tak jak w~poprzednim,
dowodzimy, że $x\in A_2\Leftrightarrow x\not\in B_2$,
i~w~konsekwencji, $x$ należy do drugiego składnika
prawej strony wzoru (\ref{rown1}).

\krok{Przypadek 2:}
$x\not\in (A_1\cup A_2)$.
Z~równoważności (\ref{rown2}) otrzymujemy teraz, że
$x\in (B_1\cup B_2)$. Mamy więc sytuację analogiczną
do opisanej w~przypadku 1. Dalszy dowód prowadzimy tak,
jak w~przypadku 1 zastępując $A_1$ i $A_2$ zbiorami $B_1$ oraz $B_2$,
i~odwrotnie.

Zawieranie (\ref{rown4}) jest też prawdziwe dla wszystkich zbiorów
i~można się o~tym przekonać w~bardzo podobny sposób.
Proponuję, aby zainteresowane osoby same przekształciły podany
dowód zawierania (\ref{rown1}) w~dowód inkluzji (\ref{rown4}).
W~przypadku 1 w~przekształconym dowodzie powinna być rozważana sytuacja, 
w~której $x\not\in B_1\cap B_2$.
\end{rozwiazanie}

\begin{rozwiazanie}[drugi sposob]
Będziemy korzystać z~następująch praw rachunku zbiorów:
\begin{eqnarray*}
X\rsym Y&=&(X\setminus X)\cup (Y\setminus X),\\
(X\cup Y)\setminus Z&=&(X\setminus Z)\cup(Y\setminus Z),\\
X\setminus (Y\cup Z)&\subseteq&X\setminus Y.
\end{eqnarray*}
Posługując się tymi prawami oraz monotonicznością sumy mnogościowej
można wykazać, że
\[
\begin{array}{l}
(A_1\cup A_2)\rsym(B_1\cup B_2)=
((A_1\cup A_2)\setminus (B_1\cup B_2))
\cup ((B_1\cup B_2)\setminus (A_1\cup A_2))=\\[1ex]
=(A_1\setminus (B_1\cup B_2))\cup(A_2\setminus (B_1\cup B_2))
\cup (B_1\setminus (A_1\cup A_2))
\cup (B_2\setminus (A_1\cup A_2)\subseteq\\[1ex]\subseteq
(A_1\setminus B_1)\cup(A_2\setminus B_2)
\cup (B_1\setminus A_1)
\cup (B_2\setminus A_2)=
(A_1\rsym B_1)\cup(A_2\rsym B_2)
.\end{array}\]

Jeżeli wprowadzimy pojęcie dopełnienia zbioru,
to w~dowodzie zawierania (\ref{rown4}) możemy wykorzystać wzór
\[X\rsym Y=X^c\rsym Y^c.\]
Zauważmy, że
\[\begin{array}{l}
(A_1\cap A_2)\rsym(B_1\cap B_2)=
(A_1\cap A_2)^c\rsym(B_1\cap B_2)^c=
(A_1^c\cup A_2^c)\rsym(B_1^c\cup B_2^c)\subseteq\\[1ex]
\subseteq
(A_1^c\rsym B_1^c)\cup(A_2^c\rsym B_2^c)
=(A_1\rsym B_1)\cup(A_2\rsym B_2).
\end{array}\]
\end{rozwiazanie}

\stepcounter{zadanie}
\stepcounter{zadanie}

\begin{zadanie}
Dla jakich zbiorów $C$ prawdziwe jest zdanie
stwierdzające, że dla dowolnych zbiorów $A$ i~$B$
zachodzi
\begin{equation}\label{zaw1}
A\times C\subseteq B\times C\Rightarrow A\subseteq B
\end{equation}
\end{zadanie}

\begin{rozwiazanie}
Najpierw spróbujemy dowieść implikację (\ref{zaw1}).
Mamy więc zbiory $A$, $B$ i $C$, zakładamy, że
zbiory te spełniają założenie $A\times C\subseteq B\times C$.
W~tej sytuacji staramy się dowieść, że $A\subseteq B$.
Aby dowieść to zawieranie, bierzemy $x\in A$
i~próbujemy wykazać, że $x\in B$.
Oczywiście, powinniśmy skorzystać z~założenia.
Łatwo zauważyć, że w~tym celu przydałaby się para
o~pierwszej współrzędnej $x$ i~drugiej należącej do $C$.
Aby taką parę utworzyć, musimy mieć element zbioru $C$.
Jest to proste pod warunkiem, że $C$ jest zbiorem niepustym.
Wtedy zbiór $C$ ma przynajmniej jeden element. Jeden z
elementów zbioru $C$ oznaczamy symbolem $c$ i~tworzymy parę $\p{x,c}$.
Ta para należy do iloczynu kartezjańskiego $A\times C$.
Na podstawie założenia stwierdzamy, że należy także do
iloczynu $B\times C$. Jeżeli $\p{x,c}\in B\times C$, to
także $x\in B$.

Przedstawione rozumowanie pozwala dowieść
implikację (\ref{zaw1}),
ale wymaga dodatkowego założenia, że zbiór $C$ jest niepusty.
Nietrudno zauważyć, że w~przypadku, gdy $C$ jest zbiorem pustym,
to puste są także zbiory $A\times C$ i $B\times C$,
i~w~konsekwencji, poprzednik implikacji (\ref{zaw1}) jest prawdziwy
dla dowolnych zbiorów $A$ i $B$.
Jeżeli przyjmiemy, że $A$ jest dowolnym zbiorem niepustym
(np. zbiorem liczb naturalnych), a $B$ jest zbiorem pustym, to
następnik implikacji (\ref{zaw1}) będzie fałszywy,
i~to samo będzie można powiedzieć o~całej implikacji.

Ostatecznie otrzymujemy, że implikacja
$A\times C\subseteq B\times C\Rightarrow A\subseteq B$
zachodzi dla wszystkich zbiorów $A$ i $B$ wtedy i~tylko wtedy,
gdy $C$ nie jest zbiorem pustym.
\end{rozwiazanie}

\stepcounter{zadanie}

\begin{zadanie}
Niech~$f$ będzie bijekcją przekształcającą
zbiór~$A$ w~$A$. Zdefiniujmy relację $R\subseteq A^2$
przyjmując, że
\[xRy\;\Leftrightarrow\;f(x)=y.\]
Symbolem $R_\infty$ oznaczamy przechodnie domknięcie relacji~$R$,
czyli relację $\bigcup_{n=1}^\infty R^n$, gdzie $R^1=R$ oraz
$R^{n+1}=R^nR$.
Czy
\begin{enumerate}\itemsep0pt
\item $R_\infty$ jest relacją równoważności?
\item $R_\infty$ jest relacją równoważności, jeśli~$A$ jest zbiorem
skończonym?
\end{enumerate}
Odpowiedzi uzasadnij.
\end{zadanie}

\begin{rozwiazanie}[część pierwsza]
Najpierw zauważmy, że jeżeli funkcję $f$
będziemy traktować jak relację, to
warunek $f(x)=y$ będzie równoważny z $\p{x,y}\in f$.
Tak więc
\[\p{x,y}\in R\Leftrightarrow xRy\Leftrightarrow f(x)=y\Leftrightarrow
\p{x,y}\in f,\]
czyli relacja $R$ jest tożsama z~funkcją $f$.
Wobec tego, relacja $R^n$ jest niczym innym,
jak $n$-krotnym złożeniem funkcji $f$.

Na ogół przechodnie domknięcie relacji $R$
zdefiniowanej w~zadaniu nie jest relacją równoważności.
Tak jest np.\ dla zbioru liczb całkowitych $Z$ i
funkcji $f:Z\rightarrow Z$ zdefiniowanej wzorem $f(k)=k+1$.
Funkcja $f$ jest oczywiście bijekcją.
Dla dowolnego $n\in N$ relacja $R^n$
spełnia dla wszystkich $x,y\in Z$ równoważność
\[xR^ny\Leftrightarrow y=x+n.\]
Jeżeli przedstawione argumenty
nie implikują tej równoważności
w~sposób oczywisty, to proponuję sprawdzenie jej
przez indukcję ze względu na $n$.

Dla tej funkcji $f$ relacja $R_\infty$ nie jest zwrotna,
a~nawet jest antyzwrotna.
Dla wszystkich $x\in Z$, założenie $xR_\infty x$
można sprowadzić
do sprzeczności w~następujący sposób:
warunek $xR_\infty x$ oznacza, że
$\p{x,x}\in\bigcup_{n=1}^\infty R^n$.
Tak więc dla pewnej liczby $m>0$ mamy $\p{x,x}\in R^m$,
czyli $xR^mx$.
Z~podanej charakteryzacji relacji $R^m$
wynika, że $x=x+m$. Jest to możliwe tylko, gdy $m=0$.
Przeczy to jednak warunkowi $m>0$.

Jeżeli $R_\infty$ nie jest zwrotna,
to nie jest relacją równoważności.
Można też dowieść w~podobny sposób,
że $R_\infty$ nie jest też symetryczna.
\end{rozwiazanie}

\begin{rozwiazanie}[część druga]
Założenie o~skończoności zbioru $A$ implikuje, że
$R_\infty$ jest relacją równoważności.
Dla dowolnego $x\in A$, rozważamy funkcję $I:N\rightarrow A$
taką, że $I(n)=f^n(x)$ dla wszystkich $n\in N$
($I(n)$ to wartość $n$-krotnego złożenia funkcji $f$ dla argumentu $x$,
$f^0(x)=x$).
Gdyby funkcja $f$ była różnowartościowa,
to zbiór $A$ byłby nieskończony.
Dla skończonego zbioru $A$ funkcja $f$ nie jest różnowartościowa.
Tak więc możemy znaleźć dwie liczby naturalne $p,q$ 
takie, że $p<q$ oraz $f^p(x)=I(p)=I(q)=f^q(x)$.
Składanie funkcji jest operacją łączną i~zachowuje
różnowartościowość.
Wobec tego, $f^p(x)=f^q(x)=f^p(f^{q-p}(x))$. 
Różnowartościowości funkcji $f^p$ implikuje także równość
$f^{p-q}(x)=x.$
Udowodniliśmy więc, że jeżeli $A$ jest zbiorem skończonym, to
dla dowolnego $x\in A$ istnieje liczba dodatnia $r$ taka, że
\begin{equation}\label{rownosc}
f^{r}(x)=x.
\end{equation}

Udowodniona własność oznacza, że relacja $R_\infty$ jest
zwrotna. Aby się o~tym przekonać,
bierzemy $x\in A$ i~liczbę $r>0$ spełniającą
(\ref{rownosc}). Z~równości (\ref{rownosc})
wynika, że $\p{x,x}\in f^r=R^r$.
Zawieranie $R^r\subseteq R_\infty$ implikuje zaś, że
$\p{x,x}\in R_\infty$.

Równość (\ref{rownosc}) implikuje także, że
jeżeli iterujemy obliczanie
wartości funkcji $f$ zaczynając od argumentu $x$,
to otrzymujemy w~kółko te same wartości
\[f(x),f^2(x),\dots,f^r(x)=x, f(x),f^2(x),\dots,f^r(x)=x,f(x),\dots\]
Spostrzeżenie to pozwala dowieść symetryczność
relacji $R_\infty$.
Najpierw jednak zauważmy,
że równość (\ref{rownosc}) zachodzi także dla
wszystkich wielokrotności $r$. Świadczą o~tym następujące
obliczenia będące fragmentem dowodu indukcyjnego:
\[f^{(k+1)r}(x)=f^{kr}(f^r(x))=f^{kr}(x)=x.\]

Teraz możemy przystąpić do dowodu,
że relacja $R_\infty$ jest symetryczna.
Przypuśćmy, że $\p{x,y}\in R_\infty$. Na podstawie definicji
$R_\infty$ stwierdzamy, że $\p{x,y}\in R^n$ dla pewnej dodatniej
liczby naturalnej~$n$. Ponieważ relacja $R^n$ jest równa $f^n$, więc
$f^n(x)=y$. Weźmy liczbę naturalną $k$ taką, że $n<kr$.
Dla tej liczby $k$ mamy $kr-n>0$ oraz
\[f^{kr-n}(y)=f^{kr-n}(f^n(x))=f^{kr}(x)=x.\]
Udowodniona równość oznacza, że
\[\p{y,x}\in f^{kr-n}=R^{kr-n}\subseteq R_\infty.\]

Przechodniość relacji $R_\infty$ wynika z~zadania 114,
które miało być robione na ćwiczeniach.

Z~przedstawionych rozumowań otrzymujemy, że jeżeli zbiór $A$
jest skończony, to relacja $R_\infty$ jest zwrotna, symetryczna.
Wiemy też, że jest przechodnia.
Tak więc dla zbioru skończonego $A$, relacją $R_\infty$
jest równoważnością.
\end{rozwiazanie}

\begin{zadanie}
Niech $A, B$ będą dowolnymi zbiorami. Kiedy równanie
\[A\cup X=B\]
\begin{enumerate}\itemsep0pt
\item ma dokładnie jedno rozwiązanie,
\item ma nieskończenie wiele rozwiązań,
\item nie ma rozwiązań?
\end{enumerate}
Odpowiedź uzasadnij.
\end{zadanie}

\begin{rozwiazanie}
Jeżeli równanie $A\cup X=B$ ma rozwiązanie, to jest taki zbiór $C$,
że $A\cup C=B$. Wtedy oczywiście zbiór $A$ jest podzbiorem  $B$.
Także na odwrót, jeżeli $A\subseteq B$, to zbiór $X=B\setminus A$
spełnia równanie $A\cup X=B$.

Udowodniliśmy więc, że równanie $A\cup X=B$ ma rozwiązanie
wtedy i~tylko wtedy, gdy $A\subseteq B$. Tym samym odpowiedzieliśmy
na pytanie 3: równanie $A\cup X=B$ nie ma rozwiązania
wtedy i~tylko wtedy, gdy $A\not\subseteq B$.

Załóżmy, że $A\subseteq B$. Scharakteryzujemy rozwiązania
równania $A\cup X=B$. Warunek $A\cup C=B$ implikuje, że
$C$ jest podzbiorem $B$ oraz zawiera różnicę $B\setminus A$.
Prawdziwa jest także implikacja odwrotna:
jeżeli $B\setminus A\subseteq C\subseteq B$,
to
\[B=A\cup (B\setminus A)\subseteq A\cup C\subseteq A\cup B=B,\]
a~więc $C$ spełnia równanie $A\cup X=B$.
Tak więc zbiorem rozwiązań równania $A\cup X=B$ jest
\[\{X:B\setminus A\subseteq X\subseteq B\}.\]

Policzymy jeszcze liczbę elementów tego zbioru, albo jego moc.
W~tym celu definiujmy funkcję
$f$ określoną w~zbiorze ${\cal P}(A)$ wszystkich podzbiorów
zbioru $A$ i~przyjmującą wartości dane wzorem
\[f(Y)=Y\cup (B\setminus A).\]
Łatwo dowodzi się, że funkcja $f$ przekształca
${\cal P}(A)$ na zbiór rozwiązań równania $A\cup X=B$.
Co więcej, jest to funkcja różnowartościowa.
Jeżeli bowiem $f(Y_1)=f(Y_2)$ dla pewnych $Y_1,Y_2\in{\cal P}(A)$,
to
\[Y_1=(Y_1\cup(B\setminus A))\cap A=f(Y_1)\cap A=f(Y_2)\cap A
=(Y_2\cup(B\setminus A))\cap A=Y_2.\]
Tak więc funkcja $f$ ustala rownoliczność
zbioru ${\cal P}(A)$ i~zbioru rozwiązań równania $A\cup X=B$.
Oznacza to, że równanie $A\cup X=B$ ma tyle elementów, co
zbiór ${\cal P}(A)$ (albo zbiór rozwiązań równania $A\cup X=B$
jest tej samej mocy, co zbiór ${\cal P}(A)$).

Teraz łatwo odpowiedzieć na pytania 2 i~3.
Jeżeli $A$ jest niepusty to ma przynajmniej dwa podzbiory:
zbiór pusty i~samego siebie. Tak więc równanie $A\cup X=B$
ma dokładnie jedno rozwiązanie wtedy i~tylko wtedy, gdy
$A$ jest zbiorem pustym.

Zbiory skończone mają skończenie wiele podzbiorów, a~nieskończone
--- nieskończenie wiele. Wobec tego, równanie $A\cup X=B$
ma nieskończenie wiele rozwiązań wtedy i~tylko wtedy, gdy
$A$ jest zbiorem nieskończonym.
\end{rozwiazanie}
\vfill
\null\hfill\textit{Rozwiązania przygotował Antoni Kościelski}

\end{document}
