If...Then as element of a superset

What is the basis for reason? And mathematics?

Moderators: AMod, iMod

Post Reply
ProfAlexHartdegen
Posts: 20
Joined: Mon Jul 31, 2017 5:43 pm

If...Then as element of a superset

Post by ProfAlexHartdegen »

okay, again from the Logic Book there is something I don't understand - I'll quote the discussion with the part that confuses me bolded:

"6.4.11: If Γ* is maximally consistent in SD and P and Q are sentences of SL, then:

a. ~P ∈ Γ* if and only if P ∉ Γ*

b. P & Q ∈ Γ* if and only if both P ∈ Γ* and Q ∈ Γ*

c. P ∨ Q ∈ Γ* if and only if either P ∈ Γ* or Q ∈ Γ*

d. P ⊃ Q ∈ Γ* if and only if either P ∉ Γ* or Q ∈ Γ*

e. P ≡ Q ∈ Γ* if and only if either P ∈ Γ* and Q ∈ Γ*, or P ∉ Γ* and Q ∉ Γ* "



So, what confuses me is part d. - how is it that P could not be an element of the superset and yet P ⊃ Q ∈ Γ* ??? What is the reasoning for that? :?:
User avatar
Arising_uk
Posts: 12314
Joined: Wed Oct 17, 2007 2:31 am

Re: If...Then as element of a superset

Post by Arising_uk »

Is it because it doesn't matter for the material conditional to be true what P is if Q is true, that is P could be any other element or even no element of the set?
ProfAlexHartdegen
Posts: 20
Joined: Mon Jul 31, 2017 5:43 pm

Re: If...Then as element of a superset

Post by ProfAlexHartdegen »

I was thinking about that after I published my original post.

The conditional is true for only three cases: When both P and Q are true, when P is false and Q is true, or when P is false and Q is false. The fourth case is when P is true and Q is false.

If the truth of the conditional is all that's necessary then maybe that's why it's okay for P to be false and not an element of the set?

I forgot to mention ( at least I think they mean) that to be maximally consistent then the the members of the set must all be true.
Averroes
Posts: 535
Joined: Thu Jul 20, 2017 8:48 pm

Re: If...Then as element of a superset

Post by Averroes »

ProfAlexHartdegen wrote: Wed Aug 30, 2017 2:11 pm So, what confuses me is part d. - how is it that P could not be an element of the superset and yet P ⊃ Q ∈ Γ* ??? What is the reasoning for that? :?:
A maximally consistent set is one that is consistent and complete.
There are various definitions of maximally consistent but they are all equivalent. How does your book defines it?

I choose the following definitions:

A set Γ is consistent if and only if there is no formula φ such that φ ∈ Γ & ~φ ∈ Γ.
A set Γ is complete if and only if for all formula φ, either φ ∈ Γ v ~φ ∈ Γ.

Combining these two we get:
A maximally consistent set of sentences/theory Γ is such that for all sentences φ, either φ ∈ Γ v ~φ ∈ Γ, but not both.
Last edited by Averroes on Wed Sep 06, 2017 12:23 am, edited 1 time in total.
ProfAlexHartdegen
Posts: 20
Joined: Mon Jul 31, 2017 5:43 pm

Re: If...Then as element of a superset

Post by ProfAlexHartdegen »

Thanks again for your detailed replies -they are very helpful. 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 Logic Book does discuss maximal consistency. It describes it as:

"A maximally consistent set is, intuitively, a consistent set that contains as many sentences as it can without being inconsistent in SD: A set Γ of sentences of SL is maximally consistent in SD if and only if Γ is consistent in SD and, for every sentence P of SL that is not a member of Γ, Γ ∪ {P} is inconsistent in SD."

They discuss a "Maximal Consistency Lemma: If Γ is a set of sentences of SL that is consistent in SD, then Γ is a subset of at least one set of sentences that is maximally consistent in SD."

Also, this discussion: "It remains to be shown that for every set that is maximally consistent in SD we can construct a truth value assignment on which all the sentences in the set are true. From this we have following: the Consistency Lemma: Every set of sentence of SL that is maximally consistent in SD is truth functionally consistent"

As for the Paradox of Material Implication I can't find it listed in the Index and I don't recall reading about it so far. They do discuss Implication: P ⊃ Q ⊲⊳ ~P ∨ Q.

I obtained a copy of the solutions manual for this book (I bought it used) so I will be sure to study the solved problems to help me improve my knowledge of developing Proofs. Thanks again I do appreciate it very much!
Averroes
Posts: 535
Joined: Thu Jul 20, 2017 8:48 pm

Re: If...Then as element of a superset

Post by Averroes »

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.
ProfAlexHartdegen
Posts: 20
Joined: Mon Jul 31, 2017 5:43 pm

Re: If...Then as element of a superset

Post by ProfAlexHartdegen »

Thanks again for your time and effort and willingness to help, sorry for the slow reply it took me time to read your post carefully to see if I could understand. I think that I do.

One point to thank you especially because my book did not discuss The transposition/contraposition rule: (P ≡ Q) ≡ (~Q ≡ ~P). I penciled a little note next to the table summaries in the book because it seems such a simple and obvious one to include in the book that I'm surprised they didn't include it at this level. I'm sure it will help me to follow proofs and make them simpler!

Once again your time and assistance are appreciated always! Have a good weekend!

One last question: Do you recommend any logic book for beginners that might include the paradox for material implication and the contraposition rule above. Now I begin to see that although my book is a fairly good book for beginning students of Logic, it seems to omit some important logical rules and tools for solving proofs.
Averroes
Posts: 535
Joined: Thu Jul 20, 2017 8:48 pm

Re: If...Then as element of a superset

Post by Averroes »

ProfAlexHartdegen wrote:my book did not discuss The transposition/contraposition rule: (P ≡ Q) ≡ (~Q ≡ ~P). I penciled a little note next to the table summaries in the book because it seems such a simple and obvious one to include in the book that I'm surprised they didn't include it at this level. I'm sure it will help me to follow proofs and make them simpler!
The contraposition rule has been known since the time of Aristotle. When contraposition is discussed, it is discussed in relation to implication. There is another related concept with which it is often mentioned alongside, it is the concept of converse. Both these concepts concern implication.
If we have an implication of the form P ⊃ Q then its converse is Q ⊃ P.

And now it is easy to see that contraposition also applies to the biconditional as the biconditional is defined as the conjunction of an implication and its converse, i.e. P ≡ Q := ( P ⊃ Q) & (Q ⊃ P). ":=" is the symbol for definition.

Contraposition of ( P ⊃ Q) ≡ (~Q ⊃ ~P)
Contraposition of ( Q ⊃ P) ≡ ( ~P ⊃ ~Q)

By the definition of equivalence, (~Q ≡ ~P) :=(~Q ⊃ ~P) & ( ~P ⊃ ~Q).

Note here, that in the case of the implication, the implication of the form ( P ⊃ Q) is different than the implication of the form ( Q ⊃ P).
But the biconditional of the form (P ≡ Q) has the same meaning as the biconditional of the form (Q ≡ P). You can check their truth table to verify that they have the same meaning.

As an aside, about the proof in my previous post did you notice that it is a different method than the proofs you have been doing so far. For proofs of (c) to (e) I have been substituting subformulas of already proved statements with equivalent formulas and using the method of substitution to arrive at (c) to (e). For the proofs (c) to (e), I find an analogy in mathematics in the method of proving identities. In the wake of the proof, I found it to make intuitive sense (not a proof though) that the statements (a) to (e) are related to each other like this because each of the sentential connectives, i.e. ⊃, &, v, ~, ≡, are inter-definable. For example with either of the sets of connectives {~,v}, or {~,&}, or {~, ⊃ }, we can express the meaning (i.e. the truth table) of the other connectives. Because of this, each of these sets is said to have the property of expressive completeness.


Once again your time and assistance are appreciated always! Have a good weekend!
Thank you, I hope you had a nice weekend too.

I have spent some time today in experimenting with how to make forums such as this one, more maths and logic friendly. And I thank God, the Almighty that my efforts have paid off. I created a forum on the model of this forum and started to experiment with the various possibilities; tell me what you think: http://philosophyforum.aba.ae/viewtopic.php?f=4&t=3
ProfAlexHartdegen
Posts: 20
Joined: Mon Jul 31, 2017 5:43 pm

Re: If...Then as element of a superset

Post by ProfAlexHartdegen »

I think it is a great idea, averroes! I recommend subforums for Philosophy of Science, Philosophy of Language and Philosophy of History also. :D
Post Reply