Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
This question comes from from my algebra paper:
$(p \rightarrow q)$ is logically equivalent to ... (then four options are given).
The module states that the correct option is $(\sim p \lor q)$. That is:
$$(p\rightarrow q) \iff (\sim p \lor q )$$
but I could not understand this problem or the solution. Could anybody help me?
As it was suggested in a comment above, drawing a truth-table, especially when there are only two or three variables (i.e. atomic sentences) can really help to illustrate exactly when two given expressions are equivalent.
In this case, we see that $(\sim p \lor q)$ is true exactly when $(p\rightarrow q)$ is true, and it is false exactly when $(p\rightarrow q)$ is false. That is, $(p\rightarrow q) \equiv (\sim p \lor q)$. Alternatively, we can recognize the equivalence of the two expressions simply by comparing column of truth-values corresponding to each expression and see that the two columns are identical, and hence, the expressions are logically equivalent.
Logical Equivalence : (p → q) $\equiv$ (¬p ∨ q) $\;\;$ Note that $"\equiv"$ is equivalent to $"\iff"$
Another way to use the truth-table above is to see that the implication $(p \rightarrow q)$ is false if and only if the truth-value of $p$ is true and value of $q$ is false. Symbolically, we can express that fact by asserting that for the implication to be true, then (it cannot be the case) that $(p \land \sim q)$; in other words, $\sim (p \land \sim q)$. This conveys exactly the same information as the material implication $(p \rightarrow q)$. Note that $\sim (p \land \sim q) \equiv (\sim p \lor q)$, by De Morgan.
As for understanding that when $(p \rightarrow q)$, then if $p$ is true, we must have that $q$ is true: perhaps the following analogy will help.
In many respects, the proper inclusion (proper "is a subset of") relation corresponds to material implication, where $\subset$ corresponds to the $\rightarrow$ relation. For example, suppose $A \subset B$. Then if it is true that $x \in A$, then it must be true that $x \in B$, since $B$ contains $A$. However, if $x \notin A$, that does not mean that $x \notin B$, since if $A \subset B$, then $B$ contains elements that $A$ does not contain.
As Peter Suber (Philosophy Department, Earlham College) points out in his website titled “Paradoxes of Material Implication”, material implication is the price of truth-functionality. Here is the link:
http://www.earlham.edu/~peters/courses/log/mat-imp.htm
These are paradoxes in the ancient sense, violations of intuition. They are not contradictions. But, you may well ask, why would we adopt a type of implication with such counter-intuitive results? … Primarily, the answer is that we want a truth-functional kind of implication. Remember that a connective is truth-functional if we can figure out the truth-value of the statement solely on the basis of the truth-values of its components. If we use a truth-functional form of implications, then we can construct truth-tables for our implication statements
Edit: I forgot to point out that material implication is not unknown in ordinary language. When I was about 6 years old, trying to catch one of the birds that lighted in our yard, my grandfather gave me some this joking advice: “If you want to catch a sparrow, all you have to do is put salt on its tail.” :-)
Further edit: Nonetheless, there is a tendency to avoid material implication. A good example is the Wikipedia article on absolute value, at the line:
If b > 0, two other useful properties concerning inequalities are:
(We need to digress a moment to point out that this line ought to be edited to say that b is non-negative. That is, the case where b = 0, although trivial, is still germane. In our discussion below, we will assume that such an edit has been done.)
By material implication, it is irrelevant if b is non-negative, but, admittedly, relevance disappears if b < 0. Perhaps the chin-strokers at Wikipedia feel that they are making it easier to understand for the layman by filtering the “irrelevance”, but a heavy price is paid for that, namely, the disruption of the nice chart that they were creating. If you simply let material implication do its work, then you can continue with the chart in an uninterrupted way.
Further edit: Another example of the avoidance of material implication is in the definition of a “critical point” of a function, namely, the usual practice of saying that a point c is a critical point of a function f if, and only if, c is in the domain of f, and either f’(c) = 0 or f’(c) does not exist. A niftier way of putting it is that c is in the domain of f, and f is differentiable at c implies f’(c) = 0. Period. End of story. Anyone who asks “What if f is not differentiable at c? Is c a critical point or not in that case?” labels themself as mathematically, or at least logically, illiterate. (I hope I don’t get labelled as being literarily illiterate for using “themself”! - see the discussion in Wiktionary.) Of course, if the student asks this, then the teacher must answer, and the answer is: “Yes, by material implication. That is, if f is not differentiable at c, then, by material implication, the implication if true, and so c is a critical point of f in that case as well.” The formulation using material implication is niftier not only for being more concise, but also for avoiding explicit reference to something non-existent. Knowledge of and acceptance of material implication should be established and assumed at an early point in one’s mathematical training. Notice that, unlike the example in Wikipedia regarding absolute value, material implication in this case addresses a condition that is relevant.
I daresay that this example of spoon-feeding filtering of irrelevance is quite widespread, and may even be partly contributory to the difficulty in appreciating material implication when those moments come when it cannot be avoided. That is, if the unrequested filtering were not routinely done, then people would be used to material implication already, just as they are used to tricky idioms in ordinary language, complex word-play jokes, and so on. In other words, it is the needless UNFAMILIARITY with material implication that is partly to blame here.
Further edit: Material implication often involves the null set. For example, the intersection of the null set is, by material implication, the universal set. Letting material implication work for you this way means that you do not have to separately consider the null case. Including the null case, by material implication, into the set of all cases allows for unity of treatment, and recognition of otherwise hidden patterns. For example, a selfie is basically a photobomb in which the victim is non-existent (i.e., null). (A photobomb might be accidental, or involve something other than the image of the perpetrator, and so the precise definition of a selfie would be “an intentional victimless photobomb featuring the image of the perpetrator”).
Further edit: It is because of material implication that a minute of silence (such as at the beginning of a school day) is not in violation of the "English only" rule that may be in effect.
Further edit: A classic example of material implication is one known from antiquity, namely, Archimedes' boast about the lever: "Give me a place to stand, and I will move the Earth." - which is just an emphatic way of saying, "If I had a place to stand, I could move the Earth."
Further edit: Material implication is also used by religion to raise the topic of transcendence, transcendence being the raison d'être of religion. For this reason, the false assertions of religion are not a defect of religion, but an essential part of its dynamic. For example, is it not true that if an infinite amount of time has passed, then 2 plus 2 equals 5? By material implication, it is true. The assertion that 2 plus 2 is 5 is not really of interest. It is like the nail in the story about nail soup. What is of interest is that the subject of "an infinite amount of time" - in other words, transcendence, has been raised.
further edit: A nice (“classic”?) example of material implication at work is the fact that symmetry together with transitivity does not imply reflexivity. This situation is dealt with in detail on page 30 of the book ESSENTIALS OF ABSTRACT ALGEBRA by Bundrick and Leeson (1972), and is listed as one of the answers here in MSE to the question about “obvious” theorems that are actually false, at the following location:
Understanding that $p \implies q$ is equivalent to $\sim p \vee q$ is usually very tricky for most people first learning it. I learned it in a philosophy class, of all things.
The basic idea is this: $p$ and $q$ are "statements" that are either True or False. Then $p \implies q$ is also a statement. That the first part of what's confusing, that we're talking about a "statement about statements."
Example: "If you own a dog, then you own an animal." Here "you own a dog" is a statement that is either true or false, "you own an animal" is either true or false, and the whole sentence "if you own a dog, then you own an animal" is either true or false.
Now most people would agree that the last statement, "if you own a dog, then you own an animal" is True since a dog is generally considered to be an animal. What does it mean for this statement to be True? Well, it means that if a person owns a dog, then he/she owns an animal. But it does not say anything about people who do not own a dog. For example, someone who owns a cat does own an animal, but our assertion has nothing to say about cat owners. In fact, this point is what causes a huge amount of trouble for novices in my experience.
So all of this is my long-winded way of saying, that the statement "if you own a dog, then you own an animal" remains true even for people who are not dog owners.
So let's now write $p \implies q$ as a truth table with what we've learned above.
P --> T F Q -v ----------- T | T T F | F T
In other words, our statement "if you own a dog, then you own an animal" is true provided that owning a dog means you own an animal. The statement is always true if you don't own a dog. And the only way for the statement to be false is to own a dog and yet somehow do not own an animal. In other words, the main thrust of an implication like $p \implies q$ is the assertion that if $p$ is true, we absolutely must have $q$ true.
Now, what is another way to get this same truth table? $\sim p \vee q$ gives you the same table, so $p \implies q$ is equivalent to $\sim p \vee q$.
$p \to q$ is only logically false if $p$ is true and $q$ is false. So if not-$p$ or $q$ (or both) are true, you do not have to worry about $p \to q$ being false. On the other hand, if both are false, then that's the same as saying $p$ is true and $q$ is false (De Morgan's Law), so $p \to q$ is false. Therefore, the two are logically equivalent.
Given the material implication X,
X: if p is true, then q is true
the possibilities are:
A: p, q
B: p, ¬q
C: ¬p, q
D: ¬p, ¬q
The implication X is silent on the cases where p is not true (¬p or ~p in your notation), C and D above. X asserts that A, not B, is the case when p is true. A, above, represents the intersection of p and q, in set theoretic terms, i.e. (p Λ q).
So, we can argue
Y: either (p is false) or (p is true: if p is true, then q is true)
If we convert Y to symbols, we get*
Y: (¬p) v (p ^ q)
*Please note I use '^' to mean the intersection/conjunction of two sets, as I cannot seem to paste in the lambda symbol. :(
Where 'v' refers to the union of the two sides of Y, i.e. either p is false OR it is true. Since the right-hand side of the disjunction Y considers the case when p is true, and asserts that q is true if p is true, then we can alter it from (p ^ q) to simply (q).
Y: ¬p V q
Given that Y expresses all the possibilities (A, C and D above) asserted by X, we an argue that, if X is true, then
X <=> Y
Thus, substituting for X and Y using symbols, we have:
p -> q <=> ~p V q
which is what you wanted to prove.
Regarding possibility B above: If we assert the material implication X, then we deny possibility B above. If we state that X is true, then this amounts to asserting that the scenario
'B: if p is true, then q is false'
is false. In symbols,
¬(B: p Λ ¬q)
i.e. it is not the case that B is true. Drawing out the Venn diagrams for these various expressions - if done correctly! :) - shows that they are equivalent, i.e.
¬p V q <=> ¬p V (p ^ q) <=> ¬ (p ^ ¬q)
To understand, consider this question: How must the world be designed to make this statement ( $p \implies q$ ) true?
There are two options:
Combining these we get $\sim p \vee q$.
