%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%% file:      s4.tex                                                        %%%
%%% author:    Tatiana Jajcayová, Ján Komara                                 %%%
%%% email:     Jan.Komara@fmph.uniba.sk                                      %%%
%%% copyright: public domain                                                 %%%
%%% version:   2017/11/29                                                    %%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt,a4paper]{article}

\usepackage[slovak]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{amsmath}
\usepackage{amssymb}

\usepackage{lmodern}
\usepackage{indentfirst}

\renewcommand{\labelenumi}{{\normalfont (\alph{enumi})}}
\renewcommand{\labelenumii}{{\normalfont (\roman{enumii})}}

\newcommand{\nR}{\ensuremath{\mathcal R}}
\newcommand{\nL}{\ensuremath{\mathcal L}}
\newcommand{\aP}[1]{\ensuremath{{\mathcal P}(#1)}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{4. domáca úloha z predmetu \\ 1-AIN-160 Matematika (3) ZS 2017/18}

\author{Tatiana Jajcayová \and Ján Komara}

%\date{}
\date{\today}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{1. príklad}

\begin{enumerate}
\item
Koľko existuje rozličných relácií na $3$-prvkovej množine?
\item 
Koľko existuje relácií čiastočného usporiadania na $3$-prvkovej množine?
\item  
Koľko existuje relácií čiastočného usporiadania na $3$-prvkovej množine bez
najmenšieho prvku?
\item 
Koľko existuje lineárnych usporiadaní na $3$-prvkovej množine?
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 1. príkladu}

Táto časť obsahuje riešenie 1. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{2. príklad}

Nech $A = \{1,2,3,4,5,6,7\}$ a nech \nR\ je relácia "byť podmnožinou"
$\subseteq_A$  definovaná na potenčnej množine \aP{A}. Podľa predchádzajúcej
domácej úlohy vieme, že táto relácia je čiastočné usporiadanie na \aP{A}.

Nech $M = \{\{1\},\{2\},\{2,3\}\}$.
Nájdite:
\begin{enumerate}
\item 
Počet horných ohraničení $M$, ktoré obsahujú
\begin{enumerate}
\item 
štyri prvky.
\item 
päť prvkov.
\end{enumerate}
\item 
Počet všetkých horných ohraničení $M$ a  počet všetkých dolných ohraničení $M$.
\item 
$\sup(M)$ a $\inf(M)$.
\item 
Pripomeňme:
\begin{quote}
\emph{Definícia.}
Čiastočne usporiadaná množina $(A, \nR)$ sa nazýva zväz, ak  $\sup(\{x,y\})$ aj
$\inf(\{x,y\})$ existujú v $A$ pre každé $x,y \in A$.
\end{quote}
Je $(\aP{A}, \subseteq_A)$ zväz? (Svoju odpoveď zdôvodnite.)
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 2. príkladu}

Táto časť obsahuje riešenie 2. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{3. príklad}

Profesor Grimaldi sa chystá na svoju prezentáciu na seminári z Diskrétnej
matematiky. Ráno sa oblieka a množina $O$ obsahuje kusy šatstva, ktoré si dá na
seba, aby pri prezentácii vyzeral slušne.
\begin{align*}
O = 
\{&
\text{opasok}, 
\text{sako}, 
\text{nohavice}, 
\text{košeľa}, 
\text{topánky}, 
\text{ponožky}, 
\text{spodky}, 
\text{tielko},
\\ &
\text{hodinky}, 
\text{kravata}
\}
.
\end{align*}
Na množine $O$ definujme reláciu čiastočného usporiadania \nR\ nasledovne:
\begin{quote}
$o_1 \nR o_2$, ak oblečenie $o_1$ si musí  profesor obliecť predtým ako si
oblečie oblečenie $o_2$.
\end{quote}
Napríklad, dvojica 
\(
(\text{košeľa}, \text{kravata}) \in \nR
\), 
lebo kravatu si nemôže uviazať bez toho aby mal na sebe košeľu, ale dvojice
\(
(\text{košeľa}, \text{ponožky}) \notin \nR
\), 
ani 
\(
(\text{ponožky}, \text{košeľa}) \notin \nR
\),
lebo oblečenie košele a ponožiek je nezávislé a môže to urobiť v akomkoľvek
poradí.
\begin{enumerate}
\item 
Nakreslite Hasseho diagram čiastočne usporiadanej množiny $(O, \nR)$.
\item 
$(O, \nR)$ nie je lineárne usporiadaná. Prečo?
\item 
Nájdite dve rôzne lineárne usporiadania $\nL_1$ a $\nL_2$ množiny $O$, ktoré
rešpektujú čiastočné usporiadanie $\nR$ (t.j. $ \nR \subseteq \nL_i$ ) a v
ktorých si profesor Grimaldi nasadí hodinky ako posledné.
\item 
Koľko je všetkých možných lineárnych usporiadaní \nL\ množiny $O$, ktoré
rešpektujú čiastočné usporiadanie $\nR$  a v ktorých si profesor Grimaldi
oblečie ako prvé spodky a nasadí hodinky ako posledné.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 3. príkladu}

Táto časť obsahuje riešenie 3. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{4. príklad}

Dokážte, že 
\begin{enumerate}
\item 
množina všetkých (konečných) slov nad konečnou abecedou je spočítateľná množina.
\item 
množina všetkých nekonečných reťazcov nad konečnou abecedou je nespočítateľná
množina.
\item 
systém všetkých konečných podmnožín množiny prirodzených čísel je spočítateľná
množina.
\item 
systém všetkých podmnožín množiny celých čísel je nespočítateľná množina.
\item 
množina všetkých zobrazení z množiny celých čísel do množiny celých čísel je
nespočítateľná množina.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 4. príkladu}

Táto časť obsahuje riešenie 4. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{5. príklad}

Nech $S$ je množina, ktorá obsahuje $0$ a všetky kladné celé čísla, ktoré sa
dajú vytvoriť ako súčty čísel $7$ a $11$.
\begin{quote}
Tak napríklad okrem $0,7$ a $11$, aj $14 \in S$, $18 \in S$,  $21 \in S$ a $22
\in S$. $S$ je samozrejme nekonečná množina.
\end{quote}
Na tejto množine $S$ definujme reláciu $\leq_S$ nasledovne:
\begin{quote}
Pre $x,y \in S$, $x \leq_S y$, ak $y-x \in S$.
\end{quote}
\begin{enumerate}
\item 
Ukážte, že takto definovaná relácia $\leq_S$ je čiastočné usporiadanie na $S$.
\item 
Načrtnite ``kúsok''  Hasseho diagramu pre $(S,\leq_S)$.
\item 
Je toto čiastočné usporiadanie lineárne? (Svoju odpoveď - ako ostatne máte robiť
vždy - zdôvodnite.)
\item 
Nech $M = \{21,25,29\}$. Nájdite $\sup(M)$ a $\inf(M)$, ak existujú.
\item 
Je $(S,\leq_S)$ zväz?
\item 
Dokážte, že množina $S$ je spočítateľná množina.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Riešenie 5. príkladu}

Táto časť obsahuje riešenie 5. príkladu.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
