## 187 – Midterm 2

March 24, 2010

Here is midterm 2.

Solutions follow.

## 187 – Extra credit problems

March 24, 2010

These questions are due Friday, April 9 at the beginning of lecture.

1. Let $f:{\mathbb N}\times{\mathbb N}\to{\mathbb N}$ be the function given by $\displaystyle f(x,y)=\frac{(x+y)(x+y+1)}2+y.$ Show that $f$ is a bijection.
2. Define $g:{\mathbb N}\to{\mathbb N}$ by setting $g(0)=0,$ $g(1)=1$ and, if $n>1,$ then, letting $p$ be the smallest prime such that $p|n,$ then $g(n)=2^p\times 3^{g(n/p)}.$ [Here, $n/p=n\mathrel{\rm div} p$.] Compute $g(n)$ for $n\le 15,$ and show that $g$ is one-to-one.

## 187 – Quiz 7

March 22, 2010

Here is quiz 7.

Solutions follow.

## 403/503 – Homework 5

March 15, 2010

This set is due Friday, March 26.

## 187 – Quizzes 5 and 6

March 14, 2010

Here is quiz 5 and here is quiz 6.

Problem 1 asks to show that the relation $R$ defined as follows is antisymmetric: Given a set $A,$ the relation $R$ is defined on the subsets of $A$ by setting $x\mathrel{R}y$ for $x,y\subseteq A,$ iff $y\setminus x=\emptyset,$ where $\setminus$ denotes set-theoretic difference of sets.

To show that $R$ is antisymmetric, we need to show that whenever $x,y\subseteq A$ are such that $x\mathrel{R}y$ and $y\mathrel{R}x,$ then $x=y.$ Suppose $x,y$ satisfy these assumptions. We need to show that they are equal as sets, i.e., that they have the same elements.

By definition, $x\mathrel{R}y$ holds iff $y\setminus x=\emptyset,$ and $y\mathrel{R}x$ holds iff $x\setminus y=\emptyset.$ Recall that if $B,C$ are sets, then $B\setminus C=\{a\in B\mid a\notin C\}.$ It follows that $y\setminus x=\emptyset$ iff every element of $y$ is also an element of $x,$ and that $x\setminus y=\emptyset$ iff every element of $x$ is also an element of $y.$ But these two facts together mean precisely that $x$ and $y$ have the same elements, i.e., that $x=y,$ as we needed to show.

Problem 2(a) of quiz 6 asks to consider the relation $R$ defined on ${\mathbb N}$ by setting $x\mathrel{R} y$ for $x,y\in{\mathbb N},$ iff $5|(2^x-2^y),$ and to show that $R$ is an equivalence relation. This means that $R$ is reflexive, symmetric, and transitive. Problem 2(a) of quiz 5 asks to show one of these properties.

To show that $R$ is reflexive, we need to show that for any $x\in{\mathbb N},$ we have that $x\mathrel{R}x,$ i.e., that $5|(2^x-2^x).$ But $2^x-2^x=0$ is certainly divisible by 5.

To show that $R$ is symmetric, we need to show that for any $x,y\in{\mathbb N},$ if it is the case that $x\mathrel{R}y,$ then it is also the case that $y\mathrel{R}x.$ Suppose then that $x\mathrel{R}y.$ This means that $5|(2^x-2^y),$ i.e., there is an integer $a$ such that $5a=2^x-2^y.$ But then $2^y-2^x=-5a=5(-a),$ showing that also $5|(2^y-2^x),$ i.e., $y\mathrel{R}x.$

To show that $R$ is transitive, we need to show that if $x,y,z\in{\mathbb N}$ and both $x\mathrel{R}y$ and $y\mathrel{R}z$ hold, then also $x\mathrel{R}z$ holds. But if $x\mathrel{R}y$ and $y\mathrel{R}z,$ then $5|(2^x-2^y)$ and $5|(2^y-2^z).$ But then it is certainly the case that $5|\bigl((2^x-2^y)+(2^y-2^z)\bigr).$ Since $(2^x-2^y)+(2^y-2^z)=2^x-2^z,$ this proves that, indeed $5|(2^x-2^z),$ or $x\mathrel{R}z,$ as we needed to show.

(If one feels the need to be somewhat more strict: That $5|(2^x-2^y)$ means that there is an integer $a$ such that $5a=2^x-2^y.$ Similarly, $5|(2^y-2^z)$ means that there is an integer $b$ such that $5b=2^y-2^z.$ But then $5(a+b)=5a+5b=(2^x-2^y)+(2^y-2^z)=2^x-2^z,$ showing that there is an integer $c$ such that $5c=2^x-2^z,$ namely, we can take $c=a+b.$)

Problem 2(b) asks to find all natural numbers $n$ such that $3\mathrel{R}n,$ where $R$ is as defined for problem 2(a).

That $3\mathrel{R}n$ means exactly the same that $5|(2^3-2^n).$ Since $2^3=8$ and an integer is a multiple of 5 iff it ends in 5 or 0, we need to find all natural numbers $n$ such that $2^n$ ends in $8$ or $3.$ Since $2^0=1$ and $2^m$ is even for all  naturals $m\ne 0,$ we actually need to find all natural numbers $n$ such that $2^n$ ends in 8. For this, we only need to examine the last digit of the numbers $2^1,2^2,2^3,2^4,2^5,\dots,$ and we find that these last digits form the sequence $2,4,8,6,2,4,8,6,2,4,8,6,\dots$ which is periodic, repeating itself each 4. This means that the numbers $n$ we are looking for are precisely $3,7,11,15,19,\dots,$ i.e., the natural numbers of the form $4k+3$ with $k\in{\mathbb N}.$

## 403/503 – Homework 4

March 5, 2010

This set is due Friday, March 12.

It is common in algebraic settings to build new structures by taking quotients of old ones. This occurs in topology (building quotient spaces), in abstract algebra when building field extensions, or in the homomorphism theorems. Here we explore quotients in vector spaces.

First we briefly consider an example from differential equations.

Let $V$ be the space $C^1({\mathbb R})$ consisting of all continuously differentiable functions $f:{\mathbb R}\to{\mathbb R}$ and let $W$ be the space $C({\mathbb R})$ of all continuous functions $g:{\mathbb R}\to{\mathbb R}.$ Let $T:V\to W$ be the linear transformation $Tf=f'-2f.$

Show that ${\rm null}(T)$ is a real vector space of dimension 1, by showing that $Tf=0$ iff $e^{-2x}f$ is a constant. This means, of course, that ${\rm null}(T)={\rm span}(e^{2x})=\{\alpha e^{2x}\mid \alpha\in{\mathbb R}\}.$

Show that $e^x\in{\rm ran}(T)$ by finding a particular solution $f_0$ to the equation $Tf=e^x.$ One way of doing this is by looking for such a function $f_0$ of the form $ae^x$ for some constant $a.$ Find the form of an arbitrary function $f$ such that $Tf=e^x$ by noting that if $Tf=Tf_0$ then $T(f-f_0)=0.$

More generally, show that $T$ is surjective, by finding for any $g\in C({\mathbb R})$ the explicit form of the solutions $f$ to the equation $Tf=g.$ It may help you solve this equation if you first multiply both sides by $e^{-2x}.$

For another example, denote by ${\mathbb R}^{3\times 3}$ the space of all $3\times 3$ matrices with real entries. Define a map $T:{\mathbb R}^{3\times 3}\to{\mathbb R}^3$ by $TA=A\begin{pmatrix}1\\1\\1\end{pmatrix}.$ Show explicitly that ${\rm null}(T)$ has dimension 6 and that $T$ is surjective.

Now we abstract certain features of these examples to a general setting:

Suppose ${\mathbb F}$ is a field and $T:V\to W$ is a linear transformation between two ${\mathbb F}$-vector spaces $V$ and $W.$ It is not necessary to assume that $V$ or $W$ are finite dimensional.

Let $w\in{\rm ran}(T),$ and let $v_0\in V$ be any preimage, i.e., $Tv_0=w.$ Show that the set $T^{-1}\{w\}$ of all preimages of $w$ is precisely $v_0+{\rm null}(T)=\{v_0+v\mid Tv=0\}.$

Define a relation $\sim$ in $V$ by setting $v_1\sim v_2$ iff $Tv_1=Tv_2.$ Show that $\sim$ is an equivalence relation. Denote by ${}[v]$ the equivalence class of the vector $v\in V.$

Let $U=V/\sim$ be the quotient of $V$ by $\sim,$ i.e., the collection of equivalence classes of the relation $\sim.$ We want to give $U$ the structure of an ${\mathbb F}$-vector space. In order to do this, we define ${}[v_1]+[v_2]=[v_1+v_2]$ and $a[v]=[av]$ for all $v_1,v_2,v\in V$ and $a\in{\mathbb F}.$ Show that this is well-defined and satisfies the axioms of an ${\mathbb F}$-vector space. What is the usual name we give to the 0 vector of this space?

It is standard to denote $V/\sim$ by $V/{\rm null}(T).$ Define two functions $\pi$ and $\phi$ as follows: $\pi:V\to V/{\rm null}(T)$ is given by $\pi(v)=[v].$ Also, $\phi:V/{\rm null}(T)\to W$ is given by $\phi([v])=Tv.$ Show that $\phi$ is well-defined and that both $\pi$ and $\phi$ are linear.

Show that $T=\phi\pi,$ that $\pi$ is a surjection, and that $\phi$ is an isomorphism between $V/{\rm null}(T)$ and ${\rm ran}(T).$ In particular, any surjective image of a vector space $V$ by a linear map can be identified with a quotient of $V.$