To prove a goal of the form $\forall x P(x)$:

Let x be arbitrary

[Prove P(x)]

Since x was arbitrary, we can conclude that $\forall x P(x)$

Here it is very important to make no assumption about x. Main advantage of this strategy is that it enables you to prove a goal about all objects by reasoning about only one object. If you find yourself using a lot of "all x's" or "every x", then you are probably making your proof unnecessarily complicated by not using this strategy.

To prove a goal of the form $\exists x P(x)$:

Find a particular value x such that P(x) is true. Thus, $\exists x P(x)$

Finding the right value to use for x may be difficult in some cases. One method that is sometimes helpful is to assume that P(x) is true and then see if you can figure out what x must be, based on this assumption.

Next important thing is to learn, how to use a given quantified sentence.

To use a given of the form $\exists x P(x)$:

We can use this by introducing a new variable $x_0$ into the proof to stand for an object for which $P(x_0)$ is true. That is, you can now assume $P(x_0)$ is true.

To use a given of the form $\forall x P(x)$:

This is useful only when you're talking about some value a in your proof, you can always assume that P(a) is true.

In general, its a good strategy to simplify the goal as much possible by using the strategies we're learning.

======================================================================================

Ex-1 Given that $\exists x (P(x) \rightarrow Q(x))$, so we can find a $x_0$ s.t. $P(x_0) \rightarrow Q(x_0)$. Suppose $\forall x P(x)$, it follows that $P(x_0)$ is true and hence $Q(x_0)$ is also true. Thus $\exists x Q(x)$ is true. So, $\forall x P(x) \rightarrow \exists x Q(x)$ is true.

Ex-2 Scratch Work:

given:

goal: $A \cap B \setminus C = \emptyset \rightarrow A \cap B \subseteq C$

Assume the hypotheses

given: $A \cap B \setminus C = \emptyset$

goal: $A \cap B \subseteq C$ $\equiv$ $\forall x (x \in A \cap B \rightarrow x \in C)$

Let x be arbitrary

given: $A \cap B \setminus C = \emptyset$

goal: $x \in A \cap B \rightarrow x \in C$

Assume the hypotheses

given: $A \cap B \setminus C = \emptyset$ , $x \in A \cap B$

goal: $x \in C$

we can not analyse goal any further, so let us analyze the givens now.

It is given that

$A \cap B \setminus C = \emptyset$

$\equiv$ $\lnot \exists x x \in (A \cap B \setminus C)$

$\equiv$ $\forall x \lnot (x \in (A \cap B \setminus C))$

$\equiv$ $\forall x \lnot (x \in A \land x \in B \land x \notin C)$

$\equiv$ $\forall x [\lnot (x \in A \land x \in B) \lor x \in C]$

$\equiv$ $\forall x (x \in A \cap B \rightarrow x \in C)$

Hence $x \in C$

Formal Proof:

Let x be an arbitrary element of $A \cap B$. Suppose A and $B \setminus C$ are disjoint, so it can not happen that x belongs to A and B but not C. So x must be an element of C. Thus $x \in A \cap B \rightarrow x \in C$. Since x is arbitrary, hence $\forall x (x \in A \cap B \rightarrow x \in C)$ or $A \cap B \subseteq C$. So, If A and $B \setminus C$ are disjoint then $A \cap B \subseteq C$

Ex-3

given:

goal: If $A \subseteq B \setminus C$ then A and C are disjoint

Assume the hypotheses

given: $A \subseteq B \setminus C$

goal:

A and C are disjoint

= $\lnot \exists x (x \in A \land x \in C)$

= $\forall x (x \notin A \lor x \notin C)$

= $\forall x (x \in A \rightarrow x \notin C)$

Let x be arbitrary

given: $A \subseteq B \setminus C$

goal: $x \in A \rightarrow x \notin C$

Assume the hypotheses

given: $A \subseteq B \setminus C$ , $x \in A$

goal: $x \notin C$

Formal Proof:

Let x be an arbitrary element of A and $A \subseteq B \setminus C$. It follows that x must belong to $B \setminus C$, so x must not be in C. Hence, If $A \subseteq B \setminus C$ and $x \in A$ then $x \notin C$. Since x is arbitrary, so If $A \subseteq B \setminus C$ then A and C are disjoint.

Ex-4

Note: In this exercise $P(A)$ means Power Set of A.

given: $A \subseteq P(A)$

goal: $P(A) \subseteq P(P(A))$ = $\forall x (x \in P(A) \rightarrow x \in P(P(A)))$

Let x be arbitrary

given: $A \subseteq P(A)$

goal: $x \in P(A) \rightarrow x \in P(P(A))$

Assume the hypotheses

given: $A \subseteq P(A)$, $x \in P(A)$

goal: $x \in P(P(A))$ = $x \subseteq P(A)$ = $\forall y (y \in x \rightarrow y \in P(A))$

Let y be arbitrary

given: $A \subseteq P(A)$, $x \in P(A)$

goal: $y \in x \rightarrow y \in P(A)$

Assume the hypotheses

given: $A \subseteq P(A)$, $x \in P(A)$, $y \in x$

goal: $y \in P(A)$

Since $x \in P(A)$

=> $x \subseteq A$

and Since $A \subseteq P(A)$

=> $x \subseteq P(A)$

and Since $y \in x$, so $y \in P(A)$

Formal Proof:

Let x be an arbitrary element of $P(A)$, it follows that $x \subseteq A$. Since $A \subseteq P(A)$, so $x \subseteq P(A)$ and hence $x \in P(P(A))$. It means if $A \subseteq P(A)$ and $x \in P(A)$ then $x \in P(P(A))$. Since x is arbitrary, it follows, if $A \subseteq P(A)$ then $P(A) \subseteq P(P(A))$

Ex-5

(a) Yes, the empty set $\emptyset$

(b) {$\emptyset$}

Ex-6(a)

given:

goal: if $x \neq 1$ then $\exists y (\frac{y+1}{y-2} = x)$

Assume the hypotheses

given: $x \neq 1$

goal: $\exists y (\frac{y+1}{y-2} = x)$

in order to prove it, we have to find a $y_0$ s.t. $\frac{y_0+1}{y_0-2} = x$

=> $y_0 + 1$ = $x(y_0 - 2)$

=> $y_0 + 1$ = $xy_0 - 2x$

=> $xy_0 - y_0$ = $1 + 2x$

=> $y_0$ = $\frac{1 + 2x}{x - 1}$

It is defined since $(x-1) \neq 0$.

Formal Proof:

Assume $y$ = $y_0$ = $\frac{1 + 2x}{x - 1}$

Now, $\frac{y+1}{y-2}$

= $\frac{y_0+1}{y_0-2}$

= $\frac{(\frac{1 + 2x}{x - 1}) + 1}{(\frac{1 + 2x}{x - 1}) - 2}$

= $\frac{1 + 2x + x - 1}{1 + 2x - 2x + 2}$

= $\frac{3x}{3}$

= $x$

Thus, If $x \neq 1$ then there exists a real number y s.t. $\frac{y+1}{y-2} = x$

Ex-6(b)

For $\frac{y+1}{y-2} = x$ to be true

$y$ = $\frac{1 + 2x}{x - 1}$

which is defined only when $(x-1) \neq 0$ => $x \neq 1$

Thus, if there exists a real number y s.t. $\frac{y+1}{y-2} = x$ then $x \neq 1$

Ex-7 Let x be an arbitrary real number and x > 2.

For a real number y = $\frac{x + \sqrt{x^2 - 4}}{2}$

$\sqrt{x^2 - 4}$ is defined because $x > 2$ => $x^2 > 4$ => $x^2 - 4 > 0$

Now, $y + \frac{1}{y}$

= $\frac{x + \sqrt{x^2 - 4}}{2}$ + $\frac{2}{x + \sqrt{x^2 - 4}}$

= $\frac{(x + \sqrt{x^2 - 4})(x + \sqrt{x^2 - 4}) + 4}{2(x + \sqrt{x^2 - 4})}$

= $\frac{x^2 + (x^2 - 4) + 2x\sqrt{x^2 - 4} + 4}{2(x + \sqrt{x^2 - 4})}$

= $\frac{2x^2 + 2x\sqrt{x^2 - 4}}{2(x + \sqrt{x^2 - 4})}$

= $x$

Thus, for any real number x, if x > 2, then there exists a real number y s.t. $y + \frac{1}{y}$ = x.

Ex-8

Note: $F$ in this ex means a Family of Sets.

given:

goal: if $A \in F$ then $A \subseteq \cup F$

Assume the hypotheses

given: $A \in F$

goal: $A \subseteq \cup F$ $\equiv$ $\forall x (x \in A \rightarrow x \in \cup F)$

Let x be arbitrary

given: $A \in F$

goal: $x \in A \rightarrow x \in \cup F$

Assume the hypotheses

given: $A \in F$, $x \in A$

goal: $x \in \cup F$ $\equiv$ $\exists y \in F (x \in y)$

Since, $x \in A$ and $A \in F$, so y = A satisfies the goal.

Formal Proof:

Suppose $A \in F$ and x be an arbitrary element of A. Since $\cup F$ is union of all the sets in $F$ and that includes A, it follows that $x \in \cup F$. Thus if $A \in F$ then $x \in A \rightarrow x \in \cup F$. Since x is arbitrary, hence If $A \in F$ then $A \subseteq \cup F$

Ex-9 Suppose $A \in F$ and x be an arbitrary element of $\cap F$. Since $\cap F$ is intersection of all sets in $F$, it follows that $x \in A$. In other words, If $A \in F$ and $x \in \cap F$ then $x \in A$. Since x is arbitrary, we can conclude that If $A \in F$ then $\cap F \subseteq A$

Ex-10

given: $F$ is a non-empty family of sets, B is a set, $\forall A \in F (B \subseteq A)$

goal: $B \subseteq \cap F$

Formal Proof:

Let x be an arbitrary element of B. Since $\forall A \in F (B \subseteq A)$, that is B is subset of each element of $F$, it follows that x must be an element of every set in $F$. So $x \in \cap F$. Hence $x \in B \rightarrow x \in \cap F$. Since x is arbitrary, Therefore $B \subseteq \cap F$

Ex-11

given:

goal: If $\emptyset \in F$ then $\cap F = \emptyset$

Assume the hypotheses

given: $\emptyset \in F$

goal:

$\cap F = \emptyset$

$\equiv$ $\lnot \exists x (x \in \cap F)$

$\equiv$ $\forall x \lnot (x \in \cap F)$

Let x be arbitrary

given: $\emptyset \in F$

goal:

$\lnot (x \in \cap F)$

$\equiv$ $\lnot \forall y (y \in F \rightarrow x \in y)$

$\equiv$ $\exists y (y \in F \land x \notin y)$

$y = \emptyset$ satisfies the goal, because no matter what x is, it can not be an element of $\emptyset$

Formal Proof:

Suppose $\emptyset \in F$. Now We will prove by contradiction that $\cap F = \emptyset$. Let x be an arbitrary element of $\cap F$, it follows that x must belong to every element of $F$. Since $\emptyset \in F$, so x should also belong to $\emptyset$ which is not possible, hence x can not belong to $\cap F$. Since x is arbitrary, we can conclude that If $\emptyset \in F$ then $\cap F = \emptyset$

Ex-12

Note: $F$ and $G$ are families of sets.

given:

goal: If $F \subseteq G$ then $\cup F \subseteq \cup G$

Suppose the hypotheses

given: $F \subseteq G$

goal: $\cup F \subseteq \cup G$

Formal Proof:

Suppose $F \subseteq G$ and Let x be an arbitrary element of $\cup F$. By definition of $\cup F$ it follows that there must be atleast one element A of $F$ s.t. $x \in A$. Since $F \subseteq G$, so A should be an element of $G$ also. That is we have $x \in A$ and $A \in G$, so $x \in \cup G$. Since x is arbitrary, Therefore If $F \subseteq G$ then $\cup F \subseteq \cup G$

Ex-13 Suppose $F \subseteq G$ and x be an arbitrary element of $\cap G$. By definition of $\cap G$ it follows that x must be an element of every element of $G$. Since $F \subseteq G$, therefore x must be an element of every element of $F$ also. So $x \in \cap F$. Thus If $F \subseteq G$ then $x \in \cap G \rightarrow x \in \cap F$. Since x is arbitrary, we can conclude that If $F \subseteq G$ then $\cap G \subseteq \cap F$

Ex-14

given:

goal:

$\cup_{i \in I}P(A_i) \subseteq P(\cup_{i \in I}A_i)$

$\equiv$ $\forall x (x \in \cup_{i \in I}P(A_i) \rightarrow x \in P(\cup_{i \in I}A_i))$

Let x be arbitrary

given:

goal: $x \in \cup_{i \in I}P(A_i) \rightarrow x \in P(\cup_{i \in I}A_i)$

Assume the hypotheses

given: $x \in \cup_{i \in I}P(A_i)$

goal: $x \in P(\cup_{i \in I}A_i)$

$\equiv$ $x \subseteq \cup_{i \in I}A_i$

Formal Proof:

Let x be an arbitrary element of $\cup_{i \in I}P(A_i)$. It follows, there should exist atleast one $k \in I$ s.t. $x \in P(A_k)$.

So $x \subseteq A_k$

=> $x \subseteq \cup_{i \in I}A_i$

=> $x \in P(\cup_{i \in I}A_i)$

Thus, if $x \in \cup_{i \in I}P(A_i)$ then $x \in P(\cup_{i \in I}A_i)$. Since x is arbitrary, we can conclude that $\cup_{i \in I}P(A_i) \subseteq P(\cup_{i \in I}A_i)$

Ex-15

given: $I \neq \emptyset$

goal: $\cap_{i \in I}A_i \in \cap_{i \in I}P(A_i)$

Let us try to see what it means for an arbitrary x to be an element of $\cap_{i \in I}P(A_i)$

$x \in \cap_{i \in I}P(A_i)$

=> $\forall i \in I (x \in P(A_i))$

=> $\forall i \in I (x \subseteq A_i)$

Formal Proof:

By definition of $\cap_{i \in I}A_i$ it follows that

$\forall i \in I (\cap_{i \in I}A_i \subseteq A_i)$

=> $\forall i \in I (\cap_{i \in I}A_i \in P(A_i))$

=> $\cap_{i \in I}A_i \in \cap_{i \in I}P(A_i)$

Ex-16

given:

goal: If $F \subseteq P(B)$ then $\cup F \subseteq B$

assume the hypotheses

given: $F \subseteq P(B)$

goal: $\cup F \subseteq B$

Formal Proof:

Suppose $F \subseteq P(B)$ and Let x be an arbitrary element of $\cup F$. By definition of $\cup F$ it follows that there exists atleast one $A \in F$ s.t. $x \in A$. Since $F \subseteq P(B)$, therefore $A \in P(B)$ is also true. It follows that $A \subseteq B$ and hence $x \in B$. Thus, If $x \in \cup F$ then $x \in B$. Since x is arbitrary, we conclude that If $F \subseteq P(B)$ then $\cup F \subseteq B$

Ex-17

given: $F$ and $G$ are non-empty family of sets, every element of $F$ is subset of every element of $G$

goal: $\cup F \subseteq \cup G$

Formal Proof:

Let x be an arbitrary element of $\cup F$. By definition of $\cup F$ it follows that there exists atleast on $A \in F$ s.t. $x \in A$. Since every element of $F$ is subset of every element of $G$, therefore A is subset of every element of $G$ and hence $A \subseteq \cup G$. So $x \in \cup G$. Since x is arbitrary, we conclude that $\cup F \subseteq \cup G$

Ex-18(a) Suppose a|b and a|c, so there exists atleast two integers $k_1$ and $k_2$ s.t.

$ak_1 = b$ ..... (i)

and

$ak_2 = c$ ..... (ii)

adding eq (i) and (ii) we get

$a(k_1 + k_2) = (b+c)$

since $k_1 + k_2$ is another integer, so a|(b+c).

Ex-18(b) Suppose ac|bc and $c \neq 0$. There exists an integer k s.t. ack = bc

=> ack - bc = 0

=> c(ak - b) = 0

Since $c \neq 0$, therefore (ak - b) = 0

=> ak = b

=> a|b

Ex-19

(a)Let x and y be arbitrary real numbers and z = $\frac{y-x}{2}$.

x + z

= x + $\frac{y-x}{2}$

= 2x + y - x

= y + x

and

y - z

= y - $\frac{y-x}{2}$

= 2y - y + x

= y + x

so x+z = y-z

Thus, for all real numbers x and y there exists a real number z such that x+z = y-z

(b) No, it wouldn't be justified as z = $\frac{y-x}{2}$ might not be an integer even though x and y are.

Ex-20 The flaw is in the conclusion that "for every real number x, $x^2$ < 0" because assumption of negation of the statement given in the theorem being true means just that "there exists atleast one real number x s.t. $x^2$ < 0.

Ex-21

(a) x being an arbitrary element of A does not mean its an arbitrary element of B also.

(b) A = {1}; B{0,1}

Ex-22 Given proof does not consider y to be arbitrary. For a particular value of x = $\frac{y}{y^2 + 1}$, there is only one(not all real number) real number y s.t. $xy^2 = y-x$

Ex-23

(a)
Let us focus on the second half of the proof given, which basically says $A \subseteq (\cup F \cap \cup G)$ contradicts $\cup F \cap \cup G = \emptyset$ because no such A can exist, which is not true.

Suppose $A = \emptyset$, then clearly both, $A \subseteq (\cup F \cap \cup G)$ and $\cup F \cap \cup G = \emptyset$, are true.

(b) A counter example is

$F$ = {$\emptyset$,{1}}

$G$ = {$\emptyset$,{3}}

Ex-24

(a) x and y are not considered completely arbitrary but equal.

(b) Theorem is incorrect. x = 2, y = 1 is a counterexample as $x^2 + xy -2y^2$

= 4 + 2 - 2

= 4, which is non-zero

Ex-25 Let x be an arbitrary real number and y = 2. Let z be an arbitrary real number.

$(x + z)^2 - (x^2 + z^2)$

= $x^2 + z^2 + 2z - x^2 + z^2$

= 2z

= yz

Thus, for every real number x there is a real number y s.t. for every real number z, yz = $(x + z)^2 - (x^2 + z^2)$

Ex-26

(a) For goals of the form $\forall x P(x)$ we can immediately initiate the proof by assuming x arbitrary and P(x) true. And for given of the form $$\exists x P(x)$ also we can immediately initiate the proof by assuming one $x_0$ that satisfies $P(x_0)$

For both, the goal of the form $\exists x P(x)$ and given of the form $\forall x P(x)$, we can not immediately start the proof unless we find a value $x_0$ of interest.

(b) Because negation of universal quantifier is existential quantifier and viceversa.

Subscribe to:
Post Comments (Atom)

Ex-5

ReplyDelete(b) Yes, the set {∅}.

Ex-23

ReplyDelete(a) The statement A ∈ F → A ⊆ ∪F is all right. I think the problem here is the last two statements. Since (∪F ∩ ∪G) = ∅ and A ⊆ (∪F ∩ ∪G), it follows that A = ∅, which is not a contradiction.

@Stavros : I agree, You're right in Ex-5(b) and Ex-23(a). Updating both in original post.

ReplyDeleteNice work

ReplyDelete