Sunday, May 16, 2010

how to prove it - ch3, sec3.5(Proofs Involving Disjunctions) ex

To use a given of the form PQ
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 PQ, 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 PQ. 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 ¬P 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 PQ

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 PQ = ¬PQ = ¬QP, 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 A(BC). Then xA and x(BC). Let us consider the two cases.
Case1: xB
Since xA and xB, so x(AB). Thus clearly x(AB)C

Case2: xC, clearly x(AB)C

Since x is arbitrary, we can conclude A(BC)(AB)C


Ex-2
Let x be an arbitrary element of (AB)\C. It follows that x(AB) and xC. Let us consider the two exhaustive cases

Case1: xA
clearly xA(B\C)

Case2: xB
Since xC and xB, so clearly x(B\C). Thus xA(B\C)

Since x is arbitrary, we can conclude (AB)\CA(B\C)


Ex-3
Let x be arbitrary. Then
xA\(A\B) iff
xA¬(x(A\B)) iff
xA¬(xAxB) iff
xA(xAxB) iff
(xAxA)(xAxB) iff
xAxB iff
x(AB)

Since x is arbitrary, we can conclude that A\(A\B) = AB


Ex-4
Let x be an arbitrary element of A. Let us consider 2 exhaustive cases

Case1: xC
Then, xAC. Since ACBC, therefore xBC and hence xB.

Case2: xC
Then, xAC. Since ACBC, therefore xBC. Since xC ,therefore xB.

Since x is arbitrary, we can conclude AB


Ex-5
Suppose ABA. Let x be an arbitrary element of B. We will prove by contradiction that xA. Assume xA. Since xB and xA, therefore xB\A, and then x(A\B)(B\A). Thus xAB. Since ABA, so xA should be true and that contradicts our assumption of xA. So the assumption is wrong and xA. Since x is arbitrary, we can conclude BA


Ex-6
() Suppose ACBC. Let x be an arbitrary element A\C. It follows that xA and xC and hence xAC. Since ACBC, so xBC. Since xC, therefore xB. Since x is arbitrary, we can conclude A\CB\C

() Suppose A\CB\C. Let x be arbitrary element of AC. Let us consider the two exhaustive cases

Case1: xC
clearly x(BC) also

Case2: xC
Since xAC and xC, it follows that xA and hence xA\C. Since A\CB\C, therefore xB\C and hence xB and therefore x(BC)

Since x is arbitrary, we can conclude ACBC


Ex-7
Suppose x be an arbitrary element of P(A)P(B). Let us consider the two exhaustive cases

Case1: xP(A)
then, xA. And then x(AB), so xP(AB)

Case2: xP(B)
then, xB. And then x(AB), so xP(AB)

Since x is arbitrary, we can conclude P(A)P(B)P(AB)


Ex-8
given:
goal: If P(A)P(B)=P(AB) then AB or BA

Assume the hypotheses

given: P(A)P(B)=P(AB)
goal: AB or BA If A is not subset of B then BA

Assume the hypotheses again

given: P(A)P(B)=P(AB) , ¬(AB)
goal: BA

Formal Proof:
Suppose P(A)P(B)=P(AB) and ¬(AB). Since ¬(AB), so we can chose a y s.t. yA and yB.

Now, We will prove by contradiction that BA. Let us assume that ¬(BA). Then we can chose a x s.t. xB and xA. Let us call C to be the set {x,y}. Clearly C is neither a subset of A nor that of B but CAB. However P(A)P(B)=P(AB) means, P(AB)P(A)P(B) and that means for any arbitrary set D, if DAB then either DA or DB. Since CAB, 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 ¬(BA) is false and it means BA.


Ex-9
y+1x = 1+yx iff
xy+1x = x+yx iff
xy+1 = x+y iff
xy-x-y+1=0 iff
x(y-1)-(y-1)=0 iff
(x-1)(y-1)=0 iff
(x-1)=0 or (y-1)=0 iff
x=1 or y=1


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 x2 > 6x

Case2: (x - 3) < 0
Since |x - 3| > 3, so -(x - 3) > 3
=> (x - 3) < -3
=> x < 0

therefore x2 > 0 but 6x < 0
so clearly x2 > 6x


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
=> x2 = 4k2
=> x2+x = 4k2+2k
=> x2+x = 2k(2k+1)

Since k(k+1) is an integer, thus x2+x is even

Case2: x is odd
Then there exists an integer k s.t. x = 2k + 1
=> x2 = (2k+1)2
=> x2 = 4k2+1+4k
=> x2+x = (4k2+1+4k)+(2k+1)
=> x2+x = 4k2+6k+2
=> x2+x = 2(2k2+3k+1)

Since (2k2+3k+1) is an integer, thus x2+x is even


Ex-14
Let us consider two exhaustive cases

Case1: x is even
Then there exists an integer k s.t. x = 2k
=> x4 = 16k4
=> x4 = 8(2k4)

Clearly x4 is divisible by 8. Thus remainder, when x4 is divided by 8, is 0

Case2: x is odd
Then there exists an integer k s.t. x = 2k + 1
=> x4 = (2k+1)4
=> x4 = (4k2+1+4k)2
=> x4 = 16k4+1+16k2+2(4k2+4k+16k3)
=> x4 = 16k4+1+24k2+8k+32k3
=> x4 = 8(2k4+4k3+3k2+k)+1

Clearly, remainder, when x4 is divided by 8, is 1

Thus, when x4 is divided by 8, remainder is either 0 or 1


Ex-15
(a)
Let x be an arbitrary element of (FG)

x(FG) iff
there exists a set A s.t.
xAA(FG) iff
xA(AFAG) iff
(xAAF)(xAAG) iff
xFxG iff
x(F)(G)

Since x is arbitrary, we can conclude that (FG) = (F)(G)

(b)
My conjecture is (FG) = (F)(G)

Proof:
Let x be an arbitrary element of (FG)

So x(FG)
=> A(AFGxA)
=> A(AFAGxA)
=> A(¬(AFAG)xA)
=> A((AFAG)xA)
=> A((AFxA)(AGxA))
=> [A(AFxA)][A(AGxA)]
=> [A(AFxA)][A(AGxA)]
=> (xF)(xG)
=> x(F)(G)

Since x is arbitrary, so (FG) = (F)(G)


Ex-16
(a)
()
Let x be an arbitrary element of B(F). Let us consider the two cases

Case1: xB
It follows that x{B}. And also x(F{B})

Case2: xF
Then, there exists a set AF s.t. xA, since AF{B} also. So x(F{B})

Since x is arbitrary, clearly B(F)(F{B})

()
Let x be an arbitrary element of (F{B}). Then there exists a set A(F{B}) s.t. xA. Let us consider the two cases

Case1: AF
Then xF and therefore xB(F)

Case2: A{B}
It means A = B, so xB and hence xB(F)

Since x is arbitrary, we conclude that (F{B})B(F)

Thus, B(F) = (F{B})

(b)
()
Let x be an arbitrary element of B(F). Let us consider the two cases

Case1: xB
Then for any set A, xBA. Thus for all AF, xBA and therefore xAF(BA)

Case2: xF
Then for all AF, xA. So xBA also and therefore xAF(BA)

Since x is arbitrary, we conclude that B(F)AF(BA)

()
Let x be an arbitrary element of AF(BA). Then for any AF, xBA. Let us consider the two cases

Case1: xB
Then xB(F) also.

Case2: xA
Since A any set in F. So xF and therefore xB(F)

Since x is arbitrary, we conclude that AF(BA)B(F)

Thus, B(F) = AF(BA)

(c)
My conjecture: B(F) = (F{B})

Proof:
Let x be an arbitrary element.

xB(F) iff
xBxF iff
xBAF(xA) iff
[A{B}(xA)][AF(xA)] iff
A(F{B})(xA) iff
x(F{B})

Since x is arbitrary, we can conclude B(F) = (F{B})


Ex-17
Let x be an arbitrary element of H. So for all sets CH, xC. Let A be an arbitrary element of F and B be an arbitrary element of G. Since ABH, so xAB. Let us consider the two cases

Case1: xA
Since A is arbitrary, so xF, Thus x(F)(G)

Case2: xB
Since B is arbitrary, so xG, Thus x(F)(G)

Since x is arbitrary, we can conclude H(F)(G)


Ex-18
Let x be arbitrary element of AB

xAB iff
x(AB)\(AB) iff
x(AB)¬(xAB) iff
(xAxB)¬(xAxB) iff
(xBxA)(xAxB) iff
(xBxA)(xAxB) iff
xAxB

Thus x(xAB(xAxB))


Ex-19
()
Suppose AB and C are disjoint.

Let x be an arbitrary element of AC. It follows that xA and xC. Since AB and C are disjoint and xC, so xAB. By definition of AB, either xAB or xAB. Since xA so xAB can not be true and hence xAB. Thus xB. Since xC and xB, so xBC. Since x is arbitrary, we can conclude ACBC

By exactly similar argument as above we can prove that BCAC. Thus AC = BC

()
Suppose AC = BC. Let x be an arbitrary element of AB. By definition of AB, xA\B or xB\A. We will prove by contradiction that xC. Let us assume that xC. Now consider the two cases

Case1: xA\B
It follows that xA and xB. Since xC also, so xAC. Since AC = BC, so xBC and hence xB but that contradicts our assumption for this case. Thus xC

Case2: xB\A
It follows that xB and xA. Since xC also, so xBC. Since BC = AC, so xAC and hence xA but that contradicts our assumption for this case. Thus xC.

Since above cases are the exhaustive set, so xC. Since x is arbitrary, we can conclude that AB and C are disjoint.


Ex-20
()
Suppose ABC. Let x be an arbitrary element of AC. It follows that xA or xC. Let us consider both the cases

Case1: xA
We'll prove by contradiction that xBC. Assume xBC, therefore xB and xC. Since xA and xB,
so xA\B
=> xAB

Since ABC
therefore xC, but this contradicts our assumption and hence xBC.

Case2: xC
so definitely xBC

Since x is arbitrary, we conclude that ACBC

By using an exactly similar argument we can prove that BCAC also. Thus AC = BC

()
Suppose AC = BC. Let x be an arbitrary element of AB. Then, either xA\B or xB\A. let us consider both the cases

Case1: xA\B
Then xA and xB. Since xA, so xAC also. And since AC = BC, so xBC. Since xB, so xC

Case2: xB\A
Then xB and xA. Since xB, so xBC also. And since BC = AC, so xAC. Since xA, so xC

From above cases, we can conclude that xC. Since x is arbitrary, so ABC


Ex-21
()
Suppose CAB.

Let x be an arbitrary element of C, then xAB. Thus xAB and xAB. So xAB. Since x is arbitrary, so CAB

Let x be an arbitrary element of xABC. Then xA and xB and xC. Since CAB, so xAB and then xA\B or xB\A. Let us consider both the cases

Case1: xA\B
Then xA and xB. But we already said that xB. This is a contradiction and such x can not exist

Case2: xB\A
Then xB and xA. But we already said that xA. This is a contradiction and such x can not exist

Hence a x s.t. xABC can not exist and hence ABC=

So if CAB then CAB and ABC=

()
Suppose CAB and ABC=. Let x be an arbitrary element of C. So xAB and hence xA or xB. Let us consider both the cases

Case1: xA
Since xC and xA, then xB as ABC=. Since xA and xB, so xA\B and hence xAB. Since x is arbitrary, we can conclude that CAB

Case2: xB
Since xC and xB, then xA as ABC=. Since xB and xA, so xB\A and hence xAB. Since x is arbitrary, we can conclude that CAB


Ex-22
(a)
Let x be an arbitrary element of A\C. Then xA and xC. Let us consider two cases

Case1: xB
Then xB\C, so x(A\B)(B\C)

Case2: xB
Then xA\B, so x(A\B)(B\C)

From two cases above, its clear that x(A\B)(B\C). Since x is arbitrary, so A\C(A\B)(B\C)

(b)
Let x be an arbitrary element of AC. Let us consider the two cases

Case1: xB
Since xAC, so xA\C or xC\A. Let us consider these cases further
Case-a: xA\C
Then xA and xC. Since xB and xC, so xB\C and hence xBC
Case-b: xC\A
Then xC and xA. Since xB and xA, so xB\A and hence xAB

So x(AB) or x(BC). Thus x(AB)(BC)

Case2: xB
Since xAC, so xA\C or xC\A. Let us consider these cases further
Case-a: xA\C
Then xA and xC. Since xB and xA, so xA\B and hence xAB
Case-b: xC\A
Then xC and xA. Since xB and xC, so xC\B and hence xBC

So x(AB) or x(BC). Thus x(AB)(BC)

Since x is arbitrary, so AC(AB)(BC)


Ex-23
(a)
Let x be an arbitrary element of (AB)C. It follows that either x(AB)\C or xC\(AB). Let us consider both the cases

Case1: x(AB)\C
Then x(AB) and xC. So, either xA\C or xB\C. Thus xAC or xBC. Hence x(AC)(BC)

Case2: xC\(AB)
Then xC and x(AB). Since x(AB), so xA and xB. Hence xC\A and xC\B. And therefore x(AC) and x(BC). So x(AC) or x(BC) also. Thus x(AC)(BC)

Since x is arbitrary, we can conclude that (AB)C(AC)(BC)

(b)
A = {3}
B = {4}
C = {3,4}


Ex-24
(a)
Let x be an arbitrary element of (AC)(BC). So xAC and xBC. xAC means either xA\C or xC\A. Similarly xBC means xB\C or xC\B. So following 4 cases are possible.

Case1: xA\C and xB\C
Then xA and xB and xC. Thus xAB and xC. So x(AB)\C. Hence x(AB)C

Case2: xA\C and xC\B
This case is not possible as xA\C suggests that xC while xC\B suggests xC

Case3: xC\A and xB\C
This case is also not possible for the same reason as above

Case4: xC\A and xC\B
Then xC and xA and xB. Since xA and xB, so xAB and then xAB also. Thus xC\(AB). Hence x(AB)C

From above cases, it is clear that x(AB)C. Since x is arbitrary, so we can conclude that (AC)(BC)(AB)C

(b)
Here is the counterexample
A = {3}
B = {4}
C = {3,4}

(AB)C = {3,4}
(AC)(BC) =


Ex-25
(A\B)C is not a subset of (AC)\(BC) and here is the counterexample
A = {1}
B = {2}
C = {3}

(A\B)C = {1,3}
(AC)\(BC) = {1}

and (AC)\(BC)(A\B)C, here is the proof
Let x be an arbitrary element of (AC)\(BC). It follows that xAC and xBC.
xAC means xA\C or xC\A
xBC means xBC or xBC

So there are 4 cases to consider

Case1: xA\C and xBC
It means xA and xC and xB. So x(A\B)\C, thus x(A\B)C

Case2: xA\C and xBC
This case is not possible as xA\C suggests that xC while xBC suggests xC

Case3: xC\A and xBC
This case is also not possible for the same reason as above

Case4: xC\A and xBC
It means xC and xA and xB. Since xA, so xA\B should also be true. Since xC and xA\B, therefore xC\(A\B). Thus x(A\B)C

From above cases, its clear that x(A\B)C. Since x is arbitrary, we can conclude that (AC)\(BC)(A\B)C

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 PQR

So, First strategy is to suppose that P and Q are true. Then we use existential instantiation on P that is ¬(AB). Later we get xA or xB, that is xAxB, since xA is known already so xB 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 PQ, but since x being real can be divided in to 2 exhaustive cases x=0 and x0, therefore the strategy of taking cases is used


Ex-29
Suppose xP(x)xQ(x)
=> ¬(xP(x))(xQ(x))
=> (x¬P(x))(xQ(x))
=> x(¬P(x)Q(x))
=> x(P(x)Q(x))

Thus if xP(x)xQ(x) then x(P(x)Q(x))


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 xA and xB, not xAxB. Same is the problem with the other one. (convincing enough??)


Ex-31
Prove that x(P(x)xP(x)).
TODO, no idea how to prove this. Is the given statement even correct?

10 comments:

  1. Ex-8
    A 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.

    ReplyDelete
  2. Ex-31
    It is correct. http://en.wikipedia.org/wiki/Drinker_paradox

    ReplyDelete
  3. I think for Q26 :
    Suppose |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.

    ReplyDelete
    Replies
    1. 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.

      Delete
  4. This comment has been removed by the author.

    ReplyDelete
  5. Thank 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?

    PROOF: 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. ▄

    ReplyDelete
  6. Ex-31 Can be proved as follows:
    Either 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.

    ReplyDelete
  7. Ex-31 Can be proved as follows:
    Either 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.

    ReplyDelete
  8. Could not figure out problem 8 by myself. I found your solution really clever. Thanks for posting these here.

    ReplyDelete
  9. It 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.
    Instead 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.

    ReplyDelete