Tag Archives: logic

Prove It by Velleman, Section 3.1, Problem 1

January 1, 2015 etoix Leave a comment

Problem

Consider the following theorem. (This theorem was proven in the introduction.)

1. Identify the hypotheses and conclusion of the theorem. Are the hypotheses true when n = 6? What does the theorem tell you in this instance? Is it right?

2. What can you conclude from the theorem in the case n = 15? Check directly that this conclusion is correct.

3. What can you conclude from the theorem in the case n = 11?

Solution

1. Identify the hypotheses and conclusion of the theorem. Are the hypotheses true when n = 6? What does the theorem tell you in this instance? Is it right?

The hypotheses are: $n \in \mathcal{Z}$ , n > 1, and n is not prime.

The conclusion is $2^n - 1$ is not prime.

6 is an integer. 6 > 1. 6 is not prime. The hypotheses are true when n = 6.

$2^6 - 1 = 63$ , which is not prime, so this instance of the theorem is correct.

2. What can you conclude from the theorem in the case n = 15? Check directly that this conclusion is correct.

The hypotheses are true when n = 15.

$2^{15} - 1 = 32767$ which is not prime (32767 is divisible by 7). So this instance of the theorem is correct.

3. What can you conclude from the theorem in the case n = 11?

11 is not prime so the hypothesis, n is not prime, is false. Therefore, the theorem does not apply.

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 15

December 31, 2014 etoix Leave a comment

Problem

In Section 2.3 we saw that a set can have other sets as elements. When discussing sets whose elements are sets, it might seem most natural to consider the universe of discourse to be collection of all sets. However, as we will see in this problem, assuming that there is such a universe leads to contradictions.

Suppose U were the collection of all sets. Note that in particular U is a set, so we would have $U \in U$ . This is not yet a contradiction; although most sets are not elements of themselves, perhaps some sets are elements of themselves. But it suggests that the sets in the universe U could be split into two categories: the unusual sets that, like U itself, are elements of themselves, and the more typical sets that are not. Let R be the set of sets in the second category. In other words, $R = \{ A \in U \mid A \notin A \}$ . This means that for any set A in the universe U, A will be an element of R iff $A \notin A$ . In other words, we have $\forall A \in U (A \in R \iff A \notin A)$ .

1. Show that applying this last fact to the set R itself (in other words, plugging in R for A) leads to a contradiction. This contradiction was discovered by Bertrand Russell in 1901, and is known as Russell’s Paradox.

2. Think some more about the paradox in part 1. What do you think it tells us about sets?

Solution

$\forall R \in U (R \in R \iff R \notin R)$

Biconditional

$\forall R \in U [(R \in R \to R \notin R) \land (R \notin R \to R \in R)]$

Conditional

$\forall R \in U [(R \notin R \lor R \notin R) \land (R \in R \lor R \in R)]$

Idempotent

$\forall R \in U (R \notin R \land R \in R)$

This is a contradiction.

2. Think some more about the paradox in part 1. What do you think it tells us about sets?

It’s best to define sets to avoid recursive definitions.

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 14

December 30, 2014 etoix 1 Comment

Problem

1. Show that if $\mathcal F = \emptyset$ , then the statement $x \in \cup \mathcal F$ will be false no matter what x is. It follows that $\cup \emptyset = \emptyset$ .
2. Show that if $\mathcal F = \emptyset$ , then the statement $x \in \cap \mathcal F$ will be true to no matter what x is. In a context in which it is clear what the universe of discourse U is, we might therefore want to say that $\cap \emptyset = U$ . However, this has the unfortunate consequence that the notation $\cap \emptyset$ will mean different things in different contexts. Furthermore, when working with sets whose elements are sets, mathematicians often do not use a universe of discourse at all. (For more on this, see the next exercise.) For these reasons, some mathematicians consider the notation $\cap \emptyset$ to be meaningless. We will avoid this problem in this book by using the notation $\cap \mathcal F$ only in contexts in which we can be sure that $\mathcal \neq \emptyset$ .

Soultion

1. Show that if $\mathcal F = \emptyset$ , then the statement $x \in \cup \mathcal F$ will be false no matter what x is. It follows that $\cup \emptyset = \emptyset$ .

$\cup \mathcal F = \forall A (A \in \mathcal F \land x \in A)$

Substitute $\emptyset$ for $\mathcal F$ .

$\cup \emptyset = \forall A (A \in \emptyset \land x \in A)$

$\emptyset$ by definition cannot contain anything. So we know that $A \in \emptyset$ is always false. Since $A \in \emptyset$ is the lead of a conjunction, we know that the entire statement is always false.

2. Show that if $\mathcal F = \emptyset$ , then the statement $x \in \cap \mathcal F$ will be true to no matter what x is. In a context in which it is clear what the universe of discourse U is, we might therefore want to say that $\cap \emptyset = U$ . However, this has the unfortunate consequence that the notation $\cap \emptyset$ will mean different things in different contexts. Furthermore, when working with sets whose elements are sets, mathematicians often do not use a universe of discourse at all. (For more on this, see the next exercise.) For these reasons, some mathematicians consider the notation $\cap \emptyset$ to be meaningless. We will avoid this problem in this book by using the notation $\cap \mathcal F$ only in contexts in which we can be sure that $\mathcal \neq \emptyset$ .

$\cap \mathcal F = \forall A (A \in \mathcal F \to x \in A)$

Substitute $\emptyset$ for $\mathcal F$ .

$\cap \emptyset = \forall A (A \in \emptyset \to x \in A)$

$\emptyset$ by definition cannot contain anything. So we know that $A \in \emptyset$ is always false. Since $A \in \emptyset$ is the lead of a conditional and always false, we know that the entire statement is always true, albeit vacuously.

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 13

December 29, 2014 etoix Leave a comment

Problem

13. Sometimes each set in an indexed family of sets has *two* indices. For this problem, use the following definitions: I = {1,2}, J = {3,4}. For each $i \in I$ and $j \in J$ , let $A _{i,j} = \{i, j, i+j\}$ . Thus, for example, $A _{2,3} = \{2, 3, 5 \}$ .

1. For each $j \in J$ let $B_j = \bigcup \limits_{i \in I} A_{i,j} = A_{1,j} \cup A_{2,j}$ . Find $B_3$ and $B_4$ .
2. Find $\bigcap \limits{j \in J} B_j$ . (Note that, replacing $B_j$ with its definition, we could say that $\bigcap \limits_{j \in J} B_j = \bigcap \limits_{j \in J} (\bigcup \limits_{i \in I} A_{i,j})$ .)
3. Find $\bigcup \limits_{i \in I} (\bigcap \limits_{j \in J} A_{i,j})$ . (Hint: You may want to do this in two steps, corresponding to parts 1 and 2.) Are $\bigcap \limits_{j \in J} (\bigcup \limits_{i \in I} A_{i,j})$ and $\bigcup \limits_{i \in I} ( \bigcap \limits_{j \in J} A_{i,j})$ equal?
4. Analyze the logical forms of the statements $x \in \bigcap \limits_{j \in J} (\bigcup \limits_{i \in I} A_{i,j})$ and $x \in \bigcup \limits_{i \in I} (\bigcap \limits_{j \in J} A_{i,j})$ . Are they equivalent?

Solution

1. For each $j \in J$ let $B_j = \bigcup \limits_{i \in I} A_{i,j} = A_{1,j} \cup A_{2,j}$ . Find $B_3$ and $B_4$ .

$A_{1,3} = \{1, 3, 4\}$

$A_{1,4} = \{1, 4, 5\}$

$A_{2,3} = \{2, 3, 5\}$

$A_{2,4} = \{2, 4, 6\}$

$B_3$ = { 1, 2, 3, 4, 5 }

$B_4$ = { 1, 2, 4, 5, 6 }

2. Find $\bigcap \limits{j \in J} B_j$ . (Note that, replacing $B_j$ with its definition, we could say that $\bigcap \limits_{j \in J} B_j = \bigcap \limits_{j \in J} (\bigcup \limits_{i \in I} A_{i,j})$ .)

$\bigcap \limits{j \in J} B_j$ = { 1, 2, 4, 5 }

3. Find $\bigcup \limits_{i \in I} (\bigcap \limits_{j \in J} A_{i,j})$ . (Hint: You may want to do this in two steps, corresponding to parts 1 and 2.) Are $\bigcap \limits_{j \in J} (\bigcup \limits_{i \in I} A_{i,j})$ and $\bigcup \limits_{i \in I} ( \bigcap \limits_{j \in J} A_{i,j})$ equal?

Let $C_i = \bigcap \limits_{j \in J} A_{i,j}$

$C_1$ = { 1, 4 }

$C_2$ = { 2 }

$\cup i \in I C_i$ = { 1, 2, 4 }

{ 1, 2, 4 } $\neq$ { 1, 2, 4, 5 }

$\bigcap \limits_{j \in J} (\bigcup \limits_{i \in I} A_{i,j})$ and $\bigcup \limits_{i \in I} ( \bigcap \limits_{j \in J} A_{i,j})$ are not equal.

4. Analyze the logical forms of the statements $x \in \bigcap \limits_{j \in J} (\bigcup \limits_{i \in I} A_{i,j})$ and $x \in \bigcup \limits_{i \in I} (\bigcap \limits_{j \in J} A_{i,j})$ . Are they equivalent?

$x \in \bigcap \limits_{j \in J} (\bigcup \limits_{i \in I} A_{i,j}) = \forall x \forall j \in J \exists i \in I x \in A_{i,j}$

$x \in \bigcup \limits_{i \in I} (\bigcap \limits_{j \in J} A_{i,j}) = \forall x \exists i \in I \forall j \in J x \in A_{i,j}$

We see that $\forall j \in J$ and $\exists i \in I$ are swapped. The existential and universal quantifiers are not commutative with each other. So the statements are not equivalent.

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 12

December 28, 2014 etoix Leave a comment

Problem

Verify the following identities by writing out (using logical symbols) what it means for an object x to be an element of each set and then using logical equivalences.

1. $\bigcup \limits_{i \in I} (A_i \cup B_i) = (\bigcup \limits_{i \in I} A_i) \cup (\bigcup \limits_{i \in I} B_i)$
2. $(\cap \mathcal F) \cap (\cap \mathcal G) = \cap (\mathcal F \cup \mathcal G)$
3. $\bigcap \limits_{i \in I} (A_i \setminus B_i) = (\bigcap \limits_{i \in I} A_i) \setminus (\bigcap \limits_{i \in I} B_i)$

Solution

1. $\bigcup \limits_{i \in I} (A_i \cup B_i) = (\bigcup \limits_{i \in I} A_i) \cup (\bigcup \limits_{i \in I} B_i)$

General definition

$x \in \bigcup \limits_{i \in I} A_i = \forall x \exists i \in I(x \in A_i)$

$\forall x \exists i \in I(x \in A_i \lor x \in B_i) = \forall x (\exists i \in I(x \in A_i) \lor \exists i \in I(x \in B_i))$

Quantifier Distribution

$\forall x \exists i \in I(x \in A_i \lor x \in B_i) = \forall x \exists i \in I(x \in A_i \lor x \in B_i)$

2. $(\cap \mathcal F) \cap (\cap \mathcal G) = \cap (\mathcal F \cup \mathcal G)$

General Definition

$x \in \cap \mathcal F = \forall A (A \in \mathcal F \to x \in A)$

$\forall A [(A \in \mathcal F \to x \in A) \land (A \in \mathcal G \to x \in A)] = \forall A [A \in (\mathcal F \cup \mathcal G) \to x \in A]$

Conditional

$\forall A [(A \notin \mathcal F \lor x \in A) \land (A \notin \mathcal G \lor x \in A)] = \forall A [A \in (\mathcal F \cup \mathcal G) \to x \in A]$

Distributive

$\forall A [(A \notin \mathcal F \land A \notin \mathcal G) \lor x \in A] = \forall A [A \in (\mathcal F \cup \mathcal G) \to x \in A]$

DeMorgan

$\forall A [\neg (A \in \mathcal F \lor A \in \mathcal G) \lor x \in A] = \forall A [A \in (\mathcal F \cup \mathcal G) \to x \in A]$

Conditional

$\forall A [(A \in \mathcal F \lor A \in \mathcal G) \to x \in A] = \forall A [A \in (\mathcal F \cup \mathcal G) \to x \in A]$

Definition of Union

$\forall A [A \in (\mathcal F \cup \mathcal G) \to x \in A] = \forall A [A \in (\mathcal F \cup \mathcal G) \to x \in A]$

3. $\bigcap \limits_{i \in I} (A_i \setminus B_i) = (\bigcap \limits_{i \in I} A_i) \setminus (\bigcap \limits_{i \in I} B_i)$

General definition

$\bigcap \limits_{i \in I} A_i = \forall x \forall i \in I(x \in A_i)$

$\forall x \forall i \in I(x \in A_i \land x \notin B_i) = \forall x \forall i \in I [(x \in A_i) \land \neg (x \in B_i)]$

On the right hand side, does it make sense to place $\forall i \in I$ on the outside?

$\forall x \forall i \in I(x \in A_i \land x \notin B_i) = \forall x \forall i \in I(x \in A_i \land x \notin B_i)$

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 11

December 27, 2014 etoix Leave a comment

Problem

Give an example of sets A and B for which $\mathcal P ( A \cup B ) \neq \mathcal P(A) \cup \mathcal P(B)$ .

Solution

A = { 1 }

B = { 2 }

$\mathcal P(A)$ = { $\emptyset$ , { 1 } }

$\mathcal P(B)$ = { $\emptyset$ , { 2 } }

$\mathcal P(A) \cup \mathcal P(B)$ = { $\emptyset$ , { 1 }, { 2 } }

$A \cup B$ = { 1, 2 }

$\mathcal P(A \cup B)$ = { $\emptyset$ , { 1 }, { 2 } { 1, 2 } }

$\{ \emptyset, \{ 1 \}, \{ 2 \} \} \neq \{ \emptyset, \{ 1 \}, \{ 2 \}, \{ 1, 2 \} \}$

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 10

December 26, 2014 etoix Leave a comment

Problem

Show that for any sets A and B, $\mathcal P(A \cap B) = \mathcal P(A) \cap \mathcal P(B)$ , by showing that the statements $x \in \mathcal P (A \cap B)$ and $x \in \mathcal P(A) \cap \mathcal P(B)$ are equivalent. (See Example 2.3.3.)

Solution

$x \in \mathcal P (A \cap B) = x \in \mathcal P(A) \cap \mathcal P(B)$

From 2.3.3 we know that $x \in \mathcal P (A \cap B) = \forall x (x \in y \to (x \in A \land x \in B))$ .

$\forall x (x \in y \to (x \in A \land x \in B)) = x \in \mathcal P(A) \cap \mathcal P(B)$

Abbreviation

$\forall x (x \in y \to (x \in A \land x \in B)) = \forall x (x \in \mathcal P(A) \cap \mathcal P(B))$

Definition of Intersection

$\forall x (y \in x \to (x \in A \land x \in B)) = \forall x (x \in \mathcal P(A) \land x \in \mathcal P(B))$

Definition of Power Set

$\forall x (x \in y \to (x \in A \land x \in B)) = \forall x ((x \in y \to x \in A) \land (x \in y \to x \in B)$

Conditional

$\forall x (x \in y \to (x \in A \land x \in B)) = \forall x ((x \notin y \lor x \in A) \land (x \notin y \lor x \in B)$

Distributive

$\forall x (x \in y \to (x \in A \land x \in B)) = \forall x (x \notin y \lor ( x \in A \land x \in B))$

Conditional

$\forall x (x \in y \to (x \in A \land x \in B)) = \forall x (x \in y \to ( x \in A \land x \in B))$

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 9

December 25, 2014 etoix Leave a comment

Problem

Give an example of an index set I and indexed families of set ${ A_i \mid i \in I }$ and ${ B_i \mid i \in I }$ such that $\bigcup \limits_{i \in I} (A_i \cap B_i) \neq (\bigcup \limits_{i \in I} A_i) \cap (\bigcup \limits_{i \in I} B_i)$ .

Solution

The trick here is to make sure that $A_j$ and $B_i$ have overlap but not overlap $A_i$ , $i \neq j$ . These overlaps would be excluded from $\bigcup \limits_{i \in I} (A_i \cap B_i)$ (because it’s not in $B_i$ ) but still be in $(\bigcup \limits_{i \in I} A_i) \cap (\bigcup \limits_{i \in I} B_i)$ .

I = {1, 2}

$A_i$ = { i, i + 1 }

$B_i$ = { i, i + 2 }

$A_1$ = { 1, 2 }

$A_2$ = { 2, 3 }

$B_1$ = { 1, 3 }

$B_2$ = { 2, 4 }

$A_1 \cap B_1$ = { 1 }

$A_2 \cap B_2$ = { 2 }

$\bigcup \limits_{i \in I} A_i$ = { 1, 2, 3 }

$\bigcup \limits_{i \in I} B_i$ = { 2, 3, 4 }

$\bigcup \limits_{i \in I} (A_i \cap B_i)$ = { 1, 2 }

$(\bigcup \limits_{i \in I} A_i) \cap (\bigcup \limits_{i \in I} B_i)$ = { 1, 2, 3, 4 }

{1, 2 } $\neq$ { 1, 2, 3, 4 }

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 8

December 24, 2014 etoix Leave a comment

Problem

Let I = {2, 3}, and for each $i \in I$ let $A_i = {i, 2i}$ and $B_i = {i, i+1}$ .

1. List the elements of the set $A_i$ and $B_i$ for $i \in I$ .
2. Find $\bigcap \limits_{i \in I} (A_i \cup B_i)$ and $(\bigcap \limits_{i \in I} A_i) \cup (\bigcap \limits_{i \in I} B_i)$ . Are they the same?
3. In parts 3 and 4 of exercise 2 you analyzed the statements $x \in \bigcap \limits_{i \in I} (A_i \cup B_i)$ and $x \in (\bigcap \limits_{i \in I} A_i) \cup (\bigcap \limits_{i \in I} B_i)$ . What can you conclude from your answer to part 2 about whether or not these statements are equivalent?

Solution

1. List the elements of the set $A_i$ and $B_i$ for $i \in I$ .

$A_2$ = {2, 4}

$A_3$ = {3, 6}

$B_2$ = {2, 3}

$B_3$ = {3, 4}

2. Find $\bigcap \limits_{i \in I} (A_i \cup B_i)$ and $(\bigcap \limits_{i \in I} A_i) \cup (\bigcap \limits_{i \in I} B_i)$ . Are they the same?

$A_2 \cup B_2 =$ {2, 3, 4}

$A_3 \cup B_3 =$ {3, 4, 6}

$\bigcap \limits_{i \in I} (A_i \cup B_i)$ = {3, 4}

$\bigcap \limits_{i \in I} A_i = \emptyset$

$\bigcap \limits_{i \in I} B_i$ = {3}

$(\bigcap \limits_{i \in I} A_i) \cup (\bigcap \limits_{i \in I} B_i)$ = {3}

3. In parts 3 and 4 of exercise 2 you analyzed the statements $x \in \bigcap \limits_{i \in I} (A_i \cup B_i)$ and $x \in (\bigcap \limits_{i \in I} A_i) \cup (\bigcap \limits_{i \in I} B_i)$ . What can you conclude from your answer to part 2 about whether or not these statements are equivalent?

They are not equivalent. This confirms that the universal quantifier does not distribute over disjunction.

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 7

December 23, 2014 etoix Leave a comment

Problem

Let P = {Johann Sebastian Bach, Napoleon Bonparte, Johann Wolfgang von Goethe, David Hume, Wolfgang Amadeus Mozart, Isaac Newton, George Washington} and let Y = {1750, 1751, 1752, …, 1759}. For each $y \in Y$ , and let $A_y = {p \in P \mid \text{the person p was live at some time during the year y} }$ . Find $\bigcup \limits_{y \in Y} A_y$ and $\bigcap \limits_{y \in Y} A_y$ .