### This assignment has been graded.

### Questions

1. **Choose one** of the following statements, and write the first lines of a direct proof of the statement, enough to show how the definitions would be used in the forward direction. (Bonus points are definitely available if you can write more of the proof than that, although if any line makes no sense, I won't consider anything beyond it.) Consult the definitions on page 26 of *How to Read and Do Proofs* if necessary.

- If $m$, $n$ and $k$ are integers and $m$ divides $n$ then $m$ divides $nk$.
- If $a$ and $b$ are rational numbers, then $\frac {a}{b}$ is also a rational number.
- If $n$ and $m$ are odd integers, then $m+n$ is even.
- If the ordered pairs $(a_1,a_2)$ and $(b_1,b_2)$ are equal, then so are the pairs $(a_1,b_2)$ and $(b_1,a_2)$.
- If $m$ and $n$ are positive integers and each divides the other, then they are equal.
- If $x$ is odd, then $2x^2+x$ is odd.

2. Consider the set of integers $S=\{1,3,5,7,9,11,15,17,19\}$. Write a set in set-builder notation that is a *proper* subset of $S$.

3. Consider the four sets defined below

- $S_1 = \{ x \in \mathbb Z^+ : x = 4^m \text{ for some } m \in \mathbb Z^+ \}$
- $S_2 = \{ x \in \mathbb Z^+ : x = 2^m \text{ for some } m \in \mathbb Z^+ \}$
- $S_3 = \{ x \in \mathbb Z^+ : x = 4m \text{ for some } m \in \mathbb Z^+ \}$
- $S_4 = \{ x \in \mathbb Z^+ : x = 2m \text{ for some } m \in \mathbb Z^+ \}$

**Choose one** subset $\{i,j\}$ of the set $\{1,2,3,4\}$. Decide whether $S_i \subseteq S_j$ or $S_j \subseteq S_i$, and write a direct proof to show that you are correct. (Start out by stating clearly what you are going to prove, e.g., "$S_1 \subseteq S_4$" — this will also help other teams avoid choosing the same $i$ and $j$.)

4. For the $i$ and $j$ you chose for Question 3, explain as succinctly as possible how to see that $S_i \not= S_j$.

5. Give an example of a predicate P(x) such that $\{ x \in \mathbb Z^+ : P(x) \} = \emptyset.$

6. Give an example of a predicate P(x) and a predicate Q(x) such that

(1)(Note that the symbol $\supset$ means the same as $\supseteq$, except that it specifically excludes the possibility that the two sets are equal; that is, it denotes a *proper* subset, not just a subset.)

### Team B1

1.If m, n and k are integers and m divides n then m divides nk.

p1. Assume m, n and k are integers.

p2. Assume m divides n.

p3. By definition, because we know m divides n, there must exist an integer k such that n=km.

p4. Now, we want to show that there exisits an integer k such that (nk)=km

This is very nicely clear, and does a great job of showing how the definition is used in unpacking the meaning of the hypothesis. In P4, however, "we want to show that there exists an integer k" is a problem — in line P3, the name 'k' was already assigned to a (potentially) different integer! Lines P1-P3 do a nice job of showing how the definitions are used in the forward direction, however!

2. A proper subset of S = {positive odd integers x: $1 \leq x \leq 11$}

Perfect!

3. $S_2 \subseteq S_4$

Proof

P1: Assume $S_2=\{x \in \mathbb{Z^+}:x=2^m \text{ for some } m \in \mathbb{Z^+}\}$.

P2: $x=2^m$ can also be written as $x=2(2^{m-1})$.

P3: Since $m \in \mathbb{Z^+}$, $2^{m-1} \in \mathbb{Z^+}$ .

P4: Let $z=(2^{m-1})$.

P5: Thus $x=2z$ for some $z \in \mathbb{Z^+}$.

P6: Therefore $S_2 \subseteq S_4$. QED

This is nearly perfect! But an important thing is missing, namely some line between P1 and P2 that says something like "Let $x \in S_2$. This means that there exists some integer $m \in \mathbb Z^+$ such that $x=2^m$." Without this, the variable $x$ in P2 is simply not defined. (Your P1 uses $x$ in the definition of $S_2$, but that doesn't establish a meaning for $x$ outside of that definition.) Still, very nicely done!

4.

- $S_2 = \{ x \in \mathbb Z^+ : x = 2^m \text{ for some } m \in \mathbb Z^+ \}$

- $S_4 = \{ x \in \mathbb Z^+ : x = 2m \text{ for some } m \in \mathbb Z^+ \}$

In order for two sets to equal each other, they need to be subsets of each other in both directions. For example, in order for S_2 = S_4, $S_2 \subseteq S_4$ AND $S_4 \subseteq S_2$. In this specific example, S_2 is indeed a subset of S_4. However, because S_4 is NOT a subset of S_2, they are not equal.

(NOTE): Definition of a subset: If A and S are sets, we say that S is a subset of A if every element of S is in A.

Using this definition, we were able to conclude that $S_2 \subseteq S_4$ and therefore, every element of S_2 is in S_4. But, not every element of S_4 is in S_2 (ex, 6,10, and 12 are not in S_2 just to name a few). And therefore $S_2 \not= S_4$.

This is nice! The crux is that because there are integers, e.g., 6, 10 and 12, that are in $S_4$ and not in $S_2$, $S_2 \not= S_4$. But this is a great analysis of all the logic involved!

5. P(x): $2x=x$, such that {x∈ℤ+:P(x)}=∅. because no positive integers $x$ satisfy this equation. Since no integer in the domain satisfy the equation you are left with the empty set.

Great!

6. Q(x)= 10 divides x

P(x)= 5 divides x

Okay, that definitely works!

*Comments:*

### Team B2

1. statement: If x is odd, then 2$x^2$+x is odd.

Proof:

P1: Assume $x$ is odd

P2: By definition $x = 2k + 1$ for some integer $k$.

P3: Assume $2x^2 + x$ is an integer

P4: So, $2x^2 + x$ = $2(2k + 1)^2 + 2k+1$ = $(2k + 1) (2(2k + 1)+ 1)$

P5: Let $2(2k +1) + 1$ = $2l + 1$ for some integer $l$

P6: So $2x^2 + x$ = $(2k + 1) (2l + 1)$ for some integer $k$ and some integer $l$

P7: By definition the product of two odd integers is an odd integer. (See homework 7 problem 2.)

P8: So $(2k + 1) (2l +1)$ is odd, therefore $2x^2 + x$ is odd.

In P3, the fact that $2x^2 + x$ is an integer, does not need to be

assumed. It just results form the properties of algebra. In P5, it's true to say, "for some integer $l$'' — but you can be more specific and say "where $l=2k+1$." In P7, the fact that the product of two odd integers is odd is not a result of thedefinitionof anything; rather, as you point out, it's a result proved in an earlier homework.By the way, in line P4, it may have been more effective to write $2x^2 + x = 2(2k + 1)^2 + 2k+1 = 2((2k + 1)^2 + k) +1$ and then let $l=(2k + 1)^2 + k$.

2. S={1,3,5,7,9,11,15,17,19}

Let N= a proper subset of S

N={real odd numbers x: 1≤x≤9}

This looks pretty good! In terms of phrasing, you want to say "Let N={real odd numbers x: 1≤x≤9}". Then N is a proper subset of S."

3. S1 ⊆ S2.

P1: We want to prove that S1 is a subset of S2.

P2: This means that every element in S1 is in S2.

P3: Let S1=$2^m$

P4: By algebra, S2 is $4^m$ = ($2^m$)($2^m$)

P5: Therefore, S1 ⊆ S2 since you can define S1 in terms of S2.

Line P3 is does not make sense; $S_1$ is a set, not a number. Not only that, but $S_1$ is already defined (it must be, since you are referring to it in lines P1 and P2) so there is no need to define it in line P3. Similarly, "S2 is $4^m$ makes no sense either. Finally, the statement that "you can define S1 in terms of S2" is too vague to be meaningful.

4. $S_1$ is not equal to $S_2$ because not every value that is in $S_2$ is in $S_1$. For example, if you make the variable m=1 then the first x value in $S_1$ is 4 and the first x value in $S_2$ is 2. Therefore, $S_1$ will never have the value 2 in its set, so $S_1$ and $S_2$ cannot be equal. So, $S_1$ is a proper subset of $S_2$ because $S_2$ contains all the values in $S_1$, but they are not equal.

Good.

5. P(x): $x^2$=-1

$x^2$=-1 is a predicate, P(x), such that {x∈ℤ+:P(x)}=∅ because there are no positive integers x that satisfy this equation. Therefore, there are no elements in the set, so it is a null set.

Nice! (And people would actually say "

thenull set", as there's only one set that doesn't contain anything.)

6. Q(x) is a proper subset of P(x).

Based on this, we have come up with the following predicates for Q(x) and P(x).

Q(x)= x divides 12

P(x)= x divides 36

Q(x) is a proper subset of P(x) because the sets are NOT equal and all of the elements in Q(x) are in P(x), but not all of the elements in

P(x) are in Q(x).

Okay!

*Comments:*

### Team B3

1.) If $m$ and $n$ are positive integers and each divides the other, then they are equal.

Proof:

P1: Assume $m$ and $n$ are integers

P2: Assume $m$ divides $n$.

P3: Therefore there must exist some number $k$ such that $km = n$

P4: Assume n divides m.

P5: Therefore there must exist some number $j$ such that $jn = m$

Looks good. Usually people will try to get all assumptions from the hypothesis out in front in the very beginning, but that's something I didn't mention in class until very recently. Good attention to detail in using different variables $k$ and $j$ in P3 and P4.

2.)S={1,3,5,7,9,11,15,17,19}

Let L be the proper subset of S

L={prime numbers x : 3<x<17}

Your set L contains the integer 13, which is not an element of S. So you don't have a subset of S here.

3.) $S_1$ ⊆ $S_4$

P1: Assume $S_1 = \{ x \in \mathbb Z^+ : x = 4^m \text{ for some } m \in \mathbb Z^+ \}$

P2: $x=4^m$ can also be written as $x=2(2^m)$.

P3: Then by definition of an even number, $x=2(2^m)$ is even

P4: Therefore $x=4^m$ is even.

P5: Now Assume $S_4 = \{ x \in \mathbb Z^+ : x = 2m \text{ for some } m \in \mathbb Z^+ \}$

P6: Then by definition $S_4$ must be the set of all even numbers

P7: Therefore, $S_1$ ⊆ $S_4$.

Lines P1 and P5 are not necessary, since $S_1$ and $S_4$ are already defined before the proof begins. (Not that this is a big deal.)

Also, $x$ is never quantified in the proof, so that in P3, for example, $x$ is technically a free variable. And this is a problem; see my comments on Team B1's solution.

I like the approach in P5-P6, in identifying $S_4$ as the set of all even numbers. This is

almostcorrect, except that the set of all even numbers would include some negative numbers, which $S_4$ does not.

4.) $S_1$ ≠ $S_4$

To see this we must analyze what each set is comprised of. In 3 we proved that $S_4$ is a set that contains all even numbers. $S_1$ is also comprised of even numbers. However, $S_1$ is not comprised of all even numbers: it only contains certain even numbers. More specifically, it only contains the even numbers one gets when 4 is raised to a positive integer. For example, numbers such as 4, 16, and 64. There are many even numbers that are left out of $S_1$ (such as 2 and 62). Therefore, we can say that $S_1$ is a proper subset of $S_4$ because $S_4$ contains all of the elements of $S_1$ but there are not equal.

As I pointed out above, $S_4$ does not contain

alleven integers, however your analysis here is still fundamentally sound, and nicely presented.

5.) $P(x) : x^2 = 4^x$. This is an empty set because there is no x in the domain of positive integers that could satisfy this equation. Therefore, it is an empty set.

Yes, I think that predicate definitely works! Also, take the time to say things precisely; for example, when you say "This is an empty set", how can the word "this" refer to what you just wrote, when what you just wrote is not a set, but a predicate?

6.) P(x)= All prime numbers

Q(x)= All prime numbers that are odd

Q(x) is a proper subset of P(x) because P(x) contains all of the elements of Q(x), but they are not equal because Q(x) does not contain the number 2, while P(x) does.

Unfortunately, "All prime numbers" and "All prime numbers that are odd" are not predicates. They aren't even sentences!

*Comments:*

### Team B4

1. If m and n are positive integers and each divide each other, then they are equal.

P1. Assume m, n, and k are integers.

P2. Assume m divides n.

P3. By definition, if m divides n, then there must exist a k such that m = nk.

P4. Assume n divides m.

P5. By definition, there must exist a k such that n = mk.

Unfortunately, it looks like Team B3 had already chosen this implication. See my comments on that solution.

2. S = {odd integers x: 1<x<7}

I don't think you intend to say "S=", do you? In any case, your set looks equal to {3,5} and that's definitely a proper subset of S, so that works!

3. S3⊆S2

P1. Assume x∈S3

P2. By definition, if S3⊆S2 then every element of S3 must be in S2.

P3. By algebra: 4m= (2^2)m

P4. Since S3 can be defined as S2, then S3⊆S2.

The best thing about this proof is that it starts by assuming an arbitrary element $x$ is in $S_3$ — and that is exactly how the proof needs to go. (Other teams take note!) In your P2, it's true that if $S_3$ is a subset of $S_2$, then every element in $S_3$ is in $S_2$ — but since you don't know that $S_3$ is a subset of $S_2$, who cares? I think you're more interested in the fact that $S_3$ being a subset of $S_2$

meansthat every element of $S_3$ is in $S_2$, because that is what you can show by demonstrating that your arbitrary element $x \in S_3$ is in $S_2$.

Line P3 is not a statement, since $m$ has not been defined. Meanwhile, in P4, what is "S3 can be defined as S2" even supposed to mean?

4. S3 cannot be equal to S2 because even though S3⊆S2 , S2 is not a subset of S3 because S2 cannot be algebraically turned to look like S3. In order for 2 sets to be equal, S3⊆S2 and S2⊆S3 and since both of those are not true, the sets cannot be equal.

"S2 cannot be algebraically turned to look like S3" is not stated precisely enough to be meaningful. I agree with your claim that "both of those are not true" — but which one fails? How can you show that it fails?

5. $P(x) = |x|> x$. We see that when this predicate is the defining feature of the set, it is empty, because there are no positive integers whose absolute value is greater than their actual value (If $x\in\mathbb Z^-$, the set would contain all negative integers).

Just FYI, I think people would say "defining property" if the set. But this is a great answer!

6. $P(x) = x>0$

$Q(x) = x \text{ is a prime number}$

Every$x$ in the first set will be a positive integer. Every $x$ in the second set will be a prime number. Since all prime numbers are positive integers, but not all positive integers are prime, we see that the set of all positive integers is the superset of the set of all prime numbers, or $\{ x \in \mathbb Z : P(x) \} \supset \{ x \in \mathbb Z : Q(x) \}$

Excellent!

*Comments:*

### Team B5

1. Statement: If n and m are odd integers, then m+n is even

Proof:

P1. Assume n and m are odd integers.

P2. By definition, n=2a+1 and m=2b+1 where a and b are integers.

P3. With algebra, m+n=(2a+1)+(2b+1)=2a+2b+2=2(a+b+1)

P4. (a+b+1) is an integer because adding integers produces integers

P5. m+n is even by the definition of even

People will try pretty hard to avoid letting a sentence start with a mathematical expression, just because it "doesn't look right" (even if the first thing in the mathematics is a capital letter like $A$). But anyway, this looks just about perfect to me.

2. Subset S= {real odd numbers x: $1 \leq x \leq 5$ }

Well, "odd number" implies integer (since "odd" is not defined for any numbers that are not integers) and "integer" implies real number, so the "real" in your definition is a little redundant. Also, the "S=" is incorrect, as this set is not equal to S. It is, however, equal to {1,3,5}, and that's definitely a proper subset of S!

3. S_{3} is a subset of S_{4}

Proof:

P1: Assume S_{3}={x∈Z+:x=4m for some m∈Z+} and S_{4}={y∈Z+:y=2m for some m∈Z+}

P2: By definition if S_{3} ⊆ S_{4} all values in S_{3} are in S_{4}

P3: Through algebra 2y=x

P4: By substitution, this means 2(2m)=4m

P4: This means that S_{4} can be used in an equation to define S_{3}

P5: Thus S_{3} ⊆ S_{4}

In P2, you're telling us what we would know if we knew that $S_3 \subseteq S_4$, but we don't know that yet! It seems what you actually care about is the

otherimplication there, that if all elements (not "values") of $S_3$ are in $S_4$, then $S_3 \subseteq S_4$, since that shows how you can prove that $S_3 \subseteq S_4$.I have no idea how to interpret P3; what is y? What is x? The only way P1 can be interpreted as quantifying x and y is if the meaning of the set-builder notation is misinterpreted. Meanwhile, in P4, what does it mean to "use S

_{4}in an equation"? That is too vague to be meaningful.

4. S_{4} is not a subset of S_{3} and therefore they are not equal to one another.

Proof:

P1: Assume S_{3}={x∈Z+:x=4m for some m∈Z+} and S_{4}={y∈Z+:y=2m for some m∈Z+}

P2: By definition for two sets to be equal S_{3} ⊆ S_{4} and S_{4} ⊆ S_{3}

P3: Through algebra and substitution, it can be proven that S_{3} ⊆ S_{4}

P4: Now, suppose x=4m for some positive integer m and y=2m for some positive integer m

P5: There is no way through algebra to prove that x=y

P6: Thus $S_4 is not a subset S_3$ and $S_3 \neq S_4$

Okay, so you want to show that

it is not the casethat $S_4$ is a subset of $S_3$. That latter statementmeansthat "If $x \in S_4$, then $x \in S_3$." So you show this is false via a counterexample. Find an $x$ that is in $S_4$ but is not in $S_3$.Anyway, line P4 is very unclear. What are x and y? If we were to let x be an arbitrary element of $S_3$ and y be an arbitrary element of $S_4$, this would then make sense. Also, m is quantified by saying "x=4m for some positive integer m" but then quantified again as something else by saying "y=2m for some positive integer m". Each of those statements in isolation might be true, but why should they be true

for the same valueof m?In P5, sure there is no way to prove that x=y, but why should there be? We don't expect that if we take any element of $S_3$ and any element of $S_4$ that the two will be equal, do we?

5. P(x)=x^{3} < x for positive integers. Thus, the set of x that make this true would be the null set.

Okay, looks good!

6. A predicate for Q(x) and for P(x) such that $\{ x \in \mathbb Z : P(x) \} \supset \{ x \in \mathbb Z : Q(x) \}$ would be:

$Q(x): x = 10n$ for some integer $n$

$P(x): x = 2n$ for some integer $n$

Those are some nice predicates.

*Comments:*

- Is the subset you created for number 2 a "proper" subset?

### Team B6

1. If a and b are rational numbers, then a/b is also a rational number.

Definition 7: A real number r is rational if and only if r can be expressed as the ratio of two integers p and q in which the denominator q is not 0.

P1: Assume a and b are rational numbers.

P2: This means there exists a ratio p/q and x/y such that a = p/q and b = x/y where p, q, x and y are integers and q and y are not 0.

P3: We want to show there exists a rational number z such that z = a/b.

P4: Through algebra, let z = py/qx (where we know p, q, x and y are integers but q and y are not 0).

P5: Therefore z can be expressed as a ratio of integers through a little algebra and we wanted to show this ratio is equal to a/b, which we did, proving that a/b is also a rational number.

Well, this looks pretty good! Just a minor thing: It's not that "we know p, q, x and y are integers but q and y are not 0" but rather that "we know pq and qx are integers and qx is not 0". For that matter, how

doyou know that qx is not 0? You don't! Because I should have put "b is nonzero" into the hypothesis! Otherwise, the theorem is not true… Sorry about that!!

2. Subset S= {odd numbers x: 3<x<11}

I don't know how "Subset S=" is supposed to read, but the set you wrote out in set-builder notation looks to be equal to {5,7,9}, which is definitely a proper subset of S.

3. S_{1} is a subset of S_{3}

P1: Assume $S_1 = \{ x \in \mathbb Z^+ : x = 4^m \text{ for some } m \in \mathbb Z^+ \}$ and $S_3 = \{ x \in \mathbb Z^+ : x = 4m \text{ for some } m \in \mathbb Z^+ \}$.

P2: By definition, S_{1} ⊆ S_{3} means if x is in S_{1}, then x must be in S_{3}.

P3: $x=4^m$ = $x=4(4^{m-1})$.

P4: Through algebra, let $m=(4^{m-1})$.

P5: Thus we can say that x = 4m for some $m \in \mathbb{Z^+}$.

P6: Therefore we have proved that S_{1} ⊆ S_{3}.

Line P2 is very promising, going right to the meaning of what you're trying to show! P3 is technically not a statement, since x and m have not been quantified. If you had said "Assume $x\in S_1$. Then $x=4^m$ for some integer $m$," then this would make sense. In P4, you don't use the word "let" in a situation where there is no choice involved; indeed, "through algebra" there isn't any choice about it! However, I think "$m=(4^{m-1})$" has a bigger problem — suddenly m is redefined as something different than what it was in the last couple of lines…

Ultimately, all of the right ideas are probably present, but a logical proof has not been constructed.

4. In order for two sets to be equal to one another we would have to prove that S_{1} ⊆ S_{3} AND S_{3} ⊆ S_{1}. Given the above proof for question 3, we can easily see that S_{1} ⊆ S_{3} however if we tried to prove these sets the other way (S_{3} ⊆ S_{1}) we wouldn't be successful. Because we can see that every element in S_{1} is in S_{3} we know S_{1} ⊆ S_{3} is true, but if we visualize some of the elements in S_{3} we can see they do not belong to S_{1}. For example, some of the first few element included in S_{1} are; 4, 16, 64, 256. The first few elements of S_{3} are; 4, 8, 12, 16, 20, 24. We can literally see most elements in S_{3} are not included in S_{1} (like 8, 12, 20, 24 etc.) and therefore we can say S_{1} ⊆ S_{3} is true but S_{3} ⊆ S_{1} is false, therefore $S_1 \not= S_3$.

This sounds fine, even if it's a little imprecise. Your final sentence is really the one that matters; it would have been better to devote the space to justifying the claim that 8 is not in S

_{1}, since that alone would have established everything you need.

5. P(x)= "x=-x^{3}"

Looks good.

6.P(x) includes G(x)

P(x)= x=k^{2} for some integer k

G(x)= x=k^{4} for some integer k

Those predicates look good, but what is G(x)? For that matter, if P(x) and G(x) are predicates, what does it mean to say "P(x) includes G(x)"? How can one predicate "include" another predicate?