Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Correct way to understand logical implication?

  1. Feb 23, 2017 #1
    If an object type ◌ exists and within the set of these objects exist some which have both well defined properties A and B, and some which only have the property A. There is at least one ◌ which does not have both properties.

    Thus say we create the set of such objects such that A or B (inclusive or) is true. And we create the set of ◌ such that property B is true. It then becomes that:
    [tex]\left \{ \cdot | B(\cdot ) = true \right \} \subset \left \{ \cdot | B(\cdot ) \vee A(\cdot ) = true \right \} [/tex]

    We can then say that A is a necessary but not sufficient condition for B. If there do not exist any where only one of a or b apply then:
    [tex]\left \{ \cdot | B(\cdot ) = true \right \} = \left \{ \cdot | B(\cdot ) \vee A(\cdot ) = true \right \} [/tex]

    In which case it becomes that A is a necessary and sufficient condition for B. Or, b is a neccesarry or sufficient condition for A. (due to symmetry of equivalence).
  2. jcsd
  3. Feb 23, 2017 #2


    User Avatar
    Gold Member

    It could be that I am misinterpreting your notation, so please correct me as I go. First, I assume there are brackets around "A(.)∨B(.)", and that there is an understood evaluation operator , so that , for example, we are talking about {.|val[(B(.)∨A(.))] = true}, or something like that.
    Next, I am not quite sure how your subject line relates to your development. What is supposed to be implying what?
    Next, in your development, suppose we have B being a tautology and A a contradiction. In this case, your line
    would be correct, yet I find it difficult to imagine
    as one usually interprets "necessary and sufficient" to mean mutual implication. That is, you seem to require a contradiction and a tautology to be equivalent (under mutual implication).
    Please clarify.
  4. Feb 23, 2017 #3
    Yes, there are brackets.

    Sorry, b(*) simply means some proposition in which the * is the object in place of the variable...kind of like p(x): x is an even number...

    in my case I am trying to generalise for two properties/propositions for which the object in oplace of the variable gives a truth value of true.
    Last edited: Feb 23, 2017
  5. Feb 23, 2017 #4


    User Avatar
    Gold Member

    OK so far.

    Your (.) was clear; I had no question about that.

    If I understand what you mean here, you are saying that yes, there is a valuation function understood.

    So, up to here, we are just talking about your notation which, although a bit loose, I nonetheless understood. However, the rest of my questions remain in place. I still need to understand why you are not saying that "0=0"⇔"1=0" according to the situation I proposed in my first answer. We could perhaps start from https://en.wikipedia.org/wiki/Necessity_and_sufficiency
  6. Feb 23, 2017 #5
    hmm yes I read it but I was thinking in purely set theoretic terms, eg..

    take the set of numbers which are natural and even (two well defined properties) make sets of their properties...
    Set C in reals such that A(x) : x is a natural number. (property, well defined)
    Set D in reals such that B(x) : is an even number. (property, well defined)

    A(x): x is a natural number. being true is a necessary but not sufficient condition for B(x):is an even number..

    This is because the set of even numbers is a subset of Natural numbers.

    So I was wondering whether my reasoning could NOT be extended to all general situations, where A and B are two properties with truth values..? or is this not the correct way to think about logical implication?
    Last edited: Feb 23, 2017
  7. Feb 23, 2017 #6


    User Avatar
    Gold Member

    First, a technicality.
    Actually, no, the set of non-negative even numbers is a subset of the set of natural numbers. (Or, taking the definition of natural numbers as excluding zero, as do American and British secondary schools, then the set of positive even numbers....)

    Anyway, let's suppose you meant that. I think I see where your difficulty arises.

    About the set theoretical context: you may be interested in looking up the connections between "material conditional" and "semantic consequence". You have thrown the semantic and syntactic meanings together. "B is a non-zero even number " ⇒ "A is a natural number " is a syntactic statement, and the semantic interpretation is of one set interpreting the first statement being a subset of another set interpreting the second statement. Yes, the syntactic ∨ can be interpreted with the set theoretic union, which is where you end up saying that the union of the interpretations of the two sentences is equal to the set of natural numbers, and you then put equality of these sets to correspond to ⇔ on the syntactic level. This doesn't work, and I will explain tomorrow evening (in my time zone it's evening as I write this) (unless someone else beats me to it), but I must go now.

    Till then.
  8. Feb 23, 2017 #7
    ok, thank you.
  9. Feb 23, 2017 #8
    if it helps to understand my mistake...and prevent confusion...I am saying the property used to define larger set is the neccesary but not sufficient condition for an element of the subset defined:
    1. for the larger sets property AND containing another one.

    My thinking:
    - natural numbers including 0 contain the set of even positive integers. So choosing a natural number is a necessary but not sufficient condition to have chosen an even positive integer.

    - The set of differentiable functions contain the subset of all continuous and differentiable functions, so differentiatiability is a necessary but not sufficient condition.

    - The set of integrable functions contain the subset of all continuous and integrable functions, so integrability is a necessary but not sufficience condition for continouty.

    - The set of all people studying some physics topics in college contains a subset of people who hate physics and are studying it in college. So studying physics is a necessary but not sufficient condition to hate it?
    Last edited: Feb 23, 2017
  10. Feb 23, 2017 #9
    I'm taking a predicate logic course right now ("Introduction to Mathematical Thinking," a MOOC designed by Keith Devlin), so I have a tiny tiny tiny tiny bit of practice with the sort of logic used for proofs. We have recently added sets a little more than half-way through the course.

    What I wonder, with statements such as the above, is why you wouldn't do something much simpler, and simply specify a domain - that is, use quantifiers - for whatever variables you're working with; or just specify a subset's properties as such, if working with sets?

    Put more broadly, what's the larger purpose here? If it's to play w/ a few things as a way to understand "necessary and sufficient", with or without a context that includes sets, there are books, courses, good web sites, etc. that might help. Me, as a beginner I like http://abstractmath.org for a web site and Hammack's The Book of Proof for a book.
    Last edited: Feb 23, 2017
  11. Feb 24, 2017 #10


    User Avatar
    Gold Member

    Logical Dog:
    As it is expressed now, it doesn’t work, but made I will show you how, cleaning up everything up, you can put your ideas in a form that you can develop further. UsableThought's idea to put everything down in clear notation is a good one. I will nonetheless try to explain all notation, because I do not know how familiar you are with the symbolism. Forgive me if it sounds a bit pedantic, but the devil lies in the details. Let me introduce a couple of basic concepts in a rough way; you can easily find the details on the net. A theory is a collection of sentences composed of symbols which obey certain grammatical rules. Purely syntactical. A sentence is a formula with no free variables; that is, if you have a variable, then it is governed by a quantifier such as “for all” or “there exists”

    Here we get to the main part of your difficulty. You refer to a property as being true. A property is not a sentence. A property cannot be true or false. To justify that, I need to define “true”, which links syntax with semantics.

    Many amusing paradoxes arise out of the confusion between syntax and semantics. One can usually distinguish between the symbol “dog” (syntactical entity) and the bunch of cooperating living cells that mess up your carpet (semantic entity), but the word “set” tends to lead to confusion.

    Start with the concept of model (aka interpretation), which is a semantic structure which consists of a class (a collection) of (semantic) individuals along with special subcollections [ i.e., (semantic) relations, functions, and constants], and a function which assigns semantic entities to syntactic ones.

    A sentence S is satisfied by a model M , in symbols M S, if, basically, the interpretation works. That is, a sentence is true under a given model if the model satisfies the sentence. So, “the dog messed up the carpet” is true if we agree on the English meanings and the dog is convicted of the crime.

    E⇒F if all the sets (from the model) with satisfy F also satisfy E. E⇔F if E and F are satisfied by the same sets.

    Now we can see where properties can be used in conjunction with the word “true”. What I think you want to say is that for each property P(.) you are handling the sentence For all xP(x) (∀xP(x)). Let's call that S(P), and let's work in the model [ℕ,∈] (the semantic natural numbers with the relation of set membership).

    Following your definitions,

    A(.) is the property (a syntactical entity) “. is a natural number”, i.e., “.∈ C” where you define C as the set of natural numbers (usually denoted by ℕ, although that is also used for the semantic notion: C is likely to get confused with ℂ).

    B(.) is the property “. is a non-zero even number”, which is the same as “. ∈ D” , where you define D as the set of even numbers {x∈C|x/2∈C}.

    So S(A) is ∀x A(x), i.e, ∀x (x∈C)

    The syntactic entity S(A) is interpreted by the semantic entity {0,1,2,...}

    and S(B) is similar for evens, so that S(B) is interpreted by {0,2,4,...}

    Now, we have two different possibilities as to what you mean by your conjunction.

    Perhaps you want to compare S(B) with S(AvB) or perhaps with [S(A) v S(B)]

    S(AvB) is "For all x, x is either a natural number or a non-zero even number." Satisfied by the set of natural numbers and also by the set of evens. S(B) is satisfied only by the set of evens. That is, S(AvB) is not satisfied by the same set as S(B). So S(AvB) is not equivalent to S(B), so that doesn’t work.

    Similarly for [S(A) v S(B)] which is "Either for all x, x is a natural number or for all y, y is an even number." (The variables are different because x need not equal y.)

    To put that into your phrasing:

    X is a sufficient condition for Y if X⇒Y, and X is a necessary condition for Y if ~X⇒~Y, which, if you are not an intuitionist, will be equivalent to Y⇒X. So, X is a necessary and sufficient condition for Y iff X⇔Y. So, if we are working in the model (ℕ,∈), S(B) will not be a necessary and sufficient condition for either S(AvB) or S(A) v S(B) .

    I may have skimped a little or made some typos, as again I must leave, so if this is not clear or you suspect something is not correct, I can explain further.
  12. Feb 24, 2017 #11
  13. Feb 24, 2017 #12
    @Logical Dog - I can't follow everything @nomadreid said above, since I'm still new to the material & for example haven't yet specifically explored semantics; but in general I agree w/ those parts of his comment that I do understand!

    Now, if I may jump in again - regarding this discussion thread you have referenced . . .

    . . . Personally I wouldn't use that thread as a starting point. The OP's question in that thread has to do with terminology and whether historically there is a connection between the history of a particular symbol and the modern meaning of "implication." Thus he gets answers that have to do largely with history. To me this would seem a hugely confusing way to get started on understanding the very important role of sets in mathematical logic.

    A much better source to learn from - because it is a well-written primer for beginners that takes things in order & feeds them to you in bite-sized pieces - is the book I referenced earlier by Richard Hammack, The Book of Proof. You can buy the printed hard copy via Amazon or elsewhere on line; but the PDF on the page I linked to is free. The first chapter in fact has to do with sets; subsequent chapters introduce logic statements and proofs. The chapter on logic addresses some of the differences that I believe @nomadreid is speaking of, to do with the difference between how we use natural language vs. how we use a combination of very precise natural language & symbolic language in presenting a proof. You'll learn what a statement is; what a proposition is; etc. etc.

    The only thing with The Book of Proof or any other book or article on logic, for that matter, is that it takes work to go through it! The differences between how we understand implication and causation in ordinary speech, vs. how implication is construed in mathematical logic, are quite large. If you're going to drive down the logic road, you've got to know where the potholes are!
  14. Feb 24, 2017 #13
    Hi UT,

    I have the book of proof in harcopy as well. I've done most of it but I do not remember it being very strong in the logic section, its a basic introduction to logic and then more about sets and mathematical logic I believe. In fact, I recommended it to YOU when you first came to pf lol. I;ve done the chapters (most of them) The only time I remember logical implciation was in the context of using the contrapositive to prove it, and some other logical equivalences. Its a good book but just as an introduction.

    Forgive my memory if I am wrong. Its a great book and got me into math and set theory, but not too deep into pure logic. If you want to be an expert in logic I am sure Mr Nomad Reid can recommend tougher and more thourough books. I have logic for dummies and schaums outlines of logic, but I have not gone through them properly. I know, it is not right, but I was just wondering whether I could justify this little line of thinking.

    thanks for the help. it seems i need to re read a lot.

    To me
    p \to q [/tex] means that
    [tex] P \supset Q [/tex] which is the same as [tex] Q \subset P [/tex]

    P is the larger set that contains elements which do not have both properties, and Q is the subset which contains elements that do have both properties.
    Last edited: Feb 24, 2017
  15. Feb 24, 2017 #14
    Thanks for clarifying! Times flies, eh? I don't remember who recommended what; I actually picked up Book of Proof later when I was searching around to find something to go with Devlin's book.

    More generally though, an implication built with sentences ( ##p \Rightarrow q## ) doesn't necessarily involve sets, and vice versa; so just in terms of notation, it wouldn't seem we could literally say ##p \Rightarrow q## is the same as ##P \subset Q## since the contexts may at times be exclusive of each other.

    Also, from further Googling it seems that the original reverse horseshoe ⊃ was used "a century ago" for implication, but was later replaced by →; or so someone says in this thread, which seems similar to the thread you found earlier; this would seem to make the horseshoe symbol too ambiguous to build an argument around: http://philosophy.stackexchange.com/questions/31029/why-was-the-horseshoe-symbol-⊃-selected-for-material-implication [Broken]

    As for whether the underlying concept of implication in predicate logic can be described in terms of set theory, see my next post . . . I've made it separate since it has new material (well, new to me, at least).
    Last edited by a moderator: May 8, 2017
  16. Feb 24, 2017 #15
    I did a quick search for "material conditional" (which is the right-pointing arrow) and "subset" and came up with some hits; e.g. here's a thread where someone asked about how to understand the material conditional, and one answer was to think in terms of a subset. This is the thread -
    http://math.stackexchange.com/quest...terial-conditional-and-explain-it-to-freshmen - and this is that answer, about half-way down the page:

    A couple of differences I notice - the writer here is using the symbol for a subset (i.e. including the possibility of equality, that is, the subset being the full parent set) while you have been using the symbol for a proper subset (required to be smaller than the parent set). Also this writer does not suggest the biconditional, where you seem to have speculated that the biconditional might hold, again using the symbol for a proper subset?

    Last edited: Feb 24, 2017
  17. Feb 24, 2017 #16
    Ok, I think it is getting more clear now.
    ill be back with something closer to an answer. thank for the help.

    I don;t think its a good idea to see this in purely set theoretic terms.
    Last edited: Feb 24, 2017
  18. Feb 24, 2017 #17
    As you know, ALL math theorems are always true and most are in the if then, or conditional, or logical implication form.

    My lecture notes says, differentiability implies continuity for all functions.
    [tex] Differentiability \Rightarrow Continuity [/tex]

    I understand this as..
    1. The set of all differentiable and continous functions are a proper subset of the set of all continuous functions. Or
    2. equivalently, the set of differentiable functions are a proper subset of continuous OR differentiable functions.

    [tex]\left \{ F(x) | Differentiable(F(x)) = true \right \} \subset \left \{ F(x) | [Differentiable(F(x) \vee continuous(F(x))] = true \right \} [/tex]

    so to me, it seems that continuity is a necessary but not sufficient condition for differentiability.

    Now for the sake of argument, if we lived in a reailty such that all functions that were differentiable were also continous..then:
    [tex]\left \{ F(x) | Differentiable(F(x)) = true \right \} = \left \{ F(x) | [Differentiable(F(x) \vee continuous(F(x))] = true \right \} [/tex]
    and here, I would say differentiatiability is a necessary and sufficient condition for continuity.
    because to me, now it would seem that:
    [tex] Differentiability \Leftrightarrow Continuity [/tex]
    Now if we replace the specific terms differentiability and continuity with other things, even variables if possible, can this line of reasoning allow us to say that x is neccessary but not sufficienct condition for y.
    Last edited: Feb 24, 2017
  19. Feb 24, 2017 #18
    one who recommends bad books doesn't know his subject well :p WHen in doubt go to a few good universities module/lesson plan and see the books recommended. :-)
  20. Feb 24, 2017 #19


    User Avatar
    Gold Member

    I have several comments, mostly for Logical Dog, but UsableThought's name will also pop up.
    Logical Dog:
    First, no, differentiability is not equivalent (under ⇔) to continuity: https://en.wikipedia.org/wiki/Weierstrass_function

    Secondly, I emphasized that one generally talks of a sentence implying another sentence, and that a property alone is neither true nor false, but in a way you can talk about one property P(.) implying another Q(.) in the following way: ∀x(P(x)⇒Q(x)). (This reminds me that in my previous post I mentioned that ~[S(A∨B) ⇔S(B)] and ~([S(A)∨S(B)]⇔S(B)), but I forgot to add that also ~[S((AvB) ⇔B)] (I am using ~ as negation).)

    Thirdly, UsableThought's advice to ignore the historical reasons for the sign ⊃ being used earlier for → is good. Nonetheless, it probably irks to see the symbol ⊃ used in this way when you read older books where it would seem natural to use ⊂ instead. So, in order to give this usage some sense, rather than mull through the historical reasons, you can use the following reasoning: Given a fixed model, let's say that for a sentence S, Con(S) is the set of consequences of S. That is, Con(S)={T: S→T}. Then, if X→Y, then Con(Y)⊂Con(X). You can visualize this by forming a partially ordered set under → of a theory, and take one branch. For simplicity let's suppose the theory is linearly ordered, and "1=0"→E→F→X→G→Y→K→"0=0". Then in this example, Con(X)={X,G,Y,K,"0=0"), and Con(Y)={Y,K, "0=0"}. (Don't get my use of "Con" here with its usage as "Consistent" that you may see.)

    Fourthly, what books you should investigate depends how deeply you want to get into it. Of course you want to get beyond Aristotelian logic into modern logic, and the book "Book of Proof" is not bad for a beginning, but it doesn't get very far. To go further I would recommend rather downloading some free and legal material from the Internet (and even consulting Wikipedia, despite its occasional faults) , for example start by picking up the little classic (any university mathematics library should have it) "Naive Set Theory" by Paul Halmos, and then google "Jech - Set Theory" and download the free Millenium 2003 edition; this will get you beyond Halmos. (You may also see Devlin's book recommended, and it is good, but expensive.) Then understand Basic Model Theory with the wealth of Model Theory books and texts on the net (or, if you really want to spend your money, the classic which is not at all expensive is from Chang & Kiesler https://www.amazon.com/Model-Theory-Third-Dover-Mathematics/dp/0486488217). Don't worry about working through these texts to the end; when it goes off into comparing large cardinals, you can put that off to another life, although a few results are quite nice. But first concentrate on understanding Gödel's three wonderful Theorems -- his Completeness Theorem and his two Incompleteness Theorems, trying to not only keep in mind what is complete and in what sense, but also avoid the many, many misunderstandings of the theorem. (This is so widespread that even the great physicist Roger Penrose misunderstood the First Incompleteness Theorem. He was corrected by the late logician Solomon Fefferman, but that did not stop Penrose gettting several books on popular science which contained the incorrect interpretation on the Best Seller List. So take your time to make sure you understand these key theorems, although you can skip the full proof of the Second Incompleteness Theorem .) Also understand the extremely important first-order Compactness Theorem. By the time you get that far, other topics will suggest themselves.

    To UsableThought: you said that you did not understand everything I wrote. That is certainly my fault for not explaining it clearly. So feel free to ask me to express myself better on any point that is not clear.
    Last edited by a moderator: May 8, 2017
  21. Feb 24, 2017 #20
    Yes, I know, I said in an alternative reality just to make an argument xD..anyways thank you for your time. It helped a lot.
  22. Feb 24, 2017 #21


    User Avatar
    Gold Member

    With pleasure. I just hope you read past my first point :rolleyes:
  23. Feb 24, 2017 #22
    I did I just didn't understand as much as you do and it willt ake me WEEKS to fully comprehend. Ive abandoned my logic studies for some time now. :(

    I always see this in my notes for lectures and was trying to be clever about it. I don't like to waste others times who have been more than helpful. I find the pure logic really difficult, I am sure it is probably one of the most difficult subjects.
  24. Mar 9, 2017 #23
    Wow, this thread has been traveling around... and I'm not really able to follow much of the later posts, but I'm kind of stuck at the beginning...
    Your first line is a sentence fragment, I assume meant to end in a comma, connecting the next sentance to complete an IF-THEN statement about there being at least one without both properties. I see nothing that denies the existence of some with just property B. How do you get, "We can then say that A is a necessary but not sufficient condition for B." without defining or proving that there are no Bs only?
  25. Apr 2, 2017 #24
    it was vague but this was my intention at the time:

    I am sure it is not worth investigating any longer, and probably founded on wrong ideas/lack of knowledge. Thanks for your time.

    Attached Files:

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted