Mathematical Proofs: Concepts & Techniques

The initial section establishes the concept of an assertion as a statement of fact, acknowledging that in the real world, the truth of an assertion can be ambiguous. The example of comparing Alice and Bob's heights illustrates this ambiguity. However, the text adopts a mathematical approach, focusing on logic's application to mathematical objects where clear-cut truth values exist, unlike the uncertainties of real-world statements. An assertion, therefore, can be either true or false; there are no gray areas in this mathematical context. Examples are given, such as 'The Mona Lisa was painted by Leonardo da Vinci,' and 'Neil Armstrong was the first man on the moon,' which are considered true assertions. However, a poorly constructed deduction, such as concluding that Justin Trudeau went swimming yesterday based on the aforementioned true assertions, is presented to highlight the importance of proper logical structure in making valid deductions. The concept of validity in deductions is emphasized. A seemingly valid deduction from true premises may lead to a false conclusion if the structure of the deduction is flawed. The text emphasizes that the validity of a deduction is about its form, and not about the real-world truth of its component assertions.

This section introduces propositional logic as a formal language for representing and analyzing logical relationships between assertions. It explains the use of capital letters as symbols to represent assertions, emphasizing the need for a symbolization key to specify the meaning of each letter. The section provides examples of translating English-language statements into the symbolic language of propositional logic. This includes demonstrating the translation of conjunctions (using '&'), disjunctions, implications, and negations (using '¬'). It further explains that the translation of complex statements requires careful attention to the logical structure of the original sentences. The text shows how to translate assertions containing conjunctions, illustrating this with assertions about Barbara's athleticism and energy level. The translation of 'Barbara is athletic, but Adam is more athletic than she is' is explained, showcasing the need for new assertion letters to represent the increased complexity. The text also uses examples like 'you will have soup or salad' to show the importance of parentheses in accurately representing the intended logical structure when symbolizing statements involving disjunctions and negations.

This section introduces the concept of logical equivalence, explaining that two assertions are logically equivalent if they have the same truth value in all possible situations. It differentiates between tautologies (assertions always true, regardless of the truth values of their components) and contradictions (assertions always false). Examples are provided to demonstrate these concepts. The example of a teacher's promise ('If you do all of the homework, then you will pass the course') is used to illustrate the nuanced meaning of implications and how an implication can be true even if the consequent is false, provided the antecedent is also false. Similarly, a sarcastic statement ('If Rudy is the best player, then pigs can fly') is used to show that the truth of an implication depends on the relationship between antecedent and consequent rather than on the truth or falsity of its parts alone. The section further delves into the idea of logical equivalence, using examples of different-looking assertions that have the same truth value in all scenarios. The concepts of converse and inverse implications are also discussed, alongside illustrative examples. The importance of understanding these logical constructs for building valid deductions is stressed.

This section begins by highlighting the limitations of propositional logic in expressing ideas involving quantity, such as 'some' or 'all'. It introduces first-order logic as a more expressive system that addresses these limitations. The text explains that first-order logic uses predicates and quantifiers to capture the relationships between objects and their properties. An example is given: the statement 'All wizards are wearing funny hats' cannot be fully captured by propositional logic because it loses the connection between a wizard being a wizard and that wizard wearing a hat. However, first-order logic, using predicates and quantifiers, can handle such statements effectively. The concept of a universe of discourse is also introduced, which is essentially the set of all objects under consideration within a particular logical argument. The section emphasizes the need to clearly define this universe to avoid ambiguity when making statements such as 'Everyone is happy' – clarifying whether this refers to people in a room, a building, or the entire world. The section sets the stage for a more robust system of logic capable of handling complex statements about quantities and properties of objects.

This section delves deeper into the components of first-order logic: predicates and quantifiers. A predicate is described as an expression that is neither true nor false on its own but becomes an assertion once variables are assigned values. For example, '___ is wearing a funny hat' is a predicate, becoming a true or false assertion when a specific individual is substituted for the blank. The section explains the use of quantifiers—the universal quantifier (∀) meaning 'for all' and the existential quantifier (∃) meaning 'there exists'—to represent statements about sets. The use of multiple quantifiers is discussed, highlighting the importance of proceeding step-by-step to avoid errors during translation from English to the formal notation of first-order logic. The text emphasizes careful paraphrasing of English sentences to make their logical structure clear before symbolizing them in first-order logic. This method simplifies the process by breaking down complex assertions into smaller, more manageable units. An example of a statement with multiple quantifiers—'There is some umbrella that does not need a new handle and is big enough'—is provided to illustrate the process of translating English statements into first-order logic.

This section addresses the process of negating assertions in first-order logic and introduces the introduction and elimination rules for quantifiers. It notes that while negating assertions in English allows for some interpretation, negating assertions in first-order logic demands precision. The recommended approach involves translating an English assertion into first-order logic, performing the negation, and translating back. The section then presents the introduction and elimination rules for both the existential (∃) and universal (∀) quantifiers. The ∃-introduction rule is explained using an example involving Inspector Thinkright's statement, 'Someone in this room has red hair'. The section highlights that proving such an existential statement involves providing a concrete example to satisfy the condition. The ∃-elimination rule is discussed, explaining how to introduce a name for an element known to exist within a set to make further logical deductions. Conversely, the ∀-introduction rule explains the challenges of verifying statements like 'All butlers in town have seen the aurora borealis', where a one-by-one check becomes impossible with infinite sets. The section notes that mathematical proofs often require handling many elements at once rather than individually to establish the validity of universally quantified statements.

This section introduces the two-column proof format as a method for demonstrating the validity of deductions. It emphasizes the importance of a clear structure, with each assertion in the left column supported by a justification in the right column. The rules governing two-column proofs are outlined, notably the requirement to list all hypotheses at the beginning of the proof, justified with the word 'hypothesis'. A horizontal line separates the hypotheses from the rest of the proof. The section explains that any previously established valid deduction can be used as a justification for a subsequent assertion. Examples of two-column proofs are provided, illustrating the use of theorems such as '⇒-elim' and '∨-elim' as justifications, underscoring that these theorems serve as building blocks in constructing larger, more complex proofs. The section also shows how to combine two-column proofs written in propositional logic with their English-language equivalents, illustrating the use of both symbolic and natural language to convey the same information. The concept of a 'subproof,' a proof within a larger proof used to derive a subgoal, is introduced along with the idea of using annotation to clarify the steps for better understanding.

This section focuses on strategies for constructing proofs, likening the process to solving a puzzle with specific rules and a defined goal. It emphasizes a backward-chaining approach: starting from the desired conclusion and working backward to find the necessary intermediate steps. The text introduces the concept of 'subgoals'—intermediate steps that represent progress towards the final conclusion—and explains how to use subproofs to derive these subgoals. An example involving the hypothetical theft of a bracelet is used to illustrate how proofs by contradiction can be employed in everyday reasoning. The example of Inspector Thinkright eliminating the butler as a suspect, through a deductive process and an appeal to contradictory evidence from a security guard, is provided. The strategy of working backwards from the conclusion is also discussed. The section also emphasizes that the choice of next step in a proof is a crucial skill, akin to navigating a maze. The text highlights that there is no single recipe for proof construction, requiring practice and problem-solving skills. The section discusses the transition from the two-column proof format to proofs presented in natural language, showing how ideas can be communicated using sentences and paragraphs, combined with mathematical notation. Although the two-column method is beneficial for beginners, the text points out that its verbosity makes it less suitable for complex mathematical situations.

This section addresses the transition from two-column proofs to proofs written in natural language. It emphasizes that while proofs in prose offer more freedom and conciseness, they require careful use of grammar and mathematical notation to ensure clarity and avoid ambiguity. The section maintains that the core rules and strategies remain the same, but prose proofs require a greater level of judgment and skill to effectively convey information. A comparison between the two-column method and prose is included, highlighting the advantages of the two-column method for beginners due to its clear rules, reducing potential ambiguities in decision-making regarding allowable proof steps. However, the text acknowledges the disadvantage that the verbosity of two-column proofs renders them impractical for highly complex mathematical problems. The ultimate goal of producing proofs that are both clear, correct, and widely acceptable (to the extent that they would stand up in any court of law, internationally) is reiterated, underscoring the importance of careful proof writing to ensure a completely convincing argument. The section concludes by highlighting the need for more powerful logical languages (such as first-order logic) to symbolize complex deductions effectively, while acknowledging that the principles of constructing proofs remain consistent.

This section begins by defining ordered pairs, denoted as (x, y), emphasizing that order matters: (x, y) ≠ (y, x) unlike unordered sets where {x, y} = {y, x}. The concept of the Cartesian product is introduced as a set operation that combines two sets A and B to create a new set containing all possible ordered pairs (a, b) where 'a' belongs to A and 'b' belongs to B. The Cartesian product of two sets A and B is denoted as A x B. The section explains that the Cartesian product of the set of real numbers with itself (R x R) represents the coordinate plane used for graphing functions in elementary algebra. The text then generalizes this concept, noting that in advanced mathematics, the elements of the ordered pairs in a Cartesian product can come from any sets, not just the set of real numbers. This generalization is crucial for extending the applicability of the Cartesian product to a broader range of mathematical contexts. The importance of understanding ordered pairs and the Cartesian product for working with functions and relations in a more general mathematical framework is stressed.

This section defines functions in terms of sets of ordered pairs. A function is characterized as a set of ordered pairs where each element in the first position (the input or domain) is associated with exactly one element in the second position (the output or codomain). The text illustrates the concept with an example relating to the prices of fruits. It uses the example of a table showing the prices of different fruits where a price is assigned to each fruit. The example also notes the problem that arises when an item (e.g., banana) has multiple prices assigned in the table, which violates the definition of a function. The concept of a function's domain (the set of inputs) and the fact that a function might not be defined for all possible inputs are discussed. The text explains that, instead of representing functions as tables, a more concise method preferred by mathematicians involves representing each row of the table as an ordered pair. This makes it possible to represent a function as a set of ordered pairs, which is mathematically more rigorous and consistent. This approach highlights the connection between functions and set theory. The example of 'mother' as a function from 'people' to 'people' is compared to 'grandmother', highlighting how a person has two grandmothers making 'grandmother' not a function.

This section focuses on the concepts of image and pre-image in the context of functions. The notion of the 'image' of a function is introduced as the set of all outputs (or range values) that the function produces for its valid inputs. It provides a real-world example of an astronomy club planning a Father's Day party and needing to generate a list of all the fathers of club members. This is framed mathematically as finding the 'image' of a set (club members) under the 'father of' function. Conversely, the concept of a 'pre-image' is explained—that is, for any element in the codomain, its pre-image is the set of all inputs that map to that element. The section also implicitly defines a binary operation as a function that takes two elements from a set as input and returns a single element from the same set as output. The section uses addition, subtraction, and multiplication as familiar examples of binary operations on the set of real numbers. It then generalizes the concept to discuss binary operations on arbitrary sets.

This section introduces mathematical induction as a powerful proof technique for establishing statements about natural numbers. The principle of mathematical induction is explained, stating that if a property P(n) holds for a base case (e.g., n=1) and the implication P(k) → P(k+1) holds for all natural numbers k, then P(n) holds for all natural numbers n. The text notes that there are various versions of induction, including strong induction (where the inductive hypothesis assumes the truth of P(i) for all i ≤ k, not just for i=k) and induction with multiple base cases. An example of strong induction with multiple base cases is given, where the proof demonstrates the truth of a proposition for all natural numbers by verifying the base cases and then showing that the inductive step holds. The text highlights the power of induction as a proof technique, although it acknowledges that it can sometimes be difficult to apply effectively. The section implicitly highlights that mathematical induction works because of the well-ordered nature of natural numbers – every nonempty subset of natural numbers has a smallest element, allowing for a structured proof by induction.

This section introduces the concept of a well-ordered set, defined as a set in which every non-empty subset has a least element. The natural numbers are cited as a prime example of a well-ordered set. The connection between well-ordered sets and the applicability of mathematical induction is emphasized; induction is a powerful tool for proving statements about the elements of a well-ordered set. The section suggests that working with well-ordered sets can sometimes be a less cumbersome approach than directly applying mathematical induction. The text implies that the well-ordered property of natural numbers is fundamental to the success of mathematical induction as a proof method, offering a more intuitive understanding of why induction works for natural numbers, rather than just stating the method as a rule. The ability to identify a least element within any non-empty subset of natural numbers enables the systematic progression of the inductive proof, ensuring that all elements are eventually covered.

This section briefly introduces Cantor diagonalization as a proof technique used in the context of infinite sets. Although details of the technique are not fully described, the core idea is hinted at: constructing a new sequence of elements that differs from each term of a diagonal sequence formed from an existing infinite sequence. This technique is used to demonstrate certain properties about infinite sets, specifically indicating its use in proving the uncountability of certain sets (though this isn't explicitly stated in this section). The mention of Cantor diagonalization serves as a prelude to more advanced topics involving the cardinality of infinite sets. The specific goal or property the Cantor diagonalization technique aims to prove is not defined, but the text suggests that it is a proof method used to establish properties related to infinite sequences, potentially related to concepts of countability. The mention of avoiding digits 0 and 9 to prevent issues stemming from the representation of numbers (such as 0.999... = 1.000...) indicates the care needed when working with infinite sequences and their representations.