DG_reading_assignment_chapter_10.tex

\activitytitle{Reading assignment, Chapter 10}{Due in the eleventh week of class.}

Read and understand Chapter 10 of the textbook by Daepp and Gorkin, called ``Relations.''

The main definition for Chapter 10 appears at the end of Chapter 9, on page 93.  Here is the deal.  A {\em relation} $S$ from a set $X$ to a set $Y$ is a subset of $X \times Y$.  If $Y = X$, we say the relation is a relation on $X$.
At the beginning of Chapter 10, we see that we are going to be only working with relations on a set $X$.

Suppose that $S$ is a relation on a set $X$.
That is, suppose that $S$ is a subset of $X \times X$, which means that $S$ is a set of points of the form $(x,y)$, where $x \in X$ and $y \in X$.
Rather than write $(x,y) \in S$, we usually write $x \sim y$.
How to read this out loud?  There is no perfect solution.  I would suggest that you read it as ``$x$ tilde $y$'' (because $\sim$ is the tilde that appears above the n in some Spanish words).

Suppose that $X = \R$ and let $S = \{ (x,y) : x \leq y\}$.
Then $x \sim y$ means that $(x,y) \in S$, which means that $x \leq y$.
In this way, we see that $\leq$ is a relation on $\R$.
{\bf Write out the set $S$ corresponding to the relations $<$, $\leq$, =, $\geq$, and $>$.  Then also sketch these as regions in the $xy$ plane.}

Note that relations are between two elements.
Thus, ``divisible by 4'' is not a relation.
However, if $X = \Z^+$, you could say that $x \sim y$ if $y$ is divisible by $x$, and then you would have a relation.
People often write $x | y$ for this relation and say that $x$ divides $y$.
Call this relation $S$.
{\bf Write out at least ten of the ordered pairs in $S$, using at least five different values of $x$.}

Read Exercises 10.1 and 10.2.  

Read the definitions of reflexive, symmetric, and transitive.
A relation that satisfies all three is called an equivalence relation.
This is where most of the action is with relations.
{\bf Do Problem 10.2.}
{\bf \Large You should start every part of the problem by writing down examples.}
For example, for (a), the example $3 < 3$ will tell you whether the relation is reflexive, $3 < 5$ and $5 < 3$ will tell you about symmetry, and $3 < 5, 5 < 7$, and $3 < 7$ will get you started on transitivity.

Read Example 10.3, then {\bf do Problem 10.3.}
Use examples to check reflexivity, symmetry, and transitivity.

Equivalence relations are very important, as are equivalence classes.
An equivalence relation is like the equality relation (=), but applied to other contexts.
Here is an example that is useful.
Think of the integers, $\Z$.
Say that $x \sim y$ if $x$ and $y$ have the same remainder when you divide by 2.
Then $6 \sim 22$ and $31 \sim 7$.
This relation is reflexive, because $x \sim x$.
It is symmetric because if $x \sim y$ then $y \sim x$.
And it is transitive because if $x \sim y$ and $y \sim z$, then $x \sim z$.
Now we can say that 6 is equivalent to 22, and 31 is equivalent to 7, according to this definition of equivalence.
The equivalence class that contains 6 and 22 is all even numbers, and the equivalence class containing 31 and 7 is all odd numbers.
Let this sink into your mind, and you will start to see that it makes for a useful way to organize things, when an equivalence relation is available.

{\bf Do Problem 10.1}  Start by writing out examples for the pairs $(x,y)$ and $(w,z)$.  Think about lines and circles in the plane.

{\tiny 
\blist{0.0in}
\item Read somewhere quiet, minimizing distractions from phones and friends
\item Note the time that you start and stop reading, and add up the minutes
\item Read with a pencil in your hand and your notebook open in front of you
\item Write a sentence to summarize each paragraph, re-draw diagrams, work out examples and exercises on your own
\item Look up words you don't know, and write down ones you really don't know
\item Read slowly. 
\item Tally up how much time you have spent on reading this chapter.
\elist
}
\vfill          % pad the rest of the page with white space