To use a given of the form
Strategy#1:
In this case the proof can be broken into cases. So, form of the final proof looks like following
Case 1. P is true
[Proof of goal goes here]
Case 2. Q is true
[Proof of goal goes here]
Since we know , these cases cover all the possibilities. Therefore the goal must be true.
However, this is a general technique, you may find it useful to break proof into cases even if the cases are not directly suggested by a given of the form . Any proof can be broken into cases at any time, as long as the cases exhaust all of the possibilities. For example, if we're proving something about integers. We can assume the cases like "x is even, x is odd" or "x < 0, x = 0, x > 0".
Strategy#2:
If you are also given or if you can prove P to be false, then use this given to conclude that Q is true... viceversa is also true.
To prove a goal of the form
Strategy#1: In the place where we write "proof of the goal", we need to prove only one of P or Q.
Strategy#2: Since = = , we can apply the strategies of proofs involving conditionals. This suggests a rule of inference called disjunctive syllogism .
==============================================================================================
Ex-1
Let x be an arbitrary element of . Then and . Let us consider the two cases.
Case1:
Since and , so . Thus clearly
Case2: , clearly
Since x is arbitrary, we can conclude
Ex-2
Let x be an arbitrary element of . It follows that and . Let us consider the two exhaustive cases
Case1:
clearly
Case2:
Since and , so clearly . Thus
Since x is arbitrary, we can conclude
Ex-3
Let x be arbitrary. Then
iff
iff
iff
iff
iff
iff
Since x is arbitrary, we can conclude that =
Ex-4
Let x be an arbitrary element of A. Let us consider 2 exhaustive cases
Case1:
Then, . Since , therefore and hence .
Case2:
Then, . Since , therefore . Since ,therefore .
Since x is arbitrary, we can conclude
Ex-5
Suppose . Let x be an arbitrary element of B. We will prove by contradiction that . Assume . Since and , therefore , and then . Thus . Since , so should be true and that contradicts our assumption of . So the assumption is wrong and . Since x is arbitrary, we can conclude
Ex-6
() Suppose . Let x be an arbitrary element . It follows that and and hence . Since , so . Since , therefore . Since x is arbitrary, we can conclude
() Suppose . Let x be arbitrary element of . Let us consider the two exhaustive cases
Case1:
clearly also
Case2:
Since and , it follows that and hence . Since , therefore and hence and therefore
Since x is arbitrary, we can conclude
Ex-7
Suppose x be an arbitrary element of . Let us consider the two exhaustive cases
Case1:
then, . And then , so
Case2:
then, . And then , so
Since x is arbitrary, we can conclude
Ex-8
given:
goal: If then or
Assume the hypotheses
given:
goal: or If A is not subset of B then
Assume the hypotheses again
given: ,
goal:
Formal Proof:
Suppose and . Since , so we can chose a y s.t. and .
Now, We will prove by contradiction that . Let us assume that . Then we can chose a x s.t. and . Let us call C to be the set {x,y}. Clearly C is neither a subset of A nor that of B but . However means, and that means for any arbitrary set D, if then either or . Since , so C should either be a subset of A or that of B but both of these are already false and this is a contradiction. Therefore is false and it means .
Ex-9
= iff
= iff
= iff
iff
iff
iff
or iff
or
Ex-10
Suppose |x - 3| > 3. Let us consider the two exhaustive cases
Case1: (x - 3) 0
Since |x - 3| > 3, so (x - 3) > 3, then x > 6. On multiplying both sides with x we get >
Case2: (x - 3) < 0
Since |x - 3| > 3, so -(x - 3) > 3
=> (x - 3) < -3
=> x < 0
therefore > 0 but < 0
so clearly >
Ex-11
()
Suppose |2x - 6| > x. Let us consider the two cases
Case1: (2x - 6) 0
Then (2x - 6) > x
=> x - 6 > 0
=> x > 6
=> x - 4 > 2 , so (x - 4) is positive and hence |x - 4| = (x - 4)
=> |x - 4| > 2
Case2: (2x - 6) < 0
Then -(2x - 6) > x
=> 2x - 6 < -x
=> 3x < 6
=> x < 2
=> x - 4 < -2 , so (x - 4) is negative and hence |x - 4| = -(x - 4)
=> -(x - 4) > 2
=> |x - 4| > 2
()
Suppose |x - 4| > 2. Let us consider the two cases
Case1: (x - 4) 0
Then (x - 4) > 2
=> x > 6
=> x + x > 6 + x
=> 2x > 6 + x
=> 2x - 6 > x
Also since (x - 4) 0
=> x 4
=> x > 0
Since 2x - 6 > x and x > 0, so 2x - 6 > 0 and so |2x - 6| = (2x - 6)
hence |2x - 6| > x
Case2: (x - 4) < 0
Then -(x - 4) > 2
=> (x - 4) < -2
=> x < 2 ...(i)
=> 2x < 4
=> 2x - 6 < -2 and so 2x - 6 is negative and hence |2x - 6| = -(2x - 6)
Again x < 2
=> 3x < 6
=> 3x - 6 < 0
=> 2x - 6 < -x
=> -(2x - 6) > x
=> |2x - 6| > x
Ex-12
(a)
()
Suppose |a| b. Let us consider the two cases
Case1: a 0
then a b
Case2: a < 0
then -a b
=> a -b
So either a b or a -b and hence -b a b
()
Suppose -b a b. Let us consider the two cases
Case1: a 0
So , |a| = a
=> -b |a| b
=> |a| b
Case2: a < 0
So, |a| = -a
Since -b a b
=> b -a -b
=> b |a| -b
=> b |a|
=> |a| b
(b)
Above we proved |a| b iff -b a b
For any real number x
|x| = |x|
we could also say
|x| |x|
Let say a = x and b = |x|
Since -b a b
so -|x| x |x|
(c)
Let us consider following set of exhaustive cases
Case1: x 0 and y 0
Then |x| = x, |y| = y. Since (x + y) is also positive
So, |x + y| = x + y
=> |x + y| = |x| + |y|
Case2: x < 0 and y < 0
Then |x| = -x, |y| = -y. Since (x + y) is also negative
So, |x + y| = -(x + y)
=> |x + y| = -x + (-y)
=> |x + y| = |x| + |y|
Case3: x 0 , y < 0 , (x + y) 0
Then |x| = x, |y| = -y and |x + y| = (x + y)
=> |x + y| = |x| - |y|
Since |x| - |y| < |x| + |y|
So |x + y| < |x| + |y|
Case4: x 0 , y < 0 , (x + y) < 0
Then |x| = x, |y| = -y and |x + y| = -(x + y)
=> |x + y| = -|x| + |y|
Since -|x| + |y| < |x| + |y|
So |x + y| < |x| + |y|
Case5: x < 0, y 0 , (x + y) 0
Then |x| = -x, |y| = y and |x + y| = (x + y)
=> |x + y| = -|x| + |y|
=> |x + y| < |x| + |y|
Case6: x < 0, y 0 , (x + y) < 0
Then |x| = -x, |y| = y and |x + y| = -(x + y) = -x - y
=> |x + y| = |x| - |y|
=> |x + y| < |x| + |y|
Since above set of cases is exhaustive, hence |x + y| |x| + |y|
Ex-13
Let us consider two exhaustive cases.
Case1: x is even
Then there exists an integer k s.t. x = 2k
=> =
=> =
=> =
Since k(k+1) is an integer, thus is even
Case2: x is odd
Then there exists an integer k s.t. x = 2k + 1
=> =
=> =
=> =
=> =
=> =
Since is an integer, thus is even
Ex-14
Let us consider two exhaustive cases
Case1: x is even
Then there exists an integer k s.t. x = 2k
=> =
=> =
Clearly is divisible by 8. Thus remainder, when is divided by 8, is 0
Case2: x is odd
Then there exists an integer k s.t. x = 2k + 1
=> =
=> =
=> =
=> =
=> =
Clearly, remainder, when is divided by 8, is 1
Thus, when is divided by 8, remainder is either 0 or 1
Ex-15
(a)
Let x be an arbitrary element of
iff
there exists a set A s.t.
iff
iff
iff
iff
Since x is arbitrary, we can conclude that =
(b)
My conjecture is =
Proof:
Let x be an arbitrary element of
So
=>
=>
=>
=>
=>
=>
=>
=>
=>
Since x is arbitrary, so =
Ex-16
(a)
()
Let x be an arbitrary element of . Let us consider the two cases
Case1:
It follows that . And also
Case2:
Then, there exists a set s.t. , since also. So
Since x is arbitrary, clearly
()
Let x be an arbitrary element of . Then there exists a set s.t. . Let us consider the two cases
Case1:
Then and therefore
Case2:
It means A = B, so and hence
Since x is arbitrary, we conclude that
Thus, =
(b)
()
Let x be an arbitrary element of . Let us consider the two cases
Case1:
Then for any set A, . Thus for all , and therefore
Case2:
Then for all , . So also and therefore
Since x is arbitrary, we conclude that
()
Let x be an arbitrary element of . Then for any , . Let us consider the two cases
Case1:
Then also.
Case2:
Since A any set in . So and therefore
Since x is arbitrary, we conclude that
Thus, =
(c)
My conjecture: =
Proof:
Let x be an arbitrary element.
iff
iff
iff
iff
iff
Since x is arbitrary, we can conclude =
Ex-17
Let x be an arbitrary element of . So for all sets , . Let A be an arbitrary element of and B be an arbitrary element of . Since , so . Let us consider the two cases
Case1:
Since A is arbitrary, so , Thus
Case2:
Since B is arbitrary, so , Thus
Since x is arbitrary, we can conclude
Ex-18
Let x be arbitrary element of
iff
iff
iff
iff
iff
iff
Thus
Ex-19
()
Suppose and C are disjoint.
Let x be an arbitrary element of . It follows that and . Since and C are disjoint and , so . By definition of , either or . Since so can not be true and hence . Thus . Since and , so . Since x is arbitrary, we can conclude
By exactly similar argument as above we can prove that . Thus =
()
Suppose = . Let x be an arbitrary element of . By definition of , or . We will prove by contradiction that . Let us assume that . Now consider the two cases
Case1:
It follows that and . Since also, so . Since = , so and hence but that contradicts our assumption for this case. Thus
Case2:
It follows that and . Since also, so . Since = , so and hence but that contradicts our assumption for this case. Thus .
Since above cases are the exhaustive set, so . Since x is arbitrary, we can conclude that and C are disjoint.
Ex-20
()
Suppose . Let x be an arbitrary element of . It follows that or . Let us consider both the cases
Case1:
We'll prove by contradiction that . Assume , therefore and . Since and ,
so
=>
Since
therefore , but this contradicts our assumption and hence .
Case2:
so definitely
Since x is arbitrary, we conclude that
By using an exactly similar argument we can prove that also. Thus =
()
Suppose = . Let x be an arbitrary element of . Then, either or . let us consider both the cases
Case1:
Then and . Since , so also. And since = , so . Since , so
Case2:
Then and . Since , so also. And since = , so . Since , so
From above cases, we can conclude that . Since x is arbitrary, so
Ex-21
()
Suppose .
Let x be an arbitrary element of C, then . Thus and . So . Since x is arbitrary, so
Let x be an arbitrary element of . Then and and . Since , so and then or . Let us consider both the cases
Case1:
Then and . But we already said that . This is a contradiction and such x can not exist
Case2:
Then and . But we already said that . This is a contradiction and such x can not exist
Hence a x s.t. can not exist and hence
So if then and
()
Suppose and . Let x be an arbitrary element of C. So and hence or . Let us consider both the cases
Case1:
Since and , then as . Since and , so and hence . Since x is arbitrary, we can conclude that
Case2:
Since and , then as . Since and , so and hence . Since x is arbitrary, we can conclude that
Ex-22
(a)
Let x be an arbitrary element of . Then and . Let us consider two cases
Case1:
Then , so
Case2:
Then , so
From two cases above, its clear that . Since x is arbitrary, so
(b)
Let x be an arbitrary element of . Let us consider the two cases
Case1:
Since , so or . Let us consider these cases further
Case-a:
Then and . Since and , so and hence
Case-b:
Then and . Since and , so and hence
So or . Thus
Case2:
Since , so or . Let us consider these cases further
Case-a:
Then and . Since and , so and hence
Case-b:
Then and . Since and , so and hence
So or . Thus
Since x is arbitrary, so
Ex-23
(a)
Let x be an arbitrary element of . It follows that either or . Let us consider both the cases
Case1:
Then and . So, either or . Thus or . Hence
Case2:
Then and . Since , so and . Hence and . And therefore and . So or also. Thus
Since x is arbitrary, we can conclude that
(b)
A = {3}
B = {4}
C = {3,4}
Ex-24
(a)
Let x be an arbitrary element of . So and . means either or . Similarly means or . So following 4 cases are possible.
Case1: and
Then and and . Thus and . So . Hence
Case2: and
This case is not possible as suggests that while suggests
Case3: and
This case is also not possible for the same reason as above
Case4: and
Then and and . Since and , so and then also. Thus . Hence
From above cases, it is clear that . Since x is arbitrary, so we can conclude that
(b)
Here is the counterexample
A = {3}
B = {4}
C = {3,4}
= {3,4}
=
Ex-25
is not a subset of and here is the counterexample
A = {1}
B = {2}
C = {3}
= {1,3}
= {1}
and , here is the proof
Let x be an arbitrary element of . It follows that and .
means or
means or
So there are 4 cases to consider
Case1: and
It means and and . So , thus
Case2: and
This case is not possible as suggests that while suggests
Case3: and
This case is also not possible for the same reason as above
Case4: and
It means and and . Since , so should also be true. Since and , therefore . Thus
From above cases, its clear that . Since x is arbitrary, we can conclude that
Ex-26
The theorem given is correct. However the proof presented is not correct, as it actually proves that (x > 0) OR (x < 6) wherease what we want to prove is that (x > 0) AND (x < 6). It can be fixed as follows.
In Case1, the assumption is that (x - 3 0), so (x 3). And its concluded that (x < 6). So, from this case, we can conclude that (x 3) AND (x < 6)
Similarly from Case2, we can conclude that (x > 0) AND (x < 3)
Now, we can conclude that (0 < x < 6) (TODO: justify it)
Ex-27
The theorem as well as the proof given is correct.
Strategies:
Initial theorem is in the form
So, First strategy is to suppose that P and Q are true. Then we use existential instantiation on P that is . Later we get or , that is , since is known already so is established through that.
Ex-28
The theorem as well as the proof given are correct.
Notice that, even thought there is no explicit given of the form , but since x being real can be divided in to 2 exhaustive cases and , therefore the strategy of taking cases is used
Ex-29
Suppose
=>
=>
=>
=>
Thus if then
Ex-30
The theorem is incorrect. Here is the counterexample, A = {1,2} ; B = {0,1}; C = {2,3}
The flaw is in both cases. For example Case1 means and , not . Same is the problem with the other one. (convincing enough??)
Ex-31
Prove that .
TODO, no idea how to prove this. Is the given statement even correct?
Subscribe to:
Post Comments (Atom)
Ex-8
ReplyDeleteA shorter proof. Suppose P(A)∪P(B)=P(A∪B). Since A∪B ∈ P(A∪B), A∪B ∈ P(A)∪P(B). Then either A∪B ∈ P(A) or A∪B ∈ P(B). We will consider these cases separately.
Case 1. A∪B ∈ P(A). Then A∪B ⊆ A, so B⊆A.
Case 2. A∪B ∈ P(B). Then A∪B ⊆ B, so A⊆B.
Ex-31
ReplyDeleteIt is correct. http://en.wikipedia.org/wiki/Drinker_paradox
I think for Q26 :
ReplyDeleteSuppose |x - 3| < 3 and x ∈ ℝ. There are 2 cases.
1. x - 3 ≥ 0, hence x ≥ 3. Thus |x - 3|= x - 3. It follows that x < 6 from |x - 3| < 3. Thus if x ≥ 3 then x > 0 and x < 6.
2. x - 3 < 0. Hence x < 3. And |x - 3| = 3 - x. It follows that x > 0 from |x - 3| < 3. Thus if x < 3 then x < 6 and x > 0.
Since both cases conclude with 0 < x < 6, we can deduce that if |x -3| < 3 then 0 < x < 6.
You're right. On re-reading my proof, I guess, I kept it too short for others to follow but it is essentially the same as yours with a lot of steps skipped. Thanks.
DeleteThis comment has been removed by the author.
ReplyDeleteThank you for doing this and posting. This is really a tremendous resource that gets me going when I get stumped, as we use this text in class. To show that I am motivated to think by reading your work rather than do just what you have done, I propose the following for Q8. It doesn't involve negation or arbitrary sets. Does it seem rigorous to you?
ReplyDeletePROOF: Suppose A and B are sets such that P(A) ∪ P(B) = P(A ∪ B).
Case 1: A ⊆ B. Trivial.
Case 2: A ⊈ B. Suppose X is an arbitrary element such that x ∈ A and x ∉ B. Suppose y is an arbitrary element such that y ∈ B and y ∉ A. By definition of union, {x,y} ∈ p(A ∪ B). Since P(A) ∪ p(B) = P(A ∪ B), {x,y} ⊆ P(A) or {x,y} is subset P(B). Since x ∉ B, {x,y} ⊆ P(A). This contradicts our assumption that y ∉ A. Then by contradiction, if y ∈ B then y ∈ A. By definition of subset, B ⊆ A. ▄
Ex-31 Can be proved as follows:
ReplyDeleteEither P is a tautology or it is not.
If P is a tautology, then the implication can not be false since left and right side of arrow will always be true, so the implication must be true.
If P is not a tautology, then there exists an x for which P(x) is false. For this x the implication can not be false, since it is impossible for the right side of the arrow to be true while the left side is false. Hence, the implication is true in this case as well. Since the cases are exhaustive, the proof is complete.
Ex-31 Can be proved as follows:
ReplyDeleteEither P is a tautology or it is not.
If P is a tautology, then the implication can not be false since left and right side of arrow will always be true, so the implication must be true.
If P is not a tautology, then there exists an x for which P(x) is false. For this x the implication can not be false, since it is impossible for the right side of the arrow to be true while the left side is false. Hence, the implication is true in this case as well. Since the cases are exhaustive, the proof is complete.
Could not figure out problem 8 by myself. I found your solution really clever. Thanks for posting these here.
ReplyDeleteIt turns out there are a couple major mistakes in your solution to 3.5.17. To be specific, you took an arbitrary A in F and assumed that x is an element of A, then you used this assumption to wrongly conclude that for all A in F x is an element of A. This is a mistake. You've only proven that for all A in F, x is an element of A implies that x is an element of A. Obviously this is a tautology.
ReplyDeleteInstead of breaking the problem into the two cases you chose (ie Case 1:x is an element of A and Case 2: x is an element of B), you should have chosen a different pair of cases. Namely. Case 1 would be that there is a set A in F such that x is not an element of A, and Case 2 would be that there is not a set A in F such that x is not an element of A.