TCSS 321: Discrete Mathematics Assignment Solutions - Fall 2024

This document presents comprehensive solutions to a discrete mathematics assignment, addressing key concepts such as functions, bijections, and set cardinality. The assignment begins by defining a function and determining its domain, range, and invertibility. It then explores the concept of bijections using the golden ratio and Fibonacci numbers, proving or disproving whether a given function is bijective. The assignment delves into set cardinality, proving the equality of the cardinalities of rational numbers and integers. It also examines the relationship between the cardinalities of sets when one is a subset of the other, considering both surjective and injective functions. Finally, the assignment concludes with questions on relations, determining whether given relations are reflexive, symmetric, transitive, antisymmetric, and comparable. Each solution is thoroughly explained, providing a complete understanding of the underlying mathematical principles.

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\begin{document}
\title{\textbf{Solutions to Discrete Mathematics Assignment}}
\maketitle
\textbf{QUESTION ONE}\\
Given, $$f(x) = \frac {x+1}{x-1}$$
a.\\ (i) Domain of $f(x)$ is $\{x\in \mathbb{R} -\{1\}\}$. This is an implication that the function
is defined for all real numbers in exception of 1.\\
(ii) For range,\\
$$f(x)=\frac{2+(x-1)}{x-1}$$
$$ =\frac{2}{x-1} + 1$$
\hspace{30mm}$f(x)\ne1$ since $\frac{2}{x-1}\ne$ for $ x\in \mathbb{R}$\\
\hspace{10mm}The range of $\frac{2}{x-1}$ is $\{\mathbb{R} -\{0\}\} $\\
Thus Range of the function is $\{\mathbb{R} -\{1\}\} $\\
b. Proof of whether f(x) is invertible and calculation of its inverse\\
$$f^{-1} = \frac {x-1}{x+1}$$
such that $$f(x)*f^{-1}=1$$\\
$$f\circ f^{-1}(x)=f(\frac {x-1}{x+1})$$\\
$$=\frac {\frac {x-1}{x+1}+ 1}{\frac {x-1}{x+1}-1}$$
$$=\frac {\frac{x-1 + (x+1)}{x+1}}{\frac{x-1 - (x+1)}{x+1}}= -x$$
Thus $$f\circ f^{-1}(x)=-x$$
Proof that $$f\circ f^{-1}(x)=f^{-1} (\frac {x+1}{x-1})$$
$$=\frac {\frac {x+1}{x-1}- 1}{\frac {x+1}{x-1}+1}$$
$$=\frac {\frac{(x+1) - (x-1)}{x-1}}{\frac{(x+1) + (x-1)}{x-1}}= \frac {1}{x}$$
Thus $$f^{-1}\circ f(x)=\frac {1}{x}$$
\textbf{QUESTION TWO}\\
Using the concept of the golden ratio,$f(n)$ is the closed form solution of $n^{th}$ fibonacci
number. But, $n^{th}$ fibonacci number is given by:\\
$$F_n = \frac{\varphi^n-\psi^n}{\sqrt{5}}$$
where the golden ratio is $$\varphi=\frac{1+\sqrt{5}}{2}\approx 1.618$$
The domain of this problem is a natural number$\ge$ 2 with the co-domain being a set of
fibonacci numbers $\ge$ 2.\\
A bijective function is both injective and surjective i.e. $f: A\to B$. This implies that $\forall b$
in the co-domain B there is exactly one element a in the domain A such that $f(a)=b$ and vice-
versa.\\
Since $f(2)=1$, is missing in the co-domain of this example and that some elements in the co-
domain are also not fibonacci numbers, the function is not bijective.\\
\textbf{QUESTION THREE}\\

Let $\mathbb{Q}$ denote the set of rational numbers and $\mathbb{Z}$ the set of integers.
Because $\mathbb{N}$ is countable $\Rightarrow \mathbb{N}\times\mathbb{N}$ is also
countable.\\
\hspace{60mm} Defining $\mathbb{Q}= \mathbb{Q}+ \cup\{O\}\cup\mathbb{Q}$\\
$$f:\mathbb{Q}^{+}\to\mathbb{N}\times\mathbb{N}$$
$$f(p,q) = (p,q)\hspace{3mm} p,q\in v^{+}, (p,q)\in\mathbb{N}\times\mathbb{N}$$\\
$\Rightarrow$ f is one to one but not onto.\\
Since$ |\mathbb{Q}^{+}|\le|\mathbb{N}\times\mathbb{N}|$, $\mathbb{Q}^{+}$ is countable.
Similarly, $\mathbb{Q}^{-}$ is countable too.\\
Thus, $$|\mathbb{Q}|=|\mathbb{N}|$$ \hspace{90mm}...equation (i)\\
Now, $g:\mathbb{Z}\to\mathbb{N}$ defined by $g(n)=2n + 1$ if $n\in\mathbb{Z}^{+}$\\
$$g(+n)=-2n \hspace{3mm} if \hspace{1mm} n\in\mathbb{Z}^{-}$$\\
Because this is one to one and onto mapping, \\
$$|\mathbb{Z}|=|\mathbb{N}|$$ \hspace{90mm}...equation (ii)\\
Combining equations (i) and (ii),
$$|\mathbb{Q}|=|\mathbb{N}|=|\mathbb{Z}|$$
$$\Rightarrow |\mathbb{Q}|=|\mathbb{Z}|$$
\textbf{QUESTION FOUR}\\
Yes. We can infer that the cardinality of $|X|=|Y|$\\
Let,\\
X and Y be two infinite set in which X$\subseteq Y$\\
Also assume that$ f: X\to$ Y is a surjective function\\
Suppose $|X|\ne|Y|$,\\
$$As \hspace{2 mm}X\subset Y, |X|<|Y|$$\\
$\Rightarrow$ for the given function $ f: X\to Y,\exists y\in Y$ such that the function has no
pre-image in X\\
$\Rightarrow$ the given function, f is not a surjective map which contradicts $|X|<|Y|$\\
$$\therefore |X|\nless|Y|$$\hspace{90mm}...equation (i)\\
Also $$X\subseteq Y \Rightarrow |X|\le|Y|$$ \hspace{90mm}...equation (ii)\\
From (i) and (ii), $$|X|=|Y|$$
\textbf{QUESTION FIVE}\\
Given, $$Y\subset X$$\hspace{90mm}...equation 1\\
The function $ f: X\to$ Y is injective i.e. for every element in X, there is a unique element in Y \\
Therefore, $$X\subset Y$$\hspace{90mm}...equation 2\\
From (i) and (ii), $$|Y|=|X|$$\hspace{90mm}...hence proved\\
\textbf{QUESTION SIX}\\
Defining $\mathbb{R}^{+}=\{a\in\mathbb{R}:a>0\}$\\
Let, $$f:\mathbb{R}\to\mathbb{R}^{+}$$\\
$$f(x)=e^x$$
If $f(a) = f(b)$, then $e^a = e^b$ $\Rightarrow a=b$\\
$$\Rightarrow f\hspace{1mm} is \hspace{1mm}one-one$$
For any positive real number $y\in\mathbb{R}^{+}$\hspace{1mm}$\exists\hspace{1mm} \
ln(y)\in \mathbb{R}$ such that $e^{\ln(y)}= y$\\

$$\Rightarrow f \hspace{1mm}is\hspace{1mm} onto$$\\
Hence, $\exists$ a bijection between $\mathbb{R}$ and $\mathbb{R}^{+}$\\
$$\mathbb{R}\hspace{1mm}and\hspace{1mm}\mathbb{R}^{+} have\hspace{1mm}the\
hspace{1mm}same\hspace{1mm}cardinality$$\\
\textbf{QUESTION SEVEN}\\
Define the Relation R on $\mathbb{Z}$ by x R y iff $x-y=2$ for $x,y\in \mathbb{Z}$\\
(i) Not reflexive\\
For any $x\in \mathbb{Z}$, $x-x = 0$\\
Therefore, x is not R related to y\\
$$\therefore\hspace{1mm}R\hspace{1mm}is\hspace{1mm}not\hspace{1mm}Reflexive\
hspace{1mm}on\hspace{1mm}\mathbb{Z} $$
(ii) Not symmetric\\
For $x,y\in \mathbb{Z}$, suppose x R y
$$\Rightarrow x-y=2$$
But $$y-x=-(x-y)=-2$$
$$\therefore\hspace{1mm}y\hspace{1mm}is\hspace{1mm}not\hspace{1mm}R\
hspace{1mm}related\hspace{1mm}to\hspace{1mm}x $$
That is, x R y holds but y R x does not.\\
$$\therefore\hspace{1mm}R\hspace{1mm}is\hspace{1mm}symmetric\hspace{1mm}on\
hspace{1mm}\mathbb{Z} $$
(iii)Not transitive\\
Let $x,y,z\in \mathbb{Z}$ such that x R y and y R z,\\
$$\Rightarrow x-y=2\hspace{1mm}and\hspace{1mm} y-z = 2$$
but $$x-z=x+y-y-z= (x-y) + (y+z)$$
$$2+2=4$$
$$\therefore x-z = 4$$
$$\therefore x\hspace{1mm} is\hspace{1mm}not\hspace{1mm}R\hspace{1mm}related\
hspace{1mm}z$$
$$\therefore R\hspace{1mm} is\hspace{1mm}not\hspace{1mm}a\hspace{1mm}Transitive\
hspace{1mm}relation\hspace{1mm}to\hspace{1mm}z$$
\textbf{QUESTION EIGHT}\\
Let $S = \{\{1\}, \{1,2\},\{1,3\}\}$ be a set.\\
Define R on S by $A,B\in S.$\\
This implies that $(A,B)\in R$ $\Leftrightarrow$ $ A\subseteq B$\\
then\\
$R =\{(\{1\},\{1\}),(\{1,2\},\{1,2\}),(\{1,3\},\{1,3\}),(\{1\},\{1,2\}),(\{1\},\{1,3\})\}$\\
Here, R is Reflexive, Anti-Symmetric and transitive. So R is partially ordered Relation.\\
Also, for $A,B\in S$ ,we have either ARB or BRA. Therefore, R is totally ordered and hence a
totally ordered Relation.\\
\textbf{QUESTION NINE}\\
i. Reflexive: Yes\\
For (x,x), $$|x-x|=0<1, \hspace{1mm}thus\hspace{1mm} (x,y)\in\hspace{1mm}\mathbb{R}$$

ii. Symmetric: Yes\\
This is because $|x-y|=|y-x|$ so if $|x-y|<1$ then $|y-x|$ must also be $< 1$.\\
iii. Transitive: Yes\\
Considering three sets of transitive data $(2,6), (6,3), (2,3)$,\\
$$|2-6|=4\nless1, |6-3|=3\nless1, |2-3|=1\nless 1$$\\
iv. Antisymmetric: No\\
Because for for a given set of data i.e. $(x,y) = (5,2), (y,x)=(2,5)$,\\
$$|x-y|=|y-x|=3\nless1$$
v. Comparable: No\\
Since the value of $|x-y|$ when $x=y$ is $0$ which is a value $\nless 1$\\
\end{document}