Tag Archives: logic

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 6

December 22, 2014 etoix Leave a comment

Problem

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

1. List the elements of all the sets $A_i$ , for $i \in I$ .

2. Find $\bigcap \limits_{i \in I} A_i$ and $\bigcup \limits_{i \in I} A_i$ .

Solution
1. List the elements of all the sets $A_i$ , for $i \in I$ .

$A_2$ = {2, 3, 1, 4}.

$A_3$ = {3, 4, 2, 6}.

$A_4$ = {4, 5, 3, 8}.

$A_5$ = {5, 6, 4, 10}.

2. Find $\bigcap \limits_{i \in I} A_i$ and $\bigcup \limits_{i \in I} A_i$ .

$\bigcap \limits_{i \in I} A_i$ = {4}.

$\bigcup \limits_{i \in I} A_i$ = {1, 2, 3, 4, 5, 6, 8, 10}.

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 5

December 21, 2014 etoix Leave a comment

Problem

Suppose $\mathcal F$ = { {3, 7, 12}, {5, 7, 16}, {5, 12, 23} }. Find $\cap \mathcal F$ and $\cup \mathcal F$ .

Solution

$\cap \mathcal F$ = {5}.

$\cup \mathcal F$ = {3, 5, 7, 12, 16, 23}.

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 4

December 20, 2014 etoix Leave a comment

Problem

Suppose $\mathcal F$ = { {red, green, blue}, {orange, red, blue}, {purple, red, green, blue} }. Find $\cap \mathcal F$ and $\cup \mathcal F$ .

Solution
$\cap \mathcal F$ = {red, blue}.

$\cup \mathcal F$ = {red, green, blue, orange, purple}.

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 3

December 19, 2014 etoix Leave a comment

Problem

We’ve seen that $\mathcal P (\emptyset) = { \emptyset }$ , and ${ \emptyset } \neq \emptyset$ . What is $\mathcal P ( { \emptyset } )$ ?

Solution
$\mathcal P ( { \emptyset } )$ has two sets: ${\emptyset }$ and $\emptyset$ .

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 2

December 18, 2014 etoix Leave a comment

Problem

Analyze the logical forms of the following statements. You may use the symbols $\in, \notin, =, \neq, \land, \lor, \to, \iff, \forall, \text{and } \exists$ in your answers, but not $\subseteq, \subsetneq, \mathcal{P}, \cap, \cup, \setminus, \{, \}, \text{or } \neg$ . (Thus, you must write out the definitions of some set theory notation, and you must use equivalences to get rid of any occurrences of $\neg$ .)

$x \in \cup \mathcal{F} \setminus \cup \mathcal{G}$
$\{x \in B \mid x \notin C \} \in \mathcal{P}(A)$
$x \in \bigcap \limits_{i \in I} (A_i \cup B_i)$
$x \in (\bigcap \limits_{i \in I} A_i) \cup (\bigcap \limits_{i \in I} B_i)$

Solution

$x \in \cup \mathcal{F} \setminus \cup \mathcal{G}$

x is a member of the union of the $\mathcal{F}$ family but not in the union of the $\mathcal{G}$ family.

$x \in \cup \mathcal{F} = \forall x (\exists A \in \mathcal{F}(x \in A)$

$x \in \cup \mathcal{G} = \forall x (\exists B \in \mathcal{G}(x \in B)$

Combine

$\forall x[(\exists A \in \mathcal{F}(x \in A)) \land \neg (\exists B \in \mathcal{G}(x \in B)]$

Abbreviation

$\forall x[(\exists A (A \in \mathcal{F} \to x \in A)) \land \neg (\exists B (B \in \mathcal{G} \to x \in B)]$

Quantifier Negation

$\forall x[(\exists A (A \in \mathcal{F} \to x \in A)) \land (\forall B \neg (B \in \mathcal{G} \to x \in B)]$

Conditional

$\forall x[(\exists A (A \in \mathcal{F} \to x \in A)) \land (\forall B \neg (B \notin \mathcal{G} \lor x \in B)]$

DeMorgan

$\forall x[(\exists A (A \in \mathcal{F} \to x \in A)) \land (\forall B (B \in \mathcal{G} \land x \notin B)]$

$\{x \in B \mid x \notin C \} \in \mathcal{P}(A)$

x is a member of B and not a member of C. B and C are both power sets of A.

Is this right?

$\{x \in B \mid x \notin C \} = \forall x (x \in B \land x \notin C)$

$y \in \mathcal{P}(A) = \forall x (x \in y \to x \in A)$

Combine

$\forall x [(x \in B \land x \notin C) \to x \in A]$

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

Family Intersection

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

Union

$x \in A \bigcup B = x \in A \lor x \in B$

Combine

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

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

$\forall x [\forall i \in I (x \in A_i) \lor \forall i \in I (x \in A_i)]$

Cannot pull out $\forall i \in I$ because universal quantifier does not distribute over disjunction.

How To Prove It by Velleman

Prove It by Velleman, Section 2.3, Problem 1

December 17, 2014 etoix Leave a comment

Problem

Analyze the logical forms of the following statements. You may use the symbols $\in, \notin, =, \neq, \land, \lor, \to, \iff, \forall, \text{and } \exists$ in your answers, but not $\subseteq, \subsetneq, \mathcal P, \cap, \cup, \setminus, \{, \}, \text{or } \neg$ . (Thus, you must write out the definitions of some set theory notation, and you must use equivalences to get rid of any occurrences of $\neg$ .)

$\mathcal F \subseteq \mathcal P (A)$
$A \subseteq \{2n + 1 \mid n \in \mathbb{N}\}$
$\{n^2 + n + 1 \mid n \in \mathbb{N} \} \subseteq \{2n + 1 \mid n \in \mathbb{N} \}$
$\mathcal P (\bigcup \limits _{i \in I} A_i) \subsetneq \bigcup \limits _{i \in I} \mathcal P (A_i)$

Solution

$\mathcal F \subseteq \mathcal P (A)$

$\mathcal F$ is a family of sets. Any member of $\mathcal F$ , a set, is a power set of A.

So $\text{every member of } \mathcal F \subseteq A$ .

Every member of $\mathcal F$ is in $latex \mathcal P(A) $

$\forall y (y \in F \to y \in \mathcal P(A))$

To say that $y \in \mathcal P (A)$ means that $y \subseteq A$ .

$\forall y (y \in F \to y \subseteq A)$

We’ll introduce x to mean a member of y.

$\forall y (y \in F \to \forall x ( x \in y \to x \in A))$

$A \subseteq \{2n + 1 \mid n \in \mathbb{N}\}$

Definition of subset:

$A \subseteq B = \forall x (x \in A \to x \in B)$

$\forall x ( x \in A \to \exists n \mathbb{N} (x = 2n + 1))$

$\{n^2 + n + 1 \mid n \in \mathbb{N} \} \subseteq \{2n + 1 \mid n \in \mathbb{N} \}$

Definition of subset:

$A \subseteq B = \forall x (x \in A \to x \in B)$
$\forall n \in \mathbb{N} \exists m \in \mathbb{N} (n^2 + n + 1 = 2m + 1)$

Need to use n and m to allow for different values, since these were two different statements.

$\mathcal P (\bigcup \limits _{i \in I} A_i) \subsetneq \bigcup \limits _{i \in I} \mathcal P (A_i)$

There is some set that is a power set of the union of the family of A that is not a subset of the union of all power sets of the family of A.

$\mathcal P (\bigcup \limits _{i \in I} A_i) \subsetneq \bigcup \limits _{i \in I} \mathcal P (A_i)$

Add some context

$\exists y [ y \in \mathcal{P} (\bigcup \limits_{i \in I} A_i) \land y \notin \bigcup \limits_{i \in I} \mathcal P(A_i)]$

Power Set: $y \in \mathcal{P} (\bigcup \limits_{i \in I} A_i) = \forall x (x \in y \to x \in \bigcup \limits_{i \in I} A_i)$ .

$\exists y [ \forall x (x \in y \to x \in \bigcup \limits_{i \in I} A_i) \land y \notin \bigcup \limits_{i \in I} \mathcal{P}(A_i)]$

Family Union: $x \in \bigcup \limits_{i \in I} A_i = \exists i \in I (x \in A_i)$

$\exists y [ \forall x (x \in y \to \exists i \in I (x \in A_i)) \land y \notin \bigcup \limits_{i \in I} \mathcal{P}(A_i)]$

Negation

$\exists y [ \forall x (x \in y \to \exists i \in I (x \in A_i)) \land \neg (y \in \bigcup \limits_{i \in I} \mathcal P(A_i))]$

Does this work? What does it mean to be a union of power sets? Same goes for the question itself.

Family Union: $y \in \bigcup \limits_{i \in I} \mathcal P(A_i) = \exists i \in I \forall x (x \in y \to x \in \mathcal P(A_i)$ . If y contains all the members x, then there is a set $A_i$ that also contains all members x.

$\exists y [ \forall x (x \in y \to \exists i \in I (x \in A_i)) \land \neg (\exists i \in I \forall x (x \in y \to x \in \mathcal P(A_i)))]$

Power Set: $x \in \mathcal P(A_i) = x \in y \to x \in A_i$

$\exists y [ \forall x (x \in y \to \exists i \in I (x \in A_i)) \land \neg (\exists i \in I \forall x (x \in y \to (x \in y \to x \in A_i)))]$

Conditional

$\exists y [ \forall x (x \in y \to \exists i \in I (x \in A_i)) \land \neg (\exists i \in I \forall x (x \notin y \lor x \notin y \lor x \in A_i)))]$

Tautology

$\exists y [ \forall x (x \in y \to \exists i \in I (x \in A_i)) \land \neg (\exists i \in I \forall x (x \notin y \lor x \in A_i)))]$

Quantifier Negation and DeMorgan

$\exists y [ \forall x (x \in y \to \exists i \in I (x \in A_i)) \land (\forall i \in I \exists x (x \in y \land x \notin A_i)))]$

How To Prove It by Velleman

Prove It by Velleman, Section 2.2, Problem 12

December 16, 2014 etoix Leave a comment

Problem

Let T(x, y) mean “x is a teacher of y.” What do the following statements mean? Under what circumstances would each one be true? Are any of them equivalent to each other?

$\exists ! y T(x,y)$
$\exists x \exists ! y T(x,y)$
$\exists ! x \exists y T(x,y)$
$\exists y \exists ! x T(x,y)$
$\exists ! x \exists ! y T(x,y)$
$\exists x \exists y [T(x,y) \land \neg \exists u \exists v (T(u,v) \land (u \neq x \lor v \neq y))]$

Solution

$\exists ! y T(x,y)$

x teaches exactly one subject y. This could be true for many x and y.

$\exists x \exists ! y T(x,y)$

There is some teacher that teaches only one subject. This is true in many cases beyond elementary school.

Is this equivalent to 1?

$\exists ! x \exists y T(x,y)$

There is exactly one teacher for certain subjects. This is true depending on the subject. There may be only one teacher in the world of Tuvan Throat Singing.

$\exists y \exists ! x T(x,y)$

Existential quantiifers are commutative so this is the same as 3.

$\exists ! x \exists ! y T(x,y)$

There is only one subject in the world that has only one teacher. This seems hard to believe. There may be more than one esoteric subject in the world like Reproduction Cycles of Andean Mountain Fire Ants.

$\exists x \exists y [T(x,y) \land \neg \exists u \exists v (T(u,v) \land (u \neq x \lor v \neq y))]$

There is a teacher for a certain subject and there are no teachers for a different subject.

How To Prove It by Velleman

Prove It by Velleman, Section 2.2, Problem 11

December 15, 2014 etoix Leave a comment

Problem

Show that the statements $A \subseteq B$ and $A \setminus B = \emptyset$ are equivalent by writing each in logical symbols and then showing that the resulting formulas are equivalent.

Solution

$latex A \setminus B = emptyset $

$\neg \exists x (x \in A \land x \notin B)$

Quantifier Negation

$\forall x \neg (x \in A \land x \notin B)$

DeMorgan

$\forall x (x \notin A \lor x \in B)$

Conditional

$\forall x \in (x \in A \to x \in B )$

Abbreviation

$\forall x \in (A \subseteq B)$

How To Prove It by Velleman

Prove It by Velleman, Section 2.2, Problem 10

December 14, 2014 etoix Leave a comment

Problem

Show that $\exists x \in A P(x) \lor \exists x \in B P(x)$ is equivalent to $\exists x \in (A\cup B) P(x)$ .
Is $\exists x \in A P(x) \land \exists x \in B P(x)$ equivalent to $\exists x \in (A \cap B) P(x)$ ?