Lecture Notes on Mathematical Induction:
click here
These notes are provided to you for your enlightenment and edification. In some
places they go further than what was presented in the lectures. You are not responsible
for any of this additional material. Moreover, the notes contain some "exercises", which
are not to be turned in, and some of them are quite challenging, but those of you
who are seeking deeper understanding of the material may enjoy thinking about them.
Lecture Notes on Relations and Functions:
click here
HOMEWORK
Assignment 1: Due in class, Wednesday, January 20
To solve: Chapter 1, exercises 1-35
To be turned in: Chapter 1, exercises 3, 6, 10, 11, 12, 19, 23, 26, 29, 30, 31
Optional Typed Problems:
OT1.1) Draw Venn diagrams for 4 and for 5 sets. (It is not possible to use circles. You might
think about trying to prove this if that sounds interesting to you.)
OT1.2) Believe it or not, there has been some recent work done on Venn diagrams with certain
nice properties. For instance, it is possible to make a very pretty Venn diagram for 5
sets using congruent ellipses. Research this on the internet and write a short essay
(approximately two pages) detailing some of the interesting results.
Assignment 2: Due in class, Monday, February 1
To solve: Exercises 1.46 - 1.56
To be turned in: Exercises 1.36, 1.42, 1.46, 1.53, 1.59, 1.66, 2.1, 2.4, 2.7, 2.14, 2.16, 2.23, 2.24, 2.29,
2.32
Typed Problems: Please do at least two of the following problems.
T2.1) Is there a partition of the empty set? (Comment: The definition in your text explicitly
excludes the empty set. I am asking you to nevertheless consider whether there exists a
family of sets satisfying the three properties of the partition of X when X is the empty set.)
T2.2) a) Let a,b,a',b' be objects. Show that { {a}, {a,b} } = { {a'}, {a',b'} }
if and only if a = a' and b = b'.
b) Explain why the result of part a) would allow us to define the ordered pair
(a,b) as { {a}, {a,b} }.
c) Do you have any reservations about this definition? (For example, is it the only possible
definition? Is it helpful to explicitly define ordered pairs in this way?) Discuss.
T2.3) a) Let X,Y,Z be sets. Prove that (X union Y) intersect Z = (X intersect Z) union (Y intersect Z).
b) Let P,Q,R be statements. Prove that (P or Q) and R = (P and R) or (Q and R).
c) Can you give an argument which proves both a) and b) at the same time?
T2.4) a) Show that there exists a binary logical operator, P*Q, such that not P, (P or Q) and
(P and Q), can all be constructed in terms of the operator *.
b) Of the 16 binary logical operators, how many have the property in part a)?
Assignment 3: Due in class, Monday, February 8
To solve: chapter 3, all exercises (but none of the additional exercises)
To be turned in: 3.4, 3.6, 3.10, 3.12, 3.14, 3.16, 3.18, 3.24, 3.26, 3.28, 3.30, 3.36, 3.40
Typed Problems:
T3.1) a) You are shown a selection of cards, each of which has a single
letter printed on one
side and a single number printed on the other side. Then four cards are
placed on the table.
On the up side of these cards you can see, respectively, D, K, 3 and 7.
Here is a rule: "Every card that has a D on one side has a 3 on the
other." Your task is to select all those cards,
but only those cards, which you would have to turn over in order to
discover whether or not the rule has been violated.
b) You have been hired to watch, via closed-circuit camera, the bouncer
at a certain 18-and-over club. In order to be allowed to drink once
inside the club, a patron must display valid 21-and-over ID to the
bouncer, who then gives him/her a special bracelet. In theory the
bouncer should check everyone's ID, but (assume for the purposes of this
problem, at least!) it is not illegal for someone who is under 18 to
enter the club, so you are not concerned about who the bouncer lets in
or turns away, but only who gets a bracelet. You watch four people walk
into the club, but because the bouncer is so large, sometimes he
obscures the camera. Here is what you can see:
The first person gets a bracelet.
The second person does not get a bracelet.
The third person displays ID indicating they are 21.
The fourth person does not display any ID.
You realize that you need to go down to the club to check some IDs. Precisely whose ID's do you need to check to verify
that the bouncer is obeying the law?
c) Any comments?
Assignment 4: Due in class, Wednesday, February 17
To solve: Chapter 4, all even exercises from Sections 4.1, 4.4 and 4.5
To be handed in: Problems 4.2, 4.4, 4.6, 4.9, 4.13, 4.40, 4.42, 4.44, 4.46,
4.50, 4.56, 4.58 (remember that the overline denotes complementation), 4.60
Typed problems:
T4.1) Write a one page essay describing your experience with the course
so far, especially any concerns or suggestions that you may have. For
instance, the pace of
the course, the difficulty of specific topics, and/or the amount of
homework are all good topics.
How would you feel about being asked to present solutions to problems on
the board during class time?
Assignment 5: Due in class, Monday February 29(!)
To solve: Chapter 5, all even exercises (none of the additional exercises).
To be handed in: Problems 4.14, 4.16, 4.18, 4.22, 4.24, 5.50, 7.4 [The statement
here is weird. What I think you should show is: two of the three statements are
equivalent to each other and imply the third. Moreover, one of these three conjectures
has recently been proven! For one point of extra credit, identify it and say who
proved it.], 8.44
Typed Problems: Please do the following problem.
T6.1: a) Write down the multiplication tables for congruence modulo 5 [recall we
did this in class], 6 and 7.
b) Use these tables to show: (i) if for integers x and y, if 5 | xy, then 5 | x or
5 | y and (ii) for integers x and y, if 7 | xy, then 7 | x or 7 | y.
c) Use these tables to show: if for an integer x, if 6 | x^2 then 6 | x.
d) Use the previous parts to show that √5,
√6
and √7
are all irrational.
Assignment 7: Due in class, Friday, March 18
To be handed in: Chapter 6, Exercises 6.1, 6.2, 6.4, 6.6, 6.8, 6.10, 6.12, 6.16,
6.18, 6.21, 6.24, 6.50
Typed problems: none due this week
Optional Typed Problems:
OT7.1: Let x,y,z be any integers such that x2 + y2 = z2. Show that 60 | xyz. Show also
that 60 cannot be replaced by any larger integer.
Assignment 8: Due in class Wednesday, March 30
To be handed in: Chapter 6, Exercises 6.42, 6.44b), 6.45 [for one point of extra
credit, give an application of this result to football], 6.54, 6.55
Typed problems: do one of the following:
T8.1) Recall that the Fibonacci numbers are defined as follows: F1 = 1,
F2 = 1, for all n >= 1, Fn+2 = Fn+1 + Fn.
a) Explain why there is a unique way of defining F_n for all integer values of n --
positive, negative and zero -- which satisfies the above constraints. (Hint:
We can rewrite the defining recurrence as Fn = Fn+2 - Fn+1.)
b) Compute Fn for n = 0,-1,-2,-3,-4,-5,-6,-7,-8.
c) For which values of n is Fn negative? Prove your answer.
T8.2) Show that a subset S of the real numbers is not well-ordered iff there is an
infinite sequence {x_n} (n = 1,2,3,...) of real numbers such that for all
n >= 1 we have x_n in S and x_{n+1} < x_n.
Assignment 9: Due in class, Monday, April 11
To solve: Chapter 8: Exercises 1,3,5,7,9,11,13,15,17
To be handed in: Chapter 8: 8.4, 8.8, 8.10 [Suggestion: you may as well take A = {1,2,3,4} and picture R as a subset of points
arranged in a 4 x 4 square. You are trying to find the largest size of a subset
which has no points in common with its reflection across the diagonal line y = x.], 8.12, 8.14, 8.18, 8.22, 8.26, 8.28, 8.30,
8.34, 8.36, 8.40, 8.42 [Suggestion: try it with real world equivalence relations, e.g.
"Live in the same city" and "Have the same hair color".]
What follows is the three in class midterms given in the Spring 2009
course and in the Fall 2009 course. In each case, solutions are given
for exactly one of the two midterms. The motivation
for this is that you should have some study materials with solutions and also
some study materials without solutions.
But wikipedia does not do justice to this unsolved problem in the psychology of logical reasoning. A
google search reveals a rich literature on the subject.