MA0301/exercise7/main.tex

\documentclass[12pt]{article}
\usepackage{ntnu}
\usepackage{ntnu-math}

\author{Øystein Tveit}
\title{MA0301 Exercise 7}

\usepackage{amsthm}
\usepackage{mathabx}

\begin{document}
  \ntnuTitle{}
  \break{}
  
  \begin{excs}

    \exc{}
    \begin{subexcs}
      \subexc{}

      By the definitions given in the exercise, we can define the PoS (partition of S) as

      \[ \forall y \in T \{ x \in S \mid f(x) = y\} \]

      In order for PoS to be a partition of a set, the following conditions have to hold: \\

      The PoS can not contain the empty set

      This holds because $f$ is a surjective function which by its definition $\forall y \in T \exists x \in S [f(x)=y]$ needs every $y$ in $T$ to have an $x$ in $S$. There are no $y$s without and $x$ and therefore no empty sets. \\

      The union of all the subsets in $S$ has to be equal to $S$

      This holds because $f$ is a function. Every $x$ of the domain needs to have a $y$ in the range, and because the union of the blocks of the PoS contains every $x$ for which there exists a $y$, that would mean it covers the whole domain. \\
      
      No pair of sets in the PoS contains any common elements

      This holds because $f$ is a function. No $f(x)$ can have multiple values, and therefore there will not be any $x$s in several blocks of the partition.

      \subexc{}

      If $f$ were to only be a function, the PoS would not fulfill the first condition in part a, and therefore it would not be a proper partition of a set.

      \subexc{}

      If $f$ was bijective, every block in the PoS would have a cardinality of $1$, meaning that every block would only contain one element of $S$


      \setsubexc{4}
      \subexc{}

      A block of $f^{-1}[\N]$ representing a natural number $n$ would be $\{x \mid n \leq x < n + 1\}$


    \end{subexcs}

    \exc{}

    \begin{figure}[H]
      \begin{mgraphbox}[width=5cm]
        \center
        \begin{tikzpicture}[scale=1]
          \tikzset{every node/.style={shape=circle,draw,inner sep=2pt}}

          \node (2) at (0,0) {$2$};
          \node (3) at (1,0) {$3$};
          \node (4) at (-1,1) {$4$};
          \node (16) at (0,2) {$16$};

          \draw (2) -- (4) -- (16);
        \end{tikzpicture}
      \end{mgraphbox}
      \caption{Hasse diagram of $R$ on $X$}
    \end{figure}

    \begin{center}
      Minimal elements $= \{3, 3\}$ \\
      Maximal elements $= \{3, 16\}$
    \end{center}

    \exc{}

    Reflexive:
    \[ (a,a), (b,b), (c,c), (d,d) \]

    Antisymmetric:
    There are no cases where $(x,y) \wedge (y,x)$

    Transitive:
    Because $(c,a) \wedge (a,d)$, $(c,d)$ is also included.

    \begin{figure}[H]
      \begin{mgraphbox}[width=5cm]
        \center
        \begin{tikzpicture}[scale=1]
          \tikzset{every node/.style={shape=circle,draw,inner sep=2pt}}

          \node (c) at (0,0) {$c$};
          \node (a) at (-1,1) {$a$};
          \node (b) at (1,1) {$b$};
          \node (d) at (0,2) {$d$};

          \draw (c) -- (a) -- (d);
          \draw (c) -- (b);
        \end{tikzpicture}
      \end{mgraphbox}
      \caption{Hasse diagram of $P$}
    \end{figure}

    \exc{}
    The function is injective, because it is a linear polynomial. However, it is not bijective, because all integers of the form $3x$ or $3x-1$ as the input of $f^{-1}$ does not result in an integer

    \exc{}

      In order for $f$ to be an injective function, it has to hold that $f(x) = f(y) => x = y$.

      Suppose $f(x) = f(y)$ for $x,y \in \Z$

      Case i) both are even

      \[ -2x=-2y => x = y \]

      Case ii) both are odd

      \[ 2x-1=2y-1 => x = y \]

      Therefore $f$ is injective\\

      In order for $f$ to be surjective, it has to hold that $\forall n \in \N \exists x \in \Z [f(x)=n]$

      Case i) $n$ is even

      The $x$ in this case has to be in the form of

      \[n = -2x \Leftrightarrow x = -\frac{n}{2}\]

      which would be an integer, because $n$ is even and therefore divisible by $2$

      Since $x \leq 0$

      \[ f(x) = f\left(\frac-{n}{2}\right) = -2\left(-\frac{n}{2}\right) = n\]

      Case ii) $n$ is odd
      
      The $x$ in this case has to be in the form of

      \[n = 2x-1 \Leftrightarrow x = -\frac{n+1}{2}\]

      which would be an integer, because $n$ is odd and therefore $n+1$ is divisible by $2$

      Since $x > 0$

      \[ f(x) = f\left(\frac{n+1}{2}\right) = 2\left(\frac{n+1}{2}\right) - 1 = n\]

      Therefore $f$ is surjective

      From here, I will create the inverse function piece by piece

      Piece 1) $x \leq 0$

      \begin{align*}
        y &= -2x \\
        -y &= 2x \\
        \frac{-y}{2} &= x \\
        x &= \frac{-y}{2} \\
      \end{align*}

      Piece 2) $x > 0$

      \begin{align*}
        y &= 2x - 1 \\
        y + 1 &= 2x \\
        \frac{y + 1}{2} &= x \\
        x &= \frac{y + 1}{2} \\
      \end{align*}

      hence

      \[ f^{-1} =
      \begin{cases}
        \frac{-y}{2}    & \text{for } n \leq 0 \\
        \frac{y + 1}{2} & \text{for } n > 0 \\
      \end{cases} \]

      

    \exc{}
    \begin{subexcs}

      \subexc{}

      Because $(f \circ g)$ is surjective, we know that 

      \[\forall c \in C \exists a \in A [(f \circ g)(a) = c]\]

      therefore

      \[\forall f(a) = b \in B [g(b) = c]\]

      therefore $g$ is surjective

      \subexc{}

      Because an injective function is one to one, we know that if their output is equal, their inputs must also be equal. Therefore

      \begin{align*}
        (f \circ g)(x) &= (f \circ g)(y) \\
        f(g(x)) &= f(g(y)) \\
        g(x) &= g(y) \\
        x &= y \\
      \end{align*}

      \[ ((f \circ g)(x) = (f \circ g)(y) \Leftrightarrow x = y) \Rightarrow (f\text{ is injective} \wedge g\text{ is injective} \Leftrightarrow f \circ g\text{ is injective})  \]

    \end{subexcs}

    \exc{}

    \begin{figure}[H]
      \begin{mgraphbox}[width=15.8cm]
        \center
        \begin{tikzpicture}[scale=2]

          % Domains
          \filldraw[fill=blue!20, draw=blue!60] (0,0) circle (1cm);
          \filldraw[fill=blue!20, draw=blue!60] (2.5,0) circle (1cm);
          \filldraw[fill=blue!20, draw=blue!60] (5,0) circle (1cm);

          % Ranges
          \filldraw[fill=red!20, draw=red!60] (0,0) circle (0.5cm);
          \filldraw[fill=red!20, draw=red!60] (2.5,0) circle (1cm);
          \filldraw[fill=red!20, draw=red!60] (5,0) circle (0.5cm);
    
          % Labels
          \node at (0,    1.2) {$A$};
          \node at (2.5,  1.2) {$B$};
          \node at (5,    1.2) {$C$};

          \node at (1.25, 0.8) {\tiny$f(a)$};
          \node at (3.75, 0.8) {\tiny$g(b)$ or $h(b)$};

          \node at (0, 0.7) {\tiny Preimage};
          \node at (0, 0) {\tiny Domain};
          \node at (2.5, 0) {\tiny Range of $f$};
    
          % Nodes for arrows
          \node (a1) at (0,   0.3) {};
          \node (b1) at (2.5, 0.3) {};
          \node (c1) at (5,   0.3) {};

          % Arrows
          \draw[->] (a1) to [out=30,in=150] (b1);
          \draw[->] (b1) to [out=30,in=150] (c1);

        \end{tikzpicture}
      \end{mgraphbox}
      \caption{Diagram of $g \circ f: A \to C$ in the case where $f$ is surjective}
    \end{figure}

    Because the range of $f$ covers the whole preimage of $g$ or $h$ when it is surjective, it means that if $g \circ f = h \circ f$ then $g = h$

    \begin{figure}[H]
      \begin{mgraphbox}[width=15.8cm]
        \center
        \begin{tikzpicture}[scale=2]

          % Domains
          \filldraw[fill=blue!20, draw=blue!60] (0,0) circle (1cm);
          \filldraw[fill=blue!20, draw=blue!60] (2.5,0) circle (1cm);
          \filldraw[fill=blue!20, draw=blue!60] (5,0) circle (1cm);

          % Ranges
          \filldraw[fill=red!20, draw=red!60] (0,0) circle (0.5cm);
          \filldraw[fill=red!20, draw=red!60] (2.5,0) circle (0.8cm);
          \filldraw[fill=red!20, draw=red!60] (5,0) circle (0.5cm);
    
          % Labels
          \node at (0,    1.2) {$A$};
          \node at (2.5,  1.2) {$B$};
          \node at (5,    1.2) {$C$};

          \node at (1.25, 0.8) {\tiny$f(a)$};
          \node at (3.75, 0.8) {\tiny$g(b)$ or $h(b)$};

          \node at (0, 0.7) {\tiny Preimage};
          \node at (0, 0) {\tiny Domain};
          \node at (2.5, 0) {\tiny Range of $f$};

          \node at (3.7, -1) {\tiny$g(b_1)$};
          \node at (3.7, -1.35) {\tiny$h(b_1)$};
    
          % Nodes for arrows
          \node (a1) at (0,   0.3) {};

          \node (b1) at (2.5, 0.3) {};
          \node (b2) at (2.5, -0.85) {};

          \node (c1) at (5,   0.3) {};
          \node (c2) at (5.7,   -0.5) {};
          \node (c3) at (4.5,   -0.6) {};

          % Arrows
          \draw[->] (a1) to [out=30,in=150] (b1);
          \draw[->] (b1) to [out=30,in=150] (c1);

          \draw[->] (b2) to [out=-30,in=-140] (c2);
          \draw[->] (b2) to [out=-30,in=-130] (c3);

        \end{tikzpicture}
      \end{mgraphbox}
      \caption{Diagram of $g \circ f: A \to C$ in the case where $f$ is not surjective}
    \end{figure}

    Because the range of $f(a)$ restricts the domain of $g(b)$ or $h(b)$, as long as they map to the same elements within their restricted domain, $g \circ f = h \circ f$. \\

    However, since $f(a)$ is not surjective, it doesn't imply that $g$ and $h$ can not differ outside of their domain. In order for $g \circ f = h \circ f$ to imply that $g = h$, $f$ has to be surjective. \\

    Therefore  \[ f(a)\text{ is surjective} \Leftrightarrow (g \circ f = h \circ f \Rightarrow g = h) \]

    \exc{}
    \begin{align*}
      f^{-1}(B_1 \cap B_2) &= \{a \mid a \in f^{-1}(B_1 \cap B_2)\} \\
                           &= \{a \mid f(a) \in B_1 \cap B_2\} \\
                           &= \{a \mid f(a) \in B_1 \wedge f(a) \in B_2\} \\
                           &= \{a \mid a \in f^{-1}(B_1) \wedge a \in f^{-1}(B_2)\} \\
                           &= \{a \mid a \in f^{-1}(B_1) \cap f^{-1}(B_2)\} \\
                           &= f^{-1}(B_1) \cap f^{-1}(B_2)
    \end{align*}

    \begin{align*}
      f^{-1}(\overline{B_1}) &= \{a \mid a \in f^{-1}(\overline{B_1})\} \\
                             &= \{a \mid f(a) \in \overline{B_1}\} \\
                             &= \{a \mid f(a) \notin B_1\} \\
                             &= \{a \mid a \notin f^{-1}(B_1)\} \\
                             &= \{a \mid a \in \overline{f^{-1}(B_1)}\} \\
                             &= \overline{f^{-1}(B_1)} \\
    \end{align*}

  \end{excs}


  
\end{document}