HW 2 Answer Key

Section 1.3

7a. ∃x(P (x) ∧ Q(x))

b. ∃x(P (x) ∧ ¬Q(x)) c. ∀x(P (x) ∨ Q(x)) (Exclusive or would be better) d. ∀x¬(P (x) ∨ Q(x))

12. There could be several different ways of expressing these. Predicates of 1/2/3 variables can be used. Let P(s,c,m) be the statement that student s is in year of study c and is majoring in m. s ranges over students in the class, c over the four years of study, and m over all possible majors. a. ∃s∃mP (s, junior, m).T rue. b. ∀s∃cP (s, c, computerscience).T rue c. ∃s∃c∃m(P (s, c, m) ∧ (c ≠ junior) ∧ (m ≠ mathematics).T rue. d. ∀s(∃cP (s, c, computerscience) ∨ ∃mP (s, sophomore, m)).F alse. e. ∃m∀c∃sP (s, c, m).F alse.

14a. This is false, since 1+1 ≠ 1-1 b. This is true, since 2+0 = 2-0 c. This is false, there are many values of y for which 1 + y ≠ 1 − y. d. This is false, since the equation (x+2) = (x-2) has no solution. e. This is true, since we can take x=y=0. f. This is true, since we can take y=0 for each x. g. This is true, since we can take y=0. h. This is false, we already know part d is false. i. This is false.

18. a. ∀x(P (x) → Q(x))

b. ∃x(R(x) ∧ ¬Q(x)) c. ∃x(R(x) ∧ ¬P (x)) d. Yes,(c) can be concluded from (a) and (b). The unsatisfactory excuse guaranteed by (b) cannot be clear explanation by (a).

26. It is enough to prove it by giving a counter-example. The first proposition is stating that one of the two predicates P or Q are universally true, while the second proposition is saying that for every x, eitherP(x) or Q(x) holds, but which of them is true depends on x. A simple example is P(x) is the statement that x is odd. Q(x) is the statement that x is even. The universe of discourse is set of positive integers. The second proposition is true, since each positive integer is either odd or even, but, the first proposition is false, since it is niether the case that all positive integers are even , nor the case that all positive integers are odd.

28. There can be several different ways to show the equivalence, essentially the reasoning given should be correct. We need to show that each of these propositions implies the other. Suppose that ∀_{x}P (x) ∨ ∀_{x}Q(x) is true. We want to show that ∀_{x}∀_{y}(P (x) ∨ Q(y)) is true. By our hypothesis, one of two things must be true. Either P is universally true, or Q is universally true. In the first case, ∀_{x}∀_{y}(P (x) ∨ Q(y)) is true, since the first expression in the disjunction is true, no matter what x and y are; and in the second case, ∀_{x}∀_{y}(P (x)∨Q(y)) is also true, since now the second expression in the disjunction is true, no matter what x and y are.

Next we need to prove the converse. So suppose that ∀_{x}∀_{y}(P (x) ∨ Q(y)) is true. We want to show that ∀_{x}P (x) ∨ ∀_{x}Q(x) is true. If ∀_{x}P (x) is true, then we are done. Otherwise, P (x_{0}) must be false for some x_{0} in the domain of discourse. For this x_{0}, then, the hypothesis tells us that P (x_{0}) ∨ Q(y) is true, no matter what y is. Since P (x_{0}) is false, it must be the casse that Q(y) is true for each y. In other words, ∀_{y}Q(y) is true, or, to change the name of the meaningless quantified variable, ∀_{x}Q(x) is true. This certainly implies that ∀_{x}P (x) ∨ ∀_{x}Q(x) is true, as desired.

Section 1.4

3a. yes they are equal b. no c. no

4. Each of the sets is a subset of itself. B is a subset of A, C is a subset of D, and C is a subset of A

10a. The empty set has no elements, so its cardinality is 0.

b. This set has one element (the empty set), so its cardinality is 1. c. 2 d. 3

12. The union of all sets in the power set of a set X must be exactly X. In other words, we can recover X from it’s power set uniquely. Therefore the answer is yes.

18. We can conclude that A = ϕ or B = ϕ. To prove this, suppose that neither A nor B were empty. Then there would be elements a ∈ A and b ∈ B. This would give at least one element, namely (a, b) ∈ A × B, so A × B would not be ϕ. This contradiction shows that either A or B (or both) is empty.

22. Suppose A ≠ B. and niether A nor B is empty. We must prove that AxB ≠ BxA. Since A ≠ B, either we can find an element x that is in A but not B, or vice versa. The two cases are similar. Let us assume that x is in A but not B. Also, since B is not empty, there is some element y ∈ B. Then (x,y) is in AxB by definition, but it is not in BxA since x is not an element of B. Therefore AxB ≠ BxA.

24a. If S ∈ S, then by defining condition for S we conclude that SisNOT ∈ S, a contradiction. b. If SisNOT ∈ S, then by defining condition for S we conclude that it is not the case that SisNOT ∈ S (otherwise S would be an element of S), again a contradiction.

Section 1.5

2a. A ∩ B b. A − B c. A ∪ B d. ¬A ∪ ¬B

6. a. A ∪ ϕ = {x|x ∈ A ∨ x ∈ ϕ} = {x|x ∈ A ∨ F } = {x|x ∈ A} = A.

b. A ∩ ϕ = {x|x ∈ A ∧ x ∈ ϕ} = {x|x ∈ A ∧ F } = {x|F } = ϕ c. A ∪ A = {x|x ∈ A ∨ x ∈ A} = {x|x ∈ A} = A d. A ∩ A = {x|x ∈ A ∧ x ∈ A} = {x|x ∈ A} = A e. A − ϕ = {x|x ∈ A ∧ x ∉ ϕ} = {x|x ∈ A ∧ T } = {x|x ∈ A} f. A ∪ U = {x|x ∈ A ∨ x ∈ U} = {x|x ∈ A ∨ T } = {x|T } = U g. A ∩ U = {x|x ∈ A ∧ x ∈ U} = {x|x ∈ A ∧ T } = {x|x ∈ A} = A h. ϕ − A = {x|x ∈ ϕ ∧ x ∉ A} = {x|F ∧ x ∉ A} = {x|F } = ϕ

12. a. Suppose that x ∈ A ∪ B. Then either x ∈ A or x ∈ B. In either case certainly x ∈ A ∪ B ∪ C. b. Suppose that x ∈ A ∩ B ∩ C. Then x is in all three of these sets. In particular it is in both A and B therefore in A ∩ B c. Suppose that x is in (A-B)-C. Then x is in (A-B ), but not in C. Since x is in (A-B) we know that x ∈ A (we also know that x is not in B , but that fact is not of use here). Since he have that x is in A, but x is not in C, we have x ∈(A-C). d. To show that the set given on the L.H.S is empty, assume that x is some element in that set and derive a contradiction. Assume x ∈ (A − C) ∩ (C − B). Then x ∈ A − Candx ∈ C − B. The first of these statements implies by definition that x is not i C , while the second implies that x is in C, which is a contradiction. e. To establiush equality we need to prove inclusion in both directions. To prove that B-A ∪ (C-A) is a subset of (B ∪ C)-A, suppose that x ∈ (B-A) ∪ (C-A). Then either x ∈ (B-A) or x ∈ (C-A). The two cases are parallel, so let us assume the former. So x is in B and x is not in A. Hence x ∈ B ∪ C. Therefore x ∈ (B ∪ C) − A. For the converse part, suppose x ∈ (B ∪ C) − A. It means that x ∈ (B ∪ C) and x is not in A. Therefore x ∈ Borx ∈ C but x is not in A. Hence, x ∈ B − Aorx ∈ C − A. In either case x ∈ (B − A) ∪ (C − A).

16. First suppose that x is in the L.H.S., then x must be in A but in neither B nor C. Thus x ∈ A-C, but x does not belong to B-C, so x is in the R.H.S. Next suppose that x is in the R.H.S., then x must be in A-C nad not in B-C. The first of these implies that x is in A and x is not in C. But it must also be the case that x is not in B , otherwise we would have x ∈ B-C. Thus we have shown that x is in A, but is in nietherB nor C, which implies that x is in the L.H.S.

18. Insert Venn Diagrams

26. There are precisely two ways that an item can be in either A or B but not both. It can be in A but not B (which is equivalent to saying that it is in A-B), or it can be in B but not A (Which is equivalent to saying that it is in B-A). Thus an element is in A ⊕ B if and only if it is in (A − B) ∪ (B − A).

30. This is a true statement.

Each side consists of those things that are in an odd number of the sets A, B, and C.

38. a. 00111 00000 b. 10100 10001 c. 01110 01110