\documentclass[12pt]{article}
\pagestyle{empty} 
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{amssymb}
\topmargin=0pt
\textheight=9in
\oddsidemargin=0pt
\textwidth=6.5in



\begin{document}
Mathmatics 239 solutions to Homework for Chapter 2


\bigskip


Old version of 8.5 My compact disc player has space for 5 CDs; there are five trays numbered 1
through 5 into which I load the CDs. I own 100 CDs.


a) In how many ways can the CD player be loaded if all five trays are
filled with CDs?

Assume the trays are numbered this seems standard to me; if they're
not numbered, at least
I believe that the intent of the problem is that switching CDs in
adjacent trays would constitute a
different way to load from 1 to 5. So, suppose we load them in
numerical order. I have 100
choices for my first tray, then have used one up, so have 99 choices
for the second tray, 98 for the
third, 97 for the fourth, and 96 for the fifth. By the multiplication
principle, we then have
$100\cdot99\cdot98\cdot97\cdot96 = 9,034,502,400$ ways to load the player.

Note here: our author makes a comment about numerical answers that I
agree with.
Numerical answers that are uncomputed frequently give valuable
information. Numerical answers
that are computed less frequently give such information. Therefore, it
is regularly useful to not
compute out answers, and to leave them in factored form, e.g.
$100\cdot99\cdot98\cdot97\cdot96$ might be a better
answer than 9,034,502,400. Certainly this will be true on exams and
quizzes. Please keep this in
mind.

b) In how many ways can the CD player be loaded if only one CD is placed in the
machine?

Two perspectives on this question . . . using the multiplication
principle as follows: first
we choose which tray to place a CD in 5 choices, 1 through 5and
then we choose which CD to
place in the tray 100 choices. Therefore there are $5 \cdot100$ ways to load.

A different perspective which looks very similar, but might be
helpful. There are several
cases. We can either place a CD in the first tray, in which case there
are 100 choices, or the second
tray, where there are 100 choices, and so on. Because we have broken
down into cases, we add
these 100s, so $100 + 100 + 100 +100 +100$ ways to load. This
is using the addition
principle covered in section 10.

\bigskip

*NEW* 8.5  I want o create two play lists on my MP3 player from my collection of 500 songs.  One play list is titled ``Exercise" for listening in the gym, and the other is titled ``Relaxing" for leisure time at home.  I want 20 different songs on each of these lists.  

In how many ways can I load songs onto my MP3 player if I allow a song to be on both play lists?  We'll start with the first list, 500 choices for the first song, 499 for the second, down to 481 for the 20th.  Then continuing to build the second list, we again have 500 choices for the first song (because some songs are great for exercising and relaxing?) down to 481 for the 20th.  This produces $(500 \cdot 499 \cdot 498  \cdots 481)(500 \cdot 499 \cdot 498 \cdots 481)$.  Scheinerman calls this $(500)_{20}^2$, I would probably call it $\left(\frac{500!}{480!}\right)^2$.  Any of these answers are acceptable.  

And how many ways can I load the songs if I want the two lists to have no overlap?  Again, we'll start with the first list, 500 choices for the first song, 499 for the second, down to 481 for the 20th.  Then continuing to build the second list, we now have 480 choices for the first song (because we can't use the first twenty) down to 461 for the 20th.  This produces $(500 \cdot 499 \cdot 498  \cdots 481)(480 \cdot 479 \cdot 478 \cdots 461)$.  Scheinerman calls this $(500)_{40}$, I would probably call it $\frac{500!}{460!}$.  Any of these answers are acceptable.

\pagebreak

8.12 A U.S. Social Security Number is a nine-digit number. The first
digit or digits
may be 0.


a) How many Social Security numbers are available?

There are ten choices for each digit, 0,1,2,3,4,5,6,7,8,9, and because
there are nine digits
the multiplication principle gives $10^9$ numbers.


b) How many of these are even?

Base ten numbers are even exactly when they end in an even digits.
There are five even
digits, 0,2,4,6,8. Therefore, there are five choices for the last
digit, and still ten choices for the
other digits. Therefore there are $10^8\cdot 5$ even numbers.

c) How many have all their digits even?

If all the digits are even then we have five choices for each digit.
Therefore there are $5^9$ numbers with all digits even.

d) How many read the same backward and forward?

Imagine building a number that reads the same backward and forward called a
palindrome. In creating it, you are free to choose any digits for the
first half, but the second half
is determined. The middle digit is also free. Since there are nine
digits total, there are five we can
choose, and four that are determined by those choices. So we have
$10^5 1^4$ palindromes.

e) How many have none of their digits equal to 8?

Consider part a) again. In this case, however, we have one fewer
digit to choose from.
Therefore, we have nine digits to choose from in each place.
Therefore, there are $9^9$ numbers with no digits equal to 8.

f) How many have at least one digit equal to 8?

Consider the question rephrased as follows: How many do not have zero
8s?  We know
there are $10^9$ altogether, we know that $9^9$ have zero 8s. Therefore, it
must be that $10^9 - 9^9$ do not
have zero 8s, or with at
least one digit equal to 8.

g)How many have exactly one 8?

In creating a
number with exactly one 8, start by choosing a place to put 8. There
are 9 choices of places to put
8. Then, put the 8 there this involves no choice. Then fill out the
rest of the places. Each of the
other places will not have an 8, so they each have 9 choices of digits
to be placed. Therefore, we
have $9\cdot 9^8 = 9^9$ numbers with exactly one 8.
When working this the first time, I wondered why the answers to
e) and g) were the
same. This is a coincidence. Consider, for example, if social security
numbers had seven digits
as the hints used to seem to imply. Then the answer to e)would be $9^7$, and
the answer to g) would be
$7\cdot9^6$ seven choices of where to put 8, and 9 choices for the six other digits.

\bigskip

8.18. A class contains ten boys and ten girls. In how many different
ways can they stand
in line if they must alternate in gender (no two boys and no two girls
are standing next to one
another)?

It seems to me there are many different perspectives on this question.
This seems the most
efficient: First arrange the boys in your desired order there are 10!
ways, then arrange the girls in
your desired order there are 10! ways, finally decide whether to
start with boys or girls 2
choicesand weave the two arrangements together. Therefore there are
$10! 10! 2$ 
 ways they can stand in an alternating line. A
couple of other perspectives:
choose to start boy or girl, and then fill spaces with 10, 10, 9, 9,
8, 8, 7, 7, 6, 6, 5, 5, 4, 4, 3, 3,
2, 2, 1, 1 choices. A final idea would be you have a choice of 20 for
the first, but then ten for the
second and then 9, 9, 8, 8, 7, 7, 6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1
choices. All of these ideas are
fine. Be sure to attend to the details of starting with boy or girl
and how that affects the counting.

\bigskip

9.2 There are six different French books, eight different Russian
books, and five different
Spanish books.

a) In how many different ways can these books be placed on a bookshelf?
As this question does not concern language, the answer is
straightforward. There are 19
choices for first book, 18 for second, \&c. Therefore, we have 19!
ways.

b) In how many different ways can these books be placed on a
bookshelf if all books
in the same language are grouped together?

Start by asking how many ways can I order the three languages e.g.
first Russian, then
Spanish and finally French is one.There are three languages, so
there are 3! ways to order
the languages. Now, order the books within the languages, there are
6!, 8! and 5! ways to order
the books in each language. So altogether there are $3!6!8!5!$ ways to place the
books grouped by language note, far less than if they are ungrouped.

\bigskip


9.8. Calculate the following products:

(a) $\Pi_{k= 1}^4 (2k+ 1) = (2(1) + 1)(2(2)+1)(2(3)+1)(2(4)+1) = 3\cdot5\cdot7\cdot9=  945$

(b) $\Pi_{k=- 3}^4 k = -3\cdot-2\cdot-1\cdot0\cdot 1\cdot 2\cdot 3\cdot 4=0$


(c) $\Pi_{k= 1}^n \frac{k+1}{k}$, where $n$ is a positive integer.
We have $\Pi_{k= 1}^n \frac{k+1}{k} = \frac{2}{1} \frac{3}{2} \frac{4}{3} \cdots \frac{n-1}{n-2} \frac{n}{n-1} \frac{n+1}{n}$, performing the visible cancellations leaves $\frac{n+1}{1} = n+1$.

(d) $\Pi_{k=1}^n \frac{1}{k}$, where $n$ is a positive integer.

We have $\Pi_{k=1}^n \frac{1}{k} = \frac{1}{1} \frac{1}{2} \frac{1}{3} \frac{1}{4} \cdots \frac{1}{n-2} \frac{1}{n-1} \frac{1}{n} = \frac{1}{1\cdot 2\cdot 3 \cdot 4 \cdots (n-2)(n-1)n} = \frac{1}{n!}$. 

\bigskip

10.3 Find the cardinality of the following sets:



\bigskip

(a) $\{x \in \mathbb{Z} \mid |x| \leq10\}$

Here $x$ is a number, therefore $|x|$ means absolute value. This set can
be written out
explicitly as $\{-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4,
5, 6, 7, 8, 9, 10\}$. This set
has 21 elements, so its cardinality is 21.



\bigskip

(b) $\{x \in \mathbb{Z} \mid 1 \leq x^2 \leq 2\}$


$1^2 =  1$, $(-1)^2 =  1$. If $\mid x \mid \geq 2$, then $x^2 \geq 4$. If $x  = 0$, then $x^2 =  0$.
Therefore, the only
elements are 1 and -1. The set $\{1, -1\}$ has cardinality 2.



\bigskip

(c) $\{x \in \mathbb{Z} \mid  x \in \emptyset \}$
 
There are no elements of the empty set, therefore there is no number
such that it is in the
empty set. Therefore this set is itself $\emptyset$. (Alternatively, this set is
a subset of the empty set by
definition, but the only subset of the empty set is itself $\emptyset$). Because $| \emptyset| = 
0$, the cardinality here is
0. (Please remember for a set $|A|$ indicates the cardinality of A, or
the number of elements in $A$).

\pagebreak


\bigskip

(d) $\{x \in \mathbb{Z} \mid \emptyset \in  x\}$

Here $x$ is a number. The question asks ``how many integers have the
empty set as an
element?" Numbers do not have elements (at least the way we usually
think of them) sets do.
Therefore, no number contains the empty set as an element. Therefore,
this set is empty and has
cardinality 0.



\bigskip

(e) $\{x \in \mathbb{Z} \mid \emptyset \subset \{x\}\}$

$\{x\}$ is a set. The empty set is a subset of all sets. Therefore, for
all x,  $\emptyset \subset \{x\}$. How
many $x$s are there? How many integers are there? Infinitely many. So
the cardinality is infinite.



\bigskip

(f) $2^{2^{\{1, 2, 3\}}}$

This question and definitely the subsequent one are more difficult to
read than to answer.
The first question is how to associate the symbols. Does this mean
$2^{(2^{\{1, 2, 3\}})}$ or $(2^2)^{\{1, 2, 3\}}$?
Performing the first operation ($2^2$) in the second interpretation we
would then have $4^{\{1, 2, 3\}}$, which
is meaningless to us. Therefore, let us assume the first notation is intended.
What does $2^{(2^{\{1, 2, 3\}})}$ mean? The power set of the power set of $\{1, 2,
3\}$, or the set of all
subsets of the set of all subsets of $\{1, 2, 3\}$.
Lets start with $2^{\{1, 2, 3\}}$. The set of all subsets of $\{1, 2, 3\}$. This
is the set $\{\emptyset , \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$. Now, the
problem asks us to count the
set of all subsets of this set. We could start . . 

\begin{multline*}
\{\emptyset, \{\emptyset\} ,\{\{ 1\}\}, \{\{2\}\}, \{\{3\}\}, \{\{1, 2\}\}, \{\{1, 3\}\}, \{\{2, 3\}\}, \{\{1, 2, 3\}\}, \\
\{\emptyset, \{1\}\}, \{\emptyset, \{ 2\}\},\{\emptyset , \{3\}\}, \{\{1\}, \{2\}\}, \{\{1\}, \{3\}\}, \{\emptyset,\{1\}, \{2\}\}, \dots \}
\end{multline*}

But it quickly becomes apparent that there are a {\em lot} of elements in
this set. We need a better
way to count them. (Note: I wrote out this start of this set for two
reasons, first so that you would
see the futility of counting it, but also second so that you would
have an idea what set was being
counted in this problem.)
Remember we saw in class that $| 2^A | = 2^{| A|}$ which reads the
cardinality of the power set
of $A$ is the number 2 raised to the power of the cardinality of $A$.
Applying this where
$A = \{1, 2, 3\}$ gives $| 2^{\{1, 2, 3\}} | = 2^{|\{1, 2, 3\}|} = 2^3= 8$, which is
consistent with our first list,
which has eight elements (count them!).

But, now we can also apply this where $A = 2^{\{1, 2, 3\}}$. This gives
$| 2^{2^{\{1, 2, 3\}}}| = 2^{| 2^{\{1, 2, 3\}}|}=2^{(2^3)}=2^8= 256$. Certainly it is a good thing we didn't try
to list all the elements.




\pagebreak

(g) $\{x \in 2^{\{1, 2, 3, 4\}} \mid| x| =1\}$

This question is actually very easy after you translate all the
symbols. The difficult part
here is reading the mathematics, not answering the question.

Translation 1: What is the number of $x$ in the power set of $\{1, 2, 3,
4\}$ such that $| x| = 1$?

Remember the power set of a set is the set of all subsets of the set.

Translation 2: What is the number of $x$ that are subsets of $\{1, 2, 3,
4\}$ such that $| x| = 1$?

So, we now see that $x$ is a set not a number, therefore $| x |$ means the
number of elements
in $x$, not the absolute value of $x$.

Translation 3: What is the number of $x$ that are subsets of $\{1, 2, 3,
4\}$ with one element?


Let's eliminate $x$ from the question

Translation 4: How many subsets of $\{1, 2, 3, 4\}$ have one element?

Ok, now the question is finally easy. The sets $\{1\}, \{2\}, \{3\}, \{4\}$ are the only
one-element subsets of $\{1, 2, 3, 4\}$. There are four of them. Therefore
the answer is 4.
Sometimes the difficult part of mathematics is understanding the
language, not understanding the
actual concept. After unpacking all the mathematics, this turned
into an easy question. Keep this
principle in mind for future work.



\bigskip

(h) $\{\{1, 2\}, \{3, 4, 5\}\}$

This set has 2 elements (note: not 5 or 7; see (f) and the way we
counted $2^{\{1, 2, 3\}}$.





\bigskip



10.11 Generalize the previous problem.  Let $A = \{ x \in \mathbb{Z} \mid  a \mid x\}$ and $B = \{ x \in \mathbb{Z} \mid  b \mid x \}$. Find and prove a necessary and
sufficient condition for
$A \subset B$. In other words, find and prove a theorem of the form ``$A \subset B$ if
and only if \rule{1in}{.5pt}."

The key step in \#10 is underlined below:

if $x \in A$ then $4 \mid x$ then \underline{because $2 \mid 4$} then $2 \mid x$ then $x \in B$.

This might lead us to try $b \mid a$ as our
condition above. Before
attempting to prove this theorem, we should check it for some examples
of $b$ and $a$. We see that
$3 \mid 15$ and multiples of fifteen are a subset of the multiples of three. We
also see that $3 \nmid 14$ and
multiples of fourteen are not a subset of the multiples of three. It seems to check.

Now let us prove this theorem: $A \subset B$ if and only if $b\mid a$.

($\Rightarrow$) If $A \subset B$ then $b \mid a$.

Suppose that $A\subset B$. That is, if $x \in A$ then $x \in B$.
I assert that $a \in A$ (because $a$ is an integer and $a \mid a$ [see $a= a\cdot1$]).
Therefore, since $a \in A$,
we also have that $a \in B$. The definition of $B$ says that $a \in B$ implies
that $a$ is an integer (ok) and
$b \mid a$. However, $b \mid a$ is exactly what we were hoping to prove.

($\Leftarrow$) If $b \mid a$ then $A \subset B$.

Suppose that $b \mid a$.

(Hm, now I want to prove that $A \subset B$. That is I want to prove that if $x \in A$ then $x \in B$.
To do this, I will in effect be proving a theorem inside a theorem.
Overall, we have assumed that
 $b \mid a$. We will furthermore assume $x \in A$ to prove the subtheorem if $x \in
A$ then $x  \in B$. To
clarify, I will indent the entire proof of the subtheorem.)

\begin{quote}
Suppose that $x \in A$. Then $x$ is an integer and $a\mid x$.  We also know from the overriding assumption that $b \mid a$.  Using one of the very first things we proved (4.3) we thus have that $b \mid x$.  
We already know that $x$ is an integer (see first line of subtheorem),
therefore we
now have the requirements to see that $x \in B$.
\end{quote}

Therefore if $x \in A$ then $x \in B$ (because by assuming $x \in A$ we proved $x \in 
B$, or $A \subset B$,
as desired.

\bigskip

11.5. For each of the following sentences write the negation of the
sentence, but place
the symbol as far to the right as possible. Then rewrite the
negation in English.

\bigskip

(a) $\forall x \in \mathbb{Z}, x < 0$
\[\neg (\forall x \in \mathbb{Z}, x < 0) = \exists x \in \mathbb{Z} \mid  \neg (x < 0) = \exists x \in \mathbb{Z} \mid (x \geq 0)\]

``There is an integer that is not less than zero" or

``There is an integer greater than or equal to zero"

\bigskip

(b) $\exists x \in \mathbb{Z} \mid x =  x + 1$
\[\neg(\exists x \in \mathbb{Z} \mid x =  x + 1) = \forall x \in \mathbb{Z}, \neg (x = x + 1) = \forall x \in \mathbb{Z}, x \ne x +1\]

``Every integer does not have the property that it is equal to one
greater than itself."
or

``Every integer is not equal to one greater
than itself."



\bigskip

(c)	$\exists x \in \mathbb{N} \mid x > 10$
\[\neg(\exists x \in \mathbb{N} \mid x > 10) = \forall x \in \mathbb{N}, \neg(x > 10) = \forall x \in \mathbb{N}, x \leq10\]

``Every natural number is not greater than 10" or

``Every natural number is less than or equal to 10"


\bigskip

(d)	$\forall x \in \mathbb{N}, x +  x= 2x$
\[\neg(\forall x \in \mathbb{N}, x +  x= 2x) = \exists x \in \mathbb{N}\mid \neg(x +  x= 2x) = \exists x \in \mathbb{N}\mid x + x \ne2x\]

``There is a natural number that does not have the property that adding
it to itself is the same
as multiplying it by two." or

``There is a natural number such that adding it to itself is not the
same as multiplying it by
two."




\pagebreak

(e) $\exists x \in \mathbb{Z} \mid \forall y \in \mathbb{Z}, x > y$
\[\neg(\exists x \in \mathbb{Z} \mid \forall y \in \mathbb{Z}, x > y) = \forall x \in \mathbb{Z}, \exists y \in \mathbb{Z} \mid \neg(x > y) = \forall x \in \mathbb{Z}, \exists y \in \mathbb{Z} \mid x \leq y\]

``For every integer there is a second integer such that the first
integer is not greater than the
second integer." or

``For every integer there is a second integer such that the first
integer is less than or equal to
the second integer."


\bigskip

(f) $\forall x \in \mathbb{Z}, \forall y \in \mathbb{Z}, x  = y$
\[\neg(\forall x \in \mathbb{Z}, \forall y \in \mathbb{Z}, x  = y) = \exists x \in \mathbb{Z} \mid \exists y \in \mathbb{Z}\mid \neg(x = y) = \exists x \in \mathbb{Z} \mid \exists y \in \mathbb{Z}\mid x \ne y\]

``There exist two integers such that it is not the case that they are equal." or

``There exist two unequal integers."


\bigskip

(g) $\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z} \mid x+ y= 0$
\[\neg(\forall x \in \mathbb{Z}, \exists y \in \mathbb{Z} \mid x+ y= 0) = \exists x \in \mathbb{Z} \mid \forall y \in \mathbb{Z}, \neg(x+ y= 0) = \exists x \in \mathbb{Z} \mid \forall y \in \mathbb{Z}, x + y\ne 0\]

``There exists an integer such that any other integer will not have the
property that when
added to the first integer will give zero". or

``There exists an integer such that any other integer added to it will
not equal zero."

\bigskip


[extra 11.7] a. $\exists ! x \in \mathbb{N}, x^2=4$ is true, the unique natural number is 2. 

b. $\exists ! x \in \mathbb{Z}, x^2=4$ is false, there are two integers, 2 and $-2$.   

c. $\exists ! x \in \mathbb{N}, x^2 =3$ is false, there are no such natural numbers ($1^2<3<2^2$)

d.  $\exists !x \in \mathbb{Z}, \forall y \in \mathbb{Z}, xy=x$ is true, the unique integer is 0, i.e. $\forall y \in \mathbb{Z}, 0y=0$.

e. $\exists !x \in \mathbb{Z}, \forall y \in \mathbb{Z}, xy=y$ is true, the unique integer is 1, i.e. $\forall y \in \mathbb{Z}, 1y=y$.  

\bigskip

[extra] 11.8 a.  $\forall x \in R, \forall y \in R, \forall z \in L(x,y), z \in R$.  This is pretty much a literal symbolic interpretation of what is written.  For every two points (one at a time) in the region, every point on the line that connects them is again in the region.  

b. Remember to negate $\forall P$, we have $\exists \neg P$.  So, this is rather direct, too.  Aside from there being a good number of words in this problem, it's not that bad.  So, the negation here is $\exists x \in R | \exists y \in R | \exists z \in L(x,y), z \notin R$.  

c.  There are two points in the region such that the line segment joining them contains a point that is not in the region.  

d.  Drawing is not so easy for me here, but consider a region R that is U-shaped.  Consider two points, one on each side of the U, the line segment that connects them crosses over the middle of the U, and is therefore not in the U.  If you don't see this, please ask me, and I will happily show you.

\bigskip

12.18  Let $A$ and $B$ be sets.  We have $A \backslash B = B \backslash A$ if and only $A=B$.

Suppose $A=B$, $A \backslash B = A \backslash A$ by substitution $=\emptyset = B \backslash B = B \backslash A$ by substitution again.  Therefore $A \backslash B = B \backslash A$.  

Suppose $A \backslash B = B \backslash A$.  Consider an $x \in A \backslash B = B \backslash A$.  This would mean $x \in A, x \notin B, x \in B$, and $x \notin A$.  Because $x \in A$ and $x \notin A$ is impossible we have that $A \backslash B = B \backslash A = \emptyset$.  12.16 says $A \subset B$ iff $A \backslash B = \emptyset$.  If we use this we get both that $A \subset B$ and that $B \subset A$, which produces $A =B$ as desired.  

If you protest that we didn't do 12.16, here is the direction we need:  if $A \backslash B  = \emptyset$ then 
$A \subset B$.  To prove, suppose $x \in A$.  Is $x \in B$?  If it isn't, then it is in $A \backslash B$, but $A \backslash B$ is empty, so it must be that $x \in B$.  Technically this is a proof by contradiction.  

Here's a better argument:  
We wish to prove $A = B$, so we prove $A \subset B$ and $B \subset A$.  To prove $A \subset B$:

Suppose $x \in A$.  Therefore $x \notin B \backslash A$, but $B \backslash A = A \backslash B$.  So, $x \notin A \backslash B$.  We now have $x \in A$ and $x \notin A \backslash B$.  By definition of $A \backslash B$, the only way this happens is if $x \in B$.  This is what we wanted to show, so $A \subset B$.  The proof that $B \subset A$ is identical by switching letters.  Yes, this is a technical thing to say in a proof, but only when it is true.  Notice in this case, if I exchange $A$ and $B$ we get exactly the desired proof for $B \subset A$.  Don't use it carelessly, but it is a nice way to avoid being redundant.  

\bigskip

[extra] 12.20 a.  This is not true.  So, we need a counterexample.  Consider two disks that intersect in a point.  The disks are both convex, but the 
union is not.  This isn't entirely obvious to prove, so I'll prove a simpler example.  

Consider $A= \{(a,0)| a \in \mathbb{R}, -3<a<-1\}$ and $B= \{(b,0)| b \in \mathbb{R}, 1<a<3\}$ and $A \cup B$.  Both sets $A$ and $B$ are convex because the line segment joining any two points is still part of the $x$-axis which is what the two points are made of.  But, consider $(-2,0) \in A$ and $(2,0) \in B$.  Because they are each in one set, $(-2,0), (2,0) \in A \cup B$.   The line segment joining these two points contains the origin, $(0,0)$, which is not in $A$ and not in $B$, so not in $A \cup B$.   Therefore the union is not convex. 

b.  This is true.  So we need a general proof.  Suppose $A$ is convex and suppose $B$ is convex.  We wish to prove that $A \cap B$ is convex.  To prove this we must show something about any two points in $A \cap B$.  So, suppose $x, y \in A \cap B$.  In particular, because $A \cap B \subset A$, we have $x,y \in A$.  $A$ is convex, so for any point $z \in L(x,y)$, we have that $z \in A$.  The same can be said about $B$  (because $A \cap B \subset B$, we have $x,y \in B$.  $B$ is convex, so for any point $z \in L(x,y)$, we have that $z \in B$).  Therefore $z \in A \cap B$.   We have proven that for any two points $x,y \in A \cap B$, and for any $z \in L(x,y)$, $z \in A\cap B$.  Therefore by definition $A\cap B$ is convex, as desired.

\bigskip

12.21 True or False. For each of the following statements, determine
whether the
statement is true or false and the prove your assertion. 

\bigskip

(a) $A \backslash (B \backslash C) \ne (A \backslash B) \backslash C$

Consider $A=\{ 1, 2\}, B =\{1\}, C =\{1\}$. Compute:

$A \backslash (B \backslash C) = A \backslash \emptyset =  A  = \{1, 2\}$

$(A \backslash B) \backslash C = (\{2\}) \backslash \{1\} = \{2\}$


\bigskip

(b) $(A \backslash B) \backslash C = (A \backslash C) \backslash B$

{\em Proof}: Suppose that $x \in (A \backslash B) \backslash C$

Then $x \in (A \backslash B) \wedge x \notin C$.

Then $x \in A \wedge x  \notin B \wedge x \notin C$. Since $\wedge$ is associative and commutative
(5.2) we have

So, $(x \in A \wedge x \notin C) \wedge  x \notin B$. 

Hence $x \in (A \backslash C) \wedge x \notin B$.

So, $x \in (A \backslash C)\backslash B$.

Therefore $(A \backslash B) \backslash C \subset (A \backslash B) \backslash C$

The proof of the other implication is identical with $B$ and $C$ switched. Together
we get $(A \backslash B) \backslash C = 
(A \backslash C)\backslash B.$


\bigskip

(c) $(A \cup B) \backslash C \ne (A \backslash C) \cap (B \backslash C)$

Consider $A = \{1\}, B = \{2\}, C = \emptyset$. Compute:

$(A \cup B) \backslash C = \{1, 2\} \backslash \emptyset = \{1, 2\}$

$(A \backslash C) \cap (B \backslash C) = \{1\} \cap \{2\} = \emptyset$


\bigskip

(d) $B  \ne (B \backslash C) \cup C$

Let $B=\emptyset , C=\{2\}$. Compute:

$(B \backslash C) \cup C = \emptyset \cup \{2\} = \{2\} \ne \emptyset =  B$.



\bigskip

(e) $A \ne (A \cup C) \backslash C$

Let $A=\{1\}, C =\{1\}$. Compute:

$ (A \cup C) \backslash C =  \{1\}\backslash \{1\}= \emptyset \ne \{1\} = A$.



\bigskip

(f) $\mid A \backslash B\mid \ne \mid A\mid - \mid B\mid$

Let $A=\emptyset, B=\{2\}$. Compute:

$A \backslash B = \emptyset, \mid A \backslash B \mid = 0$.

$\mid A \mid = 0, \mid B \mid = 1, \mid A \mid - \mid B \mid = 0 -   1 = -  1\ne  0.$


\bigskip

(g) $(A \backslash B) \cup B \ne A$. See (d)

\bigskip

(h) $(A \cup  B) \backslash B \ne A$. See (e)

\bigskip


\bigskip



*Extra 12.22. Prove the following about set complements in a universe $U$.

\bigskip

(a) $A =  B$ if and only if $\overline{A} = \overline{B}$

($\Rightarrow$) Suppose that $A= B$.   

Very short version of the argument:  start with $\overline{A}$, substitute $B$ in for $A$, we then get $\overline{B}$, thus they are equal.  


Here's a longer version:  To show that $\overline{A} = \overline{B}$ we will first show that $\overline{A} \subset \overline{B}$.

 
Suppose that $x \in \overline{A}$ . Then $x \in U \backslash A$. Therefore $x \in U$ and $x \notin A$. Because $A= B$, if
$x \notin A$ then $x \notin B$. So, $x \in U$ and $x \notin B$. Therefore $x \in U \backslash B$, or $x \in \overline{B}$.
Therefore $\overline{A} \subset \overline{B}$. To
show $\overline{A} \supset \overline{B}$ interchange $A$ and $B$ in the previous argument.

($\Leftarrow$) 
Suppose that $\overline{A} = \overline{B}$. To show that $A= B$ we will first show that $A \subset B$.

Suppose that $x \in A$. Then $x \notin U \backslash A$ (because it is not the case that $x \notin 
A$). So, $x \notin \overline{A}$.
Because $\overline{A} = \overline{B}$, $x \notin \overline{B}$, or $x \notin U \backslash B$. This says it is not the case that
$x \in U$ and $x \notin B$. By
DeMorgans laws (5.2) we then have that either $x \notin U$ or $x \in B$. We know
from the beginning
that $x \in A$ which is a subset of $U$, therefore we know that $x \in U$. Since
the option $x \notin U$ is
therefore not possible, we must have that $x \in B$. Therefore $A \subset B$. To
show $A \supset B$ interchange
$A$ and $B$ in the argument.


\bigskip

(b) $\overline{\overline{A}} =  A$

Suppose that $x \in A$. If $y \in U \backslash A$ then $y \notin A$. Therefore $x \notin U \backslash A$, but $x \in U$ (because $x \in A \subset U$). Consequently $x \in U \backslash (U \backslash A) = U \backslash \overline{A} = \overline{\overline{A}}$. Therefore we
have shown that $A \subset \overline{\overline{A}}$.

Suppose that $x \in \overline{\overline{A}}$. Therefore $x \in U \backslash (U \backslash A)$. So, $x \in U$ and $x \notin U \backslash A$. $x \notin U \backslash A$
says that it is not the case that $x \in U$ and $x \notin A$. Applying
DeMorgans laws (5.2) again, this says that either $x \notin U$ or it is not the case that $x \notin A$. We know that
$x \in U$, so it must not be the
case that $x \notin A$. Once again, using a logic fact from 5.2, this gives
us that $x \in A$, as desired.
Therefore we have shown that $\overline{\overline{A}} \subset A$, and finally $\overline{\overline{A}} = A$.

\bigskip

(c) $\overline{(A\cup B\cup C)} =  \overline{A} \cap \overline{B} \cap \overline{C}$

{\em Proof}:
$\overline{(A\cup B\cup C)} =  U \backslash (A \cup B \cup C)$ which by DeMorgans laws 10.12

$ = (U \backslash A) \cap (U \backslash B) \cap (U \backslash C) = \overline{A} \cap \overline{B} \cap \overline{C}$

(This could be proven in a longer element method like (b), but this is
much nicer.)

\bigskip

*One more extra:   

Use the results in 11.17 to prove $\overline{A \cap (\overline{A} \cup B)} \cup B = U$

{\em Lemma 1}:  For any set $A \subset U$, $A \cup \overline{A} = U$.  

{\em Lemma 2}:  For any set $A \subset U$, $A \cap \overline{A} = \emptyset$.

{\em Lemma 3}:  For any sets $A, B \subset U$, $\overline{A \cap B} = \overline{A} \cup \overline{B}$.

Those are proven exactly as the other results in 11.17.  The first relies on the result from (6.2) of $x \vee (\neg x) =$ TRUE, and the second on $x \wedge (\neg x) =$ FALSE.  I will assume and freely use both of these results.  

(Note:  to read the following, the reasons are {\em before} the equal signs.)


Here we go:  $\overline{A \cap (\overline{A} \cup B)} \cup B$ by distributive properties 11.3

$ = \overline{(A \cap \overline{A}) \cup (A \cap B)} \cup B$ by Lemma 2

$ = \overline{\emptyset \cup (A \cap B)} \cup B$ by another part of 11.3

$ = \overline{A \cap B} \cup B$ by Lemma 3
 
$ = \overline{A} \cup \overline{B} \cup B$ by Lemma 1

$ = \overline{A} \cup U$ because $A \subset U$

$ = U$.
































\end{document}