6 ms·

Just a heads up, this pdf is not a logic tutorial or textbook, but an annotated bibliography. That said, if you got stuck on material implication (practically

Just a heads up, this pdf is not a logic tutorial or textbook, but an annotated bibliography. That said, if you got stuck on material implication (practically a topic discussed on the first or second day of logic study), as I did, and eventually were able to understand it, I'd love to know how. (Notice, only if you got stuck first, not if you never had problem understanding it).

alphaalpha101 9y ago
When I first encountered material implication I thought it was just stupid. False implies anything? Everything implies true? That's not what implies means, there must be some sort of relevancy, surely? The block for me was treating material implication as if it defined what 'if' meant in natural language. But it doesn't. 'If I am a turtle then the president of the United States is Hillary Clinton' isn't a statement about a relationship between whether or not I'm a turtle and who is the POTUS. It's a formal sentence. It's like a regular expression or something. It has no real meaning, it's just symbols. It's just 'Q Y C' or '$ ~ F' or 'A -> B' in a formal language. We give semantics to those symbols by assigning a truth value to 'A -> B' as a function of the truth values we assign to the symbols A and B. It seems silly if we substitute A for something clearly false and B is substituted for something also false and clearly unrelated, but that's because when you read the statement above it looks like natural language, and it is natural language, but logic isn't about natural language. It's about formal language. If you write it as 'I am a turtle -> Clinton is the POTUS' then it becomes a bit more clearly just 'arbitrary false thing -> arbitrary thing'. If you try to divorce the concept of material implication from the natural language construct of 'if..then..' then you shouldn't have a problem. Remember, material implication is truth-functional, which means that the truth value of 'A -> B' is just a function of the truth values of A and B (namely that it's true unless A is false and B is true), not whether they're related or relevant to each other.
benkuykendall 9y ago
Not to trivialize your issue, but I always am dismayed at how much time is spent trying to map English statements into those of sentential logic, especially in cases where their usage differ, like inclusive ors or material implication. In a more mathematical study of logic, you define your logical connectives using truth tables. So the material implication is nothing more and nothing less than X | Y | X -> Y ---------------- F | F | T F | T | T T | F | F T | T | T For the unfamiliar, a truth table works as follows: in the sentence "X -> Y", evaluate the truth values of X and Y (If X and Y are themselves sentences, this follows recursively. If they are atomic predicates, they should have fixed truth values). Then, refer to the appropriate row of the table to find the value of the sentence. Rather tangentially, my logic teacher would always say "to verify a material implication, we must falsify the hypothesis or verify the conclusion". I'm not sure that helped any of her students come to terms with the connective, but it is a succinct (if not jargon-heavy) way to summarize that table.
- zengid 9y ago
  I think time is spent trying to map Logic to English because its our more familiar framework for thinking through logical problems. We do it everyday when problem-solving and weighing options, so its only natural that we want a way to make the abstractions of formal Logic into a concrete 'cause and effect' type of explanation via language. That being said, I agree that one needs to try and resit this urge, otherwise you won't get past the barrier that material implication presents. It really just doesn't make sense at first, and not for a long time of playing with it and using it within larger statements does one start to sus-out some kind of concrete mechanical meaning for its behavior.
- fizixer 9y ago
  There are two ways of looking at logic, roughly speaking: - Logic as a game (as in a set of rules). E.g., in that regard pure math is a game, formal systems are a game, even programming and CS is a game. - Logic as an applied discipline used to formalize rational discourse, to arrive at a set of conclusive facts, with sound and valid reasoning, given a problem (which could be a problem in the real world) and a set of assumptions. Part of my frustration with logicians is that they almost exclusively treat logic as belonging to the first case, and hate it when you ask them about the second case. I am interested in logic partly because it's an aspect of the foundation of pure mathematics, but around the time I started learning logic, that was the least of my concerns. Instead, I was highly motivated by the need to have a formal system in place which I could rely on while arguing about philosophical issues, and especially topics related to religion vs atheism, because the arguments I would hear from the other side could safely be described as "stupid reasoning". However, when I started taking logic seriously, I realized that, not only do the fundamental rules of logic sound stupider (hint: material implication) than the logic I was hearing from my opponents, but logicians have no interest in helping the logic student connect the formal ideas to real world problems. When 99.999% of logicians, no matter how experienced they are, tell me to treat logic as a game, and nothing but a game, what I hear is this: I don't know how to apply logic to philosophical discourse and real world problems, and I am content with my state of knowledge, therefore you should be happy treating logic as just a game too and stop asking any deeper questions, or trying to connect it to philosophy and rational discourse.
ihm 9y ago
You can think of "A => B" as stating "there is a way of transforming proofs of A into proofs of B". If "A" is false, then there are no proofs of "A", and thus there is trivially a way of transforming proofs of "A" of "B" (since you will never be confronted with a proof of "A"). So a false statement implies anything. If "B" is true, then there is some proof p of "B". Now here is a way of transforming a proof of "A" into a proof of "B": given a proof q of "A", just return that one proof p. So anything implies a true statement.
- dvt 9y ago
  This is actually the best way to understand it. But without some background (Proof Theory 101, The Deductive Theorem, Metalogic 101), I'm sure this sounds like gibberish :) NB: Although you muddy the waters a bit. "A => B" is literally "A proves B". And to see why an inconsistent set implies anything at all, we just need to look at the Principle of Explosion[1] -- which is probably less contentious than material implication. [1] https://en.wikipedia.org/wiki/Principle_of_explosion https://en.wikipedia.org/wiki/Principle_of_explosion
  - dvt 9y ago
    Small clarification (I wrote my parent post super late last night). Via the Deduction Theorem, we have: ⊢ A -> B => A ⊢ B That's what I mean by "A proves B"
- setr 9y ago
  I just think of it as P->Q only says something about Q when P is true; no information is given about Q when P is false, so Q can be whatever it wants in that case. And since any value of Q is acceptable, then the statememt holds regardless of Q's value (when P is false). We only have the chance to return false when P is true, because thats the only time P says something about Q (that its true)
- evincarofautumn 9y ago
  That’s how I understand it now after a bunch of exposure to type theory and internalising Curry–Howard. But as a programmer my earliest practical way of thinking of it was “How would I use an ‘implies’ operator in programming?” Things like these: (a => b) == (a ? b : true) == !a || b if (a) assert(b); // == assert(a => b); #if !defined(_MSC_VER) || defined(_NATIVE_WCHAR_T_DEFINED) // == #if defined(_MSC_VER) => defined(_NATIVE_WCHAR_T_DEFINED) if (!p || !p->buffer) return 0; // == if (p => !p->buffer) return 0; That is, just talking about truth values, the results of proofs rather than the proofs themselves.
a-saleh 9y ago
My way of 'getting it' emerged only after few weeks, when we spent quite a lot of time on a proof that not (not A) is equivalent to A in propositional logic. Then I realized that I shouldn't think about these in terms of ideas about reasoning I already had in my head, but to internalize that this is a self-contained, rule-based system, where we have some arbitrary statements given as a base and some arbitrary derivation rules, and our only goal is to be able to find what we are able to derive. Does this statement have a proof then means "is there a chain of derivations from base that leads to this statement?" I still got tripped on 'implication' (that in my language means something closer to what equivalence means in logic for some reason) and 'or' (that in my language usually implies either-or), but when I looked these with "Its just a rules system, it doesn't have to mean the same thing I use in general language" I was fine. Then, of course, the usage crept from maths back to the language, and I have had confused many of my less mathematical friends (i.e. when they ask "if you are in the city, would you go to a pub", and to this, my answer always is "yes", but what they really meant is "Are you in the city and will you go to a pub?")
jimhefferon 9y ago
When I cover the topic, no one ever is confused by T -> F. For the others, I have an example (in the metalanguage, obviously). Consider "if a number is prime then it isn't a perfect square." Should be true, right? If you can't split it then you can't split it into equal parts. Now take the number to be 6. That suggests that F -> T should evaluate to T. Take the number to be 4. That suggests F -> F is T. And 3 suggests what to do with T -> T.
- fizixer 9y ago
  Your example makes sense but at the same time it's something I like to call "a positive example". If you explain it to new students, they would agree with you and would think they understand material implication. But later if you test their knowledge using one of the counter-intuitive examples, more often than not, they would have a hard time reconciling it with their understanding. (e.g, the one that I posted here: https://news.ycombinator.com/item?id=15115319 https://news.ycombinator.com/item?id=15115319).
  - jimhefferon 9y ago
    People don't learn things by being told them. For anything that is hard, they learn by gradual approximation.

alphaalpha101 9y ago

When I first encountered material implication I thought it was just stupid. False implies anything? Everything implies true? That's not what implies means, there must be some sort of relevancy, surely? The block for me was treating material implication as if it defined what 'if' meant in natural language. But it doesn't. 'If I am a turtle then the president of the United States is Hillary Clinton' isn't a statement about a relationship between whether or not I'm a turtle and who is the POTUS. It's a formal sentence. It's like a regular expression or something. It has no real meaning, it's just symbols. It's just 'Q Y C' or '$ ~ F' or 'A -> B' in a formal language. We give semantics to those symbols by assigning a truth value to 'A -> B' as a function of the truth values we assign to the symbols A and B. It seems silly if we substitute A for something clearly false and B is substituted for something also false and clearly unrelated, but that's because when you read the statement above it looks like natural language, and it is natural language, but logic isn't about natural language. It's about formal language. If you write it as 'I am a turtle -> Clinton is the POTUS' then it becomes a bit more clearly just 'arbitrary false thing -> arbitrary thing'. If you try to divorce the concept of material implication from the natural language construct of 'if..then..' then you shouldn't have a problem. Remember, material implication is truth-functional, which means that the truth value of 'A -> B' is just a function of the truth values of A and B (namely that it's true unless A is false and B is true), not whether they're related or relevant to each other.

benkuykendall 9y ago

Not to trivialize your issue, but I always am dismayed at how much time is spent trying to map English statements into those of sentential logic, especially in cases where their usage differ, like inclusive ors or material implication. In a more mathematical study of logic, you define your logical connectives using truth tables. So the material implication is nothing more and nothing less than X | Y | X -> Y ---------------- F | F | T F | T | T T | F | F T | T | T For the unfamiliar, a truth table works as follows: in the sentence "X -> Y", evaluate the truth values of X and Y (If X and Y are themselves sentences, this follows recursively. If they are atomic predicates, they should have fixed truth values). Then, refer to the appropriate row of the table to find the value of the sentence. Rather tangentially, my logic teacher would always say "to verify a material implication, we must falsify the hypothesis or verify the conclusion". I'm not sure that helped any of her students come to terms with the connective, but it is a succinct (if not jargon-heavy) way to summarize that table.

zengid 9y ago
I think time is spent trying to map Logic to English because its our more familiar framework for thinking through logical problems. We do it everyday when problem-solving and weighing options, so its only natural that we want a way to make the abstractions of formal Logic into a concrete 'cause and effect' type of explanation via language. That being said, I agree that one needs to try and resit this urge, otherwise you won't get past the barrier that material implication presents. It really just doesn't make sense at first, and not for a long time of playing with it and using it within larger statements does one start to sus-out some kind of concrete mechanical meaning for its behavior.
fizixer 9y ago
There are two ways of looking at logic, roughly speaking: - Logic as a game (as in a set of rules). E.g., in that regard pure math is a game, formal systems are a game, even programming and CS is a game. - Logic as an applied discipline used to formalize rational discourse, to arrive at a set of conclusive facts, with sound and valid reasoning, given a problem (which could be a problem in the real world) and a set of assumptions. Part of my frustration with logicians is that they almost exclusively treat logic as belonging to the first case, and hate it when you ask them about the second case. I am interested in logic partly because it's an aspect of the foundation of pure mathematics, but around the time I started learning logic, that was the least of my concerns. Instead, I was highly motivated by the need to have a formal system in place which I could rely on while arguing about philosophical issues, and especially topics related to religion vs atheism, because the arguments I would hear from the other side could safely be described as "stupid reasoning". However, when I started taking logic seriously, I realized that, not only do the fundamental rules of logic sound stupider (hint: material implication) than the logic I was hearing from my opponents, but logicians have no interest in helping the logic student connect the formal ideas to real world problems. When 99.999% of logicians, no matter how experienced they are, tell me to treat logic as a game, and nothing but a game, what I hear is this: I don't know how to apply logic to philosophical discourse and real world problems, and I am content with my state of knowledge, therefore you should be happy treating logic as just a game too and stop asking any deeper questions, or trying to connect it to philosophy and rational discourse.

ihm 9y ago

You can think of "A => B" as stating "there is a way of transforming proofs of A into proofs of B". If "A" is false, then there are no proofs of "A", and thus there is trivially a way of transforming proofs of "A" of "B" (since you will never be confronted with a proof of "A"). So a false statement implies anything. If "B" is true, then there is some proof p of "B". Now here is a way of transforming a proof of "A" into a proof of "B": given a proof q of "A", just return that one proof p. So anything implies a true statement.

dvt 9y ago
This is actually the best way to understand it. But without some background (Proof Theory 101, The Deductive Theorem, Metalogic 101), I'm sure this sounds like gibberish :) NB: Although you muddy the waters a bit. "A => B" is literally "A proves B". And to see why an inconsistent set implies anything at all, we just need to look at the Principle of Explosion[1] -- which is probably less contentious than material implication. [1] https://en.wikipedia.org/wiki/Principle_of_explosion https://en.wikipedia.org/wiki/Principle_of_explosion
- dvt 9y ago
  Small clarification (I wrote my parent post super late last night). Via the Deduction Theorem, we have: ⊢ A -> B => A ⊢ B That's what I mean by "A proves B"
setr 9y ago
I just think of it as P->Q only says something about Q when P is true; no information is given about Q when P is false, so Q can be whatever it wants in that case. And since any value of Q is acceptable, then the statememt holds regardless of Q's value (when P is false). We only have the chance to return false when P is true, because thats the only time P says something about Q (that its true)
evincarofautumn 9y ago
That’s how I understand it now after a bunch of exposure to type theory and internalising Curry–Howard. But as a programmer my earliest practical way of thinking of it was “How would I use an ‘implies’ operator in programming?” Things like these: (a => b) == (a ? b : true) == !a || b if (a) assert(b); // == assert(a => b); #if !defined(_MSC_VER) || defined(_NATIVE_WCHAR_T_DEFINED) // == #if defined(_MSC_VER) => defined(_NATIVE_WCHAR_T_DEFINED) if (!p || !p->buffer) return 0; // == if (p => !p->buffer) return 0; That is, just talking about truth values, the results of proofs rather than the proofs themselves.

a-saleh 9y ago

My way of 'getting it' emerged only after few weeks, when we spent quite a lot of time on a proof that not (not A) is equivalent to A in propositional logic. Then I realized that I shouldn't think about these in terms of ideas about reasoning I already had in my head, but to internalize that this is a self-contained, rule-based system, where we have some arbitrary statements given as a base and some arbitrary derivation rules, and our only goal is to be able to find what we are able to derive. Does this statement have a proof then means "is there a chain of derivations from base that leads to this statement?" I still got tripped on 'implication' (that in my language means something closer to what equivalence means in logic for some reason) and 'or' (that in my language usually implies either-or), but when I looked these with "Its just a rules system, it doesn't have to mean the same thing I use in general language" I was fine. Then, of course, the usage crept from maths back to the language, and I have had confused many of my less mathematical friends (i.e. when they ask "if you are in the city, would you go to a pub", and to this, my answer always is "yes", but what they really meant is "Are you in the city and will you go to a pub?")

jimhefferon 9y ago

When I cover the topic, no one ever is confused by T -> F. For the others, I have an example (in the metalanguage, obviously). Consider "if a number is prime then it isn't a perfect square." Should be true, right? If you can't split it then you can't split it into equal parts. Now take the number to be 6. That suggests that F -> T should evaluate to T. Take the number to be 4. That suggests F -> F is T. And 3 suggests what to do with T -> T.

fizixer 9y ago
Your example makes sense but at the same time it's something I like to call "a positive example". If you explain it to new students, they would agree with you and would think they understand material implication. But later if you test their knowledge using one of the counter-intuitive examples, more often than not, they would have a hard time reconciling it with their understanding. (e.g, the one that I posted here: https://news.ycombinator.com/item?id=15115319 https://news.ycombinator.com/item?id=15115319).
- jimhefferon 9y ago
  People don't learn things by being told them. For anything that is hard, they learn by gradual approximation.