ProfAlexHartdegen wrote: ↑Sun Sep 03, 2017 1:19 am
I am still developing my understanding of the Proofs. I will try to do the Proofs for the remaining parts and present them here for you to evaluate.
The following proofs is how I think it should be done.
(a) If Γ* is maximally consistent then ~P∈Γ* if and only if P ∉ Γ*
The proof for that was good, but I rewrite it thus:
Proof:
Assume Γ* is maximally consistent
Firstly prove: if ~P∈Γ* then P ∉ Γ*.
Assume ~P∈Γ*. Since Γ* is maximally consistent, it follows that P ∉ Γ*; if it was not the case, then ~P∈Γ* and P ∈ Γ* and therefore Γ* would be inconsistent and that would be a contradiction since Γ* was assumed to maximally consistent.
Secondly prove: if P ∉ Γ then ~P∈Γ*.
Assume P ∉ Γ, which means ~(P∈Γ*). Since Γ* is maximally consistent, it follows ~P∈Γ*. If it was not the case, then P ∉ Γ and ~P ∉ Γ* and therefore Γ* would not be complete and that would be a contradiction since Γ* was assumed to maximally consistent.
Hence (a) is proved.
(b) If Γ* is maximally consistent then P & Q ∈ Γ* if and only if both P ∈ Γ* and Q ∈ Γ*.
Proof
Assume Γ* is maximally consistent
If Γ* is maximally consistent then if Γ* Ͱ A then A ∈ Γ*. Proof: Γ* Ͱ A implies Γ*∪ {~A} is inconsistent. Since Γ* is maximally consistent and is a subset of Γ*∪ {~A}, then A ∈ Γ*.
Assume P & Q ∈ Γ*. Since P & Q ∈ Γ*, therefore by two application of &Elimination rule (&E) to Γ*, Γ* Ͱ P and Γ* Ͱ Q. Since Γ* is maximally consistent, therefore P ∈ Γ* and Q ∈ Γ*.
Assume P ∈ Γ* and Q ∈ Γ*, by an application of &Introduction rule to Γ*, Γ* Ͱ P & Q. Since Γ* is maximally consistent, P & Q ∈ Γ*.
Hence (b) is proved.
c. If Γ* is maximally consistent then P ∨ Q ∈ Γ* if and only if either P ∈ Γ* or Q ∈ Γ*.
To prove (c) we are going to use (b). We will use contraposition and substitution to prove (c) from (b).
The transposition/comtraposition rule:
"≡" is the symbol for the biconditional (i.e. if and only if)
(P ⊃ Q) ≡ (~Q ⊃ ~P)
Also,
(P ≡ Q) ≡ (~Q ≡ ~P)
So whenever we have '(P ⊃ Q)' in a formula, we can replace it by its contrapositive '(~Q ⊃ ~P)'.
And whenever we have '(P ≡ Q)' in a formula, we can replace it with its contrapositive '(~Q ≡ ~P)'
Proof:
Assume Γ* is maximally consistent
Code: Select all
1. (P & Q ∈ Γ*) ≡ (P ∈ Γ* and Q ∈ Γ*) (b) is already proved
2. ~(P ∈ Γ* and Q ∈ Γ*) ≡ ~(P & Q ∈ Γ*) 1, contrapositive
3. (P ∉ Γ* v Q ∉ Γ*) ≡ ~(P & Q ∈ Γ*) 2, De Morgan on left hand side
4. (~P∈ Γ* v ~Q ∈ Γ*) ≡ (~(P & Q) ∈ Γ*) 3, Maximally consistent def
5. (~P∈ Γ* v ~Q ∈ Γ*) ≡ (~P v ~Q ∈ Γ*) 4, DeMorgan on right hand side
6. (~(~P)∈ Γ* v ~(~Q)) ∈ Γ* ≡ (~(~P) v ~(~Q) ∈ Γ*) 5, substtitution of ~P for P and ~Q for Q
7. (P ∈ Γ* v Q ∈ Γ*) ≡ (P v Q ∈ Γ*) 6, Subformula double negation
8. (P v Q ∈ Γ*) ≡ (P ∈ Γ* v Q ∈ Γ*) 7, 'S ≡ V' is equivalent to 'V≡ S',i.e. swapping of arguments
Line 8 is (c). So (c) is proved from a sequence of transformations on (b).
(d) If Γ* is maximally consistent then P⊃Q ∈ Γ* iff P ∉ Γ* or Q ∈ Γ*.
(d) is proved from (c) by substitution and by using the formula you gave in the previous post: P ⊃ Q ⊲⊳ ~P ∨ Q.
The previous proof for (d) in my previous post was not how it should be done. In the previous post for (d), the method was wrong. So forget about it. Here is the correct proof for (d).
Proof:
Γ* is maximally consistent
Code: Select all
1. (P v Q ∈ Γ*) ≡ (P ∈ Γ* v Q ∈ Γ*) (c), already proved
2. ((~P) v Q ∈ Γ*) ≡ ((~P) ∈ Γ* v Q ∈ Γ*) 1, substitute ~P for P throughout
3. (P ⊃ Q ∈ Γ*) ≡ (~P ∈ Γ* v Q ∈ Γ*) 2, replace (~P v Q) by (P ⊃ Q); equivalence P ⊃ Q ⊲⊳ ~P ∨ Q.
4. (P ⊃ Q ∈ Γ*) ≡ (P ∉ Γ* v Q ∈ Γ*) Since Γ* maximally consistent, ~P ∈ Γ* implies P ∉ Γ* by (a)
Line 4 is (d). Hence (d) is proved.
(e) If Γ* is maximally consistent then P ≡ Q ∈ Γ* iff P ∈ Γ* and Q ∈ Γ* or P ∉ Γ* and Q ∉ Γ*.
Proof:
Assume Γ* is maximally consistent
Code: Select all
1. (P & Q ∈ Γ*) ≡ (P ∈ Γ* and Q ∈ Γ*) (b) is already proved
2. ((P ⊃ Q) & (Q ⊃ P) ∈ Γ*) ≡ ((P ⊃ Q) ∈ Γ* and (Q ⊃ P) ∈ Γ*) 1, substitute 'P ⊃ Q' for 'P' and 'Q ⊃ P' for 'Q' in (b)
3. (P ≡ Q ∈ Γ*) ≡ ((P ⊃ Q) ∈ Γ* and (Q ⊃ P) ∈ Γ*) 2, replace '((P ⊃ Q) & (Q ⊃ P) ∈ Γ*)' with (P ≡ Q ∈ Γ*), def of '≡'
4. (P ≡ Q ∈ Γ*) ≡ (P ∉ Γ* v Q ∈ Γ*) and (Q ⊃ P) ∈ Γ*) 3, using (d), '(P ⊃ Q) ∈ Γ*' is equivalent to '(P ∉ Γ* v Q ∈ Γ*)'
5. (P ≡ Q ∈ Γ*) ≡ (P ∉ Γ* v Q ∈ Γ*) and (Q ∉ Γ* v P ∈ Γ*) 4, using (d), (Q ⊃ P ∈ Γ*) ≡ (Q ∉ Γ* v P ∈ Γ*)
6. ~(P ≡ Q ∈ Γ*) ≡ ~((P ∉ Γ* v Q ∈ Γ*) and (Q ∉ Γ* v P ∈ Γ*)) 5, contrapositive
7. ~(P ≡ Q ∈ Γ*) ≡ ~(P ∉ Γ* v Q ∈ Γ*) v ~(Q ∉ Γ* v P ∈ Γ*) 6, DeMorgan on RHS
8. ~(P ≡ Q ∈ Γ*) ≡ (~(P ∉ Γ*) and ~(Q ∈ Γ*)) v (~(Q ∉ Γ*) and ~(P ∈ Γ*)) 7, DeMorgan on RHS
9. ~(P ≡ Q ∈ Γ*) ≡ (P ∈ Γ*) and ~(Q ∈ Γ*) v (Q ∈ Γ*) and ~(P ∈ Γ*)) 8, Subformula Double negation
10.~(P ≡ Q ∈ Γ*) ≡ (P ∈ Γ* and ~Q ∈ Γ*) v (Q ∈ Γ* and ~P ∈ Γ*) 9, since Γ* maximally consistent, on RHS ~(Q ∈ Γ*) implies ~Q ∈ Γ*,
and ~(P ∈ Γ*) implies ~P ∈ Γ*
11. (P ≡ ~Q ∈ Γ*) ≡ (P ∈ Γ* and ~Q ∈ Γ*) v (Q ∈ Γ* and ~P ∈ Γ*) 10, replace ~(P ≡ Q ∈ Γ*) by its equivalent: (P ≡ ~Q ∈ Γ*)
12. (P ≡ Q ∈ Γ*) ≡ (P ∈ Γ* and Q ∈ Γ*) v (~Q ∈ Γ* and ~P ∈ Γ*) 11, substitute 'Q' for '~Q' throughout
13. (P ≡ Q ∈ Γ*) ≡ (P ∈ Γ* and Q ∈ Γ*) v (Q ∉ Γ* and P ∉ Γ*) 12, since Γ* max. con., ~Q ∈ Γ* implies Q ∉ Γ*,
and ~P ∈ Γ* implies P ∉ Γ*
Line 13 is (e). Hence (e) is proved.
Note: Re-reading the post, I found some typing mistakes, which I corrected. If you find others let me know, I will correct it. Such mistakes can make the proofs difficult to understand sometimes.