This week we will be finishing Chapter 2, so set your reading radars on that material. We will also begin our first attempts at writing and understanding proofs. To reinforce your understanding of all of these concepts — logical statements, open sentences, the “and” operator, the “or” operator, if-then statements (i.e. the symbol), universal quantifiers (), logically equivalent statements (i.e. ), the contrapositive of an implication, and basic strategies for proofs — please complete the following problems by Thursday, February 11th.
Problem 1. One can use Venn diagrams to sense why, given any two sets it follows that
This statement claims that two sets are equal, and so a proof for it requires two parts. First one must prove . Next, one must also prove . Consider the following proof of the first part.
Claim. If and are sets, then .
Proof: Suppose and are sets. To show that we will argue that every element must necessarily be an element .
To this end, let . This means that . In other words, is not an element that sets and have in common. Specifically, it might happen that , in which case ; on the other hand, it might happen that but . Or, indeed, it could happen that and . These are all of the options for our element , and by definition of union, they are all captured by the statement
which completes this proof.
For this question, attempt your own proof that demonstrates why the opposite set containment claim must also be true, thereby completing the proof of the set equality claim.
Problem 2. Attempt a proof of the following.
Claim: If is a set, then
(In other words, prove that the complement of a set’s complement is the original set again.)
Problem 3. Exercise 2 from 2.3 (pg. 42)
Problem 4. Exercises 3, 4 from 2.4 (pg. 44)
Problem 5. Exercises 3, 5, and 9 from 2.5 (pg. 46)
Problem 6. Exercises 2, 3, and 9 from 2.6 (pg. 49)
Problem 7. Exercises 1, 3 from 2.7 (pg. 51)
Problem 8. Exercises 2, 7, and 8 from 2.9 (pg. 55)
Problem 9. Exercises 6, 7, and 11 from 2.10 (pg. 59)
Problem 10. Be sure to read Definition 2.1 on page 53. This is where the book clarifies the meaning of “if , then ” where and can be statements or they can be open sentences. To make certain this idea makes sense, consider the two open sentences
: where and
First note that neither nor are statements. Instead, they are open sentences. Find values of the variables and that make true. Similarly, find values of and that make true.
According to Definition 2.1, is, in fact, a statement since it involves a quantifier. Write out this statement making this quantifier apparent, and then decide whether the resulting statement is true or false.