2015-solutions1.tex

\documentclass[a4paper]{article}

\setlength{\marginparsep}{0.5cm}
\setlength{\oddsidemargin}{0.3cm}
\setlength{\hoffset}{0cm}
\setlength{\marginparwidth}{110pt}
\let\oldmarginpar\marginpar

\renewcommand\marginpar[1]{\-\oldmarginpar[\raggedleft\scriptsize #1]%
{\raggedright\scriptsize #1}}

\usepackage[bulgarian]{babel}
\usepackage[utf8]{inputenc}

\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{latexsym}
\usepackage{enumerate}
\usepackage{datetime}
%this package allows for hyperlinks within the pdf document
\usepackage[colorlinks=true, linkcolor=blue,pdfstartview=FitV,
citecolor=green, urlcolor=blue]{hyperref}

\theoremstyle{definition}
\newtheorem{problem}{Зад.}
\renewenvironment{proof}{\noindent{\bf Доказателство.}\hspace*{1em}}{\qed\par}
\newcommand{\A}{\mathfrak{A}}
\newcommand{\B}{\mathfrak{B}}
\renewcommand{\C}{\mathfrak{C}}
\newcommand{\D}{\mathfrak{D}}

\newcommand{\As}{\mathscr{A}}
\newcommand{\Bs}{\mathscr{B}}
\newcommand{\Cs}{\mathscr{C}}
\newcommand{\Ds}{\mathscr{D}}
\newcommand{\Es}{\mathscr{E}}
\newcommand{\Fs}{\mathscr{F}}
\newcommand{\Gs}{\mathscr{G}}
\newcommand{\Hs}{\mathscr{H}}
\newcommand{\Is}{\mathscr{I}}
\newcommand{\Js}{\mathscr{J}}
\newcommand{\Ks}{\mathscr{K}}
\newcommand{\Ls}{\mathscr{L}}
\newcommand{\Ms}{\mathscr{M}}
\newcommand{\Ns}{\mathscr{N}}
\newcommand{\Os}{\mathscr{O}}
\newcommand{\Ps}{\mathscr{P}}
\newcommand{\Qs}{\mathscr{Q}}
\newcommand{\Rs}{\mathscr{R}}
\newcommand{\Ss}{\mathscr{S}}
\newcommand{\Ts}{\mathscr{T}}
\newcommand{\Us}{\mathscr{U}}
\newcommand{\Vs}{\mathscr{V}}
\newcommand{\Ws}{\mathscr{W}}
\newcommand{\Xs}{\mathscr{X}}
\newcommand{\Ys}{\mathscr{Y}}
\newcommand{\Zs}{\mathscr{Z}}
\newcommand{\xn}{x_{1},\dots,x_{n}}

\newcommand{\xs}{\overline{x}}
\newcommand{\ys}{\overline{y}}
\newcommand{\zs}{\overline{z}}
\newcommand{\forces}{\Vdash}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\pair}[1]{\langle{#1}\rangle}
\newcommand{\abs}[1]{\vert{#1}\vert}
\begin{document}
\title{Частично решение на задачите от първото контролно (спец. ИС, гр. 1) от 20.11.2015 г.}
\date{}
\maketitle

\begin{problem}
  \begin{enumerate}[a)]
  \item 
    Вярно ли е, че $A \subseteq B \iff A\cup B = B$ ?
  \item
    Вярно ли е, че $A \subseteq B \iff A\setminus B = \emptyset$?
  \item
    За $A = \{\emptyset,\{1\},1\}$ намерете степенното множество $\Ps(A)$.
  \end{enumerate}
\end{problem}
\begin{proof}
  \begin{itemize}
  \item
    Нека $A \subseteq B$. Ще докажем, че $A \cup B = B$.
    Ясно е, че $B \subseteq A \cup B$. Остава да докажем, че $B \subseteq A\cup B$.
    За целта, нека $x \in A \cup B$. 
    \begin{itemize}
    \item 
      Ако $x \in A$, то $x \in B$, понеже $A \subseteq B$.
    \item
      Ако $x \in B$, то е очевидно, че $x \in B$.
    \end{itemize}
    Обединявайки тези два случая, получваме, че ако $x \in A \cup B$, то $x \in B$.
    
    Нека сега $A \cup B = B$. Ще докажем, че $A \subseteq B$.
    Нека $x \in A$. Следователно $x \in A \cup B$. Оттук $x \in B$, понеже $A\cup B = B$.
    Заключаваме, че $(\forall  x)[x \in A \rightarrow x \in B]$. Следователно, $A \subseteq B$.
  \item
    Задачата следва от следните еквивалентни преобразувания:
    \begin{align*}
      A \subseteq B & \iff (\forall x)[x\in A \rightarrow x \in B]\\
      & \iff (\forall x)[x\not\in A \vee x\in B]\\
      & \iff (\forall x)[\neg(x\in A\ \wedge\ x\not\in B)]\\
      & \iff \neg (\exists x)[x\in A\ \wedge\ x\not\in B]\\
      & \iff \neg (\exists x)[x\in A\setminus B]\\
      & \iff A \setminus B = \emptyset.
    \end{align*}

  \item 
    \marginpar{Обърнете внимание, че ако $A$ има $n$ елемента, то $\Ps(A)$ има $2^n$ елемента}
    $\Ps(\{\emptyset,\{1\},1\}) = \{\emptyset,\{\emptyset\}, \{\{1\}\},\{1\},\{\emptyset,\{1\}\},\{\emptyset,1\},\{1,\{1\}\},\{\emptyset,\{1\},1\}\}$
  \end{itemize}
\end{proof}

\begin{problem}
  \marginpar{Възможно ли е да са частични функции?}
  Да разгледаме функциите $f:A\to B$ и $g:B\to A$.
  \begin{enumerate}[a)]
  \item 
    Ако $f$ е сюрективна и $g\circ f = id_A$, то докажете, че $g = f^{-1}$.
  \item
    Ако $f$ е инективна и $f\circ g = id_B$, то докажете, че $g = f^{-1}$.
  \end{enumerate}
\end{problem}
\begin{proof}
  \begin{enumerate}[a)]
  \item 
    \marginpar{Да напомним, че $id_A(a) =a$ за всяко $a\in A$}
    Възможно ли е $g$ да не е тотална функция, т.е. да съществува $b\in B$, 
    за което $g(b)$ не е дефинирана ?
    Да допуснем, че съществува такова $b$. 
    Понеже $f$ е сюрективна, съществува поне едно $a \in A$, за което $f(a) = b$.
    Това означава, че $(g\circ f)(a)$ не е дефинирана. Това е противоречие с условието, че $g\circ f = id_A$.
    
    Сега ще проверим, че $f$ е инективна. От това ще следва, че $f^{-1}$ е функция.
    \marginpar{$f$ е инектвина, ако $f(a) = f(a')\rightarrow a = a'$}
    Нека да разгледаме $a, a' \in A$,  за които $f(a) = b = f(a')$. Ще докажем, че $a = a'$.
    Щом $g\circ f = id_A$, то $g(f(a)) = g(b) = a$  и $g(f(a'))= g(b) = a'$.
    Ясно е, че $a = a'$, защото $g$ е функция.

    % Вече знаем, че $f$ е биективна и следователно $f^{-1}$ е биективна функция. 
    Понеже $g$ е тотална, за да докажем, че $g = f^{-1}$, то е достатъчно е да покажем, че $g \subseteq f^{-1}$, т.е.
    \[(\forall a\in A)(\forall b\in B)[g(b) = a \implies f(a) = b].\]
    Нека $g(b) = a$ и $f(a') = b$. Знаем, че такова $a'$ съществува, защото $f$ е сюрективна.
    Но тогава $(g\circ f)(a') = a$ и следователно $a = a'$, защото $g\circ f = id_A$.
  \item    
    \marginpar{Да напомним, че $id_B(b)=b$ за всяко $b\in B$}
    Отново, възможно ли е $g$ да не е тотална функция, т.е. да съществува $b\in B$, за което $g(b)$ не е дефинирана?
    Но тогава е ясно, че $(f\circ g)(b)$ също няма да е дефинирана, което е противоречие с условието, че $f\circ g = id_B$.
    \marginpar{Добре е да отбележим, че понеже $f$ е инективна ние знаем, че $f^{-1}$ е функция.}
    Щом $g$ е тотална, за да докажем, че $g = f^{-1}$ е достатъчно да проверим, че $g\subseteq f^{-1}$, т.е.
    \[(\forall a\in A)(\forall b\in B)[g(b) = a \implies f(a) = b].\]
    \marginpar{Вярно ли е, че $f$ е сюрктивна?}
    Това е лесно да се провери. Нека $g(b) = a$. Понеже $(f\circ g)(b) = b$, то $f(g(b)) = f(a) = b$.
  \end{enumerate}
\end{proof}

\begin{problem}
  За произволна функция $f:A\to A$ и за произволно множество $X \subseteq A$, 
  винаги ли е вярно, че :
  \begin{enumerate}[a)]
  \item 
    $f(f^{-1}(X)) = X$?
  \item
    $f^{-1}(f(X)) = X$?
  \end{enumerate}
  Обосновете се!
\end{problem}
\begin{proof}
  Лесно се вижда, че двете твърдения не винаги са верни.
  Например, нека $f:\mathbb{Z} \to \mathbb{Z}$ е дефинирана като $f(x) = |x|$.
  Тогава:
  \begin{enumerate}[a)]
  \item 
    За $X = \{-1,0,1\}$, $f^{-1}(X) = \{x\in\mathbb{Z} \mid |x| \in X\} = X$.
    $f(f^{-1}(X)) = f(X) = \{|x| \mid x\in X\} = \{0,1\} \neq X$.
  \item
    За $X = \{0,1\}$, $f(X) = X$, но $f^{-1}(f(X)) = f^{-1}(X) = \{-1,0,1\} \neq X$.
  \end{enumerate}
\end{proof}



\end{document}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: