If and only if

Last updated

↔⇔≡⟺
Logical symbols representing iff

In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff" [1] ) is a biconditional logical connective between statements, where either both statements are true or both are false.

Contents

The connective is biconditional (a statement of material equivalence), [2] and can be likened to the standard material conditional ("only if", equal to "if ... then") combined with its reverse ("if"); hence the name. The result is that the truth of either one of the connected statements requires the truth of the other (i.e. either both statements are true, or both are false), though it is controversial whether the connective thus defined is properly rendered by the English "if and only if"—with its pre-existing meaning. For example, P if and only if Q means that P is true whenever Q is true, and the only case in which P is true is if Q is also true, whereas in the case of P if Q, there could be other scenarios where P is true and Q is false.

In writing, phrases commonly used as alternatives to P "if and only if" Q include: Q is necessary and sufficient for P, P is equivalent (or materially equivalent) to Q (compare with material implication), P precisely if Q, P precisely (or exactly) when Q, P exactly in case Q, and P just in case Q. [3] Some authors regard "iff" as unsuitable in formal writing; [4] others consider it a "borderline case" and tolerate its use. [5]

In logical formulae, logical symbols, such as [6] and , [7] are used instead of these phrases; see § Notation below.

Definition

The truth table of PQ is as follows: [8] [9]

Truth table
PQ PQ PQP Q
TTTTT
TFFTF
FTTFF
FFTTT

It is equivalent to that produced by the XNOR gate, and opposite to that produced by the XOR gate. [10]

Usage

Notation

The corresponding logical symbols are "↔", [6] "", [7] and "", [11] and sometimes "iff". These are usually treated as equivalent. However, some texts of mathematical logic (particularly those on first-order logic, rather than propositional logic) make a distinction between these, in which the first, ↔, is used as a symbol in logic formulas, while ⇔ is used in reasoning about those logic formulas (e.g., in metalogic). In Łukasiewicz's Polish notation, it is the prefix symbol 'E'. [12]

Another term for this logical connective is exclusive nor.

In TeX, "if and only if" is shown as a long double arrow: via command \iff. [13]

Proofs

In most logical systems, one proves a statement of the form "P iff Q" by proving either "if P, then Q" and "if Q, then P", or "if P, then Q" and "if not-P, then not-Q". [1] Proving these pair of statements sometimes leads to a more natural proof, since there are not obvious conditions in which one would infer a biconditional directly. An alternative is to prove the disjunction "(P and Q) or (not-P and not-Q)", which itself can be inferred directly from either of its disjuncts—that is, because "iff" is truth-functional, "P iff Q" follows if P and Q have been shown to be both true, or both false.

Origin of iff and pronunciation

Usage of the abbreviation "iff" first appeared in print in John L. Kelley's 1955 book General Topology. [14] Its invention is often credited to Paul Halmos, who wrote "I invented 'iff,' for 'if and only if'—but I could never believe I was really its first inventor." [15]

It is somewhat unclear how "iff" was meant to be pronounced. In current practice, the single 'word' "iff" is almost always read as the four words "if and only if". However, in the preface of General Topology, Kelley suggests that it should be read differently: "In some cases where mathematical content requires 'if and only if' and euphony demands something less I use Halmos' 'iff'". The authors of one discrete mathematics textbook suggest: [16] "Should you need to pronounce iff, really hang on to the 'ff' so that people hear the difference from 'if'", implying that "iff" could be pronounced as [ɪfː].

Usage in definitions

Technically, definitions are always "if and only if" statements; some texts — such as Kelley's General Topology — follow the strict demands of logic, and use "if and only if" or iff in definitions of new terms. [17] However, this logically correct usage of "if and only if" is relatively uncommon, as the majority of textbooks, research papers and articles (including English Wikipedia articles) follow the special convention to interpret "if" as "if and only if", whenever a mathematical definition is involved (as in "a topological space is compact if every open cover has a finite subcover"). [18]

Distinction from "if" and "only if"

Sufficiency is the converse of necessity. That is to say, given PQ (i.e. if P then Q), P would be a sufficient condition for Q, and Q would be a necessary condition for P. Also, given PQ, it is true that ¬Q¬P (where ¬ is the negation operator, i.e. "not"). This means that the relationship between P and Q, established by PQ, can be expressed in the following, all equivalent, ways:

P is sufficient for Q
Q is necessary for P
¬Q is sufficient for ¬P
¬P is necessary for ¬Q

As an example, take the first example above, which states PQ, where P is "the fruit in question is an apple" and Q is "Madison will eat the fruit in question". The following are four equivalent ways of expressing this very relationship:

If the fruit in question is an apple, then Madison will eat it.
Only if Madison will eat the fruit in question, is it an apple.
If Madison will not eat the fruit in question, then it is not an apple.
Only if the fruit in question is not an apple, will Madison not eat it.

Here, the second example can be restated in the form of if...then as "If Madison will eat the fruit in question, then it is an apple"; taking this in conjunction with the first example, we find that the third example can be stated as "If the fruit in question is an apple, then Madison will eat it; and if Madison will eat the fruit, then it is an apple".

In terms of Euler diagrams

Euler diagrams show logical relationships among events, properties, and so forth. "P only if Q", "if P then Q", and "P→Q" all mean that P is a subset, either proper or improper, of Q. "P if Q", "if Q then P", and Q→P all mean that Q is a proper or improper subset of P. "P if and only if Q" and "Q if and only if P" both mean that the sets P and Q are identical to each other.

More general usage

Iff is used outside the field of logic as well. Wherever logic is applied, especially in mathematical discussions, it has the same meaning as above: it is an abbreviation for if and only if, indicating that one statement is both necessary and sufficient for the other. [1] This is an example of mathematical jargon (although, as noted above, if is more often used than iff in statements of definition).

The elements of X are all and only the elements of Y means: "For any z in the domain of discourse, z is in X if and only if z is in Y."

See also

Related Research Articles

In propositional logic, biconditional introduction is a valid rule of inference. It allows for one to infer a biconditional from two conditional statements. The rule makes it possible to introduce a biconditional statement into a logical proof. If is true, and if is true, then one may infer that is true. For example, from the statements "if I'm breathing, then I'm alive" and "if I'm alive, then I'm breathing", it can be inferred that "I'm breathing if and only if I'm alive". Biconditional introduction is the converse of biconditional elimination. The rule can be stated formally as:

Biconditional elimination is the name of two valid rules of inference of propositional logic. It allows for one to infer a conditional from a biconditional. If is true, then one may infer that is true, and also that is true. For example, if it's true that I'm breathing if and only if I'm alive, then it's true that if I'm breathing, I'm alive; likewise, it's true that if I'm alive, I'm breathing. The rules can be stated formally as:

First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.

Logical connective Symbol connecting sentential formulas in logic

In logic, a logical connective is a logical constant used to connect two or more formulas. For instance in the syntax of propositional logic, the binary connective can be used to join the two atomic formulas and , rendering the complex formula .

Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives. Propositions that contain no logical connectives are called atomic propositions.

<i>Principia Mathematica</i> Three-volume work on the foundations of mathematics

The Principia Mathematica is a three-volume work on the foundations of mathematics written by the mathematicians Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. In 1925–27, it appeared in a second edition with an important Introduction to the Second Edition, an Appendix A that replaced ✸9 and all-new Appendix B and Appendix C. PM is not to be confused with Russell's 1903 The Principles of Mathematics. PM was originally conceived as a sequel volume to Russell's 1903 Principles, but as PM states, this became an unworkable suggestion for practical and philosophical reasons: "The present work was originally intended by us to be comprised in a second volume of Principles of Mathematics... But as we advanced, it became increasingly evident that the subject is a very much larger one than we had supposed; moreover on many fundamental questions which had been left obscure and doubtful in the former work, we have now arrived at what we believe to be satisfactory solutions."

Subset Mathematical set contained in another set

In mathematics, a set A is a subset of a set B if all elements of A are also elements of B; B is then a superset of A. It is possible for A and B to be equal; if they are unequal, then A is a proper subset of B. The relationship of one set being a subset of another is called inclusion. A is a subset of B may also be expressed as B includes A or A is included in B.

Exclusive or True when either but not both inputs are true

Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ.

Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems of intuitionistic logic do not include the law of the excluded middle and double negation elimination, which are fundamental inference rules in classical logic.

In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If P then Q", Q is necessary for P, because the truth of P guarantees the truth of Q. Similarly, P is sufficient for Q, because P being true always implies that Q is true, but P not being true does not always imply that Q is not true.

In logic and mathematics, statements and are said to be logically equivalent if they are provable from each other under a set of axioms, or have the same truth value in every model. The logical equivalence of and is sometimes expressed as , , , or , depending on the notation being used. However, these symbols are also used for material equivalence, so proper interpretation would depend on the context. Logical equivalence is different from material equivalence, although the two concepts are intrinsically related.

Logical biconditional

In logic and mathematics, the logical biconditional, sometimes known as the material biconditional, is the logical connective used to conjoin two statements P and Q to form the statement "P if and only if Q", where P is known as the antecedent, and Q the consequent. This is often abbreviated as "P iff Q". The operator is denoted using a doubleheaded arrow, a prefixed E "Epq", an equality sign (=), an equivalence sign (≡), or EQV. It is logically equivalent to both and , and the XNOR boolean operator, which means "both or neither".

In propositional logic, double negation is the theorem that states that "If a statement is true, then it is not the case that the statement is not true." This is expressed by saying that a proposition A is logically equivalent to not (not-A), or by the formula A ≡ ~(~A) where the sign ≡ expresses logical equivalence and the sign ~ expresses negation.

In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: The input and output of a truth function are all truth values; a truth function will always output exactly one truth value; and inputting the same truth value(s) will always output the same truth value. The typical example is in propositional logic, wherein a compound statement is constructed using individual statements connected by logical connectives; if the truth value of the compound statement is entirely determined by the truth value(s) of the constituent statement(s), the compound statement is called a truth function, and any logical connectives used are said to be truth functional.

In propositional logic, transposition is a valid rule of replacement that permits one to switch the antecedent with the consequent of a conditional statement in a logical proof if they are also both negated. It is the inference from the truth of "A implies B" the truth of "Not-B implies not-A", and conversely. It is very closely related to the rule of inference modus tollens. It is the rule that:

Logical equality

Logical equality is a logical operator that corresponds to equality in Boolean algebra and to the logical biconditional in propositional calculus. It gives the functional value true if both functional arguments have the same logical value, and false if they are different.

In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }, consisting of binary conjunction and negation. Each of the singleton sets { NAND } and { NOR } is functionally complete.

In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a statement has its antecedent and consequent inverted and flipped. For instance, the contrapositive of the conditional statement "If it is raining, then I wear my coat" is the statement "If I don't wear my coat, then it isn't raining." In formulas: the contrapositive of is . The law of contraposition says that a conditional statement is true if, and only if, its contrapositive is true.

An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation. The general study of interpretations of formal languages is called formal semantics.

References

  1. 1 2 3 "The Definitive Glossary of Higher Mathematical Jargon — If and Only If". Math Vault. 1 August 2019. Retrieved 22 October 2019.
  2. Copi, I. M.; Cohen, C.; Flage, D. E. (2006). Essentials of Logic (Second ed.). Upper Saddle River, NJ: Pearson Education. p. 197. ISBN   978-0-13-238034-8.
  3. Weisstein, Eric W. "Iff." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Iff.html
  4. E.g. Daepp, Ulrich; Gorkin, Pamela (2011), Reading, Writing, and Proving: A Closer Look at Mathematics, Undergraduate Texts in Mathematics, Springer, p. 52, ISBN   9781441994790, While it can be a real time-saver, we don't recommend it in formal writing.
  5. Rothwell, Edward J.; Cloud, Michael J. (2014), Engineering Writing by Design: Creating Formal Documents of Lasting Value, CRC Press, p. 98, ISBN   9781482234312, It is common in mathematical writing
  6. 1 2 "Comprehensive List of Logic Symbols". Math Vault. 6 April 2020. Retrieved 4 September 2020.
  7. 1 2 Peil, Timothy. "Conditionals and Biconditionals". web.mnstate.edu. Retrieved 4 September 2020.
  8. p <=> q. Wolfram|Alpha
  9. If and only if, UHM Department of Mathematics, Theorems which have the form "P if and only Q" are much prized in mathematics. They give what are called "necessary and sufficient" conditions, and give completely equivalent and hopefully interesting new ways to say exactly the same thing.
  10. "XOR/XNOR/Odd Parity/Even Parity Gate". www.cburch.com. Retrieved 22 October 2019.
  11. Weisstein, Eric W. "Equivalent". mathworld.wolfram.com. Retrieved 4 September 2020.
  12. "Jan Łukasiewicz > Łukasiewicz's Parenthesis-Free or Polish Notation (Stanford Encyclopedia of Philosophy)". plato.stanford.edu. Retrieved 22 October 2019.
  13. "LaTeX:Symbol". Art of Problem Solving. Retrieved 22 October 2019.
  14. General Topology, reissue ISBN   978-0-387-90125-1
  15. Nicholas J. Higham (1998). Handbook of writing for the mathematical sciences (2nd ed.). SIAM. p. 24. ISBN   978-0-89871-420-3.
  16. Maurer, Stephen B.; Ralston, Anthony (2005). Discrete Algorithmic Mathematics (3rd ed.). Boca Raton, Fla.: CRC Press. p. 60. ISBN   1568811667.
  17. For instance, from General Topology, p. 25: "A set is countable iff it is finite or countably infinite." [boldface in original]
  18. Krantz, Steven G. (1996), A Primer of Mathematical Writing , American Mathematical Society, p.  71, ISBN   978-0-8218-0635-7