Worksheet 2

Please work on the following problems. The (*) problems are optional, and should be done last.

1. Let $A$ denote the set of all points in ${\mathbb{R}}^2$ except $(0,0)$. Consider the following relation: $(a_1,b_1)\equiv (a_2,b_2)$ if there is some real number $\lambda\neq 0$ such that $a_2=\lambda a_1$ and $b_2=\lambda b_1$.
   1. Show that $\equiv$ is an equivalence relation on $A$. We have to prove that $\equiv$ is reflexive, symmetric and transitive.
      1. Reflexive: Since $a=(1)a$ and $b=(1)b$, we have that $(a,b)\equiv (a,b)$. Here, we've verified the definition of the relation defining $\equiv$ with $\lambda = 1$.
      2. Symmetric: Suppose that $(a,b)\equiv (c,d)$. Then, there exists a real number $\lambda$ with $c=\lambda a$ and $d=\lambda d$. Dividing through by $\lambda$, we have $a=(1/\lambda) c$ and $d=(1/\lambda) b$. Therefore, $(c,d)\equiv (a,b)$.
      3. Transitive: Suppose that $(a,b)\equiv (c,d)$ and that $(c,d)\equiv (f,g)$. Then there exist real numbers $\lambda$ and $\mu$ with $c=\lambda a$ and $d=\lambda b$, $f=\mu c$ and $g=\mu d$. Then, putting these together, we have $f=\mu \lambda a$ and $g = \mu \lambda b$. Therefore, $(a,b)\equiv (f,g)$.
   2. Draw a picture of the equivalence class of a point $(a,b)$ in A. The equivalence class of the point $(a,b)$ is the line through the origin and $(a,b)$ in ${\mathbb{R}}^2$, minus the origin.
   3. Let $P^1({\mathbb{R}})$ denote the quotient set $A_{\equiv}$. Find a bijection from $P^1({\mathbb{R}})$ to the set of all lines through $(0,0)$ in ${\mathbb{R}}^2$. Make sure you can show that your map is well defined, injective and surjective. Define a map by
      
      $$\Phi:[(a,b)]\mapsto (b/a)x$$
      
      
      1. $\Phi$ is well-defined: suppose that $[(a,b)]=[(c,d)]$. We proved in class that this happens iff $(a,b)\equiv (c,d)$. Then there's a real number $\lambda$ with $c=\lambda a$ and $d=\lambda b$. The line $(b/a)x$ is the same as the line $(d/c)x = (\lambda b/\lambda a)x$.
      2. $\Phi$ is onto: any line through the origin is of the form $y=mx$. The equivalence class $[(1,m)]$ has $\Phi([(1,m)])= \{y=mx\}$.
      3. $\Phi$ is 1-1: suppose that $y=(b/a)x$ is the same line as $y=(d/c)x$. Then they must have the same slope, so $b/a=d/c$. But this only happens if $d=kb$ and $c=ka$ for some number $k$. Thus, $[(a,b)]=[(c,d)]$. So $\Phi$ is 1-1.
   4. (*) Show that the map
      
      $${\mathbb{R}}\to P^1({\mathbb{R}})$$
      
      
      
      
      $$r\mapsto [(r,1)]$$
      
      
      is injective. Show that the complement of the image of this function consists only of the equivalence class $[(1,0)]$. To show that the map is injective, suppose that $[(r,1)]=[(q,1)]$. Then there's a number $k$ with $q=kr$ and $1=k(1)$. The second equation tells us that $k=1$. Therefore, $q=kr=(1)r$ so $q=r$. Thus, the map is injective. Suppose that $[(a,b)]$ is any equivalence class with $b\neq 0$. Then $[(a,b)]=[(a/b), 1)]$ since $(a,b)\equiv (a/b, 1)$ using $\lambda = 1/b$. This means that EVERY equivalence class $[(a,b)]$ with $b\neq 0$ is in the image of this map. However, there is no value of $a$ or $\lambda$ making $[(r,1)]=[(a,0)]$ (why?). Since $[(a,0)]=[(1,0)]$, this equivalence class is in the complement of the image.
   The set $P^1({\mathbb{R}})$ is called the projective line (over ${\mathbb{R}}$).
2. Suppose that the set $L_n$ is a collection of $n$ lines in the plane for which no two lines are parallel, and no three lines are concurrent (that is, no three lines meet in one point). Let $a_n$ be the number of regions into which the plane is divided by the lines in $L_n$.
   1. Show that $a_{n+1}=a_n+n+1$.
   2. Find $a_n$ by induction.

      This is very similar to a problem on the homework. I will post the solution to this problem (as well as the homework problem) on Friday. For now, I will only say that it is ok to give a good DESCRIPTION of why $a_{n+1}=a_n+n+1$ as opposed to a very rigorous PROOF.

      Apologies to those of you who have been waiting just for this problem - I forgot that it was on the homework when I said that I would post it.

3. Let $S$ be a finite set and let $Map(S,S)$ be the set of maps from $S$ to itself. Define a binary operation on $Map(S,S)$ by
   
   $$Map(S,S)\times Map(S,S)\to Map(S,S)$$
   
   
   
   
   $$(f,g)\mapsto g\circ f$$
   
   
   That is, the binary operation $\circ$ is composition of maps.
   1. Is $\circ$ associative? Explain or show a counterexample.

      Yes, $\circ$ is associative, since when composing maps there is a unique choice of order. That is, $(h\circ (g\circ f))(s)= h(g(f(s)))=((h\circ g)\circ f) (s)$.

   2. Is $\circ$ commutative? Explain or show a counterexample.

      No, $\circ$ is not commutative. Let $S$ be the set $\{ 1, 2, 3 \}$. Let $f$ be the map defined by $f(1)=2$, $f(2)=3$ and $f(3)=1$. Let $g$ be the map defined by $g(1)=1$, $g(2)=1$ and $g(3)=2$. Then $f\circ g$ is the map with $f(g(1))=2$, $f(g(2))=2$ and $f(g(3))=3$. On the other hand, $g\circ f$ is the map with $g(f(1))=1$, $g(f(2))=2$ and $g(f(3))=1$. These are not equal, so $\circ$ is not commutative. There are many many other examples.

   3. Does $\circ$ have an identity? Explain or show a counterexample. Yes, $\circ$ has an identity. It is the map $1_S$ which is defined by the property that for any $s\in S$, $1_S(s)=s$. If $f$ is any map from $S$ to $S$, then for any element $s\in S$, $(1_S\circ f)(s)=1_S(f(s))=f(s)$. So $1_S\circ f=f$. On the other hand, $(f\circ 1_S)(s)=f(1_S(s))=f(s)$, and $f\circ 1_S=f$. This shows that $1_S$ is the identity.

      In a set $X$ with binary operation $*$ and identity $e$, an element $x\in X$ is said to have an inverse if there is an element $y\in X$ such that $x*y=e=y*x$.

   4. Which elements of $Map(S,S)$ have inverses?

      The bijective maps have inverses.