\documentclass{article}
\usepackage{graphicx} 
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{hyperref}
\usepackage{tikz}
\usetikzlibrary{trees}

\begin{document} 

\title{COT 3100C Homework \#10} 
\author{Jason Yau} 

\maketitle 
\pagebreak 

\section{Question 1}
Let $R_1$ and $R_2$ be relations on a set A = \{1, 2, 3, 4\}.
\\In particular, let $R_1$ = \{(1, 3), (2, 2), (2, 4), (3, 1), (4, 2)\} and
\\$R_2$ = \{(1, 1), (1, 3), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4)\}.
\\
\\Determine the following:
\\
\\a.) Whether or not R1 is reflexive, irreflexive, symmetric, anti-symmetric and transitive or not.
\\
\\ 1. $R_1$ is not reflexive because it does not contain (1,1).
\\ 2. $R_1$ is not irreflexive because it contains (2,2).
\\ 3. $R_1$ is symmetric because for each pair in the form of (a,b), there is a (b,a).
\\ 4. $R_1$ is not anti-symmetric because there is a (1,3) and a (3,1).
\\ 5. $R_1$ is not transitive because there is a (1,3) and (3,1) but does not contain (1,1).
\\
\\b.) Whether or not R2 is reflexive, irreflexive, symmetric, anti-symmetric and transitive or not.
\\
\\ 1. $R_2$ is reflexive because it contains (1,1), (2,2), (3,3), (4,4).
\\ 2. $R_2$ is not irreflexive because it contains (1,1).
\\ 3. $R_2$ is not symmetric because it contains (1,3) but not (3,1).
\\ 4. $R_2$ is not anti-symmetric because it contains (1,1).
\\ 5. $R_2$ is transitive because for all pairs (a,b) and (b,c), there exists (a,c).
\\
\\ c.) The relation $R_1$ $^{\circ}$ $R_2$
\\
\\ = \{(1,3),(1,4),(2,2),(2,3),(2,4),(3,1),(3,3),(4,2),(4,3)\}
\\
\\ d.) The relation $R_2$ $^{\circ}$ $R_1$
\\
\\ = \{(1,1),(1,3),(2,1),(2,2),(2,4),(3,1),(3,2),(4,2)\}
\\
\\ e.) $R_1 \cup R_2$
\\
\\ = \{(1,1),(1,3),(2,2),(2,3),(2,4),(3,1),(3,3),(3,4),(4,2),(4,4)\}
\\
\\ f.) $R_1 \cap R_2$
\\
\\ = \{(1,3),(2,2)\}
\\
\\
\\ continued on page 3...
\pagebreak
\\ g.) The reflexive, symmetric and transitive closures of both $R_1$ and $R_2$
\\
\\ $r(R_1) = $ \{(1,1),(1, 3), (2, 2), (2, 4), (3, 1), (3,3), (4, 2), (4,4)\}
\\ $s(R_1) = $ \{(1, 3), (2, 2), (2, 4), (3, 1), (4, 2)\}
\\ $t(R_1) = $\{(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)\}
\\
\\ $r(R_2) = $ \{(1,1),(1,3),(2,2),(2,3),(3,3),(3,4),(4,4)\}
\\ $s(R_2) = $ \{(1,1),(1,3),(2,2),(2,3),(3,1),(3,2),(3,3),(3,4),(4,3),(4,4)\}
\\ $t(R_2) = $\{(1,1),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)\}
\section{Question 2} 
Let R be a relation over the positive integers defined as follows:
\\
\\R = ${(a,b) \mid \text{a, 2a and b form side lengths of a triangle with positive area} }$
\\
\\Determine whether or not R satisfies the following properties. Give a brief justification for each
of your answers.
\\
\\(i) reflexive
\\(ii) irreflexive
\\(iii) symmetric
\\(iv) anti-symmetric
\\(v) transitive 
\\
\\ Since in a triangle with a positive area, the sum of any two sides must be greater than the third side, we can rewrite R to be:
$$\text{R} = \{(a,b) \mid a+b > 2a \land a +2a > b\}$$
\\ Note that the largest side length of the triangle cannot be a, only 2a or b.
\\ Let's simplify the expressions:
$$\text{R} = \{(a,b) \mid b > a \land 3a > b\}$$
\\ Now we can test the given properties:
\\ 
\subsection{Part i}
R is not reflexive because (1,1) cannot be in R. a = 1, b = 1:
$$ 1 \ngtr 1$$
\\
\\continued on page 4...
\subsection{Part ii}
R is irreflexive because for all (a,a), where a = a, b = a:
$$a \ngtr a$$
\subsection{Part iii}
R is not symmetric because (1,2) is in R, where a = 1, b = 2:
$$ 2 > 1 \land 3(1) > 2$$
However (2,1) is not in R, where a = 2, b = 1:
$$1 \ngtr 2$$
\subsection{Part iv}
R is anti-symmetric because it is not possible for there to co-exist (a,b) and (b,a) as it is not possible for $(b > a) \land (a > b)$. Thus, there is a contradiction for all positive integers a, b.
\subsection{Part v}
R is not transitive because (1,2) is in R, proved previously.
\\ (2,3) is in R, where a = 2, b = 3:
$$3 > 2 \land 3(2) > 3$$
\\ However, it is not possible for (1,3) to exist in R, where a = 1, b = 3:
$$3(1) \ngtr 3$$
\section{Question 3}
How many anti-symmetric relations on the set A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} contain
the ordered pairs (1, 1), (3, 3), (4, 4), (5, 8), and (9, 1)?
\\
\\ By definition of anti-symmetric, if (a,b) in R and (b,a) in R, then a = b.
\\ Thus, we can choose to include the 7 pairs in the form (a,a): (2,2),(5,5),(6,6),(7,7),(8,8),(9,9),(10,10), or $2^7$ choices to include/not include the aforementioned pairs.
\\
\\
\\ continued on page 5...
\pagebreak
\\ The relations cannot have two ordered pairs in the form (a,b) and (b,a), where a $\neq$ b. There are 
\\ $${10 \choose 2} = 45$$
such pairs. Since the relation must be anti-symmetric and we are forced to include (5,8) and (9,1), we cannot include (8,5) and (1, 9). For each pair, it can be in the form \{\}, \{(a,b)\}, or \{(b,a)\}. This gives us:
$$ 3^{45-2} = 3^{43}$$
combinations of ordered pairs. Thus, the final answer is:
$$2^7\cdot 3^{43} \text{ relations.}$$
\section {Question 4}
Let $P(x) = x^5 + ax^4 + bx^3 + cx^2 + dx + e$. $P(4) = P(5) = P(6) = P(7) = P(8) = 0$. What is
the value of $a - b + c - d + e$?
\\
$$(x-4)(x-5)(x-6)(x-7)(x-8)=0\text{, using the given roots.}$$
$$P(-1)=(-1-4)(-1-5)(-1-6)(-1-7)(-1-8)=-15120$$
$$=(-1)^5+a(-1)^4+b(-1)^3+c(-1)^2+d(-1)+e$$
$$=-1+a-b+c-d+e$$
Thus, a - b + c - d + e = $\text{-}$15119.
\section{Question 5}
Let f(x) = $x^2 + 8x - 9$ with a domain of all real $x \in [-\infty, -4]$. Prove that f is injective. What is the range of f?
\\
\\ We must prove that for all $f(a) \neq f(b)$, unless a = b.
\\
\\Let's take the derivative of the given function:
\\
$$f'(x) = \frac{d}{dx}[x^2+8x-9]$$
$$ = 2x+8$$
\\
\\continued on page 6...
\pagebreak
\\Now let's solve for f'(x) = 0:
$$2x+8=0$$
$$2x=-8$$
$$x=-4$$
\\ Thus, there is only one critical point at x=-4. Since the domain is $x \in [-\infty,-4]$, we only need to test $x < -4$.
$$f'(-5) = 2(-5)+8 = -18$$
\\ Thus, f(x) is decreasing for all $x < -4$.
\\
\\ Since f(x) is decreasing for all $x < -4$, it follows that $f(b) \neq f(a)$ unless a = b, proving that f is injective. Since f(x) is decreasing for all $x < -4$, the upper range must be $\infty$. The minimum must be at $x = -4$:
$$f(-4)=(-4)^2+8(-4)-9=-25$$
Thus, the range of f is $[-25, \infty]$.
\section{Question 6}
Find $f^{-1}(x)$ for the function given in question \#5.
$$f(x)=y=x^2+8x-9$$
\\
$$x=y^2+8y-9$$
$$x+9=y^2+8y$$
$$x+9=(y+4)^2-16$$
$$y+4=\pm\sqrt{x+25}$$
$$f^{-1}(x) = y=\pm\sqrt{x+25}-4$$
\pagebreak
\section{Question 7}
 Let $f(x) = ax^3 + bx^2 + cx + d$ and f(-1) = -6, f(0) = 4 and f(1) = 12.
 \\
\\(1) What is the value of d?
\\(2) What is the value of b?
\\(3) What is the value of a+c?
\\(4) Prove that the value of a is not uniquely determined by finding two sets
of ordered quadruplets $(a_1, b_1, c_1, d_1)$ and $(a_2, b_2, c_2, d_2)$ with $a_1$ $\neq$ $a_2$ that is consistent
with all of the given information above.
\\
\\ Let's first generate the following equations:
$$f(-1) = -6 = a(-1)^3+b(-1)^2+c(-1)+d$$
$$= -a+b-c+d$$
$$f(0) = 0+0+0+d = d = 4$$
$$f(1) = 12 = a(1)^3+b(1)^2+c(1)+d$$
$$= a+b+c+d$$
\subsection{Part 1}
$$d=4$$
\subsection{Part 2}
$$f(1)+f(-1)=12-6=6=a+b+c+d-a+b-c+d$$
$$= 2b+2d=2b+8$$
$$b=\frac{-6-8}{2}=-1$$
\subsection{Part 3}
$$f(1) = 12 = a-1+c+4$$
$$a+c = 12+1-4 = 9$$
\subsection{Part 4}
For example, a = 5, c = 4 would satisfy the given conditions:
$$f(-1)=-a+b-c+d=-5-1-4+4=-6$$
$$f(0) = 4$$
$$f(1)=a+b+c+d=5-1+4+4=12$$
\\
\\continued on page 8...
\pagebreak
\\ Now, let a = 4, c = 5.
$$f(-1)=-a+b-c+d=-4-1-5+4=-6$$
$$f(0) = 4$$
$$f(1)=a+b+c+d=4-1+5+4=12$$
\\We have found a counter-example. Thus, the given statement must be false.
\\ This is because solving for b and d are independent of of a and c. To solve for d, we plugged in 0 for x to ``cancel'' out a, b, c to get d = 4. To solve for b, we added f(-1)+f(1) which ``canceled'' out a and c and then we plugged in 4 for d.
\section{Question 8} 
Please give a summary of the life and mathematical contributions of Srinivasa Ramanujan.
\\ 
\\ Srinivasa Ramanujan was an Indian mathematician who lived from December 1887 to April 1920. He did very little formal training and education in pure mathematicians, however, he made major contribution to mathematics after many other mathematicians took notice in his work. His contribution was in topics such as mathematical analysis, number theory, infinite series, and continued fractions, solving many problems once thought to be unsolvable. He tried showing professional mathematicians his work, and in 1913, his work was recognized by G.H. Hardy (who created the Hardy Weinberg principle for genetics) at the University of Cambridge, who realized his work was extraordinary, who arranged for him to travel to Cambridge. Hardy was amazed by his work, notably in infinite series, continued fractions, etc. He went to Cambridge in 1914, and worked with Hardy and John Littlewood at Cambridge for the next 5 years, making more mathematical breakthroughs. His health worsened and he died in 1920. In his short life, he made many important mathematical discoveries. He wrote many new and unconventional identities and equations, such as the Ramanuanprime, Ramanujan theta function, partition formulae, the taxicab number and mock thetha functions. His work has been extremely influential; much of his work has opened up new research and almost all of his work has since been proved as true. 
\\
\\Sources:
\\1. \url{https://en.wikipedia.org/wiki/Srinivasa_Ramanujan}
\end{document}