Lecture Note
University
Stanford UniversityCourse
Introduction to Mathematical ThinkingPages
7
Academic year
2022
Murphyal
Views
61
Equivalence Implication and equivalence are two types of logic statements that can be used to expressconditional or logical relationships between two propositions. ● Implication An implication is a statement that says that if one thing is true, then another thingmust be true as well. It is written in the form: “If A, then B.”For example: If it rains, then the ground will be wet. In this statement the subject (it)refers to an event (rains). The predicate (wet) describes an attribute of the subject. ● Equivalence An equivalence is a statement that says two things are equal to each other. It iswritten in the form: “A = B.”For example: 1 + 1 = 2 or "All men are created equal" ● Biconditional In logic, a biconditional statement is an expression of the form "A if and only if B".The word "if and only if" is traditionally abbreviated as "iff" or "iffy".The truth table of a biconditional is:A B A ≡ B T T T F T F F F Let's look at logical equivalence! The concepts of equivalence and implication are closely related. Two statements are saidto be logically equivalent if each implies the other. The notion of equivalence is fundamental to logic and mathematics. Many mathematicalresults are proofs that two statements are equivalent. In fact, equivalence is to logic asequations are to arithmetic and algebra. And you already know that equations play acentral role in mathematics. As we saw earlier, the conditional is an important concept in formal logic. It can be used toexpress implication but not causation. We need a new form of equivalence—thebiconditional—that allows us to express causes. We have already completed the difficult work of determining the implications of our efforts.Now we can reap the benefits. Two statements phi and psi are logically equivalent if each implies the other. A formalversion of implication, called the conditional, can be expressed as a biconditional in logic. The biconditional of phi and psi is denoted by means of a double-headed arrow, like this.The biconditional can be formally defined as an abbreviation of phi conditional psi and psiconditional phi. Since the conditional is defined in terms of truth values, it follows that thebiconditional is defined in terms of truth values. If you work out the truth tables for phi conditional psi and psi conditional phi, and thencombine the results using the De Morgan law, you will get the truth table for phibiconditional psi. If you do that, you will find that phi biconditional psi is true if both phi and psi are true orthey are both false. One way to show the equivalence of two statements phi and psi is toshow that they have the same truth table.
To avoid confusion, let’s change those to capital letters Phi and Psi, because we can usethe lowercase letters phi and psi for something else. This example shows that phi conjoined with psi or not phi is equivalent to phi conditionalpsi. Here, we will use uppercase letters for the first time. At a high school level, different lettersare chosen to denote everything. However, professional mathematicians frequently useupper- and lower-case symbols in the same context. One way to master university-level mathematics is to get used to ambiguous notations. Wemust work up the truth table for this, the truth table for that, and show that they are thesame. To start with, we will calculate phi, psi, and the negations of these values. We will thenneed to determine not phi. Next, we can determine phi and psi disjoined with not phi. Thenwe can compare this value with phi conditional on psi. It is customary to begin with the four basic combinations, TT, TF, FT, FF. It does not matterwhich order these are written in as long as all four combinations are included. The way I've written it is the way most mathematicians write it. This statement is true ifboth conjuncts are true; therefore, if the first part of the statement is true—that is, if TTgives T—then the conclusion must be true, which is an F. Here there is an F, so you are getting an F. We have two Fs, so you are getting an F.Negation simply flips T and F, so T T F F becomes F F T T. Now I'm going to disjoin this with that. The disjunction picks out one T and an F, so I willget an F here. There is no T, so I will get an F again. There is a T there, which gives me aT, and another T there also gives me a T. The truth value of Phi conditional Psi is equivalent to the truth value of Phi conditional Psi.The truth values of these expressions are T, F, T, T. We previously concluded that the truthvalues of these expressions were T, F, T, T. Since these two columns contain the samevalues, I can conclude that Phi conditional Psi is equivalent to Phi conditional Psi. Proving equivalence by means of truth tables is a special case. In general, provingequivalence is quite difficult and requires looking at what the two statements mean anddeveloping a proof based on their meanings.
The notion of implication itself is simple. What is difficult is mastering the variousnomenclatures associated with it. We start out with the notion that phi implies psi. We will be considering the conditional implications of this idea, but you may interpreteverything else in terms of the conditional. If mathematicians always used the same notation to refer to phi and psi, then life would bevery simple. But as is often the case in mathematics, there are many different notationsused to describe that relationship. Some of these statements are intuitively obvious and some are actually counter-intuitivewhen first encountered. One, if phi, then psi. Okay, that's fairly obvious. Two, phi issufficient for psi. In order to conclude that psi exists, it suffices to know the value of phi. On the face of it,this is fairly straightforward, but in complicated situations people can sometimes get misledby the use of the word sufficient. In the context of implication, the use of the word sufficient is not the most problematic. Thisone causes people a lot of problems at first. The implication of psi only if phi is not the same as the implication of phi if psi. The formerimplies psi only if phi, while the latter implies that phi only if psi. I want to emphasize thatthis "if" goes with psi and not with phi. Let's put quotes on that one: "if". As you can see, itchanges the order of the implication. To ride in the Tour de France, a person must have a bicycle. It appears true as if you don'thave a bicycle you are unable to ride in the Tour de France. Pay attention: it doesn't meanthat if you have a bicycle then you can ride in the Tour de France.
If phi, then psi; notice that we've flipped the order now. Phi is the antecedent, and psi is aconsequent. These roles will remain constant in all of these. The conditional statement Phi => Psi is equivalent to the statement Psi => Phi. Theantecedent comes first and the consequent comes second. This means that Phi impliesPsi, but now the consequent comes first and the antecedent comes second. Think about something you do that requires some type of equipment or preparation. Thenconsider how this activity can be interpreted in terms of something meaningful in your life. Continue. Whenever psi is necessary for phi, the order is flipped from the order in implication. That'sstill the consequence. That's the antecedent, but they've been written the opposite wayaround. Whenever phi occurs, psi must also occur. Finally, psi is necessary for the existence of phi. Again, the order is flipped around. That is still the antecedent, and that is still theconsequent. Phi cannot occur without psi. In order to participate in the Tour de France, you must have a bicycle. It is not sufficient,however, that you have a bicycle. To participate in the Tour de France it is necessary thatyou have a bicycle but it's not sufficient that you have a bicycle. This is the example I would use to illustrate all of these terms, but you can choose yourfavorite example to comprehend these things. It is important to understand thisterminology because it is used frequently in mathematics, science, and analytic reasoning. Mathematical language is more than a means of expressing mathematical ideas; it's alsoused in a wide variety of other contexts—e.g., legal documents, logical arguments, andanalytic arguments. Phi and psi are commonly associated with implication. We have an associated terminologyfor equivalence: phi is equivalent to psi is itself equivalent to, by the way this alreadyshows how ubiquitous the equivalence is because the obvious word to describe this, let usput quotes around that just to ambiguate. One way to describe this is to say that it is equivalent to something. The word equivalencerefers to a basic concept in mathematics, namely the relationship between two quantitiesor sets of quantities that are directly equal. So this statement, this claim, is equivalent to phi being necessary and sufficient for psi.This combination of necessity and sufficiency is very common in mathematics. And b, phi,if and only if psi. That's also very common in mathematics, if and only if. Note that we are now combining necessary and sufficient conditions. With necessaryconditions, we have psi before phi. With sufficient conditions, we have phi before psi, andthat gets us the implication in both directions (and equivalence means implication in bothdirections). An implication of the fact that psi and phi are identical is that they can be written in eitherorder; where psi comes before phi, so does phi come before psi. Similarly with b: If andonly if combines only if, where phi comes before psi, with if, where psi comes before phi. Thus, in both of these cases we have an implication from phi to psi, and from psi to phi.The abbreviation iff is often used to represent this expression: if and only if.
If and only if or if if means that the two statements are equivalent. When you master this terminology, you should be able to read and understand almost anymathematics that you encounter. You may not be able to understand the mathematics itself, but at least you should be ableto understand what it's talking about. The rest is up to you—spend some time masteringthe concepts. Quiz appears. The following questions are divided into 4 parts. How many correct answers can you get?Let's see how you did by checking the conditions for the natural number n to be a multipleof 10. First Part. The question we must ask ourselves is whether the statement "n" being a multiple of 10 implies that it is necessary for "n" to be a multiple of 10. Let us examine thisquestion. Does n being a multiple of 10 imply that it's a multiple of 5? Yes, since any multiple of 5 isalso a multiple of 10. Does n being a multiple of 10 imply that this is a multiple of 20? No,since 10 is not itself a multiple of 20. Is n a multiple of 10? Yes, does n being a multiple of 10 imply that n is even? No. Does nbeing a multiple of 10 imply that it's a multiple of 100? No. Does n being a multiple of 10imply that n squared is also a multiple of 100? Yes, so the three conditions are necessaryfor the number n to be divisible by 10. Condition 1, condition 3, condition 5. Second Part. This time we must ask whether or not the statement implies that n is a multiple of 10. Well, does it imply that n is a multiple of 10? No, it does not. 5 is itself amultiple of 5. It is not a multiple of 10.
Look at number two. Is it the case that if n is a multiple of 20, then it has to be a multiple of10? The answer is yes. Does n being even and a multiple of 5 imply that it's a multiple 10? Yes, if n is 100, does that imply that it is a multiple of 10? Yes, if n2 is a multiple of 100,does that imply that it is a multiple of 10? Yes, in this case, 2, 3, 4, and 5 are the correctanswers. They all are sufficient for n being a multiple of 10. Let's move on to Part Three . For this one, we must compare our answers for the two previous questions: necessity and sufficiency. For the first question, we have 1, 3, and 5.For sufficiency, we have 2, 3, 4 and 5. This question asks for both necessity andsufficiency; here we have just one of them; there we have only the other one; there wehave both of them; here we have only one of them; and there we can see that bothelements are present. Thus, this one, that one. For Part Four , the question we have to ask ourselves is what does the antecedent imply? In statement one, this does the implying. In question two of statement two, even though it'swritten opposite to sentence number one, essentially it's the same idea expressed. It is thealarm that does the implying. Similarly, in number three, Keith cycles only if the sun shines
does not imply that Keith was cycling at all. The implication here is that Keith does notcycle in the rain. In number 4, Amy's arrival does the implying. We've so far distinguished between genuine implication and its equivalents. They're morelike counterparts, though; the conditional and the bi-conditional. In the daily work of mathematicians, however, we often use the arrow symbol as anabbreviation for "implies"—on one side of the arrow is an abbreviation for "is equivalentto." Although this may seem confusing to beginners, it is simply the way a mathematicalpractice evolves and there is no getting around it. In fact, once you get used to the notions,it is not all that confusing as it might seem at first and here is an explanation. The conditional and bi-conditional are only different from implication and equivalents insituations that do not apply in the normal practice of mathematics. In any realmathematical context, the conditional effectively is implication, and the bi-conditionaleffectively is an equivalent. The formal notion of implication and equivalence differ from their everyday counterparts,but mathematicians simply take note of the difference and move on. The very act offormulating a definition creates an understanding that allows us to use the everydaynotions safely. Sure, programmers and people who develop aircraft control systems must ensure that allthe notions in their programs are defined and that they give answers in all circumstances. Implications and equivalences are at the heart of mathematics. Mastery of those conceptsand of the terminology associated with them is fundamental to mathematical thinking.
Equivalence: Exploring Logical Relationships and Statements
Please or to post comments