Matematička logika i teorija skupova - veoma teški zadaci sa rešenjima

Rešenje:
Donja granica. Tačno [tex]20 - 17 = 3[/tex] elementa skupa [tex]A \cup B \cup C[/tex] ne pripadaju skupu [tex]C[/tex], pa je [tex]|A \setminus C| \le 3[/tex] i [tex]|B \setminus C| \le 3[/tex]. Zato je
[tex]|A \cap C| = |A| - |A \setminus C| \ge 15 - 3 = 12, \qquad |B \cap C| = |B| - |B \setminus C| \ge 10 - 3 = 7[/tex]
Skupovi [tex]A \cap C[/tex] i [tex]B \cap C[/tex] su podskupovi skupa [tex]C[/tex], pa njihova unija ima najviše [tex]17[/tex] elemenata, a njihov presek je [tex]A \cap B \cap C[/tex]. Zato je
[tex]|A \cap B \cap C| = |A \cap C| + |B \cap C| - |(A \cap C) \cup (B \cap C)| \ge 12 + 7 - 17 = 2[/tex]
Granica se dostiže, na primer, za skupove
[tex]A = \{1 ; \ldots ; 12\} \cup \{18 ; 19 ; 20\}, \quad B = \{11 ; \ldots ; 17\} \cup \{18 ; 19 ; 20\}, \quad C = \{1 ; \ldots ; 17\}[/tex]
Ovde je [tex]|A| = 15[/tex], [tex]|B| = 10[/tex], [tex]|C| = 17[/tex], [tex]A \cup B \cup C = \{1 ; \ldots ; 20\}[/tex] i [tex]A \cap B \cap C = \{11 ; 12\}[/tex]. Dakle, najmanji mogući broj je [tex]2[/tex].

Rešenje:
Označimo proizvod sa [tex]P[/tex]. Svaki skup [tex]A_n[/tex] je prebrojivo beskonačan, pa njegove elemente možemo numerisati bez ponavljanja:
[tex]A_n = \{a_{n,1}, a_{n,2}, a_{n,3}, \ldots\}, \qquad a_{n,1} \ne a_{n,2}[/tex]
Pretpostavimo da je [tex]P[/tex] prebrojiv. On je neprazan (sadrži [tex](a_{1,1}, a_{2,1}, a_{3,1}, \ldots)[/tex]), pa se njegovi elementi mogu poređati u niz (ponavljanja su dozvoljena)
[tex]x^{(1)}, x^{(2)}, x^{(3)}, \ldots, \qquad x^{(k)} = \left(x^{(k)}_1, x^{(k)}_2, x^{(k)}_3, \ldots\right)[/tex]
Primenimo Kantorov dijagonalni postupak: za svako [tex]n[/tex] stavimo [tex]y_n = a_{n,2}[/tex] ako je [tex]x^{(n)}_n = a_{n,1}[/tex], i [tex]y_n = a_{n,1}[/tex] ako je [tex]x^{(n)}_n \ne a_{n,1}[/tex]. Neka je [tex]y = (y_1, y_2, y_3, \ldots)[/tex]. Tada je [tex]y_n \in A_n[/tex] za svako [tex]n[/tex], pa je [tex]y \in P[/tex].
S druge strane, [tex]y_n \ne x^{(n)}_n[/tex] za svako [tex]n[/tex], tj. [tex]y[/tex] se razlikuje od [tex]x^{(n)}[/tex] u [tex]n[/tex]-toj koordinati. Zato je [tex]y \ne x^{(n)}[/tex] za svako [tex]n[/tex], pa [tex]y[/tex] nije u nizu, što je kontradikcija. Dakle, [tex]P[/tex] je neprebrojiv.

Rešenje:
Konstruisaćemo [tex]F[/tex] kao kompoziciju triju bijekcija.
Korak 1. Linearna funkcija [tex]\varphi(x) = \frac{x-a}{b-a}[/tex] je bijekcija duži [tex]\left[a ; b\right][/tex] na [tex]\left[0 ; 1\right][/tex]: strogo je rastuća (jer je [tex]b - a \gt 0[/tex]), [tex]\varphi(a) = 0[/tex], [tex]\varphi(b) = 1[/tex], a njena inverzna funkcija je [tex]t \mapsto a + (b-a)t[/tex].
Korak 2. Bijekcija [tex]g\colon \left[0 ; 1\right] \to \left(0 ; 1\right)[/tex] (uklanjanje oba kraja). Pomerimo niz [tex]0 ; 1 ; \frac{1}{2} ; \frac{1}{3} ; \frac{1}{4} ; \ldots[/tex] za dva mesta unapred, a sve ostale tačke ostavimo na mestu:
[tex]g(0) = \frac{1}{2}, \qquad g(1) = \frac{1}{3}, \qquad g\left(\frac{1}{n}\right) = \frac{1}{n+2} \quad (n \ge 2)[/tex]
i [tex]g(x) = x[/tex] za svako drugo [tex]x \in \left[0 ; 1\right][/tex]. Skup [tex]S = \left\{0 ; 1 ; \frac{1}{2} ; \frac{1}{3} ; \ldots\right\}[/tex] se bijektivno preslikava na [tex]S' = \left\{\frac{1}{2} ; \frac{1}{3} ; \ldots\right\}[/tex] (član niza sa rednim brojem [tex]k[/tex] prelazi u član sa rednim brojem [tex]k + 2[/tex]), a skup [tex]\left[0 ; 1\right] \setminus S[/tex] se identički preslikava na sebe i jednak je skupu [tex]\left(0 ; 1\right) \setminus S'[/tex]. Pošto su [tex]S'[/tex] i [tex]\left(0 ; 1\right) \setminus S'[/tex] disjunktni i njihova unija je [tex]\left(0 ; 1\right)[/tex], funkcija [tex]g[/tex] je bijekcija.
Korak 3. Funkcija [tex]h(t) = \operatorname{tg} \left(\pi\left(t - \frac{1}{2}\right)\right)[/tex] je bijekcija intervala [tex]\left(0 ; 1\right)[/tex] na [tex]\mathbb{R}[/tex]. Kada [tex]t[/tex] prolazi kroz [tex]\left(0 ; 1\right)[/tex], argument [tex]\pi\left(t - \frac{1}{2}\right)[/tex] prolazi kroz [tex]\left(-\frac{\pi}{2} ; \frac{\pi}{2}\right)[/tex], gde je tangens neprekidan i strogo rastući, pa je [tex]h[/tex] injektivna. Osim toga, [tex]h(t) \to -\infty[/tex] kad [tex]t \to 0^+[/tex] i [tex]h(t) \to +\infty[/tex] kad [tex]t \to 1^-[/tex], pa prema teoremi o međuvrednosti [tex]h[/tex] uzima svaku realnu vrednost.
Dakle, [tex]F = h \circ g \circ \varphi\colon \left[a ; b\right] \to \mathbb{R}[/tex] je kompozicija bijekcija, pa je i sama bijekcija.

Rešenje:
Koristimo Kantor–Šreder–Bernštajnovu teoremu: ako postoje injekcija [tex]X \to Y[/tex] i injekcija [tex]Y \to X[/tex], onda postoji bijekcija između [tex]X[/tex] i [tex]Y[/tex]. Injekcija [tex]\left[a ; b\right] \to \mathbb{R}^2[/tex] je očigledna: [tex]t \mapsto (t ; 0)[/tex]. Ostaje da konstruišemo injekciju [tex]\mathbb{R}^2 \to \left[a ; b\right][/tex]; dobićemo je kao kompoziciju triju injekcija.
Korak 1. Funkcija [tex]\psi(x) = \frac{1}{1 + e^{-x}}[/tex] je strogo rastuća i uzima vrednosti u [tex]\left(0 ; 1\right)[/tex], jer je [tex]1 + e^{-x}[/tex] strogo opadajuća i veća od [tex]1[/tex]. Zato je [tex](x ; y) \mapsto (\psi(x) ; \psi(y))[/tex] injekcija [tex]\mathbb{R}^2 \to \left(0 ; 1\right)^2[/tex].
Korak 2. Svaki broj [tex]u \in \left(0 ; 1\right)[/tex] ima jedinstven decimalni zapis [tex]u = 0{,}u_1u_2u_3\ldots[/tex] koji se ne završava beskonačnim nizom devetki. Za [tex](u ; v) \in \left(0 ; 1\right)^2[/tex] sa takvim zapisima [tex]u = 0{,}u_1u_2u_3\ldots[/tex] i [tex]v = 0{,}v_1v_2v_3\ldots[/tex] naizmenično ređamo cifre:
[tex]D(u, v) = 0{,}u_1v_1u_2v_2u_3v_3\ldots[/tex]
Ovaj niz cifara se ne završava beskonačnim nizom devetki (inače bi cifre broja [tex]u[/tex] od nekog mesta nadalje bile devetke), pa je to standardni decimalni zapis broja [tex]D(u, v) \in \left[0 ; 1\right)[/tex]. Ako je [tex](u ; v) \ne (u' ; v')[/tex], onda se zapisi brojeva [tex]u[/tex] i [tex]u'[/tex] ili zapisi brojeva [tex]v[/tex] i [tex]v'[/tex] razlikuju u nekoj cifri, pa se razlikuju i dobijeni nizovi. Dva različita niza cifara koja se ne završavaju beskonačnim nizovima devetki predstavljaju različite brojeve, dakle [tex]D\colon \left(0 ; 1\right)^2 \to \left[0 ; 1\right)[/tex] je injekcija.
Korak 3. Funkcija [tex]t \mapsto a + (b-a)t[/tex] je injekcija [tex]\left[0 ; 1\right) \to \left[a ; b\right][/tex], jer je [tex]b - a \gt 0[/tex].
Kompozicija injekcija iz koraka 1, 2 i 3 je injekcija [tex]\mathbb{R}^2 \to \left[a ; b\right][/tex]. Prema Kantor–Šreder–Bernštajnovoj teoremi postoji bijekcija između [tex]\left[a ; b\right][/tex] i [tex]\mathbb{R}^2[/tex], tj. duž i ravan imaju istu kardinalnost.

Rešenje:
Neka je [tex]\sim[/tex] kongruencija i neka je [tex]H = \{x \in \mathbb{Z} \mid x \sim 0\}[/tex] klasa broja [tex]0[/tex].
Korak 1: [tex]x \sim y \Leftrightarrow x - y \in H[/tex]. Zaista, ako je [tex]x \sim y[/tex], dodavanjem [tex]a = -y[/tex] dobijamo [tex]x - y \sim 0[/tex]; obrnuto, ako je [tex]x - y \sim 0[/tex], dodavanjem [tex]a = y[/tex] dobijamo [tex]x \sim y[/tex].
Korak 2: [tex]H[/tex] je podgrupa grupe [tex](\mathbb{Z}, +)[/tex]. Zbog refleksivnosti je [tex]0 \in H[/tex]. Ako su [tex]x, y \in H[/tex], onda je [tex]x \sim 0[/tex] i, zbog simetričnosti, [tex]0 \sim y[/tex]; zbog tranzitivnosti je [tex]x \sim y[/tex], tj. [tex]x - y \in H[/tex] prema koraku 1. Prema tome, [tex]-y = 0 - y \in H[/tex] i [tex]x + y = x - (-y) \in H[/tex].
Korak 3: [tex]H = q\mathbb{Z}[/tex] za neki ceo broj [tex]q \ge 0[/tex]. Ako je [tex]H = \{0\}[/tex], uzmimo [tex]q = 0[/tex]. U suprotnom [tex]H[/tex] sadrži element različit od nule zajedno sa njemu suprotnim, pa i pozitivan element; neka je [tex]q[/tex] najmanji pozitivan element skupa [tex]H[/tex]. Prema koraku 2 svi umnošci [tex]kq[/tex], [tex]k \in \mathbb{Z}[/tex], pripadaju skupu [tex]H[/tex]. Za svako [tex]h \in H[/tex] deljenje sa ostatkom daje [tex]h = kq + r[/tex], gde je [tex]0 \le r \lt q[/tex]; tada je [tex]r = h - kq \in H[/tex], pa iz minimalnosti broja [tex]q[/tex] sledi [tex]r = 0[/tex]. Dakle, [tex]H = q\mathbb{Z}[/tex].
Korak 4: prema koraku 1, [tex]x \sim y \Leftrightarrow x - y \in q\mathbb{Z}[/tex]. Ako je [tex]q = 0[/tex], to znači [tex]x = y[/tex], tj. [tex]\sim[/tex] se poklapa sa [tex]\Delta_{\mathbb{Z}}[/tex]. Ako je [tex]q \ge 1[/tex], to znači [tex]q \mid x - y[/tex], tj. [tex]\sim[/tex] se poklapa sa [tex]\equiv_q[/tex].

Rešenje:
Korak 1. Za pozicije [tex]i, j \in \{1 ; 2 ; \ldots ; n\}[/tex] pišemo [tex]i \approx j[/tex] ako je [tex]s_i = s_j[/tex] za svako [tex]s \in S[/tex]. To je relacija ekvivalencije na skupu pozicija; neka su [tex]C_1, \ldots, C_k[/tex] njene klase, tako da je [tex]1 \le k \le n[/tex]. Neka je [tex]T[/tex] skup nizova koji su konstantni na svakoj klasi. Takav niz je određen nezavisnim izborom [tex]0[/tex] ili [tex]1[/tex] na svakoj klasi, pa je [tex]|T| = 2^k[/tex]. Dokazaćemo da je [tex]\bar{S} = T[/tex].
Korak 2. [tex]\bar{S} \subseteq T[/tex]. Svaki niz [tex]s \in S[/tex] je konstantan na svakoj klasi po definiciji relacije [tex]\approx[/tex]. Ako su [tex]u[/tex] i [tex]v[/tex] konstantni na klasi [tex]C[/tex], takvi su i [tex]u \wedge v[/tex], [tex]u \vee v[/tex] i [tex]\neg u[/tex], jer operacije deluju po komponentama; na primer, za [tex]i, j \in C[/tex]
[tex](u \wedge v)_i = u_i \wedge v_i = u_j \wedge v_j = (u \wedge v)_j[/tex]
Indukcijom po broju primenjenih operacija dobijamo da svaki element skupa [tex]\bar{S}[/tex] pripada skupu [tex]T[/tex].
Korak 3. [tex]T \subseteq \bar{S}[/tex]. Fiksirajmo [tex]s \in S[/tex] (moguće je, jer je [tex]S \ne \varnothing[/tex]); tada niz od samih nula [tex]\mathbf{0} = s \wedge \neg s[/tex] i niz od samih jedinica [tex]\mathbf{1} = s \vee \neg s[/tex] pripadaju skupu [tex]\bar{S}[/tex].
Fiksirajmo klasu [tex]C[/tex] i poziciju [tex]i \in C[/tex]. Za svaku poziciju [tex]j \notin C[/tex] važi [tex]i \not\approx j[/tex], pa postoji [tex]s \in S[/tex] sa [tex]s_i \ne s_j[/tex]; stavimo [tex]t^{(j)} = s[/tex] ako je [tex]s_i = 1[/tex] i [tex]t^{(j)} = \neg s[/tex] ako je [tex]s_i = 0[/tex]. Tada je [tex]t^{(j)} \in \bar{S}[/tex], [tex]t^{(j)}_i = 1[/tex] i [tex]t^{(j)}_j = 0[/tex]. Neka je
[tex]e_C = \mathbf{1} \wedge \bigwedge_{j \notin C} t^{(j)}[/tex]
(ako [tex]C[/tex] sadrži sve pozicije, onda je [tex]e_C = \mathbf{1}[/tex]). Tada je [tex]e_C \in \bar{S}[/tex]; ovaj niz ima [tex]0[/tex] na svakoj poziciji van [tex]C[/tex] i [tex]1[/tex] na poziciji [tex]i[/tex]. Pošto je prema koraku 2 [tex]e_C \in T[/tex], on je jednak [tex]1[/tex] na celoj klasi [tex]C[/tex]. Dakle, [tex]e_C[/tex] je upravo niz sa jedinicama na [tex]C[/tex] i nulama na ostalim pozicijama.
Najzad, svaki niz [tex]u \in T[/tex] jednak je [tex]1[/tex] tačno na uniji nekih klasa, pa je [tex]u[/tex] disjunkcija odgovarajućih nizova [tex]e_C[/tex] (ili [tex]u = \mathbf{0}[/tex] ako takvih klasa nema); zato je [tex]u \in \bar{S}[/tex]. Dakle, [tex]\bar{S} = T[/tex] i [tex]|\bar{S}| = 2^k[/tex], gde je [tex]1 \le k \le n[/tex].