187 – Quiz 3

Here is quiz 3. 

Problem 1 requests a counterexample to the statement: An integer x is positive if and only if x+1 is positive.

To find a counterexample to a statement of the form “an integer x has property A if and only if it has property B, we need an integer x such that one of the properties is true of x while the other is false. Note that if x is positive, i.e., x>0, then x+1>1>0, i.e., x+1 is also positive. This means that the only way the statement is going to fail is if we have that x+1 is positive yet x is not. 

We can now easily see that x=0 is a counterexample. (And, in fact, it is the only counterexample.)

Problem 2 asks to show that C\subseteq D, where C=\{x\in{\mathbb Z}\colon x|12\} and D=\{x\in{\mathbb Z}\colon x|60\}. 

By definition, C\subseteq D iff any element of C is also an element of D. Let us then consider an element x of C. By definition of C, this means that x is an integer, and x|12. We need to show that x\in D, i.e., that x\in{\mathbb Z} and that x|60. The first requirement is automatic, so we only need to verify that x|60. 

To see this, we use that x|12. By definition, this means that there is an integer, let us call it a, such that xa=12. To show that x|60, we need (again, by definition) that there is an integer b such that xb=60. Now, since xa=12, then 5(xa)=5\times 12=60, or x(5a)=60. We immediately see that we can take b=5a. This is an integer, and xb=60, as needed.

Problem 3 asks for the cardinality of the set 2^{2^{\{1,3,7,11\}}}. 

Recall that for any set A, then |2^A|=2^{|A|}, as shown in lecture. In particular, if A=\{1,3,7,11\}, then |2^A|=2^4=16. Now let A'=2^{\{1,3,7,11\}}=2^A. Then |2^{A'}|=2^{|A'|}=2^{16}=65536.


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 )

Facebook photo

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

Connecting to %s

%d bloggers like this: