\documentclass[a4paper,11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{latexsym,polski,geometry}
\geometry{vdivide={1in,*,1in}}
\prefixing
%\documentstyle[12pt]{article}
%\prefixing
%\input{skr-def}
\newcommand{\mod}{\mbox{\rm\ mod\ }}

%\theoremheaderfont{\normalfont\bfseries}
%\theoremseparator{.}
%\theorembodyfont{\normalfont\upshape}
%\theoremstyle{plain}
\newtheorem{zadanie}{Zadanie}
\newcommand{\vph}{\phi}
\newcommand{\lh}[1]{|#1|}
\newcommand{\po}[1]{\noindent{\bf #1.}}
\newtheorem{thm}{Twierdzenie}[zadanie]
\newcommand{\bth}{\begin{thm}}
\newcommand{\eth}{\end{thm}}
\newtheorem{wni}[thm]{Wniosek}
\newcommand{\bco}{\begin{wni}}
\newcommand{\eco}{\end{wni}}
\newtheorem{fac}[thm]{Fakt}
\newcommand{\bfa}{\begin{fac}}
\newcommand{\efa}{\end{fac}}
\newcommand{\bpf}{\noindent{\bf Dow/od.\ }}
\newcommand{\epf}{$\Box$\par\addvspace{4pt}}
\newcommand{\rarr}{\rightarrow}
\newcommand{\eqv}{\Leftrightarrow}
\newcommand{\sm}{\setminus}
\newcommand{\sbs}{\subseteq}
\newcommand{\cla}{{\cal A}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\begin{document}
\begin{center}
\Large\bf
Rozwi/azania zada/n z egzaminu z 3 lutego 2003
\end{center}

\begin{zadanie}
Niech~$\phi$ b/edzie formu/l/a zdaniow/a zbudowan/a ze zmiennych zdaniowych
i~sp/ojnik/ow alternatywy, koniunkcji i negacji. Przez
\emph{warto/sciowanie} formu/ly $\phi$ rozumiemy funkcj/e, kt/ora zmiennym
\emph{wystepuj/acym} w formule $\phi$ przyporz/adkowuje warto/sci ze zbioru
$\{0,1\}$.
Niech~$n$ b/edzie dodatni/a liczb/a naturaln/a.

\quad\textbf{a)}\enskip Udowodnij, /ze dla ka/zdej liczby
naturalnej~$k\leq 2^n$
istnieje formu/la zdaniowa~$\phi$ zawieraj/aca~$n$ zmiennych
i~spe/lniona przez dok/ladnie~$k$ warto/sciowa/n.

\quad\textbf{b)}\enskip Dla jakich liczb~$k$ istnieje
formu/la~$\phi$ zawieraj/aca
$n$~zmiennych, w kt/orej ka/zda ze zmiennych wyst/epuje dok/ladnie jeden raz
i~kt/ora jest spe/lniona przez dok/ladnie $k$~warto/sciowa/n?
\end{zadanie}
\po{Rozwi/azanie}
Cz/e/s/c a) zadania 1 jest oczywist/a konsekwencj/a zupe/lno/sci
zbioru sp/ojnik/ow z/lo/zonego z alternatywy, koniunkcji i negacji.
Bierzemy dowoln/a funkcj/e boolowsk/a $n$ zmiennych przyjmuj/ac/a
warto/s/c 1 dla $k$ argument/ow i korzystaj/ac z zupe/lno/sci
stwierdzamy, /ze jest to funkcja przyporz/adkowuj/aca
uk/ladowi zer i jedynej warto/s/c logiczn/a
pewnej formu/ly przy warto/sciowaniu wyznaczonym przez ten uk/lad.
Nie wiem, jak takie rozwi/azanie by/lo oceniane, ale
uwa/zam je za zbyt lakoniczne.

Mo/zna wzi/a/c $n$ zmiennych zdaniowych $p_1,\dots,p_n$
i tworzy/c formu/ly b/ed/ac/a koniunkcj/a tych zmiennych
b/ad/x ich negacji (np. $\neg p_1\wedge p_2\wedge\dots\wedge p_n$)
Formu/ly tej postaci s/a spe/lnione przez dok/ladnie jedno warto/sciowanie.
Alternatywa $k$ r/o/znych formu/l takiej postaci (dowolnie wybranych)
jest formu/l/a spe/lnion/a przez dok/ladnie $k$ warto/sciowa/n.

Bardziej szczeg/o/lowo przedstawi/e jeszcze inne rozwi/azanie
tego zadania. Przyjmijmy, /ze $W(\vph)$ oznacza zbi/or warto/sciowa/n
spe/lniaj/acych formu/l/e~$\vph$.

\bfa
Je/zeli w formule $\vph$ wyst/epuje $n$ zmiennych, to
$\lh{W(\neg\vph)}=2^n-\lh{W(\vph)}$.
\efa
\bpf
Jest to oczywisty fakt. Dla formu/ly $\vph$ z $n$ zmiennymi
jest $2^n$ warto/sciowa/n. Ka/zde z nich spe/lnia albo $\vph$,
albo $\neg\vph$, /zadne nie mo/ze jednocze/snie spe/lnia/c obu tych formu/l.
\epf


\bfa
Je/zeli /zadna zmienna nie wyst/epuje jednocze/snie w formulach
$\vph$ i $\psi$, to
\[\lh{W(\vph\wedge\psi)}=\lh{W(\vph)}\cdot\lh{W(\psi)}.\;\Box\]
\efa
\bpf
Rozwa/zmy funkcj/e, kt/ora warto/sciowaniu $h$ formu/ly
$\vph\wedge\psi$ przyporz/adkowuje
par/e dw/och warto/sciowa/n: warto/sciowania
b/ed/acego obci/eciem $h$ do zmiennych formu/ly $\vph$
i warto/sciowania
b/ed/acego obci/eciem $h$ do zmiennych formu/ly $\psi$.
R/o/znowarto/sciowo/s/c tej funkcji jest oczywista.

Wystarczy teraz zauwa/zy/c, /ze funkcja ta przekszta/lca
zbi/or $W(\vph\wedge\psi)$ na iloczyn kartezja/nski
$W(\vph)\times W(\psi)$.
(Gdzie w tym dowodzie korzysta si/e z za/lo/zenia
o zmiennych formu/l $\vph$ i $\psi$?)
\epf

\bco
Je/zeli zmienna $p$ nie wyst/epuje w formule $\vph$, to
$\lh{W(\vph\wedge p)}=\lh{W(\vph)}$.
\epf
\eco

\bco
Je/zeli w formule $\vph$ wyst/epuje $n$ zmiennych
i nie ma w/sr/od nich zmiennej $p$, to
$\lh{W(\vph\vee p)}=2^n+\lh{W(\vph)}$.
\eco
\bpf
Zauwa/zmy, /ze
\[
\begin{array}{rcl}
\lh{W(\vph\vee p)}&=&
\lh{W(\neg(\neg\vph\wedge\neg p))}=
2^{n+1}-\lh{W(\neg\vph\wedge\neg p)}=
\\&=&
2^{n+1}-\lh{W(\neg\vph)}\cdot\lh{W(\neg p)}=
2^{n+1}-(2^n-\lh{W(\vph)})\cdot(2-\lh{W(p)})=
\\&=&
2^{n+1}-2^n+\lh{W(\vph)}=
2^n+\lh{W(\vph)}.\;\Box
\end{array}
\]


\bfa
Dla ka/zdej liczby naturalnej $k\leq 2^n$ istnieje formu/la
zdaniowa z $n$ zmiennymi spe/lniona przez dok/ladnie $k$ warto/sciowa/n.
\efa
\bpf
Fakt ten dowodzimy przez indukcj/e ze wzgl/edu na $n$.

Zauwa/zmy, /ze
$\lh{W(p\wedge\neg p)}=0$, $\lh{W(p)}=1$ i $\lh{W(p\vee\neg p)}=2$.
Tym samym twierdzenie jest prawdziwe dla $n=1$.

Za/l/ozmy, /ze twierdzenie to jest zachodzi dla liczby $n$
i we/xmy $k\leq 2^{n+1}$. Zachodzi jeden z dw/och przypadk/ow:
albo $k\leq 2^n$, albo $2^n<k\leq 2^{n+1}$.

Je/zeli $k\leq 2^n$, to znajdujemy formu/l/e $\vph$ z $n$ zmiennymi,
kt/ora jest spe/lniona przez $k$ warto/sciowa/n, i zmienn/a $p$, kt/ora
nie wyst/epuje w $\vph$.
Formu/la $\vph\wedge p$ jest spe/lniona przez $k$ warto/sciowa/n
i wyst/epuje w niej $n+1$ zmiennych.

Je/zeli $2^n<k\leq 2^{n+1}$, to bierzemy formu/l/e $\vph$
z $n$ zmiennymi, spe/lnion/a przez $k-2^n$ warto/sciowa/n.
Wtedy dla dowolnej zmiennej $p$ nie wyst/epuj/acej w $\vph$
formu/la $\vph\vee p$ jest spe/lniona przez $k$ warto/sciowa/n
i wyst/epuje w niej $n+1$ zmiennych.
\epf

Podobnie dowodzimy nast/epuj/acy fakt:

\bfa
Dla ka/zdej nieparzystej liczby naturalnej $k\leq 2^n$ istnieje formu/la
zdaniowa z $n$ zmiennymi, w kt/orej ka/zda zmienna
wyst/epuje dok/ladnie jeden raz i kt/ora
jest spe/lniona przez dok/ladnie $k$ warto/sciowa/n.
\efa
\bpf
Formu/l/e, w kt/orej ka/zda zmienna wyst/epuje najwy/zej jeden raz,
b/ed/a nazywa/l prost/a.
Twierdzenie to tak/ze dowodzimy przez indukcj/e ze wzgl/edu na $n$.

Zauwa/zmy, /ze $\lh{W(p)}=1$.
Wobec tego dowodzone twierdzenie jest prawdziwe dla $n=1$.

Za/l/ozmy, /ze twierdzenie to jest zachodzi dla liczby $n$
i we/xmy nieparzyst/a liczb/e $k\leq 2^{n+1}$.
Liczba $k$ jest albo $\leq 2^n$, albo te/z spe/lnia nier/owno/sci
$2^n<k\leq 2^{n+1}$.

Je/zeli $k\leq 2^n$, to znajdujemy prost/a
formu/l/e $\vph$ z $n$ zmiennymi,
kt/ora jest spe/lniona przez $k$ warto/sciowa/n, i zmienn/a $p$, kt/ora
nie wyst/epuje w $\vph$.
Formu/la $\vph\wedge p$ jest prosta i spe/lniona przez $k$ warto/sciowa/n,
oraz wyst/epuje w niej $n+1$ zmiennych.

Je/zeli $2^n<k\leq 2^{n+1}$, to bierzemy prost/a formu/l/e $\vph$
z $n$ zmiennymi, spe/lnion/a przez $k-2^n$ warto/sciowa/n.
Wtedy dla dowolnej zmiennej $p$ nie wyst/epuj/acej w $\vph$,
formu/la $\vph\vee p$ jest prosta, spe/lniona przez $k$ warto/sciowa/n
i wyst/epuje w niej $n+1$ zmiennych.
\epf

\bfa
Je/zeli $\vph$ jest formu/l/a, w kt/orej ka/zda zmienna wyst/epuje
najwy/zej jeden raz, to $\vph$ jest spe/lniona przez nieparzyst/a
liczb/e warto/sciowa/n.
\efa
\bpf
Dow/od przeprowadzimy przez indukcj/e ze wzgl/edu na liczb/e znak/ow
wyst/epuj/acych w formule. Formu/la, kt/ora daje si/e zapisa/c
za pomoc/a jednego znaku jest zmienn/a i jest spe/lniona przez
jedno warto/sciowanie.

Przypu/s/cmy, /ze $\vph=\neg\psi$ i wyst/epuje w niej $n$ zmiennych.
Oczywi/scie, ka/zda zmienna wyst/epuje tyle samo razy w $\vph$,
co w $\psi$.
Z za/lo/zenia indukcyjnego wynika wi/ec, /ze $\psi$
jest spe/lniona przez nieparzyst/a liczb/e warto/sciowa/n
r/own/a $\lh{W(\psi)}$.
Liczba $2^n-\lh{W(\psi)}$ jest nieparzysta i jest r/owna
liczbie warto/sciowa/n spe/lniaj/acych $\vph$.

Je/zeli w koniunkcji $\vph\wedge\psi$
ka/zda zmienna wyst/epuje najwy/zej jeden raz
(je/zeli koniunkcja ta jest prosta),
to $\vph$ i $\psi$ s/a proste, i /zadna zmienna nie
wyst/epuje jednocze/snie w obu tych formu/lach.
Wobec tego, formu/la $\vph\wedge\psi$ jest spe/lniona przez
$\lh{W(\vph)}\cdot\lh{W(\psi)}$ warto/sciowa/n.
Na mocy za/lo/zenia indukcyjnego, oba czynniki tego iloczynu s/a
liczbami nieparzystymi. Iloczyn liczb nieparzystych te/z jest
nieparzysty.

Jeszcze trzeba pokaza/c (mo/zna to zrobi/c w podobny spos/ob),
/ze alternatywa b/ed/aca formu/l/a prost/a jest spe/lniona przez
nieparzyst/a liczb/e warto/sciowa/n.
\epf

\begin{zadanie}
Niech $\alpha:N\rarr \{0,1\}$ b/edzie ci/agiem zero-jedynkowym.
Symbolem $\sim_{\alpha}$ oznaczamy relacj/e w~zbiorze
$\{0,1\}^{N}$ niesko/nczonych ci/ag/ow
zero-jedynkowych zdefiniowan/a formu/l/a
\begin{eqnarray*}
\beta\sim_{\alpha}\gamma&\Leftrightarrow&
(\forall n{\in}N)\;\alpha(n)\beta(n)=\alpha(n)\gamma(n).
\end{eqnarray*}
Czy istnieje taki ci/ag $\alpha$, dla kt/orego:

\quad\textbf{a)}\enskip relacja $\sim_{\alpha}$ ma przeliczalnie i
niesko/nczenie wiele klas r/ownowa/zno/sci?

\quad\textbf{b)}\enskip wszystkie klasy r/ownowa/zno/sci
relacji $\sim_{\alpha}$ s/a przeliczalne i niesko/nczone?

\quad\textbf{c)}\enskip istnieje przeliczalna i niesko/nczona
klasa r/ownowa/zno/sci relacji $\sim_{\alpha}$?
\end{zadanie}

\po{Rozwi/azanie}
Ustalmy $\alpha$ i przyjmijmy, /ze $A=\{n\in N:\alpha(n)=1\}$.
Oczywi/scie, $\sim_\alpha$ jest relacj/a r/ownowa/zno/sci.
Przyjmijmy, /ze $N_\alpha$ jest zbiorem klas r/ownowa/zno/sci
tej relacji. Symbolem $[x]_\alpha$ b/edziemy oznacza/c klasy
abstrakcji relacji $\sim_\alpha$.

\bfa
Zbi/or $N_\alpha$ i zbi/or $\{0,1\}^A$ s/a r/ownoliczne.
\efa
\bpf
Dla funkcji $\xi:A\rarr\{0,1\}$ definiujemy
funkcj/e $\bar{\xi}:N\rarr\{0,1\}$ przyjmuj/ac, /ze
\[\bar{\xi}(n)=\left\{\begin{array}{ll}
\xi(n)&\mbox{ je/zeli }n\in A,\\
0&\mbox{ w przeciwnym razie.}
\end{array}\right.
\]
Zdefiniujmy jeszcze wzorem
\[f(\xi)=[\bar{\xi}]_\alpha\]
funkcj/e $f:\{0,1\}^A\rarr N_\alpha$.
Funkcja ta jest r/o/znowarto/sciowa i typu ,,na''.

Aby dowie/s/c r/o/znowarto/sciowo/s/c funkcji $f$
we/xmy dwa (r/o/zne) argumenty $\xi_1$ i $\xi_2$ tej funkcji.
S/a to funkcje okre/slone w zbiorze $A$. Istnieje wi/ec
liczba $n\in A$ taka, /ze  $\xi_1(n)\neq\xi_2(n)$.
Funkcje  $\bar{\xi}_1$ i $\bar{\xi}_2$ te/z przyjmuj/a r/o/zne warto/sci
dla argumentu $n$:
\[\bar{\xi}_1(n)=\xi_1(n)\neq\xi_2(n)=\bar{\xi}_2(n).\]
Oznacza to, /ze $\bar{\xi}_1\not\sim_\alpha\bar{\xi}_2$.
St/ad otrzymujemy, /ze klasy $[\bar{\xi}_1]_\alpha$ i
$[\bar{\xi}_2]_\alpha$ s/a r/o/zne
(r/o/zni/a si/e np. elementem $\bar{\xi}_1$).

We/xmy dowoln/a klas/e ze zbioru $N_\alpha$
i jej reprezentanta $\gamma$. Poka/zemy, /ze
$[\gamma]_\alpha$ jest warto/sci/a funkcji $f$.
W tym celu we/xmy funkcj/e $\delta:A\rarr \{0,1\}$
b/ed/ac/a obci/eciem $\gamma$ do zbioru $A$
(a wi/ec spe/lniaj/ac/a $\delta(n)=\gamma(n)$ dla wszystkich
$n\in A$) i zauwa/zmy, /ze tak/ze
$\bar{\delta}(n)=\gamma(n)$ dla wszystkich
$n\in A$. To jednak oznacza, /ze $\bar{\delta}\sim_\alpha\gamma$.
Wobec tego, $f(\delta)=[\bar{\delta}]_\alpha=[\gamma]_\alpha$.

\noindent
{\bf Inny dow/od.}
We/xmy funkcj/e $g:\{0,1\}^N\rarr \{0,1\}^A$ przyporz/adkowuj/ac/a
funkcji $\gamma\in\{0,1\}^N$ obci/ecie funkcji
$\gamma$ do zbioru $A$. Oczywi/scie, funkcja $g$ jest typu ,,na''.
/Swiadczy o tym np. r/owno/s/c $g(\bar{\xi})=\xi$.

Funkcja $g$ spe/lnia tak/ze r/ownowa/zno/s/c
\[g(\gamma_1)=g(\gamma_2)\eqv \gamma_1\sim_\alpha \gamma_2.\]
R/ownowa/zno/s/c ta implikuje, /ze wz/or
\[G([\gamma]_\alpha)=g(\gamma)\]
jest poprawn/a definicj/a funkcji $G:N_\alpha\rarr\{0,1\}^A$
i -- co wi/ecej -- funkcja ta jest r/o/znowarto/sciowa.
Poniewa/z $g$ jest typu ,,na'', wi/ec tak/ze $G$ jest typu ,,na''.
\epf

\bfa
Klasy r/ownowa/zno/sci relacji $\sim_\alpha$
s/a r/ownoliczne ze zbiorem $\{0,1\}^{N\sm A}$.
\efa
\bpf
We/xmy dowoln/a funkcj/e $\beta\in\{0,1\}^N$
i zdefiniujmy funkcj/e $f:[\beta]_\alpha\rarr\{0,1\}^{N\sm A}$.
Funkcja $f$ elementowi $\gamma\in[\beta]_\alpha$
przyporz/adkowuje obci/ecie $\gamma$ do zbioru $N\sm A$.
Aby dowie/s/c podany fakt poka/zemy, /ze funkcja $f$ jest
bijekcj/a.

We/xmy wi/ec r/o/zne funkcje $\gamma_1,\gamma_2\in[\beta]_\alpha$.
Poniewa/z nale/z/a do jednej klasy r/ownowa/zno/sci relacji $\sim_\alpha$,
wi/ec przyjmuj/a te same warto/sci dla dowolnego argumentu ze zbioru $A$.
Wobec tego, przyjmuj/a r/o/zne warto/sci dla pewnego $n\not\in A$.
Ich obci/ecia od zbioru $N\sm A$ te/z przyjmuj/a
r/o/zne warto/sci dla tego samego argumentu, a wi/ec s/a r/o/zne.
To dowodzi, /ze funkcja $f$ jest r/o/znowarto/sciowa.

Aby dowie/s/c, /ze funkcja $f$ jest typu ,,na'',
we/xmy dowoln/a funkcj/e $\xi\in\{0,1\}^{N\sm A}$
i zdefiniujmy $\gamma\in\{0,1\}^N$ takie, /ze
\[\gamma(n)=\left\{\begin{array}{ll}
\beta(n)&\mbox{ je/zeli }n\in A,\\
\xi(n)&\mbox{ w przeciwnym razie.}
\end{array}\right.
\]
Oczywi/scie, funkcje $\gamma$ i $\beta$ s/a w relacji $\sim_\alpha$
oraz obci/ecie $\gamma$ do $N\sm A$ jest r/owne $\xi$.
Tak wi/ec $f(\gamma)=\xi$.
\epf

\bfa
Je/zeli zbi/or $A\sbs N$ jest niesko/nczony, to
zbi/or $\{0,1\}^A$ jest nieprzeliczalny.
\efa
\bpf
Niesko/nczony podzbi/or $A$ zbioru liczb naturalnych jest
r/ownoliczny ze zbiorem liczb naturalnych $N$.
Je/zeli zbi/or $A$ jest r/ownoliczny z $N$, to tak/ze
zbiory $\{0,1\}^A$ i $\{0,1\}^N$ s/a r/ownoliczne.
Ten ostatni zbi/or jest nieprzeliczalny na podstawie
twierdzenia Cantora. Oznacza to, /ze tak/ze
zbi/or $\{0,1\}^A$ jest nieprzeliczalny.
\epf

\bco
Zbi/or $N_\alpha$ klas r/ownowa/zno/sci relacji $\sim_\alpha$
jest albo sko/nczony, albo nieprzeliczalny.
\eco
\bpf
S/a mo/zliwe dwa przypadki: albo zbi/or $A$ jest sko/nczony
i wtedy zbi/or $\{0,1\}^A$ i r/ownoliczny z nim zbi/or $N_\alpha$
s/a sko/nczone, albo zbi/or $A$ jest niesko/nczony
i zar/owno zbi/or $\{0,1\}^A$ jak i r/ownoliczny z nim zbi/or $N_\alpha$
s/a nieprzeliczalne.
\epf

Z powy/zszego wniosku wynika negatywna odpowied/x na pytanie a):
dla /zadnego $\alpha$ zbi/or klas r/ownowa/zno/sci relacji $\sim_\alpha$
nie jest przeliczalny i niesko/nczony.

\bco
Klasy abstrakcji relacji $\sim_\alpha$ s/a albo sko/nczone, albo
nieprzeliczalne.
\eco
\bpf
Ten wniosek dowodzimy dok/ladnie tak, jak poprzedni.
\epf

Z ostatniego wniosku otrzymujemy negatywn/a odpowied/x na
pytanie c): dla /zadnego $\alpha$ /zadna klasa klasa r/ownowa/zno/sci
nie jest niesko/nczona przeliczalna.

Negatywna odpowied/z na pytanie c) implikuje tak/ze negatywn/a odpowied/x
na pytanie b). Odpowied/x na pytanie b) mo/zna te/z /latwo wyprowadzi/c z
ostatniego wniosku.

\begin{zadanie}
Na zbiorze~$X$ okre/slone s/a takie relacje r/ownowa/zno/sci $Q$~i~$R$,
/ze

\quad1.~ka/zda klasa r/ownowa/zno/sci relacji~$Q$ ma $q$~element/ow,

\quad2.~ka/zda klasa relacji~$R$ ma $r$~element/ow oraz

\quad3.~istnieje klasa r/ownowa/zno/sci relacji~$Q$, kt/ora ma dok/ladnie
jeden element
wsp/olny z~ka/zd/a klas/a r/ownowa/zno/sci relacji~$R$.
Ile element/ow ma zbi/or~$X$?
\end{zadanie}

\po{Rozwi/azanie}
Przyjmijmy, /ze $A$ oznacza t/e klas/e r/ownowa/zno/sci relacji $Q$,
o kt/orej jest mowa w punkcie 3),
a $K$ -- zbi/or klas r/ownowa/zno/sci relacji $R$.

Wszystkie przedstawione rozwi/azania korzystaj/a z faktu,
/ze zbiory $K$ i $A$ maj/a tyle samo element/ow.
Je/zeli to wiemy, to na podstawie warunku 1)
stwierdzamy, /ze $K$ ma $q$ element/ow.
Relacja r/ownowa/zno/sci $R$ wyznacza wi/ec
podzia/l zbioru $X$ na $q$ roz/l/acznych klas r/ownowa/zno/sci,
kt/ore maj/a po $r$ element/ow.
St/ad otrzymujemy, /ze $X$ ma $q\cdot r$ element/ow.
Dalej poka/z/e, jak dowodzi/c, /ze $\lh{A}=\lh{K}$.

\po{Spos/ob I}
Niech $f:K\rarr A$ b/edzie funkcj/a, kt/ora
dla klasy $Y\in K$ przyjmuje warto/s/c $f(Y)\in Y\cap A$.
Punkt 3 ze sformu/lowania zadania gwaratuje poprawno/s/c tej definicji.

Poka/zemy, /ze funkcja $f$ jest bijekcj/a.
Je/zeli $f(Y)=f(Z)$ dla pewnych klas klas $Y,Z\in K$, to
$f(Y)\in(Y\cap A)\cap(Z\cap A)\sbs Y\cap Z$.
W tym przypadku klasy $Y$ i $Z$ nie s/a roz/l/aczne,
a to jest mo/zliwe tylko wtedy, gdy $Y=Z$.
Wobec tego $f$ jest r/o/znowarto/sciowa.

We/xmy teraz $a\in A$. Oczywi/scie, klasa r/ownowa/zno/sci
$[a]_R$ nale/zy do $K$. Gdyby $f([a]_R)\neq a$, to
zbi/or $[a]_R\cap A$ mia/lby przynajmniej dwa elementy:
$f([a]_R)$ oraz $a$, a to przeczy warunkowi 3).
Tak wi/ec funkcja $f$ jest typu ,,na''.


\po{Spos/ob II}
Tym razem definiujemy funkcj/e $g:A\rarr K$, kt/ora
elementowi $a\in A$ przyporz/adkowuje klas/e $[a]_R$
(przyjmujemy, /ze $g(a)=[a]_R$).
Podobnie jak w pierwszym rozwi/azaniu, funkcja $g$ jest bijekcj/a.

Je/zeli $[a]_R=[b]_R$ dla $a,b\in A$, to
do klasy $[a]_R$ nale/zy zar/owno $a$, jak i $b$.
Z wyboru $A$ mamy jednak, /ze do dowolnej klasy r/ownowa/zno/sci
mo/ze nale/ze/c tylko jeden element zbioru $A$, wi/ec $a=b$.

Je/zeli $Y$ jest dowoln/a klas/a r/ownowa/zno/sci relacji $R$, to
z warunku 3) (a raczej z wyboru $A$)
znajdujemy w niej pewien element $a\in A$.
Wobec tego, klasy r/ownowa/zno/sci $[a]_R$ i $Y$ nie s/a roz/l/aczne.
Takie klasy musz/a by/c r/owne. Otrzymali/smy wi/ec, /ze
$g(a)=[a]_R=Y$.


\po{Spos/ob III}
Zauwa/zmy, /ze
\[A=A\cap X=A\cap\bigcup_{Y\in K}Y=\bigcup_{Y\in K}A\cap Y\]
(druga r/owno/s/c wynika st/ad, /ze suma klas rownowa/zno/sci
jest r/owna dziedzinie relacji r/ownowa/zno/sci).
Zbiory $A\cap Y_1$  i $A\cap Y_2$ dla r/o/znych klas r/ownowa/zno/sci
$Y_1$ i $Y_2$ s/a rozl/aczne, poniewa/z klasy te s/a roz/l/aczne.
Wobec tego
\[\lh{A}=\lh{\bigcup_{Y\in K}A\cap Y}=\sum_{Y\in K}\lh{A\cap Y}
=\sum_{Y\in K}1=\lh{K}.\]


\begin{zadanie}
Niech~$\Sigma=\{{+},a\}$ b/edzie sygnatur/a zawieraj/ac/a dwuargumentowy
symbol funkcji~$+$ i~symbol sta/lej~$a$. Dla dowolnej
dodatniej liczby naturalnej~$n$ niech $A_n=\{0,1,\ldots,n-1\}$,
${\oplus}_n$ oznacza dodawanie modulo~$n$, za/s~$a_n=0$.
Rozwa/zmy algebry $\mathcal A_n=\langle A_n,{\oplus}_n, a_n\rangle$.
Udowodnij, /ze je/zeli $k=l\cdot m$, to
istnieje homomorfizm~$h$ algebry~$\mathcal A_k$
na~algebr/e~$\mathcal A_l$ (surjekcja) taki, /ze $|\vec{h}^{-1}(\{0\})|=m$.
Podaj przyk/lad takich~$k$, $l$~i~$m$, dla kt/orych istniej/a co najmniej
dwa takie homomorfizmy.
Ile jest takich homomorfizm/ow, je/sli zamiast sygnatury~$\Sigma$ b/edziemy
rozwa/zać sygnatur/e~$\Sigma'=\{{+},a,b\}$ zawierajac/a dwa symbole sta/lych
$a$~i~$b$ oraz algebry $\mathcal A_n'=\langle A_n,\oplus_n, a_n,
b_n\rangle$, gdzie $b_n=1$?
\end{zadanie}
\po{Analiza sytuacji}
Reszt/e z dzielenia $k$ przez $l$ b/ed/e oznacza/c tak/ze symbolem
$k\mod l$.
Zauwa/zmy, /ze ka/zdy element $A_k$ jest sum/a
pewnej liczby jedynek (daje si/e przedstawi/c w postaci
$1\oplus_k\dots\oplus_k 1$). Wobec tego
1 generuje $A_k$. Homomorfizm wystarczy zdefiniowa/c na
zbiorze generator/ow. Przyjmijmy wi/ec, /ze $h:A_k\rarr A_l$
jest homomorfizmem i $h(1)=a$. Wtedy
\[h(n)=h(\underbrace{1\oplus_k\dots\oplus_k 1}_{n\mbox{\scriptsize\ razy}})=
\underbrace{h(1)\oplus_l\dots\oplus_l h(1)}_{n\mbox{\scriptsize\ razy}}=
(a\cdot n)\mod l.\]

\po{Rozwi/azanie}
\bfa
Je/zeli $l$ dzieli $k$, to funkcja
$h_a:A_k\rarr A_l$ zdefiniowana wzorem
\[h_a(x)=(a\cdot x)\mod l\]
jest homomorfizmem algebr $\cla_k$ i $\cla_l$.
\efa
\bpf
Zauwa/zmy najpierw, /ze definicja funkcji $h_a$
zale/zy od $k$ i $l$, mimo /ze wprowadzone oznaczenie
na to nie wskazuje.
Oczywi/scie, $h_a(0)=0$. Wystarczy wi/ec dowie/s/c, /ze
dla wszystkich $x,y\in A_k$ zachodzi r/owno/s/c
$h_a(x\oplus_k y)=h_a(x)\oplus_l h_a(y)$.
Zauwa/zmy, /ze
\[a\cdot x=p\cdot l+h_a(x)\mbox{\ \ oraz\ \ }a\cdot y=q\cdot l+h_a(y)\]
dla pewnych liczb naturalnych $p$ i $q$.
Z tych samych powod/ow zachodzi r/owno/s/c
\[x+y=r\cdot k+(x\oplus_k y).\]
/L/acz/ac podane r/owno/sci otrzymujemy
\[a\cdot r\cdot k+a\cdot(x\oplus_k y)=a\cdot(x+y)=(p+q)\cdot l+h_a(x)+h_a(y).\]
Poniewa/z $l$ dzieli $k$, wi/ec
\[h_a(x\oplus_k y)=a\cdot(x\oplus_k y)\mod l=(h_a(x)+h_a(y))\mod l
=h_a(x)\oplus_lh_a(y).\;\Box\]

\po{Cz/e/s/c I}
Korzystaj/ac z podanego faktu mo/zna /latwo rozwi/aza/c pierwsz/a cz/e/s/c
zadania. Wystarczy zauwa/zy/c, /ze
je/zeli $k=l\cdot m$, to $h_1:A_k\rarr A_l$ jest homomorfizmem
takim, /ze $h_1(x)=x$ dla $x=0,\dots,l-1$,
a wi/ec jest homomorfizmem algebry $\cla_k$ na algebr/e $\cla_l$.
Mamy tak/ze
\begin{eqnarray*}
\vec{h}^{-1}_1(0)&=&
\{x<l\cdot m:x\mod l=0\}\;=\;\{x<l\cdot m:l\mbox{ dzieli }x\}
\;=\\&=&
\{i\cdot l:i<m\}\;=\;\vec{g}(\{i:i<m\})
\end{eqnarray*}
dla funkcji $g:N\rarr N$ takiej, /ze $g(i)=i\cdot l$.
Funkcja $g$ jest oczywi/scie r/o/znowarto/sciowa.
Wobec tego zbi/or $\vec{h}^{-1}_1(0)$
jest r/ownoliczny ze zbiorem $\{i:i<m\}$,
kt/ory oczywi/scie ma $m$ element/ow, i te/z ma $m$ element/ow.

\po{Cz/e/s/c II}
Aby rozwi/aza/c drug/a cz/e/s/c zadania wystarczy dodatkowo zauwa/zy/c,
/ze je/zeli we/xmiemy $k=l=3$, to odpowiednia funkcja $h_2$
przekszta/lca $A_3$ na $A_3$ ($h_2(1)=2$ i $h_2(2)=1$)
i -- wobec tego -- jest homomorfizmem algebry $\cla_3$ na algebr/e $\cla_3$.
Funkcje $h_1$ i $h_2$ s/a w tym przypadku r/o/zne, poniewa/z
$1=h_1(1)\neq h_2(1)=2$.
Podobnie jest w przypadku funkcji $h_2:A_6\rarr A_3$
(jest to inna funkcja ni/z poprzednia,
mimo /ze jest tak samo oznaczana!).
Mo/zna dowie/s/c, /ze
dla dowolnej wielokrotno/sci $k$ liczby $l$,
funkcja $h_a$ przekszta/lca $A_k$ na $A_l$
wtedy i tylko wtedy, gdy $a$ jest wzgl/ednie pierwsze z $l$.

\po{Cz/e/s/c III}
Z definicji homomorfizmu wynika, /ze
homomorfizmy algebry $\cla'_k$ w algebr/e $\cla'_l$
s/a to dok/ladnie
homomorfizmy algebry $\cla_k$ w algebr/e $\cla_l$
przekszta/lcaj/ace 1 na 1. Aby wi/ec odpowiedzie/c na
ostatnie pytanie wystarczy ustali/c, ile jest
homomorfizm/ow przekszta/lcaj/acych algebr/a $\cla_k$ na algebr/e $\cla_l$
i przeprowadzaj/acych 1 na 1. Poka/zemy, /ze je/zeli
$l$ dzieli $k$, to jest dok/ladnie jeden taki homomorfizm.
Oczywi/scie, jest taki homomorfizm (jest nim $h_1$).
Przypu/s/cmy, /ze $h$ te/z jest takim homomorfizmem.
Wtedy
\[
h(n)=h(\underbrace{1\oplus_k\dots\oplus_k 1}_{n\mbox{\scriptsize\ razy}})=
\underbrace{h(1)\oplus_l\dots\oplus_l h(1)}_{n\mbox{\scriptsize\ razy}}=
\underbrace{h_1(1)\oplus_l\dots\oplus_l h_1(1)}_{n\mbox{\scriptsize\ razy}}=
h_1(n)
\]
dla wszystkich $n\in A_k$.
Wobec tego, homomorfizmy $h$ i $h_1$ s/a identyczne.
Bardziej elegancki dow/od tego faktu powinien by/c indukcyjny.


\begin{zadanie}
Poka/z, /ze zbior liczb wymiernych ze zwyk/lym porz/adkiem i zbi/or
niepustych skończonych ci/ag/ow liczb wymiernych z porz/adkiem leksykograficznym
s/a izomorficzne (rozwa/zamy porz/adek leksykograficzny
generowany przez zwyk/ly porz/adek na liczbach wymiernych).

Przypominamy, /ze~$\preceq$ jest porz/adkiem
leksykograficznym generowanym przez porz/adek~$\leq$, je/sli
\begin{eqnarray*}
\langle a_0,a_1,\ldots a_m\rangle\preceq\langle b_0,b_1,\ldots, b_n \rangle
\end{eqnarray*}
wtedy i tylko wtedy, gdy $\langle a_0,a_1,\ldots a_m\rangle$ jest
prefiksem $\langle b_0,b_1,\ldots, b_n \rangle$ lub
\[(\exists\, k)\;\Big(k\leq m \wedge k\leq n
\wedge a_k<b_k\wedge (\forall\, i{<}k)\;a_i=b_i\Big).
\]
\emph{Wskaz/owka:} Skorzystaj z twierdzenia o g/estych porz/adkach
udowodnionego na ćwiczeniach. Przytocz sformu/lowanie tego twierdzenia.

\end{zadanie}

\po{Rozwi/azanie}
W tym zadaniu nale/zy skorzysta/c z twierdzenia, kt/ore m/owi,
/ze ka/zde dwa przeliczalne porz/adki liniowe,
kt/ore s/a g/este i bez ko/nc/ow,
s/a izomorficzne.

Aby skorzysta/c z tego twierdzenia,
nale/zy pokaza/c, /ze
\ben
\item
zbi/or sko/nczonych, niepustych ci/ag/ow o wyrazach wymiernych
jest przeliczalny,
\item
porz/adek leksykograficzny wyznaczony przez porz/adek liniowy
jest porz/adkiem liniowym,
\item
porz/adek leksykograficzny
w zbiorze sko/nczonych, niepustych ci/ag/ow o wyrazach wymiernych
jest g/esty,
\item
oraz nie ma w nim elementu najwi/ekszego, ani najmniejszego.
\een

S/adz/e, /ze zamiast dowodzi/c przeliczalno/s/c zbioru sko/nczonych
ci/ag/ow o wyrazach wymiernych
i liniowo/s/c porz/adku leksykograficznego,
mo/zna powo/la/c si/e na fakty
znane z wyk/ladu lub /cwicze/n.

Aby dowie/s/c g/esto/s/c rozwa/zanego porz/adku
we/xmy dwa sko/nczone, niepuste ci/agi $a$ i $b$ liczb wymiernych
odpowiednio
o wyrazach $a_1,a_2,\dots,a_n$ oraz $b_1,b_2,\dots,b_m$.
Za/l/o/zmy, /ze ci/ag $a$ jest mniejszy w sensie porz/adku leksykograficznego
od ci/agu $b$. S/a mo/zliwe dwa przypadki:
albo $n<m$ oraz $a_i=b_i$ dla wszystkich $i=1,\dots,n$, albo te/z
dla pewnej liczby $k\leq n,m$ zachodzi nier/owno/s/c
$a_k<b_k$ i spe/lnione s/a r/owno/sci $a_i=b_i$ dla $i=1,\dots,k-1$.
Je/zeli zachodzi pierwszy przypadek, to
bierzemy ci/ag $c$ o wyrazach $b_1,b_2,\dots,b_n,b_{n+1}-1$.
W drugim przypadku
bierzemy ci/ag $c$ o wyrazach
$b_1,b_2,\dots,b_{k-1},(a_k+b_k)//2$.
Bez trudu sprawdzamy, /ze w obu przypadkach ci/ag
$c$ jest wi/ekszy w sensie porz/adku leksykograficznego od ci/agu
$a$ i mniejszy od ci/agu $b$.

Jest te/z oczywiste, /ze
je/zeli $a_1$ jest pierwszym wyrazem ci/agu $a$,
to jednoelementowy ci/ag, kt/orego wyrazem jest liczba
$a_1+1$ jest wi/ekszy od $a$, a
jednoelementowy ci/ag, kt/orego wyrazem jest liczba
$a_1-1$ jest mniejszy od $a$.
Tak wi/ec w rozwa/zanym porz/adku leksykograficznym nie ma
elementu najwi/ekszego, ani najmniejszego.







\end{document}


