The History of Numbers
The concept of numbers, though appearing simple, is a complex abstraction that developed later in human intellectual history Early humans, like ancient shepherds, lacked formal counting methods and instead relied on primitive techniques, such as creating notches on a bone to represent each sheep they tended.
The counting numbers or natural numbers
Pythagoras of Samos, a sixth-century B.C mystic renowned for his famous theorem, believed that natural numbers form the fundamental building blocks of the universe.
Positive rational numbers, which arise from dividing a whole into smaller parts, represent a natural progression from natural numbers A number is classified as a positive rational if it can be expressed as the quotient of two natural numbers, commonly referred to as fractions.
Pythagoras and his followers were aware of fractions, but the revelation of irrational numbers—numbers that cannot be expressed as fractions—challenged the fundamental beliefs of the Pythagorean school and marked a significant crisis in mathematics The tale of Hippasus, a prominent Pythagorean philosopher who allegedly drowned at sea for revealing the incommensurability between the side of a square and its diagonal, illustrates this dramatic discovery This event has even inspired contemporary literature.
In the face of a significant mathematical crisis, Eudoxus of Cnidus introduced a groundbreaking theory of irrational quantities, laying the groundwork for the later rigorous formulations by Georg Cantor and Richard Dedekind in their development of the real number system This pivotal moment in mathematical history not only enriched the field but also opened new avenues for exploration and understanding.
The concept of zero was introduced by Hindus in the ninth century A.D., though some historians suggest it may have been known earlier by the Babylonians Negative and complex numbers, defined through imaginary numbers as the square roots of negative values, faced a gradual acceptance Despite their formal use in algebra over the centuries, the existence of negative and complex numbers was often regarded as absurd for nearly a millennium.
The economic developments of the fourteenth century, particularly the expansion of an international banking system from Italy, created a conducive environment for the acceptance of negative numbers as Europe transitioned from the Middle Ages to the Renaissance Influenced by Leonardo Fibonacci's observations in the thirteenth century, negative numbers began to be recognized as representations of loss, while positive numbers symbolized gains.
The acceptance of complex and negative numbers became widespread in the 1830s, following significant advancements in algebra during the early nineteenth century This period marked the transition from natural numbers to integers and rationals, as well as from real numbers to complex numbers Central to these mathematical developments was the concept of equivalence classes, although the formal language to describe this idea emerged only in the twentieth century.
In 1830, George Peacock released one of the pioneering texts on abstract algebra, distinguishing between "arithmetical" and "symbolical" algebra, with the former excluding negative numbers.
The acceptance of positive real numbers dates back to Eudoxus's development of irrational numbers, but a formal axiomatic construction of real numbers was not established until the nineteenth century Numerous mathematicians endeavored to create a solid foundation for real numbers, culminating in the successful work of Dedekind and Cantor in the 1870s.
The exploration of natural numbers reveals their inherent complexity, necessitating the foundational principles of set theory that emerged in the early twentieth century Key figures such as Richard Dedekind, Giuseppe Peano, Bertrand Russell, and Alfred North Whitehead played crucial roles in formalizing these concepts, which had been utilized for centuries prior.
We encourage you to explore the history of mathematics through coursework or read- ing Among the many texts are [1], [6], and [7].
The Algebra of Numbers
The development of number systems is influenced by both social conditions and intrinsic mathematical dynamics The transition from natural to rational numbers arises from practical human activities, such as combining and sharing objects Irrational numbers emerged in geometric contexts, notably during Eudoxus's time, when the lengths of diagonals were calculated from natural number sides Negative numbers, as discussed by Fibonacci, are conceptually clear but less intuitive in application This raises the question of the origins of complex numbers within the mathematical landscape.
Pause for a moment to reflect on the names given to the expanding sets of numbers.
They surely reflect the prejudices of the namers or, at the very least, the harsh criticism their introduction produced: positive versus negative, rational versus irrational, and real versus imaginary.
There is an algebraic way of explaining the need for most of these numbers and it
The Algebra of Numbers 5 introduces the concept of complex numbers through a series of elementary equations These equations utilize progressively larger sets of known numbers, revealing solutions that extend beyond these initial sets into more comprehensive collections.
Suppose that mCx Dn for natural numbersmandn Then exactly one of the following holds: n > m or nDm or n < m:
Ifn > m, then the equation has a solution in the natural numbers, which is calledn m.
The existence of solutions for equations of the form \( q nDm \) depends on the relationship between the integers \( n \) and \( m \) Specifically, when \( n < m \), negative integers are necessary for a solution to exist These equations, where \( n \) is not equal to zero, ultimately guide us to the rational numbers Additionally, polynomial equations with integer coefficients, such as \( anx^n + a1x^{n-1} + a2x^{n-2} + \ldots + a0 = 0 \), can lead to irrational and complex numbers For instance, the equation \( x^2 - 2 = 0 \) results in irrational numbers, while \( x^2 + 1 = 0 \) yields imaginary numbers.
The real numbers, which complete the rational numbers, were rigorously defined in the nineteenth century Before this, special attention was given to real solutions of polynomial equations with integer coefficients, known as algebraic numbers Additionally, proofs established that certain real numbers, such as π, are not algebraic, leading to their classification as transcendental numbers.
Rational numbers can be written as repeating decimals such as
3 D0:3 : : : : Remarkably, some rational numbers have two representations such as
To justify the former, let xD0:999 : : : :
Multiply both sides of the equation by10and subtract the first from the second to get9xD
9 You might have some reservations as to how the two right hand sides are subtracted.
Perhaps this is your first difficulty with encountering infinity.
The real numbers encompass all decimals, including those whose digits do not follow any specific pattern Defining this concept accurately can be more complex than it seems.
The Axiomatic Method
Mathematics holds a revered place in our culture, evoking feelings of awe or fear among many For some, it serves as a source of joy and admiration, viewed as an artistic endeavor of the highest caliber and the fundamental language through which the book of nature is expressed.
Mathematics derives its power from a combination of hard work, discipline, concentration, self-respect, and self-confidence While it may not have a royal road, it is accessible to those who are willing to engage deeply with the material To master mathematics, one must actively decipher its content by questioning and seeking answers, ultimately uncovering the intellectual journey behind proofs that may be obscured for aesthetic or precision reasons.
Mathematics originated as a practical discipline in Mesopotamia and Egypt, addressing everyday needs It involved the creation of rules for measuring distances, areas, and volumes, which laid the groundwork for the development of geometry.
The Greeks transformed geometry into an abstract theoretical discipline, beginning with Thales of Miletus and further developed by the Pythagorean school This evolution reached its peak with Euclid of Alexandria, who refined the deductive method to an exceptional standard The axiomatic approach embodies the key qualities of mathematics, including abstraction, linguistic precision, clarity, systematic thought, and transparent argumentation As the axiomatic method continues to serve as a foundation for justifying mathematical results, it is essential to explore and explain its main features.
In ordinary discourse, words are rarely defined Instead, the meaning of words is usually given implicitly by the socio-cultural and situational context within which they are uttered.
Ambiguity frequently arises, especially with abstract concepts, as individuals form their understanding of a word based on all the instances they have encountered it Consequently, dictionary definitions can sometimes be cyclical in nature.
In mathematics, not all terms can be precisely defined, as their meanings often rely on explanations involving other words This definitional process is endless unless we arrive at a term that is universally understood without the need for further clarification Such a term is referred to as a "primitive" word.
The axiomatic method utilizes primitive terms, such as point, straight line, and plane, which are foundational in geometry These primitive terms serve as the basis for defining other terms within the system, establishing a structured framework for geometric concepts.
Starting from undefined terms can make it challenging to define even simple objects, as individuals may have varying interpretations of terms This is crucial to address, given that discrepancies can arise even within mathematical literature, exemplified by the fundamental geometric concept of a triangle.
Figure 1.1.Triangle vs triangular region
Many people assume that everyone understands what a triangle is, but asking non-mathematicians for their definition often reveals a variety of responses, including drawings The most common answer may refer to a triangular area, like the shaded region in Figure 1.1 However, a geometer would define a triangle as the shape itself, represented by the unshaded figure This highlights the importance of clear definitions, even for seemingly simple mathematical concepts.
In an axiomatic system, primitive terms are not explicitly defined; instead, their meanings are derived from basic propositions known as axioms Unlike Euclid's traditional view of axioms as self-evident truths, the modern approach treats them as unproved propositions essential for proving other statements Axioms are necessary to provide a foundation for arguments; for instance, if one asserts that "freedom is preferable to happiness," the need for justification highlights the role of axioms in supporting such claims.
The conversation continues indefinitely as each statement requires justification from both parties This cycle persists until a mutual agreement on the truth of a statement is reached without the need for further justification.
Mathematicians skillfully construct a framework of verified propositions based on axioms and logical rules, with Euclid's Elements, written around 300 B.C., serving as the historical foundation for this axiomatic approach This method not only organizes a multitude of isolated mathematical facts into a cohesive structure but also enriches and enhances the learning experience by providing a meaningful context for educational activities.
In mathematics, a proof is a series of logical steps that establish the truth of a statement based on explicitly stated axioms or previously derived propositions It serves as the foundation of mathematics, not only validating mathematical statements but also fulfilling essential educational roles.
De Villiers, [2], we elaborate on the most important pedagogical functions of proof.
Proof might illuminate a mathematical result by giving an insight into why it is true.
Understanding the derivation of the quadratic formula reveals its underlying principles, while accepting it without question creates an air of mystery This reliance on authority can lead to uncritical acceptance of information, particularly when the lack of proof becomes a standard practice in education.
Proof serves as a vital communication tool, fostering productive dialogue and critical debate When proof is discussed in the classroom, the strength of an argument is publicly examined, aligning with the genuine practices of the mathematical community This dynamic remains relevant even in the imaginary exchange between a book's reader and its author.
Parallel Mathematical Universes
When establishing an axiomatic foundation for a mathematical area, a key question is whether a unique set of axioms exists Interestingly, different axiom collections can yield the same mathematical truths, defined as the ability to derive statements from the original axioms Additionally, altering even a single axiom—whether by removing, adding, or modifying it—can significantly transform the resulting mathematics.
Euclid’s Parallel Postulate, often discussed in high school geometry, asserts that through a point not on a given line, there is exactly one parallel line However, by altering this postulate to allow for no parallel lines or multiple parallel lines, we can develop new geometries These variations lead to the emergence of non-Euclidean geometries, which are mathematically valid and equally significant as traditional Euclidean geometry.
The issue of which geometry to use to model physical space has to be decided empir- ically Newtonian physics tried to model the physical universe with Euclidean geometry.
After the work of Einstein on relativity, the accepted model of space (or more precisely space-time) is based on non-Euclidean geometry.
Mathematical Statements
Whatever mathematics may be as a mental activity, it is communicated as a language.
Mathematics possesses a unique syntax, specialized terminology, and distinct conventions, making it an exact science This precision is crucial, as any deviation from established norms can significantly alter the intended meaning of mathematical expressions.
This chapter aims to clarify key principles related to mathematical logic, a field that formalizes the foundations of mathematical reasoning These principles are integral to mathematical thought, influencing both conscious and subconscious processes in the discipline.
In mathematics, we assert the truth of some statements Other statements are to be proved or disproved This is a fundamental dichotomy:
No mathematical statement is both true and false.
Viewed axiomatically, you can take trueandfalseto be undefined terms; the above di- chotomy can be taken as an axiom We should clarify what is meant by a mathematical statement.
Definition 1 A declarative sentence is alogical statementif and only if it is unambiguously either true or false Amathematical statementis a logical statement used in mathematical discourse.
Bystatement, without an adjective, we will always mean a logical or, usually, a mathe- matical statement Here are some examples.
The number2is positive. is a true mathematical statement and the sentence
The number 2000 is divisible by 3. is a false mathematical statement Note that the previous two sentences are both declarative.
By definition, sentences that are not declarative cannot be logical statements; such sen- tences are neither true nor false An interrogative sentence such as
Who is there? is not a logical statement An imperative sentence such as
Go away. is not a logical statement An exclamatory sentence such as
Wow! is not a logical statement A sentence like
Hello. is not a logical statement either.
A declarative sentence may be a logical statement even if its truth value is not known.
This is common in the most advanced areas of mathematics; it is the fuel of mathematical research The following sentence
The 10th digit in the decimal expansion of a number is 3, representing a clear mathematical statement Regardless of whether this assertion is true or false, it must definitively be one or the other, highlighting the importance of unambiguity in mathematical definitions.
Not every declarative sentence is a statement Opinions are not logical statements For example, the declarative sentence
While many people may consider vanilla to be the best ice cream flavor, this is ultimately a subjective opinion rather than an objective truth Individual preferences can vary greatly, making it impossible to definitively label any flavor as the best.
Vanilla is Jon’s favorite ice cream flavor. may be a statement for a specific person named Jon The sentence
Socrates is often regarded as a prominent philosopher, but to truly understand what makes a philosopher "good," we must define the criteria for this quality While the statement about Socrates holds logical significance, evaluating philosophical merit is more subjective than mathematical.
The examples given above are usually calledsimplestatements since they cannot be broken into pieces that are themselves statements Some authors call simple statements atomsoratomicstatements.
In Section 2.2, we will explore compound statements that incorporate connectives such as not, and, or, if, then, implies, and equivalent The authors refer to simple statements as atomic statements, while compound statements are termed molecular statements.
You might also imagine statements involving variables The sentences
The square of every real number is nonnegative.
Mathematical Connectives
A real number can have a square that is not positive, exemplified by the number zero While both statements are true, they differ in their implications; the first refers to all real numbers, while the second pertains specifically to at least one real number This concept of predicates, which involve variables and quantification, will be explored in Section 2.5.
Understanding the meaning of logical connectives such as "not," "and," and "or" is crucial, as their colloquial usage may differ from their mathematical implications In logic, these terms are defined based on truth values, where the truth values of compound statements depend on the truth values of the individual simple statements they comprise This distinction is essential for accurately interpreting and constructing logical statements.
Linguistics plays a crucial role in the translation between mathematical or logical language and natural languages like English, which can be complex This chapter will present statements in symbolic logic alongside their English translations Although we will eventually move away from logical notation, we encourage you to incorporate some of it as a shorthand in your mathematical writing, as highlighted in Remark 43 at the chapter's conclusion.
We are now ready to study the different connectives used in creating compound statements.
These are being defined in a formal way, based on truth values, rather than linguistically, based on the colloquial usage of English.
An integer is called aneven numberwhen it equals twice some integer and is called anodd numberwhen it equals one plus twice some integer The statement
3 is an odd number. is a true mathematical statement; the statement
The statement "3 is not an odd number" is a false mathematical assertion This leads us to consider the relationship between the two statements, where the second can be viewed as the negation of the first To clarify this relationship, we will define negation in terms of truth values rather than in a casual manner.
Definition 2 For a mathematical statementp, thenegationofpis a mathematical state- ment, denoted:p, whose truth value is the opposite of the truth value ofp.
We denote the negation of a statement,p, bynot p; some denote it symbolically as eitherpor p, rather than:p We can illustrate Definition 2 using the following truth table: p :p
A truth table displays truth values, denoted as T for true and F for false, across its column headings in each row For the truth table of not p, the first row shows that when p is true, not p is false, while the second row reveals that when p is false, not p is true These tables serve as a concise method for representing the truth values of interconnected statements, beginning with basic statements like p.
In everyday language, we often negate a statement by using the word "not." However, negation is more complex than simply replacing "p" with "not." For instance, if "p" represents a specific statement, the transformation requires careful consideration of context and meaning.
3 is not an odd number. rather than
Not 3 is an odd number.
Mathematical statements can be combined into more complex expressions using the connective "and." To understand this connection, we can define it through a truth table, illustrating how the truth values of the individual statements affect the overall statement's truth.
Definition 3 For mathematical statements p andq, the conjunctionofp andq is the mathematical statement, denotedp^q, whose truth value is false unless bothpandqare true.
The truth value of a conjunction varies according to the following truth table: p q p^q
We will generally writepandqfor the conjunctionp^q Some authors use the notation pqorp&q.
An example of conjunction is the statement
2 is positive and 3 is negative.
3 is negative is a false statement.
The conjunction of two statements is true only when both statements are true; if at least one statement is false, the conjunction is false.
2.2 Mathematical Connectives 13 tempting to think that the conjunction “false and false” is a true statement, but this is non- sense, in everyday language as well as in mathematics.
You might think we were being pedantic in defining negation and conjunction of mathe- matical statements The next two definitions may change your mind Is the statement
The statement that either 2 or 3 is positive is true, as both numbers are indeed positive Therefore, it is incorrect to assert that only one of these numbers can be considered positive.
In English, the word "or" can create ambiguity, as it may imply one option, the other, or both This uncertainty is particularly evident in phrases like "I took a bath or I took a shower," which can leave the listener unsure whether the speaker engaged in one activity, the other, or both To clarify this ambiguity, a mathematical definition can be applied, distinguishing between exclusive and inclusive interpretations of "or."
Definition 5 For mathematical statementspandq, thedisjunctionofpandqis a mathe- matical statement, denotedp_q, whose truth value is true unless bothpandqare false.
We see that the of truth value of a disjunction varies according to the following truth table: p q p_q
We will generally writeporqfor the disjunctionp_q As we said above, you should be extremely careful, since the wordoris not used with its most common meaning When someone says
I will give my ticket to Alex or to Jamie. it is implied that only one person will receive the ticket: either Alex or Jamie, but not both.
In mathematics, we useorin the sense ofat least one.
In mathematics, the disjunction of two statements is true if at least one of the statements is true, which is often referred to as the mathematical "or" or inclusive "or." This contrasts with the everyday use of "or," known as exclusive "or," where both statements cannot be true simultaneously Some individuals advocate for the term "xor" to denote exclusive "or," though opinions on its usefulness vary Ultimately, the debate over the terms "xor" and "and/or" reflects differing preferences in mathematical language.
Negation, conjunction, and disjunction are typically identified by specific keywords: "not" indicates negation, "and" signifies conjunction, and "or" represents disjunction However, the use of notation can obscure these logical constructions In the context of three true statements, this can affect the clarity of their relationships.
566 the first is a disjunction because it can be interpreted as1 < 1or1 D1, the second is the conjunction2 < 3and3 < 4, and the third is a conjunction of two disjunctions.
We now introduce two additional types of compound statements: implications and equiva- lences These are also calledconditionalsandbiconditionals, respectively, by some authors.
The next construct, implication, also disagrees with the common colloquial interpretation.
Definition 8 For mathematical statementspandq, theimplication(orconditionalstate- ment) thatpimpliesq, denotedp )q, is a mathematical statement whose truth value is true unlesspis true andqis false.
We see that the of truth value of an implication varies according to the following truth table: p q p)q
In logic, implications are often expressed as "if p, then q" or using symbols such as p → q or p ⇒ q, with some authors preferring p ! q or p ⟹ q In this context, the statement p is referred to as the hypothesis or antecedent, while the statement q is known as the conclusion or consequent of the implication.
Remark 9 In ordinary language, it is understood, for a statement of the formifp, thenq, that there exists a causal connection betweenpandq, as in
If you leave me, then I will be badly hurt.
A conditional statement in mathematics is deemed false only when the hypothesis is true and the conclusion is false It's important to note that a false hypothesis results in a true implication, which means that no causal relationship should be assumed.
Example 10 Here are four examples:
If2is positive, then3is positive. is a true statement since both the hypothesis and the conclusion are true statements.
If2is negative, then3is positive. is a true statement since the hypothesis is false.
If2is negative, then3is negative.
2.2 Mathematical Connectives 15 is a true statement since the hypothesis is false.
If2is positive, then3is negative. is a false statement since the hypothesis is true, but the conclusion is false.
Carefully analyze the middle two examples to grasp their validity Don't be misled by the seemingly trivial nature of the hypotheses and conclusions; understanding the truth values of both the hypothesis and conclusion in any implication allows you to easily determine the truth value of that implication.
Symbolic Logic
Symbolic logic is a vast field that could easily fill an entire course; however, this article will focus on key compound statements that are essential for occasional use.
Before delving into the topic, it's essential to understand how statements in symbolic logic are analyzed This section will focus on symbolic notation, while English interpretations will be addressed in the following section.
Remark 15 A rule for the order of operations in arithmetic is that multiplications are performed before additions So
There are also rules for the order of operations in logic Reading from left to right, do things in the following order: parentheses (or brackets, etc.)
Symbolic logic encompasses key operations such as negation, conjunctions, disjunctions, implication, and equivalence These operations are organized hierarchically using parentheses and brackets, ensuring that nested groupings are evaluated from the innermost to the outermost, similar to the evaluation of algebraic expressions.
We think of this as working from the inside out.
In logical expressions, the notation :p_q is equivalent to :p/_q, but distinct from :p_q/ Consistent rules must be applied within matched pairs of parentheses For instance, two compound statements, such as a_:b^c) :d^e, :f ^g_h)i, demonstrate this equivalence among simple statements a, b, c, , i.
To accurately evaluate expressions, begin with the innermost pairs of parentheses, followed by square brackets, then curly braces, and finally angle brackets.
In propositional logic, if the statement \( p \) is true, then the disjunction \( p \lor \neg p \) is also true, regardless of the truth value of \( \neg p \) Conversely, if \( p \) is false, then \( \neg p \) is true, which still makes the disjunction \( p \lor \neg p \) true This relationship is illustrated in the accompanying truth table.
In the context of logic and mathematics, the column for p shows that all T's are present, indicating that p is not always true This highlights the importance of asking clear questions to your mathematics instructor, as vague inquiries like “Will this topic be covered on the exam?” may lead to accurate but unhelpful answers, such as “Yes.”
Every simple statement, such as 1D1 or 1D2, is classified as either true or false A statement that is true is referred to as a tautology, while a false statement is known as a contradiction The complexity arises when dealing with compound statements, which present a more intriguing scenario.
Definition 17 A compound statement is atautologyif and only if it is true for all possible truth values of its component statements.
Tautologies are easily recognized in truth tables: their columns contains only T’s Next we examine the other extreme.
In propositional logic, if proposition \( p \) is false, the conjunction \( p \land \neg p \) is also false, regardless of the truth value of \( \neg p \) Conversely, if \( p \) is true, then \( \neg p \) is false, leading to the conjunction \( p \land \neg p \) being false as well This relationship can be illustrated in a truth table, which shows only false values in the column for \( p \land \neg p \).
Definition 19 A compound statement is acontradictionif and only if it is false for all possible truth values of its component statements.
Contradictions are easily recognized in truth tables: their columns contains only F’s.
Contradictions are important in mathematics In fact, we will see in the next chapter that contradictions can actually be useful in proving theorems.
Let us look at a couple of additional examples.
Example 20 The following truth table shows that the implicationp)pis a tautology. p p)p
Example 21 The equivalence::p,pis a tautology: p :p ::p ::p,p
The following shows that some data can be extraneous.
Exercise 22 Use truth tables to show that the following are tautologies:
(a)p^q)p (b)p)p_q The following gives us an alternative definition of implication.
Exercise 23 Use a truth table to show thatp)q, :p_qis a tautology.
The following exercise may remind you of the concept of equality Note these three properties of equality: xDx; x Dyif and only ifyDx; and xDyandyDzimpliesxDz; for allx,y, andz.
Exercise 24 Use truth tables to show that the following are tautologies:
The logical expressions "p only if q" and "q if p" indicate a relationship between p and q, suggesting that "p if and only if q" is equivalent to "p if q" and "p only if q." This establishes a significant principle that will be frequently utilized in our discussions.
Exercise 25 Use a truth table to show that
Remark 26 In Definition 13, we defined the equivalence ofpandq, denoted byp,q.
Exercise 25 could have been utilized to establish the concept of equivalence Specifically, in Definition 13, we could define propositions p and q as (p ↔ q) and (q ↔ p), demonstrating their equivalence through the truth table outlined in Definition 13.
Truth tables serve as a valuable tool for demonstrating various logical statements It's important to note that utilizing truth tables is a concise method for this purpose For instance, articulating the proof of Exercise 25 in a detailed manner would involve a thorough explanation of the logical relationships and outcomes represented in the truth table.
Proof There are four cases:
3 pis false andqis true, and
First, supposepis true andqis true Hence,ifp, thenqis true andifq, thenpis true.
Therefore, the conjunctionifp, thenq, and ifq, thenp is true Moreover, sincep andq are true,pis equivalent toqis true This completes the first case.
Second, Exercise 27 Complete the proof, started above, of Exercise 25 using words.
Conditional statements allow us to create implications such as "p implies q" and "q implies p" from given statements p and q Additionally, by negating p and q, we can form other significant implications Three of these constructions are noteworthy enough to have specific names.
Definition 28 Theconverseof the implicationp)qis the implicationq)p.
The converse of the statement "if p, then q" is "if q, then p." While a statement can be true, its converse may be either true or false, which can be explored through various examples and exercises.
Exercise 29 If possible, give examples of each of the following:
(a) a true implication whose converse is true, (b) a true implication whose converse is false, (c) a false implication whose converse is true, (d) a false implication whose converse is false.
Letpandqbe simple statements The implication ifp, thenqcan only be false when pis true andqis false Similarly, ifq, thenpcan only be false whenqis true andpis false.
In the previous exercise, it became clear that both an implication between simple statements and its converse cannot be false simultaneously If you believed otherwise, it likely stemmed from the introduction of a variable in your statements Soon, we will explore the introduction of variables and quantifiers, which will add complexity but also enhance the intrigue of our discussions.
Definition 30 Thecontrapositiveof the implicationp)qis the implication:q) :p.
So, the contrapositive of the statementifp, thenqis the statementif notq, then notp.
Example 31 The contrapositive of the statement
If the moon is made of cheese, then1D2 is the statement
If1¤2, then the moon is not made of cheese.
You should recognize that both of these statements are true.
The truth value of a contrapositive statement is always the same as the truth value of the original statement.
Exercise 32 Prove that an implication is equivalent to its contrapositive That is, p)q, :q) :p:
Definition 33 Theinverseof the implicationp)qis the implication:p) :q.
Compound Statements in English
Statements can get complex and writing statements in English is further complicated be- cause we do not use parentheses to indicate order of thoughts; commas can play an impor-
Predicates and Quantifiers
tant role We use italics and quotation marks to try to clarify sentences in this chapter, but this is a luxury upon which we should not depend.
In this analysis, we define three statements: p represents the assertion that statement 1 is negative, q indicates that statement 2 is negative, and r signifies that statement 3 is positive Consequently, our compound statement can be expressed as p ∧ q ∨ r, illustrating the relationship between these statements.
For symbolic logic, the order of operations dictates that this is equivalent to
Sincepandqare false andris true, this statement is true Notice thatp^q_ris different fromp^.q_r /; in fact,p^.q_r /is false.
How do we make this distinction in written English? In the following two statements
1is negative and2is negative, or3is positive.
In logical expressions, the placement of commas significantly impacts interpretation, as seen in the distinctions between p^q/_r and p^.q_r Understanding these nuances is crucial for accurate analysis, particularly when determining the negativity or positivity of the statements involved.
In spoken English, it is very difficult to hear those little commas!
An alternative is to rephrase the sentences This is not so simple For example,
The conjunction of the statement1is negative and the disjunction of the statements2is negative and3is positive.
The statement "p if and only if q" can be expressed as the conjunction of two implications: "if p, then q" and "if q, then p."
Take another look at Example 12 Also, did you have any difficulties with Exercise 29?
In this section, we explore the introduction of variables in logical and mathematical statements, highlighting their significance in most mathematical theorems Variables, often referred to as free variables, are essential as they can change freely within these statements, prompting deeper thought and understanding.
The square of 2is positive. is true since 2/ 2 D4.
The statement "The number x is positive" lacks logical clarity due to the presence of an unresolved variable Without a specific value for x, it is impossible to determine the truth of the statement For instance, if x equals 2, the statement is true; however, if x equals 4, it becomes false.
A predicate is defined as a declarative sentence containing one or more unresolved variables, which becomes a statement when specific values are substituted for those variables The term "unresolved" indicates that no values or potential sets of values have been assigned to the variables In the realm of mathematical logic, a predicate is often referred to as a propositional function or a sentential function.
Two other examples of predicates arex0andxCyD0; the former has one variable and the latter has two variables Using functional notation, we could denote these predicates byP x/andQ.x; y/, respectively.
Similar to logical statements, predicates can also be negated For example, if P(x) represents the condition x ≥ 0, then not P(x) would indicate x < 0 While this can apply to real numbers, it is important to note that such assertions typically require formal proof.
Predicates also can be combined to form new predicates as is illustrated in the following exercise.
Exercise 36 Equations and inequalities involving variables are predicates.
(a) Determine all real numbersxfor which the conjunction xC3 > 6andx 2 < 3 is a true statement.
(b) Similarly, determine all real numbersxandyfor which the disjunction xyD0or2x 3yD0 is a true statement.
Substituting a single value for a variable typically lacks significance, as it can be done directly, converting a predicate into a straightforward statement For instance, rather than expressing a predicate with a substitution like x^2 > 3 for x = 2, we can simply state the conclusion.
However, there are two important ways of creating statements out of predicates; this is calledquantifyinga predicate.
For all real numbers,x 2 D4. is a false statement since5 2 ¤4 This is one kind of quantifier.
Definition 37 LetS be a set and letP x/be a predicate Theuniversal quantifieris a phrase of the formfor allx 2 S, denoted8x 2 S Theuniversally quantified predicate sentence
8x2S; P x/ is a mathematical statement that is true if and only ifP x/becomes a true statement when- ever an element ofSis substituted forxin the predicateP x/.
In mathematical writing, we use the notation "for all x ∈ S, P(x)" to indicate universal quantification It is important to note that phrases like "for every x ∈ S" and "for any x ∈ S" also serve as universal quantifiers Caution is advised when using the word "any," as it may be misconstrued to imply "some" instead of "every." Additionally, the expression "for all real numbers x" is synonymous with "for every x ∈ R."
Example 38 Which of the following statements are true and which are false?
(a) For all real numbersx,.xC3/ 2 C.x 2/ 2 > 0.
(b) For all real numbersx,p x 2 Dx.
For (a), the squares are nonnegative xC3/ 2 D0only ifx D 3and.x 2/ 2 D0 only ifx D 2 So they cannot both be equal to0for the samex Therefore, the statement in (a) is true.
For (b), the square root notation denotes the nonnegative square root ForxD 1, p 1/ 2 Dp
In certain statements, a universal quantifier may be implicit, making it beneficial to rephrase the statement for clearer logical analysis This often occurs when the defining set of the universal quantifier is not explicitly stated.
For any real number \( x \), a positive square root exists; however, this is only valid within the set of positive real numbers In contrast, this assertion fails for the broader set of real numbers In cases where the set is unspecified, it is generally assumed to refer to the set of real numbers.
Example 40 In geometry, the isosceles triangle theorem may be stated:
The angles at the base of an isosceles triangle are congruent.
This could be restated as follows:
For every triangleT, ifT is isosceles, then the angles at the base are congruent.
You might even wonder exactly what set of triangles we are talking about!
There existsx, such thatx 2 D4. is a true statement since2 2 D 4; it is also true since 2/ 2 D 4 The expression “there exists” is a new type of quantifier.
Definition 41 LetS be a set and let P x/be a predicate The existential quantifieris a phrase of the formthere exists x 2 S, denoted9x 2 S Theexistentially quantified predicatesentence
9x2S; P x/ is a mathematical statement that is true if and only ifP x/becomes a true statement for at least one element ofSsubstituted forxin the predicateP x/.
In mathematical logic, we express the existence of elements within a set by stating "there exists x in S such that P(x) holds for some x in S." This phrase is commonly associated with existential quantifiers It is important to be cautious with the term "any" in this context to avoid ambiguity.
Example 42 Which of the following statements about sets of real numbers are true and which are false?
(c) There existx; ysuch thatx 2 Cy 2 D1.
(d) There existsxsuch that sin 2 xCcos 2 xD0.
Statement (a) is true sincex D 5satisfies the equation Statement (b) is true since x D 1 2 satisfies the equation Statement (c) is true since, for example, x D y D p
2=2, satisfies the equation Statement (d) is false since sin 2 xCcos 2 xD1for allx.
Notice that the set of values forxis important: if the wordrealwere changed tonatural, then all three statements above would be false.
Let us see how we negate a sentence that is introduced by a universal quantifier The statement
The statement "For all x and y, x + y = 0" is false The negation of this sentence asserts that there exist numbers x and y such that their sum is not zero Thus, the correct negation indicates that not all pairs of numbers add up to zero.
This is a true statement In general, the negation of the statement
For allx,P x/. is the statement
There exists anxsuch that notP x/.
The negation of predicates with more than one variable is defined in an analogous way.
To see how we negate a sentence that is introduced by the existential quantifier, we look at the following example The statement
The statement "There exists a number x such that x² < 0" is false Since no number can have a negative square, it follows that the square of all numbers is nonnegative Therefore, the negation of the original statement confirms this truth.
2.5 Predicates and Quantifiers 25 which is equivalent to
In general, the negation of the statement
There existsxsuch thatP x/. is the statement
Remark 43(logical notation) Although we have mentioned the symbols:,^,_,),,,
In this chapter, we will refrain from using the symbols 8 and 9, which are commonly employed in handwritten mathematics Notably, symbols for implications, equivalences, and quantifiers prove to be particularly beneficial Additionally, some individuals utilize the symbol 3 or "t" to denote "such that," the asterisk (*) for "since" or "because," and the parenthesis ")" for "therefore," "thus," or "hence."
We prefer to use double barred arrows (),(,,) for logical operations since single barred arrows, especially!, are used frequently in the notation for functions.
Supplemental Exercises
This chapter presents sixteen key terms, each italicized for emphasis, and explores the concept of truth values, which can be classified as true or false but may also be considered undefined In the context of logical or mathematical statements, represented by the variables p and q, it is essential to define these statements clearly and provide relevant examples for better understanding.
A logical statement can be defined in various ways, including as a mathematical statement The negation of a statement p is denoted as ¬p The conjunction of statements p and q is represented as p ∧ q, while the disjunction is expressed as p ∨ q Additionally, the implication of p implies q is written as p → q, indicating that if p is true, then q must also be true The equivalence of statements p and q is denoted as p ↔ q Lastly, a compound statement is termed a tautology when it is always true.
Definition 19.a compound statement is acontradiction Definition 28.theconverseof an implicationp )q Definition 30.thecontrapositiveof an implicationp)q Definition 33.theinverseof an implicationp)q Definition 37.theuniversal quantifier
Definition 37.anuniversally quantified predicatesentence Definition 41.theexistential quantifier
Supplemental Exercise 1 Are the following statements true or false? Explain.
Supplemental Exercise 2 Are the following statements true or false? Explain.
Supplemental Exercise 3 Are the following statements true or false? Explain.
(b) There exists a real numberxsuch thatx > 0.
Supplemental Exercise 4 Are the following statement true or false? Explain.
(a) For all real numbersx,x0orx0.
(b) There exists a real numberxsuch thatx0andx0.
In Supplemental Exercises 5–38, use truth tables to show that each statement is a tautology.
Supplemental Exercise 5 p^.p)q/)q Supplemental Exercise 6 :p^.q)p/) :q Supplemental Exercise 7 :p^.p_q/)q Supplemental Exercise 8 p).q)p^q/
Supplemental Exercise 9 .p)q/^.q)r /).p)r / Supplemental Exercise 10 .p^q)r /,.p)Œq)r /
Supplemental Exercise 12 .p)Œq^ :q/) :p Supplemental Exercise 13 .p)q/).p_r)q_r / Supplemental Exercise 14 .p)q/).Œq)r )Œp)r /
Supplemental Exercise 22 p_.q^r /,.p_q/^.p_r / Supplemental Exercise 23 p^.q_r /,.p^q/_.p^r / Supplemental Exercise 24 p_p,p
Supplemental Exercise 25 p^p,p Supplemental Exercise 26 :.p_q/, :p^ :q Supplemental Exercise 27 :.p^q/, :p_ :q
Supplemental Exercise 28 p)q, :p_q(This gives us a useful equivalent definition of implication.) This implies::.p)q/,p^ :q.
In Supplemental Exercises 35–38, letF andT represent statements that are always false or true, respectively.
Supplemental Exercise 35 p_F ,p Supplemental Exercise 36 p^F ,F Supplemental Exercise 37 p_T ,T Supplemental Exercise 38 p^T ,p
Supplemental Exercise 39 Is the following statement true or false? Explain.
For allxandy,jx yj D jy xj.
Supplemental Exercise 40 Show thatq^.p ) q/ ) p is not a tautology (This is sometimes referred to as the fallacy of asserting the conclusion.)
To demonstrate that the expression \( (p \land q) \implies (p \implies q) \) is a tautology, we can employ proof by contradiction, a technique that will be explored further in Section 3.3 of Chapter 3 In this context, \( F \) represents a false statement, and our goal is to show that the implication holds true under all possible truth values for \( p \) and \( q \).
In logic, a statement can feature multiple quantifiers, and while the sequence of identical quantifiers is flexible, the arrangement of different quantifiers is crucial This distinction is essential because it affects the meaning of the statement, leading to different interpretations based on the order in which quantifiers are presented Understanding the significance of quantifier order is vital for clear communication and accurate reasoning in logical expressions.
8x2S 9y2S xDy are not equivalent whenSDR, but are equivalent whenSD f0g.
Supplemental Exercise 43 Project.Investigate the role of formal logic in the develop- ment of mathematical practice and philosophy.
What is Mathematics?
Understanding the formal nature of a statement allows us to justify its truth or falsity Since the advent of the deductive method in Ancient Greece, proof has served as a cornerstone for validating mathematical knowledge Beyond justification, proof organizes mathematical results, elucidates their truths, and fosters clearer communication within the field Furthermore, it aids in developing mathematical competence and facilitates the discovery of new mathematical insights.
Mathematics is fundamentally a creative pursuit, where theorems are not simply bestowed by authority figures but are the result of human effort and understanding Engaging in mathematics involves the creation of theorems and their proofs, reflecting individual exploration and insight While some may argue otherwise, the educational experience often positions professors and textbooks as authoritative figures, expecting students to undertake the challenging work of discovery and proof.
This article focuses on the process of constructing proofs rather than the discovery of theorems Throughout their education, from elementary school to master's programs, mathematics students seldom engage with the creation of theorems The pursuit of discovering new theorems becomes central during doctoral dissertations and in mathematical research.
Typically, a theorem is accompanied by its proof, requiring you to understand both elements To effectively learn how to construct proofs, consider how you would approach proving the theorem yourself Embracing a mathematical mindset involves reading deliberately and taking time to reflect Periodically asking yourself questions during this process will enhance your comprehension and analytical skills.
“What can I try to prove next?” you will be better able to construct proofs and perhaps you will be taking your first firm step towards becoming a mathematician.
To enhance your understanding of theorems and proofs, it is essential to frequently think of examples and create visual representations These activities are interconnected, as working through examples can clarify the underlying principles that validate a theorem and guide you in constructing a proof Additionally, by altering the hypotheses and examining cases where the conclusion does not hold, you can identify counterexamples that highlight the critical concepts needed for a successful proof.
Many people find that images in mathematics textbooks often fail to provide clarity This is because the value of a diagram lies in its construction rather than its final appearance Similar to simply looking up answers in the back of a textbook, having the solution does not shed light on the process of solving the problem.
If you get nothing else out of this chapter, we hope you will understand two things.
To master complex subjects, especially in mathematics, prioritize deep thinking over extensive reading, as it may take hours or even days to fully grasp a single page Additionally, actively engage with the material by considering examples and counterexamples, and utilize drawings to enhance understanding; visual representations can reveal insights that mental images alone may not convey.
In the remainder of this chapter, we will examine various techniques of proof.
Direct Proof
A universally quantified predicate statement in mathematics is expressed as "for all x in S, if p(x), then q(x)," where p(x) and q(x) are predicates This form is commonly encountered in mathematical proofs, making it essential for understanding various mathematical concepts.
To demonstrate that the given statement is a tautology, we need to establish that for every instance where p(x) is true, q(x) must also be true The truth table provided clearly illustrates this relationship, confirming that whenever p(x) holds, q(x) follows accordingly.
To demonstrate the validity of the statement “for all x, p(x) implies q(x),” it is essential to ensure that the scenario in the second row of the truth table, where the implication is false, never occurs This situation arises when p(x) is always false, leading to the conclusion that the statement is considered vacuously true For further reference, see Remark 11 in Chapter 2.
Direct proof is a fundamental method in mathematical reasoning, often described as "by brute force" or "following your nose." This approach involves straightforwardly demonstrating the truth of a statement through logical deductions and established principles.
“brute force” implies some sort of explicit computation, all the descriptions describe the basic nature of a direct proof.
Many mathematicians often use the term "construct" when referring to proofs, but this usage can be misleading The phrase "constructive proof" is associated with the constructivist philosophy of mathematics, which asserts that a mathematical object is only considered to exist if it can be explicitly constructed or demonstrated with a concrete example However, not all mathematicians adhere to this philosophy, and the term does not necessarily imply a direct proof.
The basic idea of direct proof is simple: start from the hypotheses, make a sequence of implications, and arrive at the conclusion.
An Example of a Direct Proof
Here are the first five axioms from Euclid’sElements This book, written around 300B.C., was the prototype of mathematical exposition for two millennia.
According to Axiom 1, when two straight lines are crossed by a transversal and the sum of the interior angles on one side is less than 180 degrees, it indicates that the two lines will converge on that same side.
Axiom 2 Things that are equal to the same thing are equal to one another.
Axiom 3 If equals are added to the same thing, the sums are equal.
Axiom 4 If equals are subtracted from equals, the differences are equal.
Axiom 5 All right angles are equal to one another.
These axioms are referred to in the next proof.
Proposition 2 If two different lines intersect, then their vertical angles are equal.
Before writing down a proof, let us start with a picture Consider Figure 3.1, which shows two intersecting lines.
The figure serves as a helpful reference for our proof by labeling the angles involved If you're unfamiliar with vertical angles, you can deduce their definition from the proposition and the accompanying figure Our goal is to demonstrate that angle BAC is equal to angle DAE, and that angle CAD is equal to angle EAB.
In the proof, let lines BAD and CAE intersect at point A, resulting in angles BAD and CAE, each measuring two right angles, or 180 degrees According to Axiom 5 and the established method of constructing perpendicular lines, the angle formed at any point on a line is equal to two right angles By subtracting angle CAD from both angles and applying Euclid’s Axiom 4, we arrive at the conclusion that angle BAC is equal to angle DAE, thereby proving our statement.
Using the same line of reasoning, we can prove that†CADD †EAB.
Exercise 3 Complete the proof of Proposition 2: prove†CADD †EAB.
If you prefer to think about the measures of angles, then you might rewrite the above proof as follows:
Proof LetBADandCAEbe two lines intersecting at the pointA Then m†BADD and m†CAE D: Therefore, m†BADDm†CAE and m†BAD m†CAD Dm†CAE m†CAD:
Since m†BAC Dm†BAD m†CAD and m†DAEDm†CAE m†CAD; we have proved that m†BAC D m†DAE Using the same line of reasoning, you can prove that m†CADDm†EAB.
Incorporating drawings can enhance your thought process when tackling complex problems However, it's crucial to avoid making assumptions based on these sketches; for instance, when demonstrating properties of intersecting lines, ensure they do not automatically intersect at right angles unless specified.
Proof by Brute Force: Another Example of Direct Proof
Every even integer can be represented as 2n for some integer n, while every odd integer can be expressed as 2n + 1 for a certain integer n This article explores and proves various statements concerning even and odd integers.
Proposition 5 The sum of two even integers is even.
Proof Start with any two even integers, x andy Since x and y are even, there exist integersmandnsuch thatxD2mandyD2n Then xCyD2mC2nD2.mCn/D2k; wherekis the integermCn Hence,xCyis even.
In the proof of Proposition 5, we implicitly assumed that the sum of two integers results in an integer, a fact that can be demonstrated through the construction of integers and the operation of addition This concept, while seemingly straightforward, is surprisingly complex and will be explored in detail in Chapter 10.
Proposition 7 The square of any odd integer is odd.
Proof Every odd integer is of the formxD2nC1for some integern Then x 2 D.2nC1/ 2 D4n 2 C4nC1D2.2n 2 C2n/C1D2kC1; wherekis the integer2n 2 C2n Hence,x 2 is odd.
Exercise 8 Prove that the square of an even integer is even.
Contraposition and Proof by Contradiction
In proving a proposition, we sometimes have to distinguish cases The following example is suggestive.
Example 9 To prove that 1/ n C 1/ n C 1 D0for all integersn, we have two cases:n is either even or odd.
Case 1: supposenis even ThennC1is odd (Why is this true? You should prove this from our definitions of even and odd.) Hence, 1/ n D1and 1/ n C 1 D 1 Therefore, the sum equals0.
Case 2: supposenis odd ThennC1is even Hence, 1/ n D 1and 1/ n C 1 D 1.
We give another proof of 1/ n C 1/ n C 1 D0for all integersn:
The key takeaway from this example is that multiple approaches can exist for proving a theorem While the challenge often lies in discovering a proof, some mathematicians strive to identify "the best" proof, a notion that is inherently subjective The renowned twentieth-century mathematician P Erdős famously suggested that God possesses "The Book," which contains all theorems alongside their optimal proofs.
You may recall the definition of the absolute value,jxj, of a real number,x We can definejxjto equalp x 2 However, the first definition you saw was probably something like jxj D
( x ; ifx0 x ; ifx < 0; where xplays the role of “dropping the negative sign” whenxis negative Since this is a definition by cases, proofs of statements involving absolute values often split into cases.
To prove that |x| = x for all x in ℝ, we consider two cases based on the definition of absolute value First, if x is greater than or equal to zero, then |x| equals x by definition, confirming that |x| = x Conversely, if x is less than zero, |x| equals -x, which is positive, thus reinforcing that |x| = x in this scenario as well.
Exercise 11 Prove that for allx2R,j2xC1j> x.
Proof by cases is not an actual proof technique; rather, it serves as a method for simplifying a problem by breaking it down into smaller, more manageable problems.
In fact, the methods of proof used to prove each of the individual cases may be different.
Compare with Supplemental Exercise 33 in Chapter 2.
3.3 Contraposition and Proof by Contradiction
An implication is equivalent to its contrapositive Therefore, to prove a statement, we can prove its contrapositive We call this proof by contraposition.
An Example of Proof by Contraposition
We prove the converse of Exercise 8.
Proposition 13 If the square of an integer is even, then the integer is even.
The proof establishes that the statement "If an integer is odd, then its square is odd" is logically equivalent to its contrapositive, thereby confirming Proposition 7 Since every statement holds the same truth value as its contrapositive, this effectively concludes the proof.
The following exercises are examples of statements whose proofs are most easily done by contraposition.
Exercise 14 Prove that if 1 C 2n n 2 is irrational, thennis irrational.
Exercise 15 Prove that, for all real numbersa, ifa 2 > 0, thena¤0.
The converse of Proposition 7 can be established through contraposition In this exercise, we demonstrate that an equivalence can be validated by proving both the forward and backward implications, as indicated in Exercise 25 of Chapter 2.
So, in the following exercise, it remains to prove that the square of an even integer is even.
Exercise 16 Prove that the square of an integernis odd if and only ifnis odd.
Proof by contradiction is a method that parallels contraposition In this technique, we leverage the logical equivalence between an implication and its contrapositive Specifically, to demonstrate that \( p \) implies \( q \), we assume that \( q \) is false and then show that \( p \) must also be false This approach essentially contradicts the original hypothesis \( p \), as it suggests that both \( p \) and its negation cannot be true simultaneously This concept allows us to broaden the application of this proof method.
To prove the implication p implies q by contradiction, we start by assuming the hypothesis p is true while also assuming the negation of the conclusion q is true By deriving a contradiction from these assumptions—whether it contradicts our hypothesis, our assumption, or any other established truth—we successfully demonstrate the validity of the original implication.
In mathematical proofs, it's important to differentiate between the terms "assume" and "suppose." While they are synonyms, the word "assume" should be used specifically when constructing a proof by contradiction In this context, we "suppose" the hypotheses but "assume" the negation of the conclusion, serving as a reminder that the goal is to identify a contradiction.
In proofs by contraposition and contradiction, the key distinction lies in the specific true statement that is contradicted In a proof by contraposition, the hypothesis is negated, while in a proof by contradiction, any true statement—including the assumed hypotheses and the negation of the conclusion—can be contradicted.
3.3 Contraposition and Proof by Contradiction 35
Examples of Proof by Contradiction
Before we look at any examples of proof by contradiction, let us examine a faulty attempt at a proof.
Absurdum 19 If the sum of two integers is even, then both integers are even.
If a theorem deserves a proof, then an absurdum deserves a poof!
The term "poof" signifies a contradiction in the context of integers If we assume that \( x \) is even and \( y \) is odd, we can express them as \( x = 2m \) and \( y = 2n + 1 \) for some integers \( m \) and \( n \) This leads to the conclusion that \( x + y = 2m + (2n + 1) = 2(m + n) + 1 \), which is an odd integer This result contradicts the premise that \( x + y \) is even Therefore, our initial assumption is incorrect, confirming that both \( x \) and \( y \) must be even.
Exercise 20 Explain why the statement of Absurdum 19 is absurd and why its “poof” is wrong.
Here are two examples of proof by contradiction, for Propositions 21 and 22.
Proposition 21 The sum of an odd integer and an even integer is odd.
Let \( x \) be an odd integer and \( y \) be an even integer If \( x \) choose \( y \) is even, we can express \( x \) as \( 2n + 1 \) and \( y \) as \( 2m \) for some integers \( n \) and \( m \) Thus, \( x \) choose \( y \) equals \( 2n + 1 + 2m = 2p \) for some integer \( p \) This leads to the equation \( 2(p - m - n) = 1 \), which is a contradiction since the left side is even while the right side is odd Therefore, \( x \) choose \( y \) must be odd.
This proof would not make Erd˝os’sThe Book (see Example 9) The direct proof is shorter and neater.
The second example of a proof by contradiction is given in Theorem 22 This is a famous theorem.
Before giving a proof of this proposition, you might wonder how we know that there exists a real number calledp
An informal geometric argument demonstrates the existence of a specific number based on the Pythagorean Theorem, which states that every line segment possesses a measurable length For instance, consider the length of the diagonal of a square with each side measuring 1 unit.
An algebraic proof can be provided by establishing the set of real numbers, where irrational numbers are derived from rational numbers This proof demonstrates that the resulting real number is indeed irrational.
Proof of Theorem 22 Assume thatp
2is rational Then there exist natural numbersmand nsuch that p2D m n:
Without loss of generality, we assume that the fraction m n is reduced to lowest terms; hence, mandnare not both even Squaring both sides we get m 2 n 2 D2:
This is equivalent to the equality
2n 2 Dm 2 : Since the left-hand side is an even number,m 2 is even By Proposition 13,mis even This means that mD2k for some natural numberk Hence
Therefore,n 2 is even and sonis even This is a contradiction since we assumed thatmand nare not both even Hence,p
Remark 23 The following remarks concern the style of writing proofs by contradiction.
Many mathematicians initiate their proofs by outlining their approach A strong opening for a proof by contradiction could be the phrase, “This proof is by contradiction.”
In mathematical proofs, it is often customary to omit the punch line, which typically involves stating a contradiction and negating the initial assumption Frequently, these proofs conclude with the straightforward assertion of "Contradiction," prompting readers to reflect on the implications of the argument presented.
For example, a much terser proof of Proposition 21 may look as follows.
Proof Supposex D 2nC1is odd andy D 2mis even AssumexCy D 2pis even.
We strongly suggest that you write as much as is necessary so that your fellow students could understand your proofs.