FOM Assignment 3

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 \Rightarrow symbol), universal quantifiers (\forall, \exists), logically equivalent statements (i.e. \iff), 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 A, B it follows that

\overline{A \cap B} = \overline{A} \cup \overline{B}.

This statement claims that two sets are equal, and so a proof for it requires two parts.  First one must prove \overline{A\cap B} \subseteq \overline{A} \cup \overline{B}.  Next, one must also prove \overline{A} \cup \overline{B} \subseteq \overline{A\cap B}.  Consider the following proof of the first part.

Claim.  If A and B are sets, then \overline{A \cap B} \subseteq \overline{A}\cup\overline{B}.

Proof: Suppose A and B are sets.  To show that \overline{A \cap B} \subseteq \overline{A} we will argue that every element x \in \overline{A \cap B} must necessarily be an element x \in \overline{A} \cup \overline{B}.

To this end, let x \in \overline{A \cap B}.  This means that x \notin A \cap B.  In other words, x is not an element that sets A and B have in common.  Specifically, it might happen that x \in A, in which case x \notin B; on the other hand, it might happen that x \in B but x \notin A.  Or, indeed, it could happen that x \notin A and x \notin B.  These are all of the options for our element x, and by definition of union, they are all captured by the statement

x \in \overline{A} \cup \overline{B}

which completes this proof.  \square

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 A is a set, then \overline{(\overline{A})} = A.

(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 P, then Q” where P and Q can be statements or they can be open sentences.  To make certain this idea makes sense, consider the two open sentences

P: y = mx where m \in \mathbb{Z} and m \neq 0

Q: y/x \in \mathbb{Z}

First note that neither P nor Q are statements.  Instead, they are open sentences.  Find values of the variables x and y that make P true.  Similarly, find values of x and y that make Q true.

According to Definition 2.1, P \Rightarrow Q 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s