Rozwiązania zadań z egzaminu z 3 lutego 2003

Zadanie 1 Niech ϕ będzie formułą zdaniową zbudowaną ze zmiennych zdaniowych i spójników alternatywy, koniunkcji i negacji. Przez wartościowanie formuły ϕ rozumiemy funkcję, która zmiennym wystepującym w formule ϕ przyporządkowuje wartości ze zbioru {0, 1}. Niech n będzie dodatnią liczbą naturalną.

a) Udowodnij, że dla każdej liczby naturalnej k ≤ 2^{n} istnieje formuła zdaniowa ϕ zawierająca n zmiennych i spełniona przez dokładnie k wartościowań.

b) Dla jakich liczb k istnieje formuła ϕ zawierająca n zmiennych, w której każda ze zmiennych występuje dokładnie jeden raz i która jest spełniona przez dokładnie k wartościowań?

Rozwiązanie. Część a) zadania 1 jest oczywistą konsekwencją zupełności zbioru spójników złożonego z alternatywy, koniunkcji i negacji. Bierzemy dowolną funkcję boolowską n zmiennych przyjmującą wartość 1 dla k argumentów i korzystając z zupełności stwierdzamy, że jest to funkcja przyporządkowująca układowi zer i jedynej wartość logiczną pewnej formuły przy wartościowaniu wyznaczonym przez ten układ. Nie wiem, jak takie rozwiązanie było oceniane, ale uważam je za zbyt lakoniczne.

Można wziąć n zmiennych zdaniowych p_{1}, …, p_{n} i tworzyć formuły będącą koniunkcją tych zmiennych bądź ich negacji (np. ¬p_{1} ∧ p_{2} ∧ … ∧ p_{n}) Formuły tej postaci są spełnione przez dokładnie jedno wartościowanie. Alternatywa k różnych formuł takiej postaci (dowolnie wybranych) jest formułą spełnioną przez dokładnie k wartościowań.

Bardziej szczegółowo przedstawię jeszcze inne rozwiązanie tego zadania. Przyjmijmy, że W (ϕ) oznacza zbiór wartościowań spełniających formułę ϕ.

Fakt 1.1 Jeżeli w formule ϕ występuje n zmiennych, to |W (¬ϕ)| = 2^{n} − |W (ϕ)|.

Dowód. Jest to oczywisty fakt. Dla formuły ϕ z n zmiennymi jest 2^{n} wartościowań. Każde z nich spełnia albo ϕ, albo ¬ϕ, żadne nie może jednocześnie spełniać obu tych formuł. □

Fakt 1.2 Jeżeli żadna zmienna nie występuje jednocześnie w formulach ϕ i ψ, to

|W (ϕ ∧ ψ)| = |W (ϕ)| · |W (ψ)|. □

Dowód. Rozważmy funkcję, która wartościowaniu h formuły ϕ ∧ ψ przyporządkowuje parę dwóch wartościowań: wartościowania będącego obcięciem h do zmiennych formuły ϕ i wartościowania będącego obcięciem h do zmiennych formuły ψ. Różnowartościowość tej funkcji jest oczywista.

Wystarczy teraz zauważyć, że funkcja ta przekształca zbiór W (ϕ ∧ ψ) na iloczyn kartezjański W (ϕ) × W (ψ). (Gdzie w tym dowodzie korzysta się z założenia o zmiennych formuł ϕ i ψ?) □

Wniosek 1.3 Jeżeli zmienna p nie występuje w formule ϕ, to |W (ϕ ∧ p)| = |W (ϕ)|. □

Wniosek 1.4 Jeżeli w formule ϕ występuje n zmiennych i nie ma wśród nich zmiennej p, to |W (ϕ ∨ p)| = 2^{n} + |W (ϕ)|.

Dowód. Zauważmy, że

|W (ϕ ∨ p)| = |W (¬(¬ϕ ∧ ¬p))| = 2^{n+1} − |W (¬ϕ ∧ ¬p)| =
= 2^{n+1} − |W (¬ϕ)| · |W (¬p)| = 2^{n+1} − (2^{n} − |W (ϕ)|) · (2 − |W (p)|) =
= 2^{n+1} − 2^{n} + |W (ϕ)| = 2^{n} + |W (ϕ)|. □

Fakt 1.5 Dla każdej liczby naturalnej k ≤ 2^{n} istnieje formuła zdaniowa z n zmiennymi spełniona przez dokładnie k wartościowań.

Dowód. Fakt ten dowodzimy przez indukcję ze względu na n.

Zauważmy, że |W (p∧¬p)| = 0, |W (p)| = 1 i |W (p∨¬p)| = 2. Tym samym twierdzenie jest prawdziwe dla n = 1.

Załózmy, że twierdzenie to jest zachodzi dla liczby n i weźmy k ≤ 2^{n+1}. Zachodzi jeden z dwóch przypadków: albo k ≤ 2^{n}, albo 2^{n} < k ≤ 2^{n+1}.

Jeżeli k ≤ 2^{n}, to znajdujemy formułę ϕ z n zmiennymi, która jest spełniona przez k wartościowań, i zmienną p, która nie występuje w ϕ. Formuła ϕ ∧ p jest spełniona przez k wartościowań i występuje w niej n + 1 zmiennych.

Jeżeli 2^{n} < k ≤ 2^{n+1}, to bierzemy formułę ϕ z n zmiennymi, spełnioną przez k − 2^{n} wartościowań. Wtedy dla dowolnej zmiennej p nie występującej w ϕ formuła ϕ ∨ p jest spełniona przez k wartościowań i występuje w niej n + 1 zmiennych. □

Podobnie dowodzimy następujący fakt:

Fakt 1.6 Dla każdej nieparzystej liczby naturalnej k ≤ 2^{n} istnieje formuła zdaniowa z n zmiennymi, w której każda zmienna występuje dokładnie jeden raz i która jest spełniona przez dokładnie k wartościowań.

Dowód. Formułę, w której każda zmienna występuje najwyżej jeden raz, będą nazywał prostą. Twierdzenie to także dowodzimy przez indukcję ze względu na n.

Zauważmy, że |W (p)| = 1. Wobec tego dowodzone twierdzenie jest prawdziwe dla n = 1.

Załózmy, że twierdzenie to jest zachodzi dla liczby n i weźmy nieparzystą liczbę k ≤ 2^{n+1}. Liczba k jest albo ≤ 2^{n}, albo też spełnia nierówności 2^{n} < k ≤ 2^{n+1}.

Jeżeli k ≤ 2^{n}, to znajdujemy prostą formułę ϕ z n zmiennymi, która jest spełniona przez k wartościowań, i zmienną p, która nie występuje w ϕ. Formuła ϕ ∧ p jest prosta i spełniona przez k wartościowań, oraz występuje w niej n + 1 zmiennych.

Jeżeli 2^{n} < k ≤ 2^{n+1}, to bierzemy prostą formułę ϕ z n zmiennymi, spełnioną przez k −2^{n} wartościowań. Wtedy dla dowolnej zmiennej p nie występującej w ϕ, formuła ϕ∨p jest prosta, spełniona przez k wartościowań i występuje w niej n + 1 zmiennych. □

Fakt 1.7 Jeżeli ϕ jest formułą, w której każda zmienna występuje najwyżej jeden raz, to ϕ jest spełniona przez nieparzystą liczbę wartościowań.

Dowód. Dowód przeprowadzimy przez indukcję ze względu na liczbę znaków występujących w formule. Formuła, która daje się zapisać za pomocą jednego znaku jest zmienną i jest spełniona przez jedno wartościowanie.

Przypuśćmy, że ϕ = ¬ψ i występuje w niej n zmiennych. Oczywiście, każda zmienna występuje tyle samo razy w ϕ, co w ψ. Z założenia indukcyjnego wynika więc, że ψ jest spełniona przez nieparzystą liczbę wartościowań równą |W (ψ)|. Liczba 2^{n} − |W (ψ)| jest nieparzysta i jest równa liczbie wartościowań spełniających ϕ.

Jeżeli w koniunkcji ϕ ∧ ψ każda zmienna występuje najwyżej jeden raz (jeżeli koniunkcja ta jest prosta), to ϕ i ψ są proste, i żadna zmienna nie występuje jednocześnie w obu tych formułach. Wobec tego, formuła ϕ ∧ ψ jest spełniona przez |W (ϕ)| · |W (ψ)| wartościowań. Na mocy założenia indukcyjnego, oba czynniki tego iloczynu są liczbami nieparzystymi. Iloczyn liczb nieparzystych też jest nieparzysty.

Jeszcze trzeba pokazać (można to zrobić w podobny sposób), że alternatywa będąca formułą prostą jest spełniona przez nieparzystą liczbę wartościowań. □

Zadanie 2 Niech α : N → {0, 1} będzie ciągiem zero-jedynkowym. Symbolem ∼_{α} oznaczamy relację w zbiorze {0, 1}^{N} nieskończonych ciągów zero-jedynkowych zdefiniowaną formułą

β ∼_{α} γ ⇔ (∀n∈N) α(n)β(n) = α(n)γ(n).

Czy istnieje taki ciąg α, dla którego:

a) relacja ∼_{α} ma przeliczalnie i nieskończenie wiele klas równoważności?

b) wszystkie klasy równoważności relacji ∼_{α} są przeliczalne i nieskończone?

c) istnieje przeliczalna i nieskończona klasa równoważności relacji ∼_{α}?

Rozwiązanie. Ustalmy α i przyjmijmy, że A = {n ∈ N : α(n) = 1}. Oczywiście, ∼_{α} jest relacją równoważności. Przyjmijmy, że N_{α} jest zbiorem klas równoważności tej relacji. Symbolem [x]_{α} będziemy oznaczać klasy abstrakcji relacji ∼_{α}.

Fakt 2.1 Zbiór N_{α} i zbiór {0, 1}^{A} są równoliczne.

Dowód. Dla funkcji ξ : A → {0, 1} definiujemy funkcję ξ̄: N → {0, 1} przyjmując, że

ξ̄(n) = \{ \begin{matrix}ξ(n) & jeżeli n ∈ A, \\ 0 & w przeciwnym razie. \end{matrix}

Zdefiniujmy jeszcze wzorem

f(ξ) = [ξ̄]_{α}

funkcję f : {0, 1}^{A} → N_{α}. Funkcja ta jest różnowartościowa i typu „na”.

Aby dowieść różnowartościowość funkcji f weźmy dwa (różne) argumenty ξ_{1} i ξ_{2} tej funkcji. Są to funkcje określone w zbiorze A. Istnieje więc liczba n ∈ A taka, że ξ_{1}(n) ≠ ξ_{2}(n). Funkcje ξ̄_{1} i ξ̄_{2} też przyjmują różne wartości dla argumentu n:

ξ̄_{1}(n) = ξ_{1}(n) ≠ ξ_{2}(n) = ξ̄_{2}(n).

Oznacza to, że ξ̄_{1} ≁_{α} ξ̄_{2}. Stąd otrzymujemy, że klasy [ξ̄_{1}]_{α} i [ξ̄_{2}]_{α} są różne (różnią się np. elementem ξ̄_{1}).

Weźmy dowolną klasę ze zbioru N_{α} i jej reprezentanta γ. Pokażemy, że [γ]_{α} jest wartością funkcji f. W tym celu weźmy funkcję δ : A → {0, 1} będącą obcięciem γ do zbioru A (a więc spełniającą δ(n) = γ(n) dla wszystkich n ∈ A) i zauważmy, że także δ̄(n) = γ(n) dla wszystkich n ∈ A. To jednak oznacza, że δ̄ ∼_{α} γ. Wobec tego, f(δ) = [δ̄]_{α} = [γ]_{α}. Inny dowód. Weźmy funkcję g : {0, 1}^{N} → {0, 1}^{A} przyporządkowującą funkcji γ ∈ {0, 1}^{N} obcięcie funkcji γ do zbioru A. Oczywiście, funkcja g jest typu „na”. Świadczy o tym np. równość g(ξ̄) = ξ.

Funkcja g spełnia także równoważność

g(γ_{1}) = g(γ_{2}) ⇔ γ_{1} ∼_{α} γ_{2}.

Równoważność ta implikuje, że wzór

G([γ]_{α}) = g(γ)

jest poprawną definicją funkcji G : N_{α} → {0, 1}^{A} i – co więcej – funkcja ta jest różnowartościowa. Ponieważ g jest typu „na”, więc także G jest typu „na”. □

Fakt 2.2 Klasy równoważności relacji ∼_{α} są równoliczne ze zbiorem {0, 1}^{N\A}.

Dowód. Weźmy dowolną funkcję β ∈ {0, 1}^{N} i zdefiniujmy funkcję f : [β]_{α} → {0, 1}^{N\A}. Funkcja f elementowi γ ∈ [β]_{α} przyporządkowuje obcięcie γ do zbioru N \A. Aby dowieść podany fakt pokażemy, że funkcja f jest bijekcją.

Weźmy więc różne funkcje γ_{1}, γ_{2} ∈ [β]_{α}. Ponieważ należą do jednej klasy równoważności relacji ∼_{α}, więc przyjmują te same wartości dla dowolnego argumentu ze zbioru A. Wobec tego, przyjmują różne wartości dla pewnego n ∉ A. Ich obcięcia od zbioru N \ A też przyjmują różne wartości dla tego samego argumentu, a więc są różne. To dowodzi, że funkcja f jest różnowartościowa.

Aby dowieść, że funkcja f jest typu „na”, weźmy dowolną funkcję ξ ∈ {0, 1}^{N\A} i zdefiniujmy γ ∈ {0, 1}^{N} takie, że

γ(n) = \{ \begin{matrix}β(n) & jeżeli n ∈ A, \\ ξ(n) & w przeciwnym razie. \end{matrix}

Oczywiście, funkcje γ i β są w relacji ∼_{α} oraz obcięcie γ do N \ A jest równe ξ. Tak więc f(γ) = ξ. □

Fakt 2.3 Jeżeli zbiór A ⊆ N jest nieskończony, to zbiór {0, 1}^{A} jest nieprzeliczalny.

Dowód. Nieskończony podzbiór A zbioru liczb naturalnych jest równoliczny ze zbiorem liczb naturalnych N. Jeżeli zbiór A jest równoliczny z N, to także zbiory {0, 1}^{A} i {0, 1}^{N} są równoliczne. Ten ostatni zbiór jest nieprzeliczalny na podstawie twierdzenia Cantora. Oznacza to, że także zbiór {0, 1}^{A} jest nieprzeliczalny. □

Wniosek 2.4 Zbiór N_{α} klas równoważności relacji ∼_{α} jest albo skończony, albo nieprzeliczalny.

Dowód. Są możliwe dwa przypadki: albo zbiór A jest skończony i wtedy zbiór {0, 1}^{A} i równoliczny z nim zbiór N_{α} są skończone, albo zbiór A jest nieskończony i zarówno zbiór {0, 1}^{A} jak i równoliczny z nim zbiór N_{α} są nieprzeliczalne. □

Z powyższego wniosku wynika negatywna odpowiedź na pytanie a): dla żadnego α zbiór klas równoważności relacji ∼_{α} nie jest przeliczalny i nieskończony.

Wniosek 2.5 Klasy abstrakcji relacji ∼_{α} są albo skończone, albo nieprzeliczalne.

Dowód. Ten wniosek dowodzimy dokładnie tak, jak poprzedni. □

Z ostatniego wniosku otrzymujemy negatywną odpowiedź na pytanie c): dla żadnego α żadna klasa klasa równoważności nie jest nieskończona przeliczalna.

Negatywna odpowiedż na pytanie c) implikuje także negatywną odpowiedź na pytanie b). Odpowiedź na pytanie b) można też łatwo wyprowadzić z ostatniego wniosku.

Zadanie 3 Na zbiorze X określone są takie relacje równoważności Q i R, że 1. każda klasa równoważności relacji Q ma q elementów,

2. każda klasa relacji R ma r elementów oraz

3. istnieje klasa równoważności relacji Q, która ma dokładnie jeden element wspólny z każdą klasą równoważności relacji R. Ile elementów ma zbiór X?

Rozwiązanie. Przyjmijmy, że A oznacza tę klasę równoważności relacji Q, o której jest mowa w punkcie 3), a K – zbiór klas równoważności relacji R.

Wszystkie przedstawione rozwiązania korzystają z faktu, że zbiory K i A mają tyle samo elementów. Jeżeli to wiemy, to na podstawie warunku 1) stwierdzamy, że K ma q elementów. Relacja równoważności R wyznacza więc podział zbioru X na q rozłącznych klas równoważności, które mają po r elementów. Stąd otrzymujemy, że X ma q · r elementów. Dalej pokażę, jak dowodzić, że |A| = |K|. Sposób I. Niech f : K → A będzie funkcją, która dla klasy Y ∈ K przyjmuje wartość f(Y) ∈ Y ∩ A. Punkt 3 ze sformułowania zadania gwaratuje poprawność tej definicji.

Pokażemy, że funkcja f jest bijekcją. Jeżeli f(Y) = f(Z) dla pewnych klas klas Y, Z ∈ K, to f(Y) ∈ (Y ∩ A) ∩ (Z ∩ A) ⊆ Y ∩ Z. W tym przypadku klasy Y i Z nie są rozłączne, a to jest możliwe tylko wtedy, gdy Y = Z. Wobec tego f jest różnowartościowa.

Weźmy teraz a ∈ A. Oczywiście, klasa równoważności [a]_{R} należy do K. Gdyby f([a]_{R}) ≠ a, to zbiór [a]_{R} ∩ A miałby przynajmniej dwa elementy: f([a]_{R}) oraz a, a to przeczy warunkowi 3). Tak więc funkcja f jest typu „na”. Sposób II. Tym razem definiujemy funkcję g : A → K, która elementowi a ∈ A przyporządkowuje klasę [a]_{R} (przyjmujemy, że g(a) = [a]_{R}). Podobnie jak w pierwszym rozwiązaniu, funkcja g jest bijekcją.

Jeżeli [a]_{R} = [b]_{R} dla a, b ∈ A, to do klasy [a]_{R} należy zarówno a, jak i b. Z wyboru A mamy jednak, że do dowolnej klasy równoważności może należeć tylko jeden element zbioru A, więc a = b.

Jeżeli Y jest dowolną klasą równoważności relacji R, to z warunku 3) (a raczej z wyboru A) znajdujemy w niej pewien element a ∈ A. Wobec tego, klasy równoważności [a]_{R} i Y nie są rozłączne. Takie klasy muszą być równe. Otrzymaliśmy więc, że g(a) = [a]_{R} = Y. Sposób III. Zauważmy, że

A = A ∩ X = A ∩ ⋃_{Y ∈K} Y = ⋃_{Y ∈K} A ∩ Y

(druga równość wynika stąd, że suma klas rownoważności jest równa dziedzinie relacji równoważności). Zbiory A∩Y_{1} i A∩Y_{2} dla różnych klas równoważności Y_{1} i Y_{2} są rozlączne, ponieważ klasy te są rozłączne. Wobec tego

|A| = | ⋃_{Y ∈K} A ∩ Y | = ∑_{Y ∈K} |A ∩ Y | = ∑_{Y ∈K} 1 = |K|.

Zadanie 4 Niech Σ = {+, a} będzie sygnaturą zawierającą dwuargumentowy symbol funkcji + i symbol stałej a. Dla dowolnej dodatniej liczby naturalnej n niech A_{n} = {0, 1, …, n − 1}, ⊕_{n} oznacza dodawanie modulo n, zaś a_{n} = 0. Rozważmy algebry A_{n} = ⟨A_{n}, ⊕_{n}, a_{n}⟩. Udowodnij, że jeżeli k = l · m, to istnieje homomorfizm h algebry A_{k} na algebrę A_{l} (surjekcja) taki, że |h⃗^{−1}({0})| = m. Podaj przykład takich k, l i m, dla których istnieją co najmniej dwa takie homomorfizmy. Ile jest takich homomorfizmów, jeśli zamiast sygnatury Σ będziemy rozważać sygnaturę Σ′ = {+, a, b} zawierajacą dwa symbole stałych a i b oraz algebry A′_{n} = ⟨A_{n}, ⊕_{n}, a_{n}, b_{n}⟩, gdzie b_{n} = 1?

Analiza sytuacji. Resztę z dzielenia k przez l będę oznaczać także symbolem k mod l. Zauważmy, że każdy element A_{k} jest sumą pewnej liczby jedynek (daje się przedstawić w postaci 1⊕_{k} …⊕_{k} 1). Wobec tego 1 generuje A_{k}. Homomorfizm wystarczy zdefiniować na zbiorze generatorów. Przyjmijmy więc, że h : A_{k} → A_{l} jest homomorfizmem i h(1) = a. Wtedy

h(n) = h(\underbrace{1 ⊕_{k} … ⊕_{k} 1}_{n razy}) = \underbrace{h(1) ⊕_{l} … ⊕_{l} h(1)}_{n razy} = (a · n) mod l.

Rozwiązanie.

Fakt 4.1 Jeżeli l dzieli k, to funkcja h_{a} : A_{k} → A_{l} zdefiniowana wzorem

h_{a}(x) = (a · x) mod l

jest homomorfizmem algebr A_{k} i A_{l}.

Dowód. Zauważmy najpierw, że definicja funkcji h_{a} zależy od k i l, mimo że wprowadzone oznaczenie na to nie wskazuje. Oczywiście, h_{a}(0) = 0. Wystarczy więc dowieść, że dla wszystkich x, y ∈ A_{k} zachodzi równość h_{a}(x ⊕_{k} y) = h_{a}(x) ⊕_{l} h_{a}(y). Zauważmy, że

a · x = p · l + h_{a}(x) oraz a · y = q · l + h_{a}(y)

dla pewnych liczb naturalnych p i q. Z tych samych powodów zachodzi równość

x + y = r · k + (x ⊕_{k} y).

Łącząc podane równości otrzymujemy

a · r · k + a · (x ⊕_{k} y) = a · (x + y) = (p + q) · l + h_{a}(x) + h_{a}(y).

Ponieważ l dzieli k, więc

h_{a}(x ⊕_{k} y) = a · (x ⊕_{k} y) mod l = (h_{a}(x) + h_{a}(y)) mod l = h_{a}(x) ⊕_{l} h_{a}(y). □

Część I. Korzystając z podanego faktu można łatwo rozwiązać pierwszą część zadania. Wystarczy zauważyć, że jeżeli k = l · m, to h_{1} : A_{k} → A_{l} jest homomorfizmem takim, że h_{1}(x) = x dla x = 0, …, l − 1, a więc jest homomorfizmem algebry A_{k} na algebrę A_{l}. Mamy także

h⃗_{1}^{−1}(0) = {x < l · m : x mod l = 0} = {x < l · m : l dzieli x} =
= {i · l : i < m} = g⃗({i : i < m})

dla funkcji g : N → N takiej, że g(i) = i · l. Funkcja g jest oczywiście różnowartościowa. Wobec tego zbiór h⃗_{1}^{−1}(0) jest równoliczny ze zbiorem {i : i < m}, który oczywiście ma m elementów, i też ma m elementów. Część II. Aby rozwiązać drugą część zadania wystarczy dodatkowo zauważyć, że jeżeli weźmiemy k = l = 3, to odpowiednia funkcja h_{2} przekształca A_{3} na A_{3} (h_{2}(1) = 2 i h_{2}(2) = 1) i – wobec tego – jest homomorfizmem algebry A_{3} na algebrę A_{3}. Funkcje h_{1} i h_{2} są w tym przypadku różne, ponieważ 1 = h_{1}(1) ≠ h_{2}(1) = 2. Podobnie jest w przypadku funkcji h_{2} : A_{6} → A_{3} (jest to inna funkcja niż poprzednia, mimo że jest tak samo oznaczana!). Można dowieść, że dla dowolnej wielokrotności k liczby l, funkcja h_{a} przekształca A_{k} na A_{l} wtedy i tylko wtedy, gdy a jest względnie pierwsze z l. Część III. Z definicji homomorfizmu wynika, że homomorfizmy algebry A′_{k} w algebrę A′_{l} są to dokładnie homomorfizmy algebry A_{k} w algebrę A_{l} przekształcające 1 na 1. Aby więc odpowiedzieć na ostatnie pytanie wystarczy ustalić, ile jest homomorfizmów przekształcających algebrą A_{k} na algebrę A_{l} i przeprowadzających 1 na 1. Pokażemy, że jeżeli l dzieli k, to jest dokładnie jeden taki homomorfizm. Oczywiście, jest taki homomorfizm (jest nim h_{1}). Przypuśćmy, że h też jest takim homomorfizmem. Wtedy

h(n) = h(\underbrace{1 ⊕_{k} … ⊕_{k} 1}_{n razy}) = \underbrace{h(1) ⊕_{l} … ⊕_{l} h(1)}_{n razy} = \underbrace{h_{1}(1) ⊕_{l} … ⊕_{l} h_{1}(1)}_{n razy} = h_{1}(n)

dla wszystkich n ∈ A_{k}. Wobec tego, homomorfizmy h i h_{1} są identyczne. Bardziej elegancki dowód tego faktu powinien być indukcyjny.

Zadanie 5 Pokaż, że zbior liczb wymiernych ze zwykłym porządkiem i zbiór niepustych skończonych ciągów liczb wymiernych z porządkiem leksykograficznym są izomorficzne (rozważamy porządek leksykograficzny generowany przez zwykły porządek na liczbach wymiernych).

Przypominamy, że ⪯ jest porządkiem leksykograficznym generowanym przez porządek ≤, jeśli

⟨a_{0}, a_{1}, … a_{m}⟩ ⪯ ⟨b_{0}, b_{1}, …, b_{n}⟩

wtedy i tylko wtedy, gdy ⟨a_{0}, a_{1}, … a_{m}⟩ jest prefiksem ⟨b_{0}, b_{1}, …, b_{n}⟩ lub

(∃ k) (k ≤ m ∧ k ≤ n ∧ a_{k} < b_{k} ∧ (∀ i<k) a_{i} = b_{i}).

Wskazówka: Skorzystaj z twierdzenia o gęstych porządkach udowodnionego na ćwiczeniach. Przytocz sformułowanie tego twierdzenia.

Rozwiązanie. W tym zadaniu należy skorzystać z twierdzenia, które mówi, że każde dwa przeliczalne porządki liniowe, które są gęste i bez końców, są izomorficzne.

Aby skorzystać z tego twierdzenia, należy pokazać, że

1. zbiór skończonych, niepustych ciągów o wyrazach wymiernych jest przeliczalny,

2. porządek leksykograficzny wyznaczony przez porządek liniowy jest porządkiem liniowym,

3. porządek leksykograficzny w zbiorze skończonych, niepustych ciągów o wyrazach wymiernych jest gęsty,

4. oraz nie ma w nim elementu największego, ani najmniejszego.

Sądzę, że zamiast dowodzić przeliczalność zbioru skończonych ciągów o wyrazach wymiernych i liniowość porządku leksykograficznego, można powołać się na fakty znane z wykładu lub ćwiczeń.

Aby dowieść gęstość rozważanego porządku weźmy dwa skończone, niepuste ciągi a i b liczb wymiernych odpowiednio o wyrazach a_{1}, a_{2}, …, a_{n} oraz b_{1}, b_{2}, …, b_{m}. Załóżmy, że ciąg a jest mniejszy w sensie porządku leksykograficznego od ciągu b. Są możliwe dwa przypadki: albo n < m oraz a_{i} = b_{i} dla wszystkich i = 1, …, n, albo też dla pewnej liczby k ≤ n, m zachodzi nierówność a_{k} < b_{k} i spełnione są równości a_{i} = b_{i} dla i = 1, …, k −1. Jeżeli zachodzi pierwszy przypadek, to bierzemy ciąg c o wyrazach b_{1}, b_{2}, …, b_{n}, b_{n+1} −1. W drugim przypadku bierzemy ciąg c o wyrazach b_{1}, b_{2}, …, b_{k−1}, (a_{k} + b_{k})/2. Bez trudu sprawdzamy, że w obu przypadkach ciąg c jest większy w sensie porządku leksykograficznego od ciągu a i mniejszy od ciągu b.

Jest też oczywiste, że jeżeli a_{1} jest pierwszym wyrazem ciągu a, to jednoelementowy ciąg, którego wyrazem jest liczba a_{1} + 1 jest większy od a, a jednoelementowy ciąg, którego wyrazem jest liczba a_{1} − 1 jest mniejszy od a. Tak więc w rozważanym porządku leksykograficznym nie ma elementu największego, ani najmniejszego.