343 lines
10 KiB
TeX
343 lines
10 KiB
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}
|