Písomka LS 2016/17

[Martin Sleziak]

Skupina A$\newcommand{\inv}[1]{{#1}^{-1}}
\newcommand{\Invobr}[2]{\inv{#1}[#2]}
\newcommand{\Obr}[2]{{#1}[#2]}
\newcommand{\Zobr}[3]{{#1}\colon{#2}\to{#3}}
\newcommand{\mfr}[1]{\mathfrak{#1}}
\newcommand{\alnul}{\aleph_0}$

• Zistite, či výrok $[(p\Rightarrow q) \land (q\Rightarrow r)] \Rightarrow (p\Rightarrow r)$ je tautológia.
• Nech $J\ne\emptyset$ a pre každé $j\in J$ je $A_j$ množina. Dokážte, že ak $I\supseteq J$, tak $\bigcap\limits_{i\in I} A_i \subseteq \bigcap\limits_{j\in J} A_j$.
• Nech $\Zobr fXY$ je zobrazenie, $A,B\subseteq Y$. Dokážte, že $\Invobr f{A\cap B}=\Invobr fA \cap \Invobr fB$.
• Dokážte ${\mfr c}^{\mfr c}\cdot 2^{\alnul} = \mfr c \cdot 2^{\mfr c}$.
• Vypočítajte kardinalitu množiny $\mathbb N^{\mathbb N\times\mathbb N}$.

Skupina B

• Zistite či výrok $(p \Rightarrow r \lor q) \Leftrightarrow [(p \Rightarrow r) \lor (p\Rightarrow q)]$ je tautológia.
• Nech $I\ne\emptyset$ a pre každé $i\in I$ platí $A_i\subseteq B_i$. Dokážte, že $\bigcap\limits_{i\in I} A_i \subseteq \bigcap\limits_{i\in I} B_i$.
• Nech $\Zobr fXY$ je zobrazenie. Dokážte: $f$ je injektívne práve vtedy, keď pre ľubovoľné $A\subseteq B$ platí $$A\subseteq B \Leftrightarrow \Obr fA\subseteq \Obr fB.$$
• Dokážte $2^{\mfr c}\cdot\mfr c = \mfr c^{\alnul} \cdot (\alnul)^{\mfr c}$.
• Vypočítajte kardinalitu množiny $(\mathbb N\times\mathbb N)^{\mathbb N}$.

Snažil som sa aspoň k niektorým úlohám napísať aj komentár k riešeniu a aj niečo k tomu, aké chyby sa vyskytovali.

Ak by bolo k niektorej úlohe toho treba napísať viac, pokojne sa môžete pýtať aj na fóre. (Možno je rozumné otvoriť nový topic, aby toho nebolo priveľa tu pokope.)

[Martin Sleziak]

Myslel som si, že k tautológii nebudem musieť nič písať - to mala byť asi úloha, kde som rátal s tým, že skoro každý bude mať plný počet bodov.

V skupine B sa vyskytol zápis $p \Rightarrow r \lor q$. Týmto zápisom sa myslí $p \Rightarrow (r\lor q)$.
Našla sa jedna písomka, kde ste tento zápis používali ako keby to bolo $(p\Rightarrow r) \lor q$.
V princípe by som s tým nemal problém - zobral by som to tak, že sa zadanie dalo pochopiť dvoma spôsobmi. Ibaže ak ste zadanie chápali takto, tak výsledok by mal byť, že to nie je tautológia. (Zdá sa, že problém bol buď v nepozornosti alebo v neovládaní tabuľky implikácie.)

Spoiler:

Hoci som o precedencii operátorov nehovoril, je taká, ako ste zvyknutí.
Napríklad pre $p\Rightarrow r\lor q$ sa robí najprv logická spojka $\lor$. Presne tak ako by ste to robili pri inkúzii a zjednotení $A\subseteq B\cup C$ alebo pri nerovnosti a sčítaní $x\le y+z$.

V ostatných písomkách som k tejto úlohe nemal výhrady. Skoro všetci ste ju riešili tabuľkou - čo je asi v tomto prípade optimálny spôsob. (Asi úvahou by sa to niekedy dalo vyriešiť rýchlejšie, ale ak napíšete tabuľku, tak je človeku čo to opravuje jasné, o čo tam ide. Ak sa snažíte nejako zapísať úvahy, ktorými ste prišli na to, že je to vždy pravda, tak rozpísať to dosť detailne aby ste mali istotu že je to dostatočne jasne vysvetlené môže zabrať viac času než vypísať tabuľku.)

[Martin Sleziak]

K úlohe zo skupiny A som spravil samostatný post: viewtopic.php?t=1079

Úloha v druhej skupine bola rovnaká ako jedna z domácich úloh - ale s tým rozdielom, že sme zobrali ľubovoľnú indexovú množinu; v domácej úlohe to bolo pre $I=\mathbb N$.

[Martin Sleziak]

Úloha v skupine A dopadla ok a je podobná na viaceré iné úlohy o vzore či obraze množiny, niektoré sú vyriešené i na fóre.

Úloha zo skupiny B je kompletne vyriešená tu: viewtopic.php?t=1067
Našiel sa iba jeden človek, ktorý dokazoval obe implikácie. (Dosť veľa ľudí ukázalo, alebo sa aspoň pokúsilo ukázať, že pre injektívne zobrazenia platí uvedená podmienka. Súčasťou úlohy bolo dokázať aj opačný smer; t.j. ak $f$ spĺňa zadanú podmienku, tak $f$ je injektívne.)

[Martin Sleziak]

Poznamenám, že štvrtá úloha sa v oboch skupinách dala vyriešiť aj bez toho, aby ste priamo vyčíslili ľavú a pravú stranu. (Dalo sa overiť, že na oboch stranách je $\mathfrak c\cdot 2^{\mathfrak c}$. Z toho už je jasné, že sa obe strany rovnajú, aj bez toho, aby som vypočítal, že $\mathfrak c\cdot 2^{\mathfrak c}=2^{\mathfrak c}$.)

Niektoré chyby, ktoré sa vyskytli v riešeniach

$2^{\mathfrak c}=2^{{\aleph_0}^{\aleph_0}}=2^{\aleph_0\cdot \aleph_0}=2^{\aleph_0}=\mathfrak c$

Toto nie je správne. $2^{a^b}$ nie je to isté, ako $2^{ab}$.
Že to je zle sa dá vidieť aj z toho, že tvrdíte, že sa rovnajú kardinály $2^{\mathfrak c}$ a $\mathfrak c$, pričom ale z Cantorovej vety viete, že $2^{\mathfrak c}>\mathfrak c$.

Našli sa písomky, kde ste piatu úlohu počítali ako keby kardinalita množiny $\mathbb N$ bola $\mathfrak c$. Pritom priamo v zadaní písomky (v pokece o tom, ktoré identity sa môžu používať) ste mali napísané, že $|\mathbb N|=\aleph_0$. (Aj ak by ste si to náhodou nepamätali.)

Viacero ľudí v piatej úlohe tvrdilo, že ${\aleph_0}^{\aleph_0}=\aleph_0$, čo nie je pravda.

$\aleph_0^{\aleph_0}=\aleph_0\cdot \aleph_0 \cdot \aleph_0 \cdots$
Číslo $\aleph_0$ násobím sebou samým $\aleph_0$-krát a dostanem $\aleph_0$.

Toto nie je správny argument. Ak by som násobil iba konečneveľakrát $\aleph_0$, tak skutočne dostanem $\aleph_0$. Pre súčin nekonečne veľa kardinálnych čísel to už tak nefunguje.
Vieme dokázať, že $\aleph_0^{\aleph_0}=2^{\aleph_0}$. Tu napíšem aspoň nerovnosti $\aleph_0^{\aleph_0} \ge 2^{\aleph_0} > \aleph_0$, z ktorých by tiež malo byť vidieť, že $\aleph_0^{\aleph_0} \ne \aleph_0$.

[Martin Sleziak]

Skupina C$\newcommand{\inv}[1]{{#1}^{-1}}
\newcommand{\Invobr}[2]{\inv{#1}[#2]}
\newcommand{\Obr}[2]{{#1}[#2]}
\newcommand{\Zobr}[3]{{#1}\colon{#2}\to{#3}}
\newcommand{\mfr}[1]{\mathfrak{#1}}
\newcommand{\alnul}{\aleph_0}
\newcommand{\powerset}[1]{\mathcal P(#1)}$

• Zistite či výrok $(p \Rightarrow r \land q) \Leftrightarrow [(p \Rightarrow r) \land (p\Rightarrow q)]$ je tautológia.
• Nech $I\ne\emptyset$ a pre každé $i\in I$ je $A_i$ množina. Dokážte, že $B\subseteq\bigcap\limits_{i\in I} A_i$ platí práve vtedy, keď pre každé $i\in I$ platí $B\subseteq A_i$.
• Nech $\Zobr fXY$ je zobrazenie. Dokážte: $f$ je injektívne práve vtedy, keď pre ľubovoľné $A,B\subseteq X$ platí $$\Obr f{A\cap B}=\Obr fA \cap \Obr fB.$$
• Dokážte $2^{\mfr c}\cdot\mfr c^{\alnul} = \mfr c \cdot (\alnul)^{\mfr c}$.
• Vypočítajte kardinalitu množiny $\mathbb R^{\mathbb R\times\mathbb R}$.

Skupina D

• Zistite či výrok $(p \land q \Rightarrow r) \Leftrightarrow [(p \Rightarrow r) \lor (q\Rightarrow r)]$ je tautológia.
• Dokážte, alebo nájdite kontrapríklad: Pre ľubovoľné dve množiny $A$, $B$ platí
  $$\powerset{A\cap B} = \powerset{A} \cap \powerset{B}.$$
  (Pre množinu $S$ označujeme ako $\powerset{S}$ množinu všetkých podmnožín $S$; t.j. $\powerset S=\{X; X\subseteq S\}$.)
• Nech $\Zobr fXY$ je zobrazenie, $A,B\subseteq Y$. Dokážte, že $\Invobr f{A\cap B}=\Invobr fA \cap \Invobr fB$.
• Dokážte ${\mfr c}^{\mfr c}\cdot 2^{\alnul} = \mfr c \cdot 2^{\mfr c}$.
• Vypočítajte kardinalitu množiny $(\mathbb R\times\mathbb R)^{\mathbb R}$.

(Tretí a štvrtý príklad v skupine D sú rovnaké ako boli v skupine A - teda v jednej zo skupín na prvej písomke.)

[Martin Sleziak]

K tautológiám z druhej písomky som spravil samostatný topic: viewtopic.php?t=1098
Takisto k úlohe o preniku potenčných množín: viewtopic.php?t=1099
A tiež k úlohe o podmnožine prieniku systému množín: viewtopic.php?t=1100

[Martin Sleziak]

Úloha zo skupiny C pozostáva z dvoch častí.
Treba ukázať, že pre injektívne zobrazenie $f$ platí $f[A\cap B]=f[A]\cap f\left[B\right]$. Dôkaz môžete nájsť napríklad aj tu: viewtopic.php?t=94
Tiež ale treba ukázať opačnú implikáciu, t.j. ak táto rovnosť platí pre ľubovoľné dve podmnožiny definičného oboru, tak $f$ musí byť injektívne

Spoiler:

Azda najrýchejšie to ide takto: Nech $f$ nie je injektívne, teda existujú $x_{1,2}$ také, že $x_1\ne x_2$ a $f(x_1)=f(x_2)$.
Zoberme $A=\{x_1\}$ a $B=\{x_2\}$.
Potom $A\cap B=\emptyset$ a aj $f[A\cap B]=\emptyset$.
Súčasne $f[A]\cap f=\{f(x_1)\}=\{f(x_2)\}\ne\emptyset$.
Pre tieto množiny teda zadaná rovnosť neplatí.

Nikto nerobil obe implikácie.

[Martin Sleziak]

Niektorí z vás na viacerých miestach uvádzali výpočty, ako keby ste používali pravidlo, že:

• $a^b+a^c$ je to isté ako $a^{b+c}$;
• $a^b\cdot a^c$ je to isté ako $a^{bc}$.

Toto nie je pravda. (Ako sa ľahko presvedčíte už pri vyskúšaní konečných čísel.)
Dôkazy pravidiel pre počítanie s exponentami neboli jednoduché (ak ich chceme spraviť aj pre nekonečné kardinality). Ale pamätať a používať by ich malo byť ľahké, lebo vzorce pre $a^{b+c}$, $a^{bc}$, $(ab)^c$ sú presne rovnaké ako pri konečných číslach - a tie poznáte už zo strednej či základnej školy.}

Takisto ste niektorí využívali rovnosť $a^b$ a $2^{ab}$.
V skutočnosti sme dokázali iba to, že $a^b \le 2^{ab}$.
Rovnosť platiť nemusí. Dá sa nájsť veľa kontrapríkladov. Skúste napríklad $a=\aleph_0$ a $b=1$. Alebo ak chcete kontrapríklad s nekonečnými kardinálmi, tak trebárs $a=\mathfrak c$ a $b=\aleph_0$.