الرئيسية
Pure Mathematics for Beginners: A Rigorous Introduction to Logic, Set Theory, Abstract Algebra, Number..
Pure Mathematics for Beginners: A Rigorous Introduction to Logic, Set Theory, Abstract Algebra, Number Theory, Real Analysis, Topology, Complex Analysis, and Linear Algebra
Steve Warner
تحميل (pdf, 10.55 MB)
اقرأ الكتاب مباشرة
 Open in Browser
 Checking other formats...
 Please login to your account first

Need help? Please read our short guide how to send a book to Kindle.
The file will be sent to your email address. It may take up to 15 minutes before you receive it.
The file will be sent to your Kindle account. It may takes up to 15 minutes before you received it.
Please note you need to add our NEW email km@bookmail.org to approved email addresses. Read more.
Please note you need to add our NEW email km@bookmail.org to approved email addresses. Read more.
You may be interested in
Most frequently terms
theorem^{339}
topology^{208}
vector^{197}
linear^{165}
multiplication^{144}
lim^{141}
integer^{133}
integers^{107}
vector space^{105}
define^{104}
equation^{96}
arbitrary^{94}
inverse^{92}
continuous^{89}
subset^{88}
commutative^{83}
interval^{81}
binary^{81}
ker^{77}
equivalence^{72}
finite^{71}
spaces^{70}
cos^{69}
matrix^{68}
statements^{67}
gcd^{67}
vectors^{66}
scalar^{65}
topological^{64}
disk^{63}
homomorphism^{60}
linearly^{60}
subsets^{59}
intersection^{58}
injective^{55}
additive^{54}
multiplicative^{51}
binary operation^{44}
open interval^{43}
standard topology^{41}
linear combination^{40}
equivalently^{39}
bijection^{39}
proof of theorem^{38}
monoid^{38}
distributivity^{37}
associativity^{36}
disjoint^{35}
topologies^{35}
vector spaces^{34}
nonempty^{32}
surjective^{32}
propositional^{31}
lcm^{30}
commutative group^{27}
topological space^{27}
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
1

2

Legal Notice This book is copyright 2018 with all rights reserved. It is illegal to copy, distribute, or create derivative works from this book in whole or in part or to contribute to the copying, distribution, or creating of derivative works of this book. For information on bulk purchases and licensing agreements, please email support@SATPrepGet800.com Acknowledgements Thanks to Daniel Dimijian, Scott Jeffreys, Dan Seabold, C.R. Sincock, Pete Terlecky, Zoran Sunik, and David Wayne for their helpful input during the creation of this book. CONNECT WITH DR. STEVE WARNER Pure Mathematics for Beginners A Rigorous Introduction to Logic, Set Theory, Abstract Algebra, Number Theory, Real Analysis, Topology, Complex Analysis, and Linear Algebra  Dr. Steve Warner 𝑁𝜖 (𝐿) 𝑁𝛿⨀ (𝑎) 𝜖 𝛿 © 2018, All Rights Reserved iii Table of Contents Introduction For students For instructors 7 7 8 Lesson 1 – Logic: Statements and Truth Statements with Words Statements with Symbols Truth Tables Problem Set 1 Lesson 2 – Set Theory: Sets and Subsets Describing Sets Subsets Unions and Intersections Problem Set 2 Lesson 3 – Abstract Algebra: Semigroups, Monoids, and Groups Binary Operations and Closure Semigroups and Associativity Monoids and Identity Groups and Inverses Problem Set 3 Lesson 4 – Number Theory: The Ring of Integers Rings and Distributivity Divisibility Induction Problem Set 4 Lesson 5 – Real Analysis: The Complete Ordered Field of Reals Fields Ordered Rings and Fields Why Isn’t ℚ enough? Completeness Problem Set 5 Lesson 6 – Topology: The Topology of ℝ Intervals of Real Numbers Operations on Sets Open and Closed Sets Problem Set 6 Lesson 7 – Complex Analysis: The Field of Complex Numbers A Limitation of the Reals The Complex Field Absolute Value and Distance Basic Topology of ℂ Problem Set 7 iv 9 9 10 12 16 19 19 20 24 28 30 30 32 34 34 36 38 38 41 43 48 50 50 52 56 58 62 64 64 66 70 76 78 78 78 82 85 90 Lesson 8 – Linear Algebra: Vector Spaces Vector Spaces Over Fields Subspaces Bases Problem Set 8 Lesson 9 – Logic: Logical Arguments Statements and Substatements Logical Equivalence Validity in Sentential Logic Problem Set 9 Lesson 10 – Set Theory: Relations and Functions Relations Equivalence Relations and Partitions Orderings Functions Equinumerosity Problem Set 10 Lesson 11 – Abstract Algebra: Structures and Homomorphisms Structures and Substructures Homomorphisms Images and Kernels Normal Subgroups and Ring Ideals Problem Set 11 Lesson 12 – Number Theory: Primes, GCD, and LCM Prime Numbers The Division Algorithm GCD and LCM Problem Set 12 Lesson 13 – Real Analysis: Limits and Continuity Strips and Rectangles Limits and Continuity Equivalent Definitions of Limits and Continuity Basic Examples Limit and Continuity Theorems Limits Involving Infinity Onesided Limits Problem Set 13 Lesson 14 – Topology: Spaces and Homeomorphisms Topological Spaces Bases Types of Topological Spaces Continuous Functions and Homeomorphisms Problem Set 14 v 93 93 98 101 105 107 107 108 111 116 118 118 121 124 124 130 135 137 137 142 146 147 150 152 152 155 159 167 169 169 172 175 177 181 183 185 186 189 189 192 197 204 210 Lesson 15 – Complex Analysis: Complex Valued Functions The Unit Circle Exponential Form of a Complex Number Functions of a Complex Variable Limits and Continuity The Reimann Sphere Problem Set 15 Lesson 16 – Linear Algebra: Linear Transformations Linear Transformations Matrices The Matrix of a Linear Transformation Images and Kernels Eigenvalues and Eigenvectors Problem Set 16 212 212 216 218 223 228 230 234 234 239 242 244 247 253 Index 255 About the Author 259 Books by Dr. Steve Warner 260 vi I N T R O D U C T I O N PURE MATHEMATICS This book was written to provide a basic but rigorous introduction to pure mathematics, while exposing students to a wide range of mathematical topics in logic, set theory, abstract algebra, number theory, real analysis, topology, complex analysis, and linear algebra. For students: There are no prerequisites for this book. The content is completely selfcontained. Students with a bit of mathematical knowledge may have an easier time getting through some of the material, but no such knowledge is necessary to read this book. More important than mathematical knowledge is “mathematical maturity.” Although there is no single agreed upon definition of mathematical maturity, one reasonable way to define it is as “one’s ability to analyze, understand, and communicate mathematics.” A student with a higher level of mathematical maturity will be able to move through this book more quickly than a student with a lower level of mathematical maturity. Whether your level of mathematical maturity is low or high, if you are just starting out in pure mathematics, then you’re in the right place. If you read this book the “right way,” then your level of mathematical maturity will continually be increasing. This increased level of mathematical maturity will not only help you to succeed in advanced math courses, but it will improve your general problem solving and reasoning skills. This will make it easier to improve your performance in college, in your professional life, and on standardized tests such as the SAT, ACT, GRE, and GMAT. So, what is the “right way” to read this book? Simply reading each lesson from end to end without any further thought and analysis is not the best way to read the book. You will need to put in some effort to have the best chance of absorbing and retaining the material. When a new theorem is presented, don’t just jump right to the proof and read it. Think about what the theorem is saying. Try to describe it in your own words. Do you believe that it is true? If you do believe it, can you give a convincing argument that it is true? If you do not believe that it is true, try to come up with an example that shows it is false, and then figure out why your example does not contradict the theorem. Pick up a pen or pencil. Draw some pictures, come up with your own examples, and try to write your own proof. You may find that this book goes into more detail than other math books when explaining examples, discussing concepts, and proving theorems. This was done so that any student can read this book, and not just students that are naturally gifted in mathematics. So, it is up to you as the student to try to answer questions before they are answered for you. When a new definition is given, try to think of your own examples before looking at those presented in the book. And when the book provides an example, do not just accept that it satisfies the given definition. Convince yourself. Prove it. Each lesson is followed by a Problem Set. The problems in each Problem Set have been organized into five levels, Level 1 problems being considered the easiest, and Level 5 problems being considered the most difficult. If you want to get just a small taste of pure mathematics, then you can work on the easier problems. If you want to achieve a deeper understanding of the material, take some time to struggle with the harder problems. 7 For instructors: This book can be used for a wide range of courses. Although the lessons can be taught in the order presented, they do not need to be. The lessons cycle twice among eight subject areas: logic, set theory, abstract algebra, number theory, real analysis, topology, complex analysis, and linear algebra. Lessons 1 through 8 give only the most basic material in each of these subjects. Therefore, an instructor that wants to give a brief glimpse into a wide variety of topics might want to cover just the first eight lessons in their course. Lessons 9 through 16 cover material in each subject area that the author believes is fundamental to a deep understanding of that particular subject. For a first course in higher mathematics, a highquality curriculum can be created by choosing among the 16 lessons contained in this book. As an example, an introductory course focusing on logic, set theory, and real analysis might cover Lessons 1, 2, 5, 9, 10, and 13. Lessons 1 and 9 cover basic sentential logic and proof theory, Lessons 2 and 10 cover basic set theory including relations, functions, and equinumerosity, and Lessons 5 and 13 cover basic real analysis up through a rigorous treatment of limits and continuity. The first three lessons are quite basic, while the latter three lessons are at an intermediate level. Instructors that do not like the idea of leaving a topic and then coming back to it later can cover the lessons in the following order without issue: 1, 9, 2, 10, 5, and 13. As another example, a course focusing on algebraic structures might cover Lessons 2, 3, 4, 5, 10, and 11. As mentioned in the previous paragraph, Lessons 2 and 10 cover basic set theory. In addition, Lessons 3, 4, 5, and 11 cover semigroups, monoids, groups, rings, and fields. Lesson 4, in addition to a preliminary discussion on rings, also covers divisibility and the principle of mathematical induction. Similarly, Lesson 5, in addition to a preliminary discussion on fields, provides a development of the complete ordered field of real numbers. These topics can be included or omitted, as desired. Instructors that would also like to incorporate vector spaces can include part or all of Lesson 8. The author strongly recommends covering Lesson 2 in any introductory pure math course. This lesson fixes some basic set theoretical notation that is used throughout the book and includes some important exposition to help students develop strong proof writing skills as quickly as possible. The author welcomes all feedback from instructors. Any suggestions will be considered for future editions of the book. The author would also love to hear about the various courses that are created using these lessons. Feel free to email Dr. Steve Warner with any feedback at steve@SATPrepGet800.com 8 LESSON 1 – LOGIC STATEMENTS AND TRUTH Statements with Words A statement (or proposition) is a sentence that can be true or false, but not both simultaneously. Example 1.1: “Mary is awake” is a statement because at any given time either Mary is awake or Mary is not awake (also known as Mary being asleep), and Mary cannot be both awake and asleep at the same time. Example 1.2: The sentence “Wake up!” is not a statement because it cannot be true or false. An atomic statement expresses a single idea. The statement “Mary is awake” that we discussed above is an example of an atomic statement. Let’s look at a few more examples. Example 1.3: The following sentences are atomic statements: 1. 17 is a prime number. 2. George Washington was the first president of the United States. 3. 5 > 6. 4. David is lefthanded. Sentences 1 and 2 above are true, and sentence 3 is false. We can’t say for certain whether sentence 4 is true or false without knowing who David is. However, it is either true or false. It follows that each of the four sentences above are atomic statements. We use logical connectives to form compound statements. The most commonly used logical connectives are “and,” “or,” “if…then,” “if and only if,” and “not.” Example 1.4: The following sentences are compound statements: 1. 17 is a prime number and 0 = 1. 2. Michael is holding a pen or water is a liquid. 3. If Joanna has a cat, then fish have lungs. 4. Albert Einstein is alive today if and only if 5 + 7 = 12. 5. 16 is not a perfect square. Sentence 1 above uses the logical connective “and.” Since the statement “0 = 1” is false, it follows that sentence 1 is false. It does not matter that the statement “17 is a prime number” is true. In fact, “T and F” is always F. Sentence 2 uses the logical connective “or.” Since the statement “water is a liquid” is true, it follows that sentence 2 is true. It does not even matter whether Michael is holding a pen. In fact, “T or T” is always true and “F or T” is always T. 9 It’s worth pausing for a moment to note that in the English language the word “or” has two possible meanings. There is an “inclusive or” and an “exclusive or.” The “inclusive or” is true when both statements are true, whereas the “exclusive or” is false when both statements are true. In mathematics, by default, we always use the “inclusive or” unless we are told to do otherwise. To some extent, this is an arbitrary choice that mathematicians have agreed upon. However, it can be argued that it is the better choice since it is used more often and it is easier to work with. Note that we were assuming use of the “inclusive or” in the last paragraph when we said, “In fact, “T or T” is always true.” See Problem 4 below for more on the “exclusive or.” Sentence 3 uses the logical connective “if…then.” The statement “fish have lungs” is false. We need to know whether Joanna has a cat in order to figure out the truth value of sentence 3. If Joanna does have a cat, then sentence 3 is false (“if T, then F” is always F). If Joanna does not have a cat, then sentence 3 is true (“if F, then F” is always T). Sentence 4 uses the logical connective “if and only if.” Since the two atomic statements have different truth values, it follows that sentence 4 is false. In fact, “F if and only if T” is always F. Sentence 5 uses the logical connective “not.” Since the statement “16 is a perfect square” is true, it follows that sentence 5 is false. In fact, “not T” is always F. Notes: (1) The logical connectives “and,” “or,” “if…then,” and “if and only if,” are called binary connectives because they join two statements (the prefix “bi” means “two”). (2) The logical connective “not” is called a unary connective because it is applied to just a single statement (“unary” means “acting on a single element”). Example 1.5: The following sentences are not statements: 1. Are you happy? 2. Go away! 3. 𝑥 − 5 = 7 4. This sentence is false. 5. This sentence is true. Sentence 1 above is a question and sentence 2 is a command. Sentence 3 has an unknown variable – it can be turned into a statement by assigning a value to the variable. Sentences 4 and 5 are selfreferential (they refer to themselves). They can be neither true nor false. Sentence 4 is called the Liar’s paradox and sentence 5 is called a vacuous affirmation. Statements with Symbols We will use letters such as 𝑝, 𝑞, 𝑟, and 𝑠 to denote atomic statements. We sometimes call these letters propositional variables, and we will generally assign a truth value of T (for true) or F (for false) to each propositional variable. Formally, we define a truth assignment of a list of propositional variables to be a choice of T or F for each propositional variable in the list. 10 We use the symbols ∧, ∨, →, ↔, and ¬ for the most common logical connectives. The truth value of a compound statement is determined by the truth values of its atomic parts together with applying the following rules for the connectives. • 𝑝 ∧ 𝑞 is called the conjunction of 𝑝 and 𝑞. It is pronounced “𝑝 and 𝑞.” 𝑝 ∧ 𝑞 is true when both 𝑝 and 𝑞 are true, and it is false otherwise. • 𝑝 ∨ 𝑞 is called the disjunction of 𝑝 and 𝑞. It is pronounced “𝑝 or 𝑞.” 𝑝 ∨ 𝑞 is true when 𝑝 or 𝑞 (or both) are true, and it is false when 𝑝 and 𝑞 are both false. • 𝑝 → 𝑞 is called a conditional or implication. It is pronounced “if 𝑝, then 𝑞” or “𝑝 implies 𝑞.” 𝑝 → 𝑞 is true when 𝑝 is false or 𝑞 is true (or both), and it is false when 𝑝 is true and 𝑞 is false. • 𝑝 ↔ 𝑞 is called a biconditional. It is pronounced “𝑝 if and only if 𝑞.” 𝑝 ↔ 𝑞 is true when 𝑝 and 𝑞 have the same truth value (both true or both false), and it is false when 𝑝 and 𝑞 have opposite truth values (one true and the other false). • ¬𝑝 is called the negation of 𝑝. It is pronounced “not 𝑝.” ¬𝑝 is true when 𝑝 is false, and it is false when 𝑝 is true (𝑝 and ¬𝑝 have opposite truth values.) Example 1.6: Let 𝑝 represent the statement “Fish can swim,” and let 𝑞 represent the statement “7 < 3.” Note that 𝑝 is true and 𝑞 is false. 1. 𝑝 ∧ 𝑞 represents “Fish can swim and 7 < 3.” Since 𝑞 is false, it follows that 𝑝 ∧ 𝑞 is false. 2. 𝑝 ∨ 𝑞 represents “Fish can swim or 7 < 3.” Since 𝑝 is true, it follows that 𝑝 ∨ 𝑞 is true. 3. 𝑝 → 𝑞 represents “If fish can swim, then 7 < 3.” Since 𝑝 is true and 𝑞 is false, 𝑝 → 𝑞 is false. 4. 𝑝 ↔ 𝑞 represents “Fish can swim if and only if 7 < 3.” Since 𝑝 is true and 𝑞 is false, 𝑝 ↔ 𝑞 is false. 5. ¬𝑞 represents the statement “7 is not less than 3.” This is equivalent to “7 is greater than or equal to 3,” or equivalently, “7 ≥ 3.” Since 𝑞 is false, ¬𝑞 is true. 6. ¬𝑝 ∨ 𝑞 represents the statement “Fish cannot swim or 7 < 3.” Since ¬𝑝 and 𝑞 are both false, ¬𝑝 ∨ 𝑞 is false. Note that ¬𝑝 ∨ 𝑞 always means (¬𝑝) ∨ 𝑞. In general, without parentheses present, we always apply negation before any of the other connectives. 7. ¬(𝑝 ∨ 𝑞) represents the statement “It is not the case that either fish can swim or 7 < 3.” This can also be stated as “Neither can fish swim nor is 7 less than 3.” Since 𝑝 ∨ 𝑞 is true (see 2 above), ¬(𝑝 ∨ 𝑞) is false. 8. ¬𝑝 ∧ ¬𝑞 represents the statement “Fish cannot swim and 7 is not less than 3.” This statement can also be stated as “Neither can fish swim nor is 7 less than 3.” Since this is the same statement as in 7 above, it should follow that ¬𝑝 ∧ ¬𝑞 is equivalent to ¬(𝑝 ∨ 𝑞). After completing this lesson, you will be able to verify this. For now, let’s observe that since ¬𝑝 is false, it follows that ¬𝑝 ∧ ¬𝑞 is false. This agrees with the truth value we got in 7. (Note: The equivalence of ¬𝑝 ∧ ¬𝑞 with ¬(𝑝 ∨ 𝑞) is one of De Morgan’s laws. These laws will be explored further in Lesson 9. See also Problem 3 below.) 11 Truth Tables A truth table can be used to display the possible truth values of a compound statement. We start by labelling the columns of the table with the propositional variables that appear in the statement, followed by the statement itself. We then use the rows to run through every possible combination of truth values for the propositional variables followed by the resulting truth values for the compound statement. Let’s look at the truth tables for the five most common logical connectives. 𝒑 𝐓 𝐓 𝐅 𝐅 𝒒 𝐓 𝐅 𝐓 𝐅 𝒑 𝐓 𝐓 𝐅 𝐅 𝒑∧𝒒 𝐓 𝐅 𝐅 𝐅 𝒑 𝐓 𝐓 𝐅 𝐅 𝒒 𝐓 𝐅 𝐓 𝐅 𝒒 𝐓 𝐅 𝐓 𝐅 𝒑 𝐓 𝐓 𝐅 𝐅 𝒑∨𝒒 𝐓 𝐓 𝐓 𝐅 𝒑↔𝒒 𝐓 𝐅 𝐅 𝐓 𝒑 𝐓 𝐅 𝒒 𝐓 𝐅 𝐓 𝐅 𝒑→𝒒 𝐓 𝐅 𝐓 𝐓 ¬𝒑 𝐅 𝐓 We can use these five truth tables to compute the truth values of compound statements involving the five basic logical connectives. Note: For statements involving just 1 propositional variable (such as ¬𝑝), the truth table requires 2 rows, 1 for each truth assignment of 𝑝 ( T or F ). For statements involving 2 propositional variables (such as 𝑝 ∧ 𝑞), the truth table requires 2 ⋅ 2 = 4 (or 22 = 4) rows, as there are 4 possible combinations for truth assignments of 𝑝 and 𝑞 ( TT, TF, FT, FF ). In general, for a statement involving 𝑛 propositional variables, the truth table will require 2𝑛 rows. For example, if we want to build an entire truth table for ¬𝑝 ∨ (¬𝑞 → 𝑟), we will need 23 = 2 ⋅ 2 ⋅ 2 = 8 rows in the truth table. We will create the truth table for this statement in Example 1.8 below (see the third solution). Example 1.7: If 𝑝 is true and 𝑞 is false, then we can compute the truth value of 𝑝 ∧ 𝑞 by looking at the second row of the truth table for the conjunction. 𝒑 𝐓 𝐓 𝐅 𝐅 𝒒 𝐓 𝐅 𝐓 𝐅 𝒑∧𝒒 𝐓 𝐅 𝐅 𝐅 We see from the highlighted row that 𝑝 ∧ 𝑞 ≡ T ∧ F ≡ 𝐅. 12 Note: Here the symbol ≡ can be read “is logically equivalent to.” So, we see that if 𝑝 is true and 𝑞 is false, then 𝑝 ∧ 𝑞 is logically equivalent to F, or more simply, 𝑝 ∧ 𝑞 is false. Example 1.8: Let 𝑝, 𝑞, and 𝑟 be propositional variables with 𝑝 and 𝑞 true, and 𝑟 false. Let’s compute the truth value of ¬𝑝 ∨ (¬𝑞 → 𝑟). Solution: We have ¬𝑝 ∨ (¬𝑞 → 𝑟) ≡ ¬T ∨ (¬T → F) ≡ F ∨ (F → F) ≡ F ∨ T ≡ 𝐓. Notes: (1) For the first equivalence, we simply replaced the propositional variables by their given truth values. We replaced 𝑝 and 𝑞 by T, and we replaced 𝑟 by F. (2) For the second equivalence, we used the first row of the truth table for the negation (drawn to the right for your convenience). We see from the highlighted row that ¬T ≡ F. We applied this result twice. 𝒑 𝐓 𝐅 ¬𝒑 𝐅 𝐓 (3) For the third equivalence, we used the fourth row of the truth table for the conditional. 𝒑 𝐓 𝐓 𝐅 𝐅 𝒒 𝐓 𝐅 𝐓 𝐅 𝒑→𝒒 𝐓 𝐅 𝐓 𝐓 We see from the highlighted row that F → F ≡ T. (4) For the last equivalence, we used the third row of the truth table for the disjunction. 𝒑 𝐓 𝐓 𝐅 𝐅 𝒒 𝐓 𝐅 𝐓 𝐅 𝒑∨𝒒 𝐓 𝐓 𝐓 𝐅 We see from the highlighted row that F ∨ T ≡ T. (5) We can save a little time by immediately replacing the negation of a propositional variable by its truth value (which will be the opposite truth value of the propositional variable). For example, since 𝑝 has truth value T, we can replace ¬𝑝 by F. The faster solution would look like this: ¬𝑝 ∨ (¬𝑞 → 𝑟) ≡ F ∨ (F → F) ≡ F ∨ T ≡ 𝐓. Quicker solution: Since 𝑞 has truth value T, it follows that ¬𝑞 has truth value F. So, ¬𝑞 → 𝑟 has truth value T. Finally, ¬𝑝 ∨ (¬𝑞 → 𝑟) must then have truth value T. Notes: (1) Symbolically, we can write the following: ¬𝑝 ∨ (¬𝑞 → 𝑟) ≡ ¬𝑝 ∨ (¬T → 𝑟) ≡ ¬𝑝 ∨ (F → 𝑟) ≡ ¬𝑝 ∨ T ≡ 𝐓 13 (2) We can display this reasoning visually as follows: ¬𝑝 ∨ (¬𝑞 → 𝑟) T F T 𝐓 The vertical lines have just been included to make sure you see which connective each truth value is written below. We began by placing a T under the propositional variable 𝑞 to indicate that 𝑞 is true. Since ¬T ≡ F, we then place an F under the negation symbol. Next, since F → 𝑟 ≡ T regardless of the truth value of 𝑟, we place a T under the conditional symbol. Finally, since ¬𝑝 ∨ T ≡ T regardless of the truth value of 𝑝, we place a T under the disjunction symbol. We made this last T bold to indicate that we are finished. (3) Knowing that 𝑞 has truth value T is enough to determine the truth value of ¬𝑝 ∨ (¬𝑞 → 𝑟), as we saw in Note 1 above. It’s okay if you didn’t notice that right away. This kind of reasoning takes a bit of practice and experience. Truth table solution: An alternative solution is to build the whole truth table of ¬𝑝 ∨ (¬𝑞 → 𝑟) one column at a time. Since there are 3 propositional variables (𝑝, 𝑞, and 𝑟), we will need 23 = 8 rows to get all the possible truth values. We then create a column for each compound statement that appears within the given statement starting with the statements of smallest length and working our way up to the given statement. We will need columns for 𝑝, 𝑞, 𝑟 (the atomic statements), ¬𝑝, ¬𝑞, ¬𝑞 → 𝑟, and finally, the statement itself, ¬𝑝 ∨ (¬𝑞 → 𝑟). Below is the final truth table with the relevant row highlighted and the final answer circled. 𝒑 𝐓 𝐓 𝐓 𝐓 𝐅 𝐅 𝐅 𝐅 𝒒 𝐓 𝐓 𝐅 𝐅 𝐓 𝐓 𝐅 𝐅 𝒓 𝐓 𝐅 𝐓 𝐅 𝐓 𝐅 𝐓 𝐅 ¬𝒑 𝐅 𝐅 𝐅 𝐅 𝐓 𝐓 𝐓 𝐓 ¬𝒒 𝐅 𝐅 𝐓 𝐓 𝐅 𝐅 𝐓 𝐓 ¬𝒒 → 𝒓 𝐓 𝐓 𝐓 𝐅 𝐓 𝐓 𝐓 𝐅 ¬𝒑 ∨ (¬𝒒 → 𝒓) 𝐓 𝐓 𝐓 𝐅 𝐓 𝐓 𝐓 𝐓 Notes: (1) We fill out the first three columns of the truth table by listing all possible combinations of truth assignments for the propositional variables 𝑝, 𝑞, and 𝑟. Notice how down the first column we have 4 T’s followed by 4 F’s, down the second column we alternate sequences of 2 T’s with 2 F’s, and down the third column we alternate T’s with F’s one at a time. This is a nice systematic way to make sure we get all possible combinations of truth assignments. 14 If you’re having trouble seeing the pattern of T’s and F’s, here is another way to think about it: In the first column, the first half of the rows have a T and the remainder have an F. This gives 4 T’s followed by 4 F’s. For the second column, we take half the number of consecutive T’s in the first column (half of 4 is 2) and then we alternate between 2 T’s and 2 F’s until we fill out the column. For the third column, we take half the number of consecutive T’s in the second column (half of 2 is 1) and then we alternate between 1 T and 1 F until we fill out the column. (2) Since the connective ¬ has the effect of taking the opposite truth value, we generate the entries in the fourth column by taking the opposite of each truth value in the first column. Similarly, we generate the entries in the fifth column by taking the opposite of each truth value in the second column. (3) For the sixth column, we apply the connective → to the fifth and third columns, respectively, and finally, for the last column, we apply the connective ∨ to the fourth and sixth columns, respectively. (4) The original question is asking us to compute the truth value of ¬𝑝 ∨ (¬𝑞 → 𝑟) when 𝑝 and 𝑞 are true, and 𝑟 is false. In terms of the truth table, we are being asked for the entry in the second row and last (seventh) column. Therefore, the answer is 𝐓. (5) This is certainly not the most efficient way to answer the given question. However, building truth tables is not too difficult, and it’s a foolproof way to determine truth values of compound statements. 15 Problem Set 1 Full solutions to these problems are available for free download here: www.SATPrepGet800.com/PMFBXSG LEVEL 1 1. Determine whether each of the following sentences is an atomic statement, a compound statement, or not a statement at all: (i) I am not going to work today. (ii) What is the meaning of life? (iii) Don’t go away mad. (iv) I watched the television show Parks and Recreation. (v) If pigs have wings, then they can fly. (vi) 3 < – 5 or 38 > 37. (vii) This sentence has five words. (viii) I cannot swim, but I can run fast. 2. What is the negation of each of the following statements: (i) The banana is my favorite fruit. (ii) 7 > – 3. (iii) You are not alone. (iv) The function 𝑓 is differentiable everywhere. LEVEL 2 3. Let 𝑝 represent the statement “9 is a perfect square,” let 𝑞 represent the statement “Orange is a primary color,” and let 𝑟 represent the statement “A frog is a reptile.” Rewrite each of the following symbolic statements in words, and state the truth value of each statement: (i) 𝑝∧𝑞 (ii) ¬𝑟 (iii) 𝑝→𝑟 (iv) 𝑞↔𝑟 (v) ¬𝑝 ∧ 𝑞 (vi) ¬(𝑝 ∧ 𝑞) (vii) ¬𝑝 ∨ ¬𝑞 (viii) (𝑝 ∧ 𝑞) → 𝑟 16 4. Consider the compound sentence “You can have a cookie or ice cream.” In English this would most likely mean that you can have one or the other but not both. The word “or” used here is generally called an “exclusive or” because it excludes the possibility of both. The disjunction is an “inclusive or.” Using the symbol ⊕ for exclusive or, draw the truth table for this connective. LEVEL 3 5. Let 𝑝, 𝑞, and 𝑟 represent true statements. Compute the truth value of each of the following compound statements: (i) (𝑝 ∨ 𝑞) ∨ 𝑟 (ii) (𝑝 ∨ 𝑞) ∧ ¬𝑟 (iii) ¬𝑝 → (𝑞 ∨ 𝑟) (iv) ¬(𝑝 ↔ ¬𝑞) ∧ 𝑟 (v) ¬[𝑝 ∧ (¬𝑞 → 𝑟)] (vi) ¬[(¬𝑝 ∨ ¬𝑞) ↔ ¬𝑟] (vii) 𝑝 → (𝑞 → ¬𝑟) (viii) ¬[¬𝑝 → (𝑞 → ¬𝑟)] 6. Using only the logical connectives ¬, ∧, and ∨, produce a statement using the propositional variables 𝑝 and 𝑞 that has the same truth values as 𝑝 ⊕ 𝑞 (this is the “exclusive or” defined in problem 4 above). LEVEL 4 7. Let 𝑝 represent a true statement. Decide if this is enough information to determine the truth value of each of the following statements. If so, state that truth value. (i) 𝑝∨𝑞 (ii) 𝑝→𝑞 (iii) ¬𝑝 → ¬(𝑞 ∨ ¬𝑟) (iv) ¬(¬𝑝 ∧ 𝑞) ↔ 𝑝 (v) (𝑝 ↔ 𝑞) ↔ ¬𝑝 (vi) ¬[(¬𝑝 ∧ ¬𝑞) ↔ ¬𝑟] (vii) [(𝑝 ∧ ¬𝑝) → 𝑝] ∧ (𝑝 ∨ ¬𝑝) (viii) 𝑟 → [¬𝑞 → (¬𝑝 → ¬𝑟)] 17 8. Assume that the given compound statement is true. Determine the truth value of each propositional variable. (i) 𝑝∧𝑞 (ii) ¬(𝑝 → 𝑞) (iii) 𝑝 ↔ [¬(𝑝 ∧ 𝑞)] (iv) [𝑝 ∧ (𝑞 ∨ 𝑟)] ∧ ¬𝑟 LEVEL 5 9. Show that [𝑝 ∧ (𝑞 ∨ 𝑟)] ↔ [(𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)] is always true. 10. Show that [[(𝑝 ∧ 𝑞) → 𝑟] → 𝑠] → [(𝑝 → 𝑟) → 𝑠] is always true. 18 LESSON 2 – SET THEORY SETS AND SUBSETS Describing Sets A set is simply a collection of “objects.” These objects can be numbers, letters, colors, animals, funny quotes, or just about anything else you can imagine. We will usually refer to the objects in a set as the members or elements of the set. If a set consists of a small number of elements, we can describe the set simply by listing the elements in the set in curly braces, separating elements by commas. Example 2.1: 1. {apple, banana} is the set consisting of two elements: apple and banana. 2. {anteater, elephant, egg, trapezoid} is the set consisting of four elements: anteater, elephant, egg, and trapezoid. 3. {2, 4, 6, 8, 10} is the set consisting of five elements: 2, 4, 6, 8, and 10. The elements in this set happen to be numbers. A set is determined by its elements, and not the order in which the elements are presented. For example, the set {4, 2, 8, 6, 10} is the same as the set {2, 4, 6, 8, 10}. Also, the set {2, 2, 4, 6, 8, 10, 10, 10} is the same as the set {2, 4, 6, 8, 10}. If we are describing a set by listing its elements, the most natural way to do this is to list each element just once. We will usually name sets using capital letters such as 𝐴, 𝐵, and 𝐶. For example, we might write 𝐴 = {1, 2, 3}. So, 𝐴 is the set consisting of the elements 1, 2, and 3. Example 2.2: Consider the sets 𝐴 = {𝑎, 𝑏}, 𝐵 = {𝑏, 𝑎}, 𝐶 = {𝑎, 𝑏, 𝑎}. Then 𝐴, 𝐵, and 𝐶 all represent the same set. We can write 𝐴 = 𝐵 = 𝐶. We use the symbol ∈ for the membership relation (we will define the term “relation” more carefully in Lesson 10). So, 𝑥 ∈ 𝐴 means “𝑥 is an element of 𝐴,” whereas 𝑥 ∉ 𝐴 means “𝑥 is not an element of 𝐴.” Example 2.3: Let 𝐴 = {𝑎, 𝑘, 3, ⊡, ⊕}. Then 𝑎 ∈ 𝐴, 𝑘 ∈ 𝐴, 3 ∈ 𝐴, ⊡ ∈ 𝐴, and ⊕ ∈ 𝐴. If a set consists of many elements, we can use ellipses (…) to help describe the set. For example, the set consisting of the natural numbers between 17 and 5326, inclusive, can be written {17, 18, 19, … ,5325, 5326} (“inclusive” means that we include 17 and 5326). The ellipses between 19 and 5325 are there to indicate that there are elements in the set that we are not explicitly mentioning. Ellipses can also be used to help describe infinite sets. The set of natural numbers can be written ℕ = {0, 1, 2, 3, … }, and the set of integers can be written ℤ = {… , – 4, – 3, – 2, – 1, 0, 1, 2, 3, 4, … }. 19 Example 2.4: The odd natural numbers can be written 𝕆 = {1, 3, 5, … }. The even integers can be written 2ℤ = {… , – 6, – 4, – 2, 0, 2, 4, 6, … }. The primes can be written ℙ = {2, 3, 5, 7, 11, 13, 17, … }. A set can also be described by a certain property 𝑃 that all its elements have in common. In this case, we can use the setbuilder notation {𝑥𝑃(𝑥)} to describe the set. The expression {𝑥𝑃(𝑥)} can be read “the set of all 𝑥 such that the property 𝑃(𝑥) is true.” Note that the symbol “” is read as “such that.” Example 2.5: Let’s look at a few different ways that we can describe the set {2, 4, 6, 8, 10}. We have already seen that reordering and/or repeating elements does not change the set. For example, {2, 2, 6, 4, 10, 8} describes the same set. Here are a few more descriptions using setbuilder notation: • {𝑛  𝑛 is an even positive integer less than or equal to 10} • {𝑛 ∈ ℤ  𝑛 is even, 0 < 𝑛 ≤ 10} • {2𝑘  𝑘 = 1, 2, 3, 4, 5} The first expression in the bulleted list can be read “the set of 𝑛 such that 𝑛 is an even positive integer less than or equal to 10.” The second expression can be read “the set of integers 𝑛 such that 𝑛 is even and 𝑛 is between 0 and 10, including 10, but excluding 0. Note that the abbreviation “𝑛 ∈ ℤ” can be read “𝑛 is in the set of integers,” or more succinctly, “𝑛 is an integer.” The third expression can be read “the set of 2𝑘 such that 𝑘 is 1, 2, 3, 4, or 5.” If 𝐴 is a finite set, we define the cardinality of 𝐴, written 𝐴, to be the number of elements of 𝐴. For example, {𝑎, 𝑏} = 2. In Lesson 10, we will extend the notion of cardinality to also include infinite sets. Example 2.6: Let 𝐴 = {anteater, egg, trapezoid}, 𝐵 = {2, 3, 3}, and 𝐶 = {17, 18, 19, … , 5325, 5326}. Then 𝐴 = 3, 𝐵 = 2, and 𝐶 = 5310. Notes: (1) The set 𝐴 has the three elements “anteater,” “egg,” and “trapezoid.” (2) The set 𝐵 has just two elements: 2 and 3. Remember that {2, 3, 3} = {2, 3}. (3) The number of consecutive integers from 𝑚 to 𝑛, inclusive, is 𝒏 − 𝒎 + 𝟏. For set 𝐶, we have 𝑚 = 17 and 𝑛 = 5326. Therefore, 𝐶 = 5326 − 17 + 1 = 5310. (4) I call the formula “𝑛 − 𝑚 + 1” the fencepost formula. If you construct a 3foot fence by placing a fencepost every foot, then the fence will consist of 4 fenceposts (3 − 0 + 1 = 4). The empty set is the unique set with no elements. We use the symbol ∅ to denote the empty set (some authors use the symbol { } instead). Subsets For two sets 𝐴 and 𝐵, we say that 𝐴 is a subset of 𝐵, written 𝐴 ⊆ 𝐵, if every element of 𝐴 is an element of 𝐵. That is, 𝐴 ⊆ 𝐵 if, for every 𝑥, 𝑥 ∈ 𝐴 implies 𝑥 ∈ 𝐵. Symbolically, we can write ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵). 20 Notes: (1) The symbol ∀ is called a universal quantifier, and it is pronounced “For all.” (2) The logical expression ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵) can be translated into English as “For all 𝑥, if 𝑥 is an element of 𝐴, then 𝑥 is an element of 𝐵.” (3) To show that a set 𝐴 is a subset of a set 𝐵, we need to show that the expression ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵) is true. If the set 𝐴 is finite and the elements are listed, we can just check that each element of 𝐴 is also an element of 𝐵. However, if the set 𝐴 is described by a property, say 𝐴 = {𝑥𝑃(𝑥)}, we may need to craft an argument more carefully. We can begin by taking an arbitrary but specific element 𝑎 from 𝐴 and then arguing that this element 𝑎 is in 𝐵. What could we possibly mean by an arbitrary but specific element? Aren’t the words “arbitrary” and “specific” antonyms? Well, by arbitrary, we mean that we don’t know which element we are choosing – it’s just some element 𝑎 that satisfies the property 𝑃. So, we are just assuming that 𝑃(𝑎) is true. However, once we choose this element 𝑎, we use this same 𝑎 for the rest of the argument, and that is what we mean by it being specific. (4) To the right we see a physical representation of 𝐴 ⊆ 𝐵. This figure is called a Venn diagram. These types of diagrams are very useful to help visualize relationships among sets. Notice that set 𝐴 lies completely inside set 𝐵. We assume that all the elements of 𝐴 and 𝐵 lie in some universal set 𝑈. As an example, let’s let 𝑈 be the set of all species of animals. If we let 𝐴 be the set of species of cats and we let 𝐵 be the set of species of mammals, then we have 𝐴 ⊆ 𝐵 ⊆ 𝑈, and we see that the Venn diagram to the right gives a visual representation of this situation. (Note that every cat is a mammal and every mammal is an animal.) 𝐴⊆𝐵 Let’s try to prove our first theorem using the definition of a subset together with Note 3 above about arbitrary but specific elements. Theorem 2.1: Every set 𝐴 is a subset of itself. Before writing the proof, let’s think about our strategy. We want to prove 𝐴 ⊆ 𝐴. In other words, we want to show ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐴). So, we will take an arbitrary but specific 𝑎 ∈ 𝐴 and then argue that 𝑎 ∈ 𝐴. But that’s pretty obvious, isn’t it? In this case, the property describing the set is precisely the conclusion we are looking for. Here are the details. Proof of Theorem 2.1: Let 𝐴 be a set and let 𝑎 ∈ 𝐴. Then 𝑎 ∈ 𝐴. So, 𝑎 ∈ 𝐴 → 𝑎 ∈ 𝐴 is true. Since 𝑎 was an arbitrary element of 𝐴, ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐴) is true. Therefore, 𝐴 ⊆ 𝐴. □ Notes: (1) The proof begins with the opening statement “Let 𝐴 be a set and let 𝑎 ∈ 𝐴.” In general, the opening statement states what is given in the problem and/or fixes any arbitrary but specific objects that we will need. (2) The proof ends with the closing statement “Therefore, 𝐴 ⊆ 𝐴.” In general, the closing statement states the result. 21 (3) Everything between the opening statement and the closing statement is known as the argument. (4) We place the symbol □ at the end of the proof to indicate that the proof is complete. (5) Consider the logical statement 𝑝 → 𝑝. This statement is always true (T → T ≡ T and F → F ≡ T). 𝑝 → 𝑝 is an example of a tautology. A tautology is a statement that is true for every possible truth assignment of the propositional variables (see Problems 9 and 10 from Lesson 1 for more examples). (6) If we let 𝑝 represent the statement 𝑎 ∈ 𝐴, by Note 5, we see that 𝑎 ∈ 𝐴 → 𝑎 ∈ 𝐴 is always true. Alternate proof of Theorem 2.1: Let 𝐴 be a set and let 𝑎 ∈ 𝐴. Since 𝑝 → 𝑝 is a tautology, we have that 𝑎 ∈ 𝐴 → 𝑎 ∈ 𝐴 is true. Since 𝑎 was arbitrary, ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐴) is true. Therefore, 𝐴 ⊆ 𝐴. □ Let’s prove another basic but important theorem. Theorem 2.2: The empty set is a subset of every set. Analysis: This time we want to prove ∅ ⊆ 𝐴. In other words, we want to show ∀𝑥(𝑥 ∈ ∅ → 𝑥 ∈ 𝐴). Since 𝑥 ∈ ∅ is always false (the empty set has no elements), 𝑥 ∈ ∅ → 𝑥 ∈ 𝐴 is always true. In general, if 𝑝 is a false statement, then we say that 𝑝 → 𝑞 is vacuously true. Proof of Theorem 2.2: Let 𝐴 be a set. The statement 𝑥 ∈ ∅ → 𝑥 ∈ 𝐴 is vacuously true for any 𝑥, and so, ∀𝑥(𝑥 ∈ ∅ → 𝑥 ∈ 𝐴) is true. Therefore, ∅ ⊆ 𝐴. □ Note: The opening statement is “Let 𝐴 be a set,” the closing statement is “Therefore, ∅ ⊆ 𝐴,” and the argument is everything in between. Example 2.7: Let 𝐶 = {𝑎, 𝑏, 𝑐}, 𝐷 = {𝑎, 𝑐}, 𝐸 = {𝑏, 𝑐}, 𝐹 = {𝑏, 𝑑}, and 𝐺 = ∅. Then 𝐷 ⊆ 𝐶 and 𝐸 ⊆ 𝐶. Also, since the empty set is a subset of every set, we have 𝐺 ⊆ 𝐶, 𝐺 ⊆ 𝐷, 𝐺 ⊆ 𝐸, 𝐺 ⊆ 𝐹, and 𝐺 ⊆ 𝐺. Every set is a subset of itself, and so, 𝐶 ⊆ 𝐶, 𝐷 ⊆ 𝐷, 𝐸 ⊆ 𝐸, and 𝐹 ⊆ 𝐹. Note: Below are possible Venn diagrams for this problem. The diagram on the left shows the relationship between the sets 𝐶, 𝐷, 𝐸, and 𝐹. Notice how 𝐷 and 𝐸 are both subsets of 𝐶, whereas 𝐹 is not a subset of 𝐶. Also, notice how 𝐷 and 𝐸 overlap, 𝐸 and 𝐹 overlap, but there is no overlap between 𝐷 and 𝐹 (they have no elements in common). The diagram on the right shows the proper placement of the elements. Here, I chose the universal set to be 𝑈 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔}. This choice for the universal set is somewhat arbitrary. Any set containing {𝑎, 𝑏, 𝑐, 𝑑} would do. 22 Example 2.8: The set 𝐴 = {𝑎, 𝑏} has 2 elements and 4 subsets. The subsets of 𝐴 are ∅, {𝑎}, {𝑏}, and {𝑎, 𝑏}. The set 𝐵 = {𝑎, 𝑏, 𝑐} has 3 elements and 8 subsets. The subsets of 𝐵 are ∅, {𝑎}, {𝑏}, {𝑐}, {𝑎, 𝑏}, {𝑎, 𝑐}, {𝑏, 𝑐}, and {𝑎, 𝑏, 𝑐}. Let’s draw a tree diagram for the subsets of each of the sets 𝐴 and 𝐵. {𝑎, 𝑏} {𝑎} {𝑎, 𝑏, 𝑐} {𝑏} {𝑎, 𝑏} {𝑎} ∅ {𝑎, 𝑐} {𝑏} {𝑏, 𝑐} {𝑐} ∅ The tree diagram on the left is for the subsets of the set 𝐴 = {𝑎, 𝑏}. We start by writing the set 𝐴 = {𝑎, 𝑏} at the top. On the next line we write the subsets of cardinality 1 ({𝑎} and {𝑏}). On the line below that we write the subsets of cardinality 0 (just ∅). We draw a line segment between any two sets when the smaller (lower) set is a subset of the larger (higher) set. So, we see that ∅ ⊆ {𝑎}, ∅ ⊆ {𝑏}, {𝑎} ⊆ {𝑎, 𝑏}, and {𝑏} ⊆ {𝑎, 𝑏}. There is actually one more subset relationship, namely ∅ ⊆ {𝑎, 𝑏} (and of course each set displayed is a subset of itself). We didn’t draw a line segment from ∅ to {𝑎, 𝑏} to avoid unnecessary clutter. Instead, we can simply trace the path from ∅ to {𝑎} to {𝑎, 𝑏} (or from ∅ to {𝑏} to {𝑎, 𝑏}). We are using a property called transitivity here (see Theorem 2.3 below). The tree diagram on the right is for the subsets of 𝐵 = {𝑎, 𝑏, 𝑐}. Observe that from top to bottom we write the subsets of 𝐵 of size 3, then 2, then 1, and then 0. We then draw the appropriate line segments, just as we did for 𝐴 = {𝑎, 𝑏}. How many subsets does a set of cardinality 𝑛 have? Let’s start by looking at some examples. Example 2.9: A set with 0 elements must be ∅, and this set has exactly 1 subset (the only subset of the empty set is the empty set itself). A set with 1 element has 2 subsets, namely ∅ and the set itself. In the last example, we saw that a set with 2 elements has 4 subsets, and we also saw that a set with 3 elements has 8 subsets. Do you see the pattern yet? 1 = 20 , 2 = 21 , 4 = 22 , 8 = 23 . So, we see that a set with 0 elements has 20 subsets, a set with 1 element has 21 subsets, a set with 2 elements has 22 subsets, and a set with 3 elements has 23 subsets. A reasonable guess would be that a set with 𝑛 elements has 𝟐𝒏 subsets. You will be asked to prove this result later (Problem 12 in Lesson 4). We can also say that if 𝐴 = 𝑛, then 𝒫(𝐴) = 2𝑛 , where 𝒫(𝐴) (pronounced the power set of 𝐴) is the set of all subsets of 𝐴. In setbuilder notation, we write 𝒫(𝐴) = {𝐵  𝐵 ⊆ 𝐴}. Let’s get back to the transitivity mentioned above in our discussion of tree diagrams. 23 Theorem 2.3: Let 𝐴, 𝐵, and 𝐶 be sets such that 𝐴 ⊆ 𝐵 and 𝐵 ⊆ 𝐶. Then 𝐴 ⊆ 𝐶. Proof: Suppose that 𝐴, 𝐵, and 𝐶 are sets with 𝐴 ⊆ 𝐵 and 𝐵 ⊆ 𝐶, and let 𝑎 ∈ 𝐴. Since 𝐴 ⊆ 𝐵 and 𝑎 ∈ 𝐴, it follows that 𝑎 ∈ 𝐵. Since 𝐵 ⊆ 𝐶 and 𝑎 ∈ 𝐵, it follows that 𝑎 ∈ 𝐶. Since 𝑎 was an arbitrary element of 𝐴, we have shown that every element of 𝐴 is an element of 𝐶. That is, ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐶) is true. Therefore, 𝐴 ⊆ 𝐶. □ Note: To the right we have a Venn diagram illustrating Theorem 2.3. Theorem 2.3 tells us that the relation ⊆ is transitive. Since ⊆ is transitive, we can write things like 𝐴 ⊆ 𝐵 ⊆ 𝐶 ⊆ 𝐷, and without explicitly saying it, we know that 𝐴 ⊆ 𝐶, 𝐴 ⊆ 𝐷, and 𝐵 ⊆ 𝐷. Example 2.10: The membership relation ∈ is an example of a relation that is not transitive. For example, let 𝐴 = {0}, 𝐵 = {0, 1, {0}}, and 𝐶 = {𝑥, 𝑦, {0, 1, {0}}}. Observe that 𝐴 ∈ 𝐵 𝑨⊆𝑩⊆𝑪 and 𝐵 ∈ 𝐶, but 𝐴 ∉ 𝐶. Notes: (1) The set 𝐴 has just 1 element, namely 0. {0} ∈ {0, 1, {0}} ∈ {𝑥, 𝑦, {0, 1, {0}}} (2) The set 𝐵 has 3 elements, namely 0, 1, and {0}. But wait! 𝐴 = {0}. So, 𝐴 ∈ 𝐵. The set 𝐴 is circled twice in the above image. (3) The set 𝐶 also has 3 elements, namely, 𝑥, 𝑦, and {0,1, {0}}. But wait! 𝐵 = {0, 1, {0}}. So, 𝐵 ∈ 𝐶. The set 𝐵 has a rectangle around it twice in the above image. (4) Since 𝐴 ≠ 𝑥, 𝐴 ≠ 𝑦, and 𝐴 ≠ {0, 1, {0}}, we see that 𝐴 ∉ 𝐶. (5) Is it clear that {0} ∉ 𝐶? {0} is in a set that’s in 𝐶 (namely, 𝐵), but {0} is not itself in 𝐶. (6) Here is a more basic example showing that ∈ is not transitive: ∅ ∈ {∅} ∈ {{∅}}, but ∅ ∉ {{∅}} The only element of {{∅}} is {∅}. Unions and Intersections The union of the sets 𝐴 and 𝐵, written 𝐴 ∪ 𝐵, is the set of elements that are in 𝐴 or 𝐵 (or both). 𝐴 ∪ 𝐵 = {𝑥  𝑥 ∈ 𝐴 or 𝑥 ∈ 𝐵} The intersection of 𝐴 and 𝐵, written 𝐴 ∩ 𝐵, is the set of elements that are simultaneously in 𝐴 and 𝐵. 𝐴 ∩ 𝐵 = {𝑥  𝑥 ∈ 𝐴 and 𝑥 ∈ 𝐵} The following Venn diagrams for the union and intersection of two sets can be useful for visualizing these operations. 24 𝑨∪𝑩 𝑨∩𝑩 Example 2.11: 1. Let 𝐴 = {0, 1, 2, 3, 4} and 𝐵 = {3, 4, 5, 6}. Then 𝐴 ∪ 𝐵 = {0, 1, 2, 3, 4, 5, 6} and 𝐴 ∩ 𝐵 = {3, 4}. See the figure below for a visual representation of 𝐴, 𝐵, 𝐴 ∪ 𝐵 and 𝐴 ∩ 𝐵. 2. Recall that the set of natural numbers is ℕ = {0, 1, 2, 3, … } and the set of integers is ℤ = {… , – 4, – 3, – 2, – 1, 0, 1, 2, 3, 4, … }. Observe that in this case, we have ℕ ⊆ ℤ. Also, ℕ ∪ ℤ = ℤ and ℕ ∩ ℤ = ℕ. In fact, whenever 𝐴 and 𝐵 are sets and 𝐵 ⊆ 𝐴, then 𝐴 ∪ 𝐵 = 𝐴 and 𝐴 ∩ 𝐵 = 𝐵. We will prove the first of these two facts in Theorem 2.5. You will be asked to prove the second of these facts in Problem 13 below. 3. Let 𝔼 = {0, 2, 4, 6, … } be the set of even natural numbers and let 𝕆 = {1, 3, 5, 7, … } be the set of odd natural numbers. Then 𝔼 ∪ 𝕆 = {0, 1, 2, 3, 4, 5, 6, 7, … } = ℕ and 𝔼 ∩ 𝕆 = ∅. In general, we say that sets 𝐴 and 𝐵 are disjoint or mutually exclusive if 𝐴 ∩ 𝐵 = ∅. Below is a Venn diagram for disjoint sets. 𝑨∩𝑩=∅ 25 Let’s prove some theorems involving unions of sets. You will be asked to prove the analogous results for intersections of sets in Problems 11 and 13 below. Theorem 2.4: If 𝐴 and 𝐵 are sets, then 𝐴 ⊆ 𝐴 ∪ 𝐵. Before going through the proof, look once more at the Venn diagram above for 𝐴 ∪ 𝐵 and convince yourself that this theorem should be true. Proof of Theorem 2.4: Suppose that 𝐴 and 𝐵 are sets and let 𝑥 ∈ 𝐴. Then 𝑥 ∈ 𝐴 or 𝑥 ∈ 𝐵. Therefore, 𝑥 ∈ 𝐴 ∪ 𝐵. Since 𝑥 was an arbitrary element of 𝐴, we have shown that every element of 𝐴 is an element of 𝐴 ∪ 𝐵. That is, ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐴 ∪ 𝐵) is true. Therefore, 𝐴 ⊆ 𝐴 ∪ 𝐵. □ Note: Recall from Lesson 1 that if 𝑝 is a true statement, then 𝑝 ∨ 𝑞 (𝑝 or 𝑞) is true no matter what the truth value of 𝑞 is. In the second sentence of the proof above, we are using this fact with 𝑝 being the statement 𝑥 ∈ 𝐴 and 𝑞 being the statement 𝑥 ∈ 𝐵. We will use this same reasoning in the second paragraph of the next proof as well. Theorem 2.5: 𝐵 ⊆ 𝐴 if and only if 𝐴 ∪ 𝐵 = 𝐴. Before going through the proof, it’s a good idea to draw a Venn diagram for 𝐵 ⊆ 𝐴 and convince yourself that this theorem should be true. Technical note: Let 𝑋 and 𝑌 be sets. The Axiom of Extensionality says that 𝑋 and 𝑌 are the same set if and only if 𝑋 and 𝑌 have precisely the same elements. In symbols, we have 𝑋 = 𝑌 if and only if ∀𝑥(𝑥 ∈ 𝑋 ↔ 𝑥 ∈ 𝑌). It is easy to verify that 𝑝 ↔ 𝑞 is logically equivalent to (𝑝 → 𝑞) ∧ (𝑞 → 𝑝). To see this, we check that all possible truth assignments for 𝑝 and 𝑞 lead to the same truth value for the two statements. For example, if 𝑝 and 𝑞 are both true, then 𝑝↔𝑞≡T↔T≡T and (𝑝 → 𝑞) ∧ (𝑞 → 𝑝) ≡ (T → T) ∧ (T → T) ≡ T ∧ T ≡ T. The reader should check the other three truth assignments for 𝑝 and 𝑞, or draw the entire truth table for both statements. Letting 𝑝 be the statement 𝑥 ∈ 𝑋, letting 𝑞 be the statement 𝑥 ∈ 𝑌, and replacing 𝑝 ↔ 𝑞 by the logically equivalent statement (𝑝 → 𝑞) ∧ (𝑞 → 𝑝) gives us 𝑋 = 𝑌 if and only if ∀𝑥((𝑥 ∈ 𝑋 → 𝑥 ∈ 𝑌) ∧ (𝑥 ∈ 𝑌 → 𝑥 ∈ 𝑋)). It is also true that ∀𝑥(𝑝(𝑥) ∧ 𝑞(𝑥)) is logically equivalent to ∀𝑥(𝑝(𝑥)) ∧ ∀𝑥(𝑞(𝑥)). And so, we have 𝑋 = 𝑌 if and only if ∀𝑥(𝑥 ∈ 𝑋 → 𝑥 ∈ 𝑌) and ∀𝑥(𝑥 ∈ 𝑌 → 𝑥 ∈ 𝑋). In other words, to show that 𝑋 = 𝑌, we can instead show that 𝑋 ⊆ 𝑌 and 𝑌 ⊆ 𝑋. 26 Proof of Theorem 2.5: Suppose that 𝐵 ⊆ 𝐴 and let 𝑥 ∈ 𝐴 ∪ 𝐵. Then 𝑥 ∈ 𝐴 or 𝑥 ∈ 𝐵. If 𝑥 ∈ 𝐴, then 𝑥 ∈ 𝐴 (trivially). If 𝑥 ∈ 𝐵, then since 𝐵 ⊆ 𝐴, it follows that 𝑥 ∈ 𝐴. Since 𝑥 was an arbitrary element of 𝐴 ∪ 𝐵, we have shown that every element of 𝐴 ∪ 𝐵 is an element of 𝐴. That is, ∀𝑥(𝑥 ∈ 𝐴 ∪ 𝐵 → 𝑥 ∈ 𝐴) is true. Therefore, 𝐴 ∪ 𝐵 ⊆ 𝐴. By Theorem 2.4, 𝐴 ⊆ 𝐴 ∪ 𝐵. Since 𝐴 ∪ 𝐵 ⊆ 𝐴 and 𝐴 ⊆ 𝐴 ∪ 𝐵, it follows that 𝐴 ∪ 𝐵 = 𝐴. Now, suppose that 𝐴 ∪ 𝐵 = 𝐴 and let 𝑥 ∈ 𝐵. Since 𝑥 ∈ 𝐵, it follows that 𝑥 ∈ 𝐴 or 𝑥 ∈ 𝐵. Therefore, 𝑥 ∈ 𝐴 ∪ 𝐵. Since 𝐴 ∪ 𝐵 = 𝐴, we have 𝑥 ∈ 𝐴. Since 𝑥 was an arbitrary element of 𝐵, we have shown that every element of 𝐵 is an element of 𝐴. That is, ∀𝑥(𝑥 ∈ 𝐵 → 𝑥 ∈ 𝐴). Therefore, 𝐵 ⊆ 𝐴. □ 27 Problem Set 2 Full solutions to these problems are available for free download here: www.SATPrepGet800.com/PMFBXSG LEVEL 1 1. Determine whether each of the following statements is true or false: (i) 2 ∈ {2} (ii) 5∈∅ (iii) ∅ ∈ {1, 2} (iv) 𝑎 ∈ {𝑏, {𝑎}} (v) ∅ ⊆ {1, 2} (vi) {Δ} ⊆ {𝛿, Δ} (vii) {𝑎, 𝑏, 𝑐} ⊆ {𝑎, 𝑏, 𝑐} (viii) {1, 𝑎, {2, 𝑏}} ⊆ {1, 𝑎, 2, 𝑏} 2. Determine the cardinality of each of the following sets: (i) {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓} (ii) {1, 2, 3, 2, 1} (iii) {1, 2, … , 53} (iv) {5, 6, 7, … , 2076, 2077} 3. Let 𝐴 = {𝑎, 𝑏, Δ, 𝛿} and 𝐵 = {𝑏, 𝑐, 𝛿, 𝛾}. Determine each of the following: (i) 𝐴∪𝐵 (ii) 𝐴∩𝐵 LEVEL 2 4. Determine whether each of the following statements is true or false: (i) ∅∈∅ (ii) ∅ ∈ {∅} (iii) {∅} ∈ ∅ (iv) {∅} ∈ {∅} (v) ∅⊆∅ (vi) ∅ ⊆ {∅} (vii) {∅} ⊆ ∅ (viii) {∅} ⊆ {∅} 28 5. Determine the cardinality of each of the following sets: (i) {∅, {1, 2, 3}} (ii) {{{∅, {∅}}}} (iii) {{1,2}, ∅, {∅}, {∅, {∅, 1, 2}}} (iv) {∅, {∅}, {{∅}}, {∅, {∅}, {{∅}}}} 6. Let 𝑃 = {∅, {∅}} and 𝑄 = {{∅}, {∅, {∅}}}. Determine each of the following: (i) 𝑃∪𝑄 (ii) 𝑃∩𝑄 LEVEL 3 7. How many subsets does {𝑎, 𝑏, 𝑐, 𝑑} have? Draw a tree diagram for the subsets of {𝑎, 𝑏, 𝑐, 𝑑}. 8. A set 𝐴 is transitive if ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ⊆ 𝐴) (in words, every element of 𝐴 is also a subset of 𝐴). Determine if each of the following sets is transitive: (i) ∅ (ii) {∅} (iii) {{∅}} (iv) {∅, {∅}, {{∅}}} LEVEL 4 9. A relation 𝑅 is reflexive if ∀𝑥(𝑥𝑅𝑥) and symmetric if ∀𝑥∀𝑦(𝑥𝑅𝑦 → 𝑦𝑅𝑥). Show that ⊆ is reflexive, but ∈ is not. Then decide if each of ⊆ and ∈ is symmetric. 10. Let 𝐴, 𝐵, 𝐶, 𝐷, and 𝐸 be sets such that 𝐴 ⊆ 𝐵, 𝐵 ⊆ 𝐶, 𝐶 ⊆ 𝐷, and 𝐷 ⊆ 𝐸. Prove that 𝐴 ⊆ 𝐸. 11. Let 𝐴 and 𝐵 be sets. Prove that 𝐴 ∩ 𝐵 ⊆ 𝐴. LEVEL 5 12. Let 𝑃(𝑥) be the property 𝑥 ∉ 𝑥. Prove that {𝑥𝑃(𝑥)} cannot be a set. 13. Prove that 𝐵 ⊆ 𝐴 if and only if 𝐴 ∩ 𝐵 = 𝐵. 14. Let 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}, 𝐵 = {𝑋  𝑋 ⊆ 𝐴 ∧ 𝑑 ∉ 𝑋}, and 𝐶 = {𝑋  𝑋 ⊆ 𝐴 ∧ 𝑑 ∈ 𝑋}. Show that there is a natural onetoone correspondence between the elements of 𝐵 and the elements of 𝐶. Then generalize this result to a set with 𝑛 + 1 elements for 𝑛 > 0. 29 LESSON 3 – ABSTRACT ALGEBRA SEMIGROUPS, MONOIDS, AND GROUPS Binary Operations and Closure A binary operation on a set is a rule that combines two elements of the set to produce another element of the set. Example 3.1: Let 𝑆 = {0, 1}. Multiplication on 𝑆 is a binary operation, whereas addition on 𝑆 is not a binary operation (here we are thinking of multiplication and addition in the “usual” sense, meaning the way we would think of them in elementary school or middle school). To see that multiplication is a binary operation on 𝑆, observe that 0 ⋅ 0 = 0, 0 ⋅ 1 = 0, 1 ⋅ 0 = 0, and 1 ⋅ 1 = 1. Each of the four computations produces 0 or 1, both of which are in the set 𝑆. To see that addition is not a binary operation on 𝑆, just note that 1 + 1 = 2, and 2 ∉ 𝑆. Let’s get a bit more technical and write down the formal definition of a binary operation. The terminology and notation used in this definition will be clarified in the notes below and formalized more rigorously later in Lesson 10. Formally, a binary operation ⋆ on a set 𝑆 is a function ⋆ ∶ 𝑆 × 𝑆 → 𝑆. So, if 𝑎, 𝑏 ∈ 𝑆, then we have ⋆ (𝑎, 𝑏) ∈ 𝑆. For easier readability, we will usually write ⋆ (𝑎, 𝑏) as 𝑎 ⋆ 𝑏. Notes: (1) If 𝐴 and 𝐵 are sets, then 𝐴 × 𝐵 is called the Cartesian product of 𝐴 and 𝐵. It consists of the ordered pairs (𝑎, 𝑏), where 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵. A function 𝑓: 𝐴 × 𝐵 → 𝐶 takes each such pair (𝑎, 𝑏) to an element 𝑓(𝑎, 𝑏) ∈ 𝐶. As an example, let 𝐴 = {dog, fish}, 𝐵 = {cat, snake}, 𝐶 = {0, 2, 4, 6, 8}, and define 𝑓: 𝐴 × 𝐵 → 𝐶 by 𝑓(𝑎, 𝑏) = the total number of legs that animals 𝑎 and 𝑏 have. Then we have 𝑓(dog, cat) = 8, 𝑓(dog, snake) = 4, 𝑓(fish, cat) = 4, 𝑓(fish, snake) = 0. We will look at ordered pairs, cartesian products, and functions in more detail in Lesson 10. (2) For a binary operation, all three sets 𝐴, 𝐵, and 𝐶 in the expression 𝑓: 𝐴 × 𝐵 → 𝐶 are the same. As we saw in Example 3.1 above, if we let 𝑆 = {0, 1}, and we let ⋆ be multiplication, then ⋆ is a binary operation on 𝑆. Using function notation, we have ⋆ (0, 0) = 0, ⋆ (0, 1) = 0, ⋆ (1, 0) = 0, and ⋆ (1, 1) = 1. As stated in the formal definition of a binary operation above, we will usually write the computations as 0 ⋆ 0 = 0, 0 ⋆ 1 = 0, 1 ⋆ 0 = 0, and 1 ⋆ 1 = 1. We can use symbols other than ⋆ for binary operations. For example, if the operation is multiplication, we would usually use a dot (⋅) for the operation as we did in Example 3.1 above. Similarly, for addition we would usually use +, for subtraction we would usually use −, and so on. 30 Recall: ℕ = {0, 1, 2, 3, … } is the set of natural numbers and ℤ = {… , – 4, – 3, – 2, – 1, 0, 1, 2, 3, 4, … } is the set of integers. If 𝐴 is a set of numbers, we let 𝐴+ be the subset of 𝐴 consisting of just the positive numbers from 𝐴. For example, ℤ+ = {1, 2, 3, 4, … }, and in fact, ℕ+ = ℤ+ . Example 3.2: 1. The operation of addition on the set of natural numbers is a binary operation because whenever we add two natural numbers we get another natural number. Here, the set 𝑆 is ℕ and the operation ⋆ is +. Observe that if 𝑎 ∈ ℕ and 𝑏 ∈ ℕ, then 𝑎 + 𝑏 ∈ ℕ. For example, if 𝑎 = 1 and 𝑏 = 2 (both elements of ℕ), then 𝑎 + 𝑏 = 1 + 2 = 3, and 3 ∈ ℕ. 2. The operation of multiplication on the set of positive integers is a binary operation because whenever we multiply two positive integers we get another positive integer. Here, the set 𝑆 is ℤ+ and the operation ⋆ is ⋅. Observe that if 𝑎 ∈ ℤ+ and 𝑏 ∈ ℤ+ , then 𝑎 ⋅ 𝑏 ∈ ℤ+ . For example, if 𝑎 = 3 and 𝑏 = 5 (both elements of ℤ+ ), then 𝑎 ⋅ 𝑏 = 3 ⋅ 5 = 15, and 15 ∈ ℤ+ . 3. Let 𝑆 = ℤ and define ⋆ by 𝑎 ⋆ 𝑏 = min{𝑎, 𝑏}, where min{𝑎, 𝑏} is the smallest of 𝑎 or 𝑏. Then ⋆ is a binary operation on ℤ. For example, if 𝑎 = – 5 and 𝑏 = 3 (both elements of ℤ), then 𝑎 ⋆ 𝑏 = – 5, and – 5 ∈ ℤ. 4. Subtraction on the set of natural numbers is not a binary operation. To see this, we just need to provide a single counterexample. (A counterexample is an example that is used to prove that a statement is false.) If we let 𝑎 = 1 and 𝑏 = 2 (both elements of ℕ), then we see that 𝑎 − 𝑏 = 1 − 2 is not an element of ℕ. 5. Let 𝑆 = {𝑢, 𝑣, 𝑤} and define ⋆ using the following table: ⋆ 𝑢 𝑣 𝑤 𝑢 𝑣 𝑤 𝑢 𝑣 𝑤 𝑢 𝑣 𝑤 𝑤 𝑢 𝑣 The table given above is called a multiplication table. For 𝑎, 𝑏 ∈ 𝑆, we evaluate 𝑎 ⋆ 𝑏 by taking the entry in the row given by 𝑎 and the column given by 𝑏. For example, 𝑣 ⋆ 𝑤 = 𝑢. ⋆ 𝑢 𝑣 𝑤 𝑢 𝑣 𝑤 𝑢 𝑣 𝑤 𝑢 𝑣 𝑤 𝑤 𝑢 𝑣 ⋆ is a binary operation on 𝑆 because the only possible “outputs” are 𝑢, 𝑣, and 𝑤. Some authors refer to a binary operation ⋆ on a set 𝑆 even when the binary operation is not defined on all pairs of elements 𝑎, 𝑏 ∈ 𝑆. We will always refer to these “false operations” as partial binary operations. We say that the set 𝑆 is closed under the partial binary operation ⋆ if whenever 𝑎, 𝑏 ∈ 𝑆, we have 𝑎 ⋆ 𝑏 ∈ 𝑆. 31 In Example 3.2, part 4 above, we saw that subtraction is a partial binary operation on ℕ that is not a binary operation. In other words, ℕ is not closed under subtraction. Semigroups and Associativity Let ⋆ be a binary operation on a set 𝑆. We say that ⋆ is associative in 𝑆 if for all 𝑥, 𝑦, 𝑧 in 𝑆, we have (𝑥 ⋆ 𝑦) ⋆ 𝑧 = 𝑥 ⋆ (𝑦 ⋆ 𝑧) A semigroup is a pair (𝑆,⋆), where 𝑆 is a set and ⋆ is an associative binary operation on 𝑆. Example 3.3: 1. (ℕ, +), (ℤ, +), (ℕ, ⋅), and (ℤ, ⋅) are all semigroups. In other words, the operations of addition and multiplication are both associative in ℕ and ℤ. 2. Let 𝑆 = ℤ and define ⋆ by 𝑎 ⋆ 𝑏 = min{𝑎, 𝑏}, where min{𝑎, 𝑏} is the smallest of 𝑎 or 𝑏. Let’s check that ⋆ is associative in ℤ. Let 𝑎, 𝑏, and 𝑐 be elements of ℤ. There are actually 6 cases to consider (see Note 1 below). Let’s go through one of these cases in detail. If we assume that 𝑎 ≤ 𝑏 ≤ 𝑐, then we have (𝑎 ⋆ 𝑏) ⋆ 𝑐 = min{𝑎, 𝑏} ⋆ 𝑐 = 𝑎 ⋆ 𝑐 = min{𝑎, 𝑐} = 𝑎. 𝑎 ⋆ (𝑏 ⋆ 𝑐) = 𝑎 ⋆ min{𝑏, 𝑐} = 𝑎 ⋆ 𝑏 = min{𝑎, 𝑏} = 𝑎. Since both (𝑎 ⋆ 𝑏) ⋆ 𝑐 = 𝑎 and 𝑎 ⋆ (𝑏 ⋆ 𝑐) = 𝑎, we have (𝑎 ⋆ 𝑏) ⋆ 𝑐 = 𝑎 ⋆ (𝑏 ⋆ 𝑐). After checking the other 5 cases, we can say the following: Since 𝑎, 𝑏, and 𝑐 were arbitrary elements from ℤ, we have shown that ⋆ is associative in ℤ. It follows that (ℤ,⋆) is a semigroup. 3. Subtraction is not associative in ℤ. To see this, we just need to provide a single counterexample. If we let 𝑎 = 1, 𝑏 = 2, and 𝑐 = 3, then (𝑎 − 𝑏) − 𝑐 = (1 − 2) − 3 = – 1 − 3 = – 4 and 𝑎 − (𝑏 − 𝑐) = 1 − (2 − 3) = 1 − (– 1) = 1 + 1 = 2. Since – 4 ≠ 2, subtraction is not associative in ℤ. It follows that (ℤ, −) is not a semigroup. Note that (ℕ, −) is also not a semigroup, but for a different reason. Subtraction is not even a binary operation on ℕ (see part 4 in Example 3.2). 4. Let 𝑆 = {𝑢, 𝑣, 𝑤} and define ⋆ using the following table (this is the same table from part 5 in Example 3.2): ⋆ 𝑢 𝑣 𝑤 𝑢 𝑣 𝑤 𝑢 𝑣 𝑤 𝑢 𝑣 𝑤 𝑤 𝑢 𝑣 Notice that (𝑢 ⋆ 𝑣) ⋆ 𝑤 = 𝑤 ⋆ 𝑤 = 𝑣 and 𝑢 ⋆ (𝑣 ⋆ 𝑤) = 𝑢 ⋆ 𝑢 = 𝑣. So, (𝑢 ⋆ 𝑣) ⋆ 𝑤 = 𝑢 ⋆ (𝑣 ⋆ 𝑤). However, this single computation does not show that ⋆ is associative in 𝑆. In fact, we have the following counterexample: (𝑢 ⋆ 𝑤) ⋆ 𝑣 = 𝑤 ⋆ 𝑣 = 𝑣 and 𝑢 ⋆ (𝑤 ⋆ 𝑣) = 𝑢 ⋆ 𝑣 = 𝑤. Thus, (𝑢 ⋆ 𝑤) ⋆ 𝑣 ≠ 𝑢 ⋆ (𝑤 ⋆ 𝑣). So, ⋆ is not associative in 𝑆, and therefore, (𝑆,⋆) is not a semigroup. 32 5. Let 2ℤ = {… , – 6, – 4, – 2, 0, 2, 4, 6, … } be the set of even integers. When we multiply two even integers together, we get another even integer (we will prove this in Lesson 4). It follows that multiplication is a binary operation on 2ℤ. Since multiplication is associative in ℤ and 2ℤ ⊆ ℤ, it follows that multiplication is associative in 2ℤ (see Note 2 below). So, (2ℤ, ⋅) is a semigroup. Notes: (1) In part 2 above, we must prove the result for each of the following 6 cases: 𝑎≤𝑏≤𝑐 𝑎≤𝑐≤𝑏 𝑏≤𝑎≤𝑐 𝑏≤𝑐≤𝑎 𝑐≤𝑎≤𝑏 𝑐≤𝑏≤𝑎 The same basic argument can be used for all these cases. For example, we saw in the solution above that for the first case we get (𝑎 ⋆ 𝑏) ⋆ 𝑐 = min{𝑎, 𝑏} ⋆ 𝑐 = 𝑎 ⋆ 𝑐 = min{𝑎, 𝑐} = 𝑎. 𝑎 ⋆ (𝑏 ⋆ 𝑐) = 𝑎 ⋆ min{𝑏, 𝑐} = 𝑎 ⋆ 𝑏 = min{𝑎, 𝑏} = 𝑎. Let’s also do the last case 𝑐 ≤ 𝑏 ≤ 𝑎: (𝑎 ⋆ 𝑏) ⋆ 𝑐 = min{𝑎, 𝑏} ⋆ 𝑐 = 𝑏 ⋆ 𝑐 = min{𝑏, 𝑐} = 𝑐. 𝑎 ⋆ (𝑏 ⋆ 𝑐) = 𝑎 ⋆ min{𝑏, 𝑐} = 𝑎 ⋆ 𝑐 = min{𝑎, 𝑐} = 𝑐. The reader should verify the other 4 cases to complete the proof. (2) Associativity is closed downwards. By this, we mean that if ⋆ is associative in a set 𝐴, and 𝐵 ⊆ 𝐴, (𝐵 is a subset of 𝐴) then ⋆ is associative in 𝐵. The reason for this is that the definition of associativity involves only a universal statement—a statement that describes a property that is true for all elements without mentioning the existence of any new elements. A universal statement begins with the quantifier ∀ (“For all” or “Every”) and never includes the quantifier ∃ (“There exists” or “There is”). As a simple example, if every object in set 𝐴 is a fruit, and 𝐵 ⊆ 𝐴, then every object in 𝐵 is a fruit. The universal statement we are referring to might be ∀𝑥(𝑃(𝑥)), where 𝑃(𝑥) is the property “𝑥 is a fruit.” In the case of associativity, the universal statement is ∀𝑥∀𝑦∀𝑧((𝑥 ⋆ 𝑦) ⋆ 𝑧 = 𝑥 ⋆ (𝑦 ⋆ 𝑧)). Let ⋆ be a binary operation on a set 𝑆. We say that ⋆ is commutative (or Abelian) in 𝑆 if for all 𝑥, 𝑦 in 𝑆, we have 𝑥 ⋆ 𝑦 = 𝑦 ⋆ 𝑥. Example 3.4: 1. (ℕ, +), (ℤ, +), (ℕ, ⋅), and (ℤ, ⋅) are all commutative semigroups. In other words, the operations of addition and multiplication are both commutative in ℕ and ℤ (in addition to being associative). 2. The semigroup (ℤ,⋆), where ⋆ is defined by 𝑎 ⋆ 𝑏 = min{𝑎, 𝑏} is a commutative semigroup. Let’s check that ⋆ is commutative in ℤ. Let 𝑎 and 𝑏 be elements of ℤ. This time there are just 2 cases to consider (𝑎 ≤ 𝑏 and 𝑏 ≤ 𝑎). Let’s do the first case in detail, and assume that 𝑎 ≤ 𝑏. We then have 𝑎 ⋆ 𝑏 = min{𝑎, 𝑏} = 𝑎 and 𝑏 ⋆ 𝑎 = min{𝑏, 𝑎} = 𝑎. So, 𝑎 ⋆ 𝑏 = 𝑏 ⋆ 𝑎. After verifying the other case (which you should do), we can say that ⋆ is commutative in ℤ. 33 3. Define the binary operation ⋆ on ℕ by 𝑎 ⋆ 𝑏 = 𝑎. Then (ℕ,⋆) is a semigroup that is not commutative. For associativity, we have (𝑎 ⋆ 𝑏) ⋆ 𝑐 = 𝑎 ⋆ 𝑐 = 𝑎 and 𝑎 ⋆ (𝑏 ⋆ 𝑐) = 𝑎 ⋆ 𝑏 = 𝑎. Let’s use a counterexample to show that ⋆ is not commutative. Well, 2 ⋆ 5 = 2 and 5 ⋆ 2 = 5. Note: In part 3 above, the computation 𝑎 ⋆ (𝑏 ⋆ 𝑐) can actually be done in 1 step instead of 2. The way we did it above was to first compute 𝑏 ⋆ 𝑐 = 𝑏, and then to replace 𝑏 ⋆ 𝑐 with 𝑏 to get 𝑎 ⋆ (𝑏 ⋆ 𝑐) = 𝑎 ⋆ 𝑏 = 𝑎. However, the definition of ⋆ says that 𝑎 ⋆ (anything) = 𝑎. In this case, the “anything” is 𝑏 ⋆ 𝑐. So, we have 𝑎 ⋆ (𝑏 ⋆ 𝑐) = 𝑎 just by appealing to the definition of ⋆. Monoids and Identity Let (𝑆,⋆) be a semigroup. An element 𝑒 of 𝑆 is called an identity with respect to the binary operation ⋆ if for all 𝑎 ∈ 𝑆, we have 𝑒 ⋆ 𝑎 = 𝑎 ⋆ 𝑒 = 𝑎 A monoid is a semigroup with an identity. Example 3.5: 1. (ℕ, +) and (ℤ, +) are commutative monoids with identity 0 (when we add 0 to any integer 𝑎, we get 𝑎). (ℕ, ⋅) and (ℤ, ⋅) are commutative monoids with identity 1 (when we multiply any integer 𝑎 by 1, we get 𝑎). 2. The commutative semigroup (ℤ,⋆), where ⋆ is defined by 𝑎 ⋆ 𝑏 = min{𝑎, 𝑏} is not a monoid. To see this, let 𝑎 ∈ ℤ. Then 𝑎 + 1 ∈ ℤ and 𝑎 ⋆ (𝑎 + 1) = 𝑎 ≠ 𝑎 + 1. This shows that 𝑎 is not an identity. Since 𝑎 was an arbitrary element of ℤ, we showed that there is no identity. It follows that (ℤ,⋆) is not a monoid. 3. The noncommutative semigroup (ℕ,⋆), where 𝑎 ⋆ 𝑏 = 𝑎 is also not a monoid. Use the same argument given in 2 above with ℤ replaced by ℕ. 4. (2ℤ, ⋅) is another example of a semigroup that is not a monoid. The identity element of (ℤ, ⋅) is 1, and this element is missing from (2ℤ, ⋅). Groups and Inverses Let (𝑀,⋆) be a monoid with identity 𝑒. An element 𝑎 of 𝑀 is called invertible if there is an element 𝑏 ∈ 𝑀 such that 𝑎 ⋆ 𝑏 = 𝑏 ⋆ 𝑎 = 𝑒. A group is a monoid in which every element is invertible. Groups appear so often in mathematics that it’s worth taking the time to explicitly spell out the full definition of a group. A group is a pair (𝐺,⋆) consisting of a set 𝐺 together with a binary operation ⋆ satisfying: (1) (Associativity) For all 𝑥, 𝑦, 𝑧 ∈ 𝐺, (𝑥 ⋆ 𝑦) ⋆ 𝑧 = 𝑥 ⋆ (𝑦 ⋆ 𝑧). (2) (Identity) There exists an element 𝑒 ∈ 𝐺 such that for all 𝑥 ∈ 𝐺, 𝑒 ⋆ 𝑥 = 𝑥 ⋆ 𝑒 = 𝑥. (3) (Inverse) For each 𝑥 ∈ 𝐺, there is 𝑦 ∈ 𝐺 such that 𝑥 ⋆ 𝑦 = 𝑦 ⋆ 𝑥 = 𝑒. Notes: (1) If 𝑦 ∈ 𝐺 is an inverse of 𝑥 ∈ 𝐺, we will usually write 𝑦 = 𝑥 −1 . 34 (2) Recall that the definition of a binary operation already implies closure. However, many books on groups will mention this property explicitly: (Closure) For all 𝑥, 𝑦 ∈ 𝐺, 𝑥 ⋆ 𝑦 ∈ 𝐺. (3) A group is commutative or Abelian if for all 𝑥, 𝑦 ∈ 𝐺, 𝑥 ⋆ 𝑦 = 𝑦 ⋆ 𝑥. Example 3.6: 1. (ℤ, +) is a commutative group with identity 0. The inverse of any integer 𝑎 is the integer – 𝑎. 2. (ℕ, +) is a commutative monoid that is not a group. For example, the natural number 1 has no inverse in ℕ. In other words, the equation 𝑥 + 1 = 0 has no solution in ℕ. 3. (ℤ, ⋅) is a commutative monoid that is not a group. For example, the integer 2 has no inverse in ℤ. In other words, the equation 2𝑥 = 1 has no solution in ℤ. 𝑎 4. A rational number is a number of the form , where 𝑎 and 𝑏 are integers and 𝑏 ≠ 0. 𝑏 𝑎 𝑐 1 3 We identify rational numbers 𝑏 and 𝑑 whenever 𝑎𝑑 = 𝑏𝑐. For example, 2 and 6 represent the same rational number because 1 ⋅ 6 = 6 and 2 ⋅ 3 = 6. 𝑎 We denote the set of rational numbers by ℚ. So, we have ℚ = {𝑏  𝑎, 𝑏 ∈ ℤ, 𝑏 ≠ 0}. In words, ℚ is “the set of quotients 𝑎 over 𝑏 such that 𝑎 and 𝑏 are integers and 𝑏 is not zero.” 𝑎 We identify the rational number 1 with the integer 𝑎. In this way, we have ℤ ⊆ ℚ. 𝑎 𝑐 We add two rational numbers using the rule 𝑏 + 𝑑 = 0 𝑎 𝑎⋅𝑑+𝑏⋅𝑐 𝑏⋅𝑑 0 Note that 0 = 1 is an identity for (ℚ, +) because 𝑏 + 1 = . 𝑎⋅1+𝑏⋅0 𝑏⋅1 𝑎 0 𝑎 = 𝑏 and 1 + 𝑏 = 0⋅𝑏+1⋅𝑎 1⋅𝑏 𝑎 = 𝑏. You will be asked to show in Problem 11 below that (ℚ, +) is a commutative group. 𝑎 𝑐 𝑎⋅𝑐 𝑎 1 𝑎⋅1 5. We multiply two rational numbers using the rule 𝑏 ⋅ 𝑑 = 𝑏⋅𝑑. 1 𝑎 1 𝑎 1⋅𝑎 𝑎 Note that 1 = 1 is an identity for (ℚ, ⋅) because 𝑏 ⋅ 1 = 𝑏⋅1 = 𝑏 and 1 ⋅ 𝑏 = 1⋅𝑏 = 𝑏. 𝑎 0 𝑎 0⋅𝑎 0 Now, 0 ⋅ 𝑏 = 1 ⋅ 𝑏 = 1⋅𝑏 = 𝑏 = 0. In particular, when we multiply 0 by any rational number, we can never get 1. So, 0 is a rational number with no multiplicative inverse. It follows that (ℚ, ⋅) is not a group. However, 0 is the only rational number without a multiplicative inverse. In fact, you will be asked to show in Problem 9 below that (ℚ∗ , ⋅) is a commutative group, where ℚ∗ is the set of rational numbers with 0 removed. Note: When multiplying two numbers, we sometimes drop the dot (⋅) for easier readability. So, we may 𝑎 𝑐 write 𝑥 ⋅ 𝑦 as 𝑥𝑦. We may also use parentheses instead of the dot. For example, we might write 𝑏 ⋅ 𝑑 as 𝑎 𝑐 𝑎⋅𝑐 𝑎𝑐 (𝑏) (𝑑), whereas we would probably write 𝑏⋅𝑑 as 𝑏𝑑. We may even use this simplified notation for arbitrary group operations. So, we could write 𝑎 ⋆ 𝑏 as 𝑎𝑏. However, we will avoid doing this if it would lead to confusion. For example, we will not write 𝑎 + 𝑏 as 𝑎𝑏. 35 Problem Set 3 Full solutions to these problems are available for free download here: www.SATPrepGet800.com/PMFBXSG LEVEL 1 1. For each of the following multiplication tables defined on the set 𝑆 = {𝑎, 𝑏}, determine if each of the following is true or false: (i) ⋆ defines a binary operation on 𝑆. (ii) ⋆ is commutative in 𝑆. (iii) 𝑎 is an identity with respect to ⋆. (iv) 𝑏 is an identity with respect to ⋆. I ) ⋆ 𝑎 𝑏 𝑎 𝑎 𝑎 𝑏 𝑎 𝑎 II ⋆ 𝑎 𝑏 𝑎 𝑎 𝑐 𝑏 𝑏 𝑎 III ⋆ 𝑎 𝑏 𝑎 𝑎 𝑏 𝑏 𝑏 𝑎 IV ⋆ 𝑎 𝑏 𝑎 𝑎 𝑏 𝑏 𝑎 𝑏 2. Show that there are exactly two monoids on the set 𝑆 = {𝑒, 𝑎}, where 𝑒 is the identity. Which of these monoids are groups? Which of these monoids are commutative? LEVEL 2 3. Let 𝐺 = {𝑒, 𝑎, 𝑏} and let (𝐺,⋆) be a group with identity element 𝑒. Draw a multiplication table for (𝐺,⋆). 4. Prove that in any monoid (𝑀,⋆), the identity element is unique. LEVEL 3 5. Assume that a group (𝐺,⋆) of order 4 exists with 𝐺 = {𝑒, 𝑎, 𝑏, 𝑐}, where 𝑒 is the identity, 𝑎2 = 𝑏 and 𝑏 2 = 𝑒. Construct the table for the operation of such a group. 6. Prove that in any group (𝐺,⋆), each element has a unique inverse. 36 LEVEL 4 7. Let (𝐺,⋆) be a group with 𝑎, 𝑏 ∈ 𝐺, and let 𝑎−1 and 𝑏 −1 be the inverses of 𝑎 and 𝑏, respectively. Prove (i) (𝑎 ⋆ 𝑏)−1 = 𝑏 −1 ⋆ 𝑎−1. (ii) the inverse of 𝑎−1 is 𝑎. 8. Let (𝐺,⋆) be a group such that 𝑎2 = 𝑒 for all 𝑎 𝐺. Prove that (𝐺,⋆) is commutative. 9. Prove that (ℚ∗ , ⋅) is a commutative group. LEVEL 5 10. Prove that there are exactly two groups of order 4, up to renaming the elements. 11. Show that (ℚ, +) is a commutative group. 12. Let 𝑆 = {𝑎, 𝑏}, where 𝑎 ≠ 𝑏. How many binary operations are there on 𝑆? How many semigroups are there of the form (𝑆,⋆), up to renaming the elements? 37 LESSON 4 – NUMBER THEORY THE RING OF INTEGERS Rings and Distributivity Before giving the general definition of a ring, let’s look at an important example. Example 4.1: Recall that ℤ = {… , – 4, – 3, – 2, – 1, 0, 1, 2, 3, 4, … } is the set of integers. Let’s go over some of the properties of addition and multiplication on this set. 1. ℤ is closed under addition. In other words, whenever we add two integers, we get another integer. For example, 2 and 3 are integers, and we have 2 + 3 = 5, which is also an integer. As another example, – 8 and 6 are integers, and so is – 8 + 6 = – 2. 2. Addition is commutative in ℤ. In other words, when we add two integers, it does not matter which one comes first. For example, 2 + 3 = 5 and 3 + 2 = 5. So, we see that 2 + 3 = 3 + 2. As another example, – 8 + 6 = – 2 and 6 + (– 8) = – 2. So, we see that – 8 + 6 = 6 + (– 8). 3. Addition is associative in ℤ. In other words, when we add three integers, it doesn’t matter if we begin by adding the first two or the last two integers. For example, (2 + 3) + 4 = 5 + 4 = 9 and 2 + (3 + 4) = 2 + 7 = 9. So, (2 + 3) + 4 = 2 + (3 + 4). As another example, we have (– 8 + 6) + (– 5) = – 2 + (– 5) = – 7 and – 8 + (6 + (– 5)) = – 8 + 1 = – 7. So, we see that (– 8 + 6) + (– 5) = – 8 + (6 + (– 5)). 4. ℤ has an identity for addition, namely 0. Whenever we add 0 to another integer, the result is that same integer. For example, we have 0 + 3 = 3 and 3 + 0 = 3. As another example, 0 + (– 5) = – 5 and (– 5) + 0 = – 5. 5. Every integer has an additive inverse. This is an integer that we add to the original integer to get 0 (the additive identity). For example, the additive inverse of 5 is – 5 because we have 5 + (– 5) = 0 and – 5 + 5 = 0. Notice that the same two equations also show that the inverse of – 5 is 5. We can say that 5 and – 5 are additive inverses of each other. We can summarize the five properties above by saying that (ℤ, +) is a commutative group. 6. ℤ is closed under multiplication. In other words, whenever we multiply two integers, we get another integer. For example, 2 and 3 are integers, and we have 2 ⋅ 3 = 6, which is also an integer. As another example, – 3 and – 4 are integers, and so is (– 3)(– 4) = 12. 7. Multiplication is commutative in ℤ. In other words, when we multiply two integers, it does not matter which one comes first. For example, 2 ⋅ 3 = 6 and 3 ⋅ 2 = 6. So, 2 ⋅ 3 = 3 ⋅ 2. As another example, – 8 ⋅ 6 = – 48 and 6(– 8) = – 48. So, we see that – 8 ⋅ 6 = 6(– 8). 8. Multiplication is associative in ℤ. In other words, when we multiply three integers, it doesn’t matter if we begin by multiplying the first two or the last two integers. For example, (2 ⋅ 3) ⋅ 4 = 6 ⋅ 4 = 24 and 2 ⋅ (3 ⋅ 4) = 2 ⋅ 12 = 24. So, (2 ⋅ 3) ⋅ 4 = 2 ⋅ (3 ⋅ 4). As another example, (– 5 ⋅ 2) ⋅ (– 6) = −10 ⋅ (– 6) = 60 and – 5 ⋅ (2 ⋅ (– 6)) = – 5 ⋅ (– 12) = 60. So, we see that (– 5 ⋅ 2) ⋅ (– 6) = – 5 ⋅ (2 ⋅ (– 6)). 38 9. ℤ has an identity for multiplication, namely 1. Whenever we multiply 1 by another integer, the result is that same integer. For example, we have 1 ⋅ 3 = 3 and 3 ⋅ 1 = 3. As another example 1 ⋅ (– 5) = – 5 and (– 5) ⋅ 1 = – 5. We can summarize the four properties above by saying that (ℤ, ⋅) is a commutative monoid. 10. Multiplication is distributive over addition in ℤ. This means that whenever 𝑘, 𝑚, and 𝑛 are integers, we have 𝑘 ⋅ (𝑚 + 𝑛) = 𝑘 ⋅ 𝑚 + 𝑘 ⋅ 𝑛. For example, 4 ⋅ (2 + 1) = 4 ⋅ 3 = 12 and 4 ⋅ 2 + 4 ⋅ 1 = 8 + 4 = 12. So, 4 ⋅ (2 + 1) = 4 ⋅ 2 + 4 ⋅ 1. As another example, we have – 2 ⋅ ((– 1) + 3) = – 2(2) = – 4 and – 2 ⋅ (– 1) + (– 2) ⋅ 3 = 2 − 6 = – 4. Therefore, we see that – 2 ⋅ ((– 1) + 3) = – 2 ⋅ (– 1) + (– 2) ⋅ 3. Notes: (1) Since the properties listed in 1 through 10 above are satisfied, we say that (ℤ, +, ⋅) is a ring. We will give the formal definition of a ring below. (2) Observe that a ring consists of (i) a set (in this case ℤ), and (ii) two binary operations on the set called addition and multiplication. (3) (ℤ, +) is a commutative group and (ℤ, ⋅) is a commutative monoid. The distributive property is the only property mentioned that requires both addition and multiplication. (4) We see that ℤ is missing one nice property—the inverse property for multiplication. For example, 2 has no multiplicative inverse in ℤ. There is no integer 𝑛 such that 2 ⋅ 𝑛 = 1. So, the linear equation 2𝑛 − 1 = 0 has no solution in ℤ. (5) If we replace ℤ by the set of natural numbers ℕ = {0, 1, 2, … }, then all the properties mentioned above are satisfied except property 5—the inverse property for addition. For example, 1 has no additive inverse in ℕ. There is no natural number 𝑛 such that 𝑛 + 1 = 0. (6) ℤ actually satisfies two distributive properties. Left distributivity says that whenever 𝑘, 𝑚, and 𝑛 are integers, we have 𝑘 ⋅ (𝑚 + 𝑛) = 𝑘 ⋅ 𝑚 + 𝑘 ⋅ 𝑛. Right distributivity says that whenever 𝑘, 𝑚, and 𝑛 are integers, we have (𝑚 + 𝑛) ⋅ 𝑘 = 𝑚 ⋅ 𝑘 + 𝑛 ⋅ 𝑘. Since multiplication is commutative in ℤ, left distributivity and right distributivity are equivalent. (7) Let’s show that left distributivity together with commutativity of multiplication in ℤ implies right distributivity in ℤ. If we assume that we have left distributivity and commutativity of multiplication, then for integers 𝑘, 𝑚, and 𝑛, we have (𝑚 + 𝑛) ⋅ 𝑘 = 𝑘(𝑚 + 𝑛) = 𝑘 ⋅ 𝑚 + 𝑘 ⋅ 𝑛 = 𝑚 ⋅ 𝑘 + 𝑛 ⋅ 𝑘. We are now ready to give the more general definition of a ring. A ring is a triple (𝑅, +, ⋅), where 𝑅 is a set and + and ⋅ are binary operations on 𝑅 satisfying (1) (𝑅, +) is a commutative group. (2) (𝑅, ⋅) is a monoid. (3) Multiplication is distributive over addition in 𝑅. That is, for all 𝑥, 𝑦, 𝑧 ∈ 𝑅, we have 𝑥 ⋅ (𝑦 + 𝑧) = 𝑥 ⋅ 𝑦 + 𝑥 ⋅ 𝑧 and 39 (𝑦 + 𝑧) ⋅ 𝑥 = 𝑦 ⋅ 𝑥 + 𝑧 ⋅ 𝑥. Recall: The symbol ∈ is used for membership in a set. Specifically, the statement 𝑎 ∈ 𝑆 can be read as “𝑎 is a member of the set 𝑆,” or more simply as “𝑎 is in 𝑆.” For example, 2 ∈ ℕ means “2 is in the set of natural numbers,” or more simply, “2 is a natural number.” We will always refer to the operation + as addition and the operation ⋅ as multiplication. We will also adjust our notation accordingly. For example, we will refer to the identity for + as 0, and the additive inverse of an element 𝑥 ∈ 𝑅 as – 𝑥. Also, we will refer to the identity for ⋅ as 1, and the multiplicative 1 inverse of an element 𝑥 ∈ 𝑅 (if it exists) as 𝑥 –1 or 𝑥. Notes: (1) Recall from Lesson 3 that (𝑅, +) a commutative group means the following: • (Closure) For all 𝑥, 𝑦 ∈ 𝑅, 𝑥 + 𝑦 ∈ 𝑅. • (Associativity) For all 𝑥, 𝑦, 𝑧 ∈ 𝑅, (𝑥 + 𝑦) + 𝑧 = 𝑥 + (𝑦 + 𝑧). • (Commutativity) For all 𝑥, 𝑦 ∈ 𝑅, 𝑥 + 𝑦 = 𝑦 + 𝑥. • (Identity) There exists an element 0 ∈ 𝑅 such that for all 𝑥 ∈ 𝑅, 0 + 𝑥 = 𝑥 + 0 = 𝑥. • (Inverse) For each 𝑥 ∈ 𝑅, there is – 𝑥 ∈ 𝑅 such that 𝑥 + (– 𝑥) = (– 𝑥) + 𝑥 = 0. (2) Recall from Lesson 3 that (𝑅, ⋅) a monoid means the following: • (Closure) For all 𝑥, 𝑦 ∈ 𝑅, 𝑥 ⋅ 𝑦 ∈ 𝑅. • (Associativity) For all 𝑥, 𝑦, 𝑧 ∈ 𝑅, (𝑥 ⋅ 𝑦) ⋅ 𝑧 = 𝑥 ⋅ (𝑦 ⋅ 𝑧). • (Identity) There exists an element 1 ∈ 𝑅 such that for all 𝑥 ∈ 𝑅, 1 ⋅ 𝑥 = 𝑥 ⋅ 1 = 𝑥. (3) Although commutativity of multiplication is not required for the definition of a ring, our most important example (the ring of integers) satisfies this condition. When multiplication is commutative in 𝑅, we call the ring a commutative ring. In this case we have the following additional property: • (Commutativity) For all 𝑥, 𝑦 ∈ 𝑅, 𝑥 ⋅ 𝑦 = 𝑦 ⋅ 𝑥. (4) Observe that we have two distributive properties in the definition for a ring. The first property is called left distributivity and the second is called right distributivity. (5) In a commutative ring, left distributivity implies right distributivity and vice versa. In this case, the distributive property simplifies to • (Distributivity) For all 𝑥, 𝑦, 𝑧 ∈ 𝑅, 𝑥 ⋅ (𝑦 + 𝑧) = 𝑥 ⋅ 𝑦 + 𝑥 ⋅ 𝑧 (6) Some authors leave out the multiplicative identity property in the definition of a ring and call such a ring a unital ring or a ring with identity. Since we are mostly concerned with the ring of integers, we will adopt the convention that a ring has a multiplicative identity. If we do not wish to assume that 𝑅 has a multiplicative identity, then we will call the structure “almost a ring” or rng (note the missing “i”). (7) The properties that define a ring are called the ring axioms. In general, an axiom is a statement that is assumed to be true. So, the ring axioms are the statements that are given to be true in all rings. There are many other statements that are true in rings. However, any additional statements need to be proved using the axioms. 40 Example 4.2: 1. (ℤ, +, ⋅) is a commutative ring with additive identity 0 and multiplicative identity 1. The additive inverse of an integer 𝑎 is the integer – 𝑎. This is the ring we will be focusing most of our attention on. See Example 4.1 for more details. 2. (ℕ, +, ⋅) is not a ring because (ℕ, +) is not a group. The only group property that fails is the additive inverse property. For example, the natural number 1 has no additive inverse. That is, 𝑛 + 1 = 0 has no solution in ℕ. Note that (ℕ, ⋅) is a commutative monoid and the distributive property holds in ℕ. Therefore, (ℕ, +, ⋅) misses being a commutative ring by just that one property. (ℕ, +, ⋅) is an example of a structure called a semiring. 𝑎 3. Recall from Example 3.6 (4 and 5) that the set of rational numbers is ℚ = {𝑏  𝑎, 𝑏 ∈ ℤ, 𝑏 ≠ 0} 𝑎 𝑐 and we define addition and multiplication on ℚ by 𝑏 + 𝑑 = 𝑎𝑑+𝑏𝑐 𝑏𝑑 𝑎 𝑐 𝑎𝑐 and 𝑏 ⋅ 𝑑 = 𝑏𝑑. 0 1 (ℚ, +, ⋅) is a commutative ring with additive identity 0 = and multiplicative identity 1 = . 1 1 𝑎 The additive inverse of a rational number 𝑏 is the rational number –𝑎 𝑏 . ℚ has one additional property not required in the definition of a ring. Every nonzero element 𝑎 of ℚ has a multiplicative inverse. The inverse of the nonzero rational number 𝑏 is the rational 𝑏 𝑎 𝑏 𝑎𝑏 𝑎𝑏 1 𝑏 𝑎 𝑏𝑎 𝑎𝑏 1 number 𝑎. This is easy to verify: 𝑏 ⋅ 𝑎 = 𝑏𝑎 = 𝑎𝑏 = 1 = 1 and 𝑎 ⋅ 𝑏 = 𝑎𝑏 = 𝑎𝑏 = 1 = 1. So, (ℚ∗ , ⋅) is a commutative group, where ℚ∗ is the set of nonzero rational numbers. If we replace the condition “(𝑅, ⋅) is a monoid” in the definition of a ring (condition 2) with the condition (𝑅 ∗ , ⋅) is a commutative group, we get a structure called a field. By the remarks in the last paragraph, we see that (ℚ, +, ⋅) is a field. Technical note: The definition of semiring has one additional property: 0 ⋅ 𝑥 = 𝑥 ⋅ 0 = 0. Without the additive inverse property this new property does not follow from the others, and so, it must be listed explicitly. Divisibility An integer 𝑎 is called even if there is another integer 𝑏 such that 𝑎 = 2𝑏. Example 4.3: 1. 6 is even because 6 = 2 ⋅ 3. 2. – 14 is even because – 14 = 2 ⋅ (– 7). 1 3. We can write 1 = 2 ⋅ 2, but this does not show that 1 is even (and as we all know, it is not). In 1 the definition of even, it is very important that 𝑏 is an integer. The problem here is that 2 is not an integer, and so, it cannot be used as a value for 𝑏 in the definition of even. We define the sum of integers 𝑎 and 𝑏 to be 𝑎 + 𝑏. We define the product of 𝑎 and 𝑏 to be 𝑎 ⋅ 𝑏. Theorem 4.1: The sum of two even integers is even. 41 Strategy: Before writing the proof, let’s think about our strategy. We need to start with two arbitrary but specific even integers. Let’s call them 𝑚 and 𝑛. Notice that we need to give them different names because there is no reason that they need to have the same value. When we try to add 𝑚 and 𝑛, we get 𝑚 + 𝑛. Hmmm…I see no reason yet why the expression 𝑚 + 𝑛 should represent an even integer. The problem is that we haven’t yet used the definition of even. If we invoke the definition, we get integers 𝑗 and 𝑘 such that 𝑚 = 2𝑗 and 𝑛 = 2𝑘. Now, when we add 𝑚 and 𝑛, we get 𝑚 + 𝑛 = 2𝑗 + 2𝑘. Is it clear that 2𝑗 + 2𝑘 represents an even integer? Nope…not yet. To be even, our final expression needs to have the form 2𝑏, where 𝑏 is an integer. Here is where we use the fact that (ℤ, +, ⋅) is a ring. Specifically, we use the distributive property to rewrite 2𝑗 + 2𝑘 as 2(𝑗 + 𝑘). It looks like we’ve done it. We just need to verify one more thing: is 𝑗 + 𝑘 an integer? Once again, we can use the fact that (ℤ, +, ⋅) is a ring to verify this. Specifically, we use the fact that + is a binary operation on ℤ. I think we’re now ready to write the proof. Proof of Theorem 4.1: Let 𝑚 and 𝑛 be even integers. Then there are integers 𝑗 and 𝑘 such that 𝑚 = 2𝑗 and 𝑛 = 2𝑘. So, 𝑚 + 𝑛 = 2𝑗 + 2𝑘 = 2(𝑗 + 𝑘) because multiplication is distributive over addition in ℤ. Since ℤ is closed under addition, 𝑗 + 𝑘 ∈ ℤ. Therefore, 𝑚 + 𝑛 is even. □ The property of being even is a special case of the more general notion of divisibility. An integer 𝑎 is divisible by an integer 𝑘, written 𝑘𝑎, if there is another integer 𝑏 such that 𝑎 = 𝑘𝑏. We also say that 𝑘 is a factor of 𝑎, 𝑘 is a divisor of 𝑎, 𝑘 divides 𝑎, or 𝑎 is a multiple of 𝑘. Example 4.4: 1. Note that being divisible by 2 is the same as being even. 2. 18 is divisible by 3 because 18 = 3 ⋅ 6. 3. – 56 is divisible by 7 because – 56 = 7 ⋅ (– 8). Theorem 4.2: The product of two integers that are each divisible by 𝑘 is also divisible by 𝑘. Proof: Let 𝑚 and 𝑛 be integers that are divisible by 𝑘. Then there are integers 𝑏 and 𝑐 such that 𝑚 = 𝑘𝑏 and 𝑛 = 𝑘𝑐. So, 𝑚 ⋅ 𝑛 = (𝑘 ⋅ 𝑏) ⋅ (𝑘 ⋅ 𝑐) = 𝑘 ⋅ (𝑏 ⋅ (𝑘 ⋅ 𝑐)) because multiplication is associative in ℤ. Since ℤ is closed under multiplication, 𝑏 ⋅ (𝑘 ⋅ 𝑐) ∈ ℤ. Thus, 𝑚 ⋅ 𝑛 is divisible by 𝑘. □ Notes: (1) If you’re confused about how associativity was used here, it might help to make the substitution 𝑢 = (𝑘 ⋅ 𝑐). Then we have (𝑘 ⋅ 𝑏) ⋅ (𝑘 ⋅ 𝑐) = (𝑘 ⋅ 𝑏) ⋅ 𝑢 = 𝑘 ⋅ (𝑏 ⋅ 𝑢) = 𝑘(𝑏 ⋅ (𝑘 ⋅ 𝑐)). 42 (2) Although it may seem tempting to simplify 𝑘 ⋅ (𝑏 ⋅ (𝑘 ⋅ 𝑐)) further, it is unnecessary. The definition of divisibility by 𝑘 requires us only to generate an expression of the form 𝑘 times some integer, and that’s what we have done. (3) If the generality of the proof confuses you, try replacing 𝑘 by a specific integer. For example, if we let 𝑘 = 2, we have 𝑚 = 2𝑏, 𝑛 = 2𝑐, and therefore 𝑚 ⋅ 𝑛 = (2𝑏) ⋅ (2𝑐) = 2(𝑏 ⋅ (2𝑐)). Is it clear that this final expression is even (divisible by 2)? (4) It’s worth noting that the product 𝑚 ⋅ 𝑛 is actually divisible by 𝑘 2 . Indeed, we have 𝑚 ⋅ 𝑛 = 𝑘 ⋅ (𝑏 ⋅ (𝑘 ⋅ 𝑐)) = 𝑘 ⋅ ((𝑏 ⋅ 𝑘) ⋅ 𝑐) = 𝑘 ⋅ ((𝑘 ⋅ 𝑏) ⋅ 𝑐) = 𝑘 ⋅ (𝑘 ⋅ (𝑏 ⋅ 𝑐)) = 𝑘 2 (𝑏 ⋅ 𝑐) Induction The Well Ordering Principle says that every nonempty subset of natural numbers has a least element. For example, the least element of ℕ itself is 0. Theorem 4.3 (The Principle of Mathematical Induction): Let 𝑆 be a set of natural numbers such that (i) 0 ∈ 𝑆 and (ii) for all 𝑘 ∈ ℕ, 𝑘 ∈ 𝑆 → 𝑘 + 1 ∈ 𝑆. Then 𝑆 = ℕ. Notes: (1) The Principle of Mathematical Induction works like a chain reaction. We know that 0 ∈ 𝑆 (this is condition (i)). Substituting 0 in for 𝑘 in the expression “𝑘 ∈ 𝑆 → 𝑘 + 1 ∈ 𝑆” (condition (ii)) gives us 0 ∈ 𝑆 → 1 ∈ 𝑆. So, we have that 0 is in the set 𝑆, and “if 0 is in the set 𝑆, then 1 is in the set 𝑆.” So, 1 ∈ 𝑆 must also be true. (2) In terms of Lesson 1 on Sentential Logic, if we let 𝑝 be the statement 0 ∈ 𝑆 and 𝑞 the statement 1 ∈ 𝑆, then we are given that 𝑝 ∧ (𝑝 → 𝑞) is true. Observe that the only way that this statement can be true is if 𝑞 is also true. Indeed, we must have both 𝑝 ≡ T and 𝑝 → 𝑞 ≡ T. If 𝑞 were false, then we would have 𝑝 → 𝑞 ≡ T → F ≡ F. So, we must have 𝑞 ≡ T. (3) Now that we showed 1 ∈ 𝑆 is true (from Note 1 above), we can substitute 1 for 𝑘 in the expression “𝑘 ∈ 𝑆 → 𝑘 + 1 ∈ 𝑆” (condition (ii)) to get 1 ∈ 𝑆 → 2 ∈ 𝑆. So, we have 1 ∈ 𝑆 ∧ (1 ∈ 𝑆 → 2 ∈ 𝑆) is true. So, 2 ∈ 𝑆 must also be true. (4) In general, we get the following chain reaction: 0∈𝑆→1∈𝑆→2∈𝑆→3∈𝑆→⋯ I hope that the “argument” presented in Notes 1 through 4 above convinces you that the Principle of Mathematical Induction should be true. Now let’s give a proof using the Well Ordering Principle. Proofs involving the Well Ordering Principle are generally done by contradiction. Proof of Theorem 4.3: Let 𝑆 be a set of natural numbers such that 0 ∈ 𝑆 (condition (i)), and such that whenever 𝑘 ∈ 𝑆, 𝑘 + 1 ∈ 𝑆 (condition (ii)). Assume toward contradiction that 𝑆 ≠ ℕ. Let 𝐴 = {𝑘 ∈ ℕ  𝑘 ∉ 𝑆} (so, 𝐴 is the set of natural numbers not in 𝑆). Since 𝑆 ≠ ℕ, 𝐴 is nonempty. So, by the Well Ordering Principle, 𝐴 has a least element, let’s call it 𝑎. 𝑎 ≠ 0 because 0 ∈ 𝑆 and 𝑎 ∉ 𝑆. So, 𝑎 − 1 ∈ ℕ. Letting 𝑘 = 𝑎 − 1, we have 𝑎 − 1 ∈ 𝑆 → 𝑘 ∈ 𝑆 → 𝑘 + 1 ∈ 𝑆 → (𝑎 − 1) + 1 ∈ 𝑆 → 𝑎 ∈ 𝑆. But 𝑎 ∈ 𝐴, which means that 𝑎 ∉ 𝑆. This is a contradiction, and so, 𝑆 = ℕ. □ 43 Note: The proof given here is a proof by contradiction. A proof by contradiction works as follows: 1. We assume the negation of what we are trying to prove. 2. We use a logically valid argument to derive a statement which is false. 3. Since the argument was logically valid, the only possible error is our original assumption. Therefore, the negation of our original assumption must be true. In this problem we are trying to prove that 𝑆 = ℕ. The negation of this statement is that 𝑆 ≠ ℕ, and so that is what we assume. We then define a set 𝐴 which contains elements of ℕ that are not in 𝑆. In reality, this set is empty (because the conclusion of the theorem is 𝑆 = ℕ). However, our (wrong!) assumption that 𝑆 ≠ ℕ tells us that this set 𝐴 actually has something in it. Saying that 𝐴 has something in it is an example of a false statement that was derived from a logically valid argument. This false statement occurred not because of an error in our logic, but because we started with an incorrect assumption (𝑆 ≠ ℕ). The Well Ordering Principle then allows us to pick out the least element of this set 𝐴. Note that we can do this because 𝐴 is a subset of ℕ. This wouldn’t work if we knew only that 𝐴 was a subset of ℤ, as ℤ does not satisfy the Well Ordering Principle (for example, ℤ itself has no least element). Again, although the argument that 𝐴 has a least element is logically valid, 𝐴 does not actually have any elements at all. We are working from the (wrong!) assumption that 𝑆 ≠ ℕ. Once we have our hands on this least element 𝑎, we can get our contradiction. What can this least element 𝑎 be? Well 𝑎 was chosen to not be in 𝑆, so 𝑎 cannot be 0 (because 0 is in 𝑆). Also, we know that 𝑎 − 1 ∈ 𝑆 (because 𝑎 is the least element not in 𝑆). But condition (ii) then forces 𝑎 to be in 𝑆 (because 𝑎 = (𝑎 − 1) + 1). So, we wind up with 𝑎 ∈ 𝑆, contradicting the fact that 𝑎 is the least element not in 𝑆. The Principle of Mathematical Induction is often written in the following way: (⋆) Let 𝑃(𝑛) be a statement and suppose that (i) 𝑃(0) is true and (ii) for all 𝑘 ∈ ℕ, 𝑃(𝑘) → 𝑃(𝑘 + 1). Then 𝑃(𝑛) is true for all 𝑛 ∈ ℕ. In Problem 9 below, you will be asked to show that statement (⋆) is equivalent to Theorem 4.3. There are essentially two steps involved in a proof by mathematical induction. The first step is to prove that 𝑃(0) is true (this is called the base case), and the second step is to assume that 𝑃(𝑘) is true, and use this to show that 𝑃(𝑘 + 1) is true (this is called the inductive step). While doing the inductive step, the statement “𝑃(𝑘) is true” is often referred to as the inductive hypothesis. Subtraction in ℤ: For 𝑥, 𝑦 ∈ ℤ, we define the difference 𝑥 − 𝑦 to be equal to the sum 𝑥 + (– 𝑦). For example, 𝑛2 − 𝑛 = 𝑛2 + (– 𝑛) (where 𝑛2 is defined to be the product 𝑛 ⋅ 𝑛). Example 4.5: Let’s use the Principle of Mathematical Induction to prove that for all natural numbers 𝑛, 𝑛2 − 𝑛 is even. 44 Base Case (𝑘 = 0): 02 − 0 = 0 = 2 ⋅ 0. So, 02 − 0 is even. Inductive Step: Let 𝑘 ∈ ℕ and assume that 𝑘 2 − 𝑘 is even. Then 𝑘 2 − 𝑘 = 2𝑏 for some integer 𝑏. Now, (𝑘 + 1)2 − (𝑘 + 1) = (𝑘 + 1)[(𝑘 + 1) − 1] = (𝑘 + 1)[𝑘 + (1 − 1)] = (𝑘 + 1)(𝑘 + 0) = (𝑘 + 1) ⋅ 𝑘 = 𝑘 2 + 𝑘 = (𝑘 2 − 𝑘) + 2𝑘 = 2𝑏 + 2𝑘 = 2(𝑏 + 𝑘). Here we used the fact that (ℤ, +, ⋅) is a ring. Since ℤ is closed under addition, 𝑏 + 𝑘 ∈ ℤ. Therefore, (𝑘 + 1)2 − (𝑘 + 1) is even. By the Principle of Mathematical Induction, 𝑛2 − 𝑛 is even for all 𝑛 ∈ ℕ. □ Notes: (1) Instead of listing every property that we used at each step, we simply stated that all the computations we made were allowed because (ℤ, +, ⋅) is a ring. We will discuss the property we used at each step in the notes below. (2) We first used left distributivity to rewrite (𝑘 + 1)2 − (𝑘 + 1) as (𝑘 + 1)[(𝑘 + 1) − 1]. If you have trouble seeing this, try working backwards, and making the substitutions 𝑥 = (𝑘 + 1), 𝑦 = (𝑘 + 1), and 𝑧 = – 1. We then have (𝑘 + 1)[(𝑘 + 1) − 1] = (𝑘 + 1)[(𝑘 + 1) + (– 1)] = 𝑥(𝑦 + 𝑧) = 𝑥𝑦 + 𝑥𝑧 = (𝑘 + 1)(𝑘 + 1) + (𝑘 + 1)(– 1) = (𝑘 + 1)2 + (– 1)(𝑘 + 1) = (𝑘 + 1)2 − (𝑘 + 1). Notice how we also used commutativity of multiplication for the second to last equality. (3) For the second algebraic step, we used associativity of addition to write (𝑘 + 1) − 1 = (𝑘 + 1) + (– 1) = 𝑘 + (1 + (– 1)) = 𝑘 + (1 − 1). (4) For the third algebraic step, we used the inverse property for addition to write 1 − 1 = 1 + (– 1) = 0. (5) For the fourth algebraic step, we used the additive identity property to write 𝑘 + 0 = 𝑘. (6) For the fifth algebraic step, we used right distributivity and the multiplicative identity property to write (𝑘 + 1) ⋅ 𝑘 = 𝑘 ⋅ 𝑘 + 1 ⋅ 𝑘 = 𝑘 2 + 𝑘. (7) For the sixth algebraic step, we used what I call the “Standard Advanced Calculus Trick.” I sometimes abbreviate this as SACT. The trick is simple. If you need something to appear, just put it in. Then correct it by performing the opposite of what you just did. In this case, in order to use the inductive hypothesis, we need 𝑘 2 − 𝑘 to appear, but unfortunately, we have 𝑘 2 + 𝑘 instead. Using SACT, I do the following: • I simply put in what I need (and exactly where I need it): 𝑘 2 − 𝒌 + 𝑘. • Now, I undo the damage by performing the reverse operation: 𝑘 2 − 𝑘 + 𝒌 + 𝑘. • Finally, I leave the part I need as is, and simplify the rest: (𝑘 2 − 𝑘) + 2𝑘 45 (8) For the seventh step, we simply replaced 𝑘 2 − 𝑘 by 2𝑏. We established that these two quantities were equal in the second sentence of the inductive step. (9) For the last step, we used left distributivity to write 2𝑏 + 2𝑘 as 2(𝑏 + 𝑘). Sometimes a statement involving the natural numbers may be false for 0, but true from some natural number on. In this case, we can still use induction. We just need to adjust the base case. Example 4.6: Let’s use the Principle of Mathematical Induction to prove that 𝑛2 > 2𝑛 + 1 for all natural numbers 𝑛 ≥ 3. Base Case (𝑘 = 3): 32 = 9 and 2 ⋅ 3 + 1 = 6 + 1 = 7. So, 32 > 2 ⋅ 3 + 1. Inductive Step: Let 𝑘 ∈ ℕ with 𝑘 ≥ 3 and assume that 𝑘 2 > 2𝑘 + 1. Then we have (𝑘 + 1)2 = (𝑘 + 1)(𝑘 + 1) = (𝑘 + 1)𝑘 + (𝑘 + 1)(1) = 𝑘 2 + 𝑘 + 𝑘 + 1 > (2𝑘 + 1) + 𝑘 + 𝑘 + 1 = 2𝑘 + 2 + 𝑘 + 𝑘 = 2(𝑘 + 1) + 𝑘 + 𝑘 ≥ 2(𝑘 + 1) + 1 (because 𝑘 + 𝑘 ≥ 3 + 3 = 6 ≥ 1). By the Principle of Mathematical Induction, 𝑛2 > 2𝑛 + 1 for all 𝑛 ∈ ℕ with 𝑛 ≥ 3. □ Notes: (1) If we have a sequence of equations and inequalities of the form =, ≥, and > (with at least one inequality symbol appearing), beginning with 𝑎 and ending with 𝑏, then the final result is 𝑎 > 𝑏 if > appears at least once and 𝑎 ≥ 𝑏 otherwise. For example, if 𝑎 = 𝑗 = ℎ = 𝑚 > 𝑛 = 𝑝 = 𝑞 ≥ 𝑏, then 𝑎 > 𝑏. The sequence that appears in the solution above has this form. (𝑘 + 1)2 = (𝑘 + 1)(𝑘 + 1) = (𝑘 + 1)𝑘 + (𝑘 + 1)(1) = 𝑘 2 + 𝑘 + 𝑘 + 1 > (2𝑘 + 1) + 𝑘 + 𝑘 + 1 = 2𝑘 + 2 + 𝑘 + 𝑘 = 2(𝑘 + 1) + 𝑘 + 𝑘 ≥ 2(𝑘 + 1) + 1 2 (2) By definition, 𝑥 = 𝑥 ⋅ 𝑥. We used this in the first equality in the inductive step to write (𝑘 + 1)2 as (𝑘 + 1)(𝑘 + 1). (3) For the second equality in the inductive step, we used left distributivity to write (𝑘 + 1)(𝑘 + 1) as (𝑘 + 1)𝑘 + (𝑘 + 1)(1). If you have trouble seeing this, you can make a substitution like we did in Note 2 following Example 4.5. (4) For the third equality in the inductive step, we used right distributivity to write (𝑘 + 1)𝑘 as 𝑘 ⋅ 𝑘 + 1 ⋅ 𝑘 = 𝑘 2 + 𝑘. We also used the multiplicative identity property to write (𝑘 + 1)(1) = 𝑘 + 1. (5) Associativity of addition is being used when we write the expression 𝑘 2 + 𝑘 + 𝑘 + 1. Notice the lack of parentheses. Technically speaking, we should have written (𝑘 2 + 𝑘) + (𝑘 + 1) and then taken another step to rewrite this as 𝑘 2 + (𝑘 + (𝑘 + 1)). However, since we have associativity, we can simply drop all those parentheses. (6) The inequality “𝑘 2 + 𝑘 + 𝑘 + 1 > (2𝑘 + 1) + 𝑘 + 𝑘 + 1” was attained by using the inductive hypothesis “𝑘 2 > 2𝑘 + 1.” 46 (7) The dedicated reader should verify that the remaining equalities in the proof are valid by determining which ring properties were used at each step. Example 4.7: Let’s use the Principle of Mathematical Induction to prove that for every natural number 𝑛, there is a natural number 𝑗 such that 𝑛 = 2𝑗 or 𝑛 = 2𝑗 + 1. Base Case (𝑘 = 0): 0 = 2 ⋅ 0 Inductive Step: Suppose that 𝑘 ∈ ℕ and there is 𝑗 ∈ ℕ such that 𝑘 = 2𝑗 or 𝑘 = 2𝑗 + 1. If 𝑘 = 2𝑗, then 𝑘 + 1 = 2𝑗 + 1. If 𝑘 = 2𝑗 + 1, then 𝑘 + 1 = (2𝑗 + 1) + 1 = 2𝑗 + (1 + 1) = 2𝑗 + 2 = 2(𝑗 + 1). Here we used the fact that (ℕ, +, ⋅) is a semiring (more specifically, we used associativity of addition in ℕ and distributivity of multiplication over addition in ℕ). Since ℕ is closed under addition, 𝑗 + 1 ∈ ℕ. By the Principle of Mathematical Induction, for every natural number 𝑛, there is a natural number 𝑗 such that 𝑛 = 2𝑗 or 𝑛 = 2𝑗 + 1. □ Notes: (1) We can now prove the analogous result for the integers: “For every integer 𝑛, there is an integer 𝑗 such that 𝑛 = 2𝑗 or 𝑛 = 2𝑗 + 1.” We already proved the result for 𝑛 ≥ 0. If 𝑛 < 0, then – 𝑛 > 0, and so there is a natural number 𝑗 such that – 𝑛 = 2𝑗 or – 𝑛 = 2𝑗 + 1. If – 𝑛 = 2𝑗, then 𝑛 = 2(– 𝑗) (and since 𝑗 ∈ ℕ, – 𝑗 ∈ ℤ). If – 𝑛 = 2𝑗 + 1, then 𝑛 = – (2𝑗 + 1) = – 2𝑗 − 1 = – 2𝑗 − 1 − 1 + 1 (SACT) = – 2𝑗 − 2 + 1 = 2(– 𝑗 − 1) + 1. Here we used the fact that (ℤ, +, ⋅) is a ring. Since ℤ is closed under addition, – 𝑗 − 1 = – 𝑗 + (– 1) ∈ ℤ. (2) If there is an integer 𝑗 such that 𝑛 = 2𝑗, we say that 𝑛 is even. If there is an integer 𝑗 such that 𝑛 = 2𝑗 + 1, we say that 𝑛 is odd. (3) An integer 𝒏 cannot be both even and odd. Indeed, if 𝑛 = 2𝑗 and 𝑛 = 2𝑘 + 1, then 2𝑗 = 2𝑘 + 1. So, we have 2(𝑗 − 𝑘) = 2𝑗 − 2𝑘 = (2𝑘 + 1) − 2𝑘 = 2𝑘 + (1 − 2𝑘) = 2𝑘 + (– 2𝑘 + 1) = (2𝑘 − 2𝑘) + 1 = 0 + 1 = 1. So, 2(𝑗 − 𝑘) = 1. But 2 does not have a multiplicative inverse in ℤ, and so, this is a contradiction. Theorem 4.4: The product of two odd integers is odd. Proof: Let 𝑚 and 𝑛 be odd integers. Then there are integers 𝑗 and 𝑘 such that 𝑚 = 2𝑗 + 1 and 𝑛 = 2𝑘 + 1. So, 𝑚 ⋅ 𝑛 = (2𝑗 + 1) ⋅ (2𝑘 + 1) = (2𝑗 + 1)(2𝑘) + (2𝑗 + 1)(1) = (2𝑘)(2𝑗 + 1) + (2𝑗 + 1) = ((2𝑘)(2𝑗) + 2𝑘) + (2𝑗 + 1) = (2(𝑘(2𝑗)) + 2𝑘) + (2𝑗 + 1) = 2(𝑘(2𝑗) + 𝑘) + (2𝑗 + 1) = (2(𝑘(2𝑗) + 𝑘) + 2𝑗) + 1 = 2((𝑘(2𝑗) + 𝑘) + 𝑗) + 1. Here we used the fact that (ℤ, +, ⋅) is a ring. (Which properties did we use?) Since ℤ is closed under addition and multiplication, we have (𝑘(2𝑗) + 𝑘) + 𝑗 ∈ ℤ. Therefore, 𝑚𝑛 is odd. □ 47 Problem Set 4 Full solutions to these problems are available for free download here: www.SATPrepGet800.com/PMFBXSG LEVEL 1 1. The addition and multiplication tables below are defined on the set 𝑆 = {0, 1}. Show that (𝑆, +, ⋅) does not define a ring. + 0 1 0 0 1 1 1 0 ⋅ 0 1 0 1 0 1 0 1 2. Let 𝑆 = {0, 1} and define addition (+) and multiplication (⋅) so that (𝑆, +, ⋅) is a ring. Assume that 0 is the additive identity in 𝑆 and 1 is the multiplicative identity in 𝑆. Draw the tables for addition and multiplication and verify that with these tables, (𝑆, +, ⋅) is a ring. LEVEL 2 3. Use the Principle of Mathematical Induction to prove the following: (i) 2𝑛 > 𝑛 for all natural numbers 𝑛 ≥ 1. (ii) 0 + 1 + 2 + ⋯+ 𝑛 = 𝑛(𝑛+1) 2 for all natural numbers. (iii) 𝑛! > 2𝑛 for all natural numbers 𝑛 ≥ 4 (where 𝑛! = 1 ⋅ 2 ⋯ 𝑛 for all natural numbers 𝑛 ≥ 1). (iv) 2𝑛 ≥ 𝑛2 for all natural numbers 𝑛 ≥ 4. 4. Show that the sum of three integers that are divisible by 5 is divisible by 5. LEVEL 3 5. Prove that if 𝑎, 𝑏, 𝑐 ∈ ℤ with 𝑎𝑏 and 𝑏𝑐, then 𝑎𝑐. 6. Prove that 𝑛3 − 𝑛 is divisible by 3 for all natural numbers 𝑛. LEVEL 4 7. Prove that if 𝑎, 𝑏, 𝑐, 𝑑, 𝑒 ∈ ℤ with 𝑎𝑏 and 𝑎𝑐, then 𝑎(𝑑𝑏 + 𝑒𝑐). 8. Prove that 3𝑛 − 1 is even for all natural numbers 𝑛. 48 9. Show that Theorem 4.3 (the Principle of Mathematical Induction) is equivalent to the following statement: (⋆) Let 𝑃(𝑛) be a statement and suppose that (i) 𝑃(0) is true and (ii) for all 𝑘 ∈ ℕ, 𝑃(𝑘) → 𝑃(𝑘 + 1). Then 𝑃(𝑛) is true for all 𝑛 ∈ ℕ. LEVEL 5 10. The Principle of Strong Induction is the following statement: (⋆⋆) Let 𝑃(𝑛) be a statement and suppose that (i) 𝑃(0) is true and (ii) for all 𝑘 ∈ ℕ, ∀𝑗 ≤ 𝑘 (𝑃(𝑗)) → 𝑃(𝑘 + 1). Then 𝑃(𝑛) is true for all 𝑛 ∈ ℕ. Use the Principle of Mathematical Induction to prove the Principle of Strong Induction. 11. Show that (ℚ, +, ⋅) is a field. 12. Use the Principle of Mathematical Induction to prove that for every 𝑛 ∈ ℕ, if 𝑆 is a set with 𝑆 = 𝑛, then 𝑆 has 2𝑛 subsets. (Hint: Use Problem 14 from Lesson 2.) 49 LESSON 5 – REAL ANALYSIS THE COMPLETE ORDERED FIELD OF REALS Fields Let’s review the number systems we have discussed so far. The set ℕ = {0, 1, 2, 3, … } is the set of natural numbers and the structure (ℕ, +, ⋅) is a semiring. The set ℤ = {… , – 3, – 2, – 1, 0, 1, 2, 3, … } is the set of integers and the structure (ℤ, +, ⋅) is a ring. 𝑎 The set ℚ = {𝑏 𝑎 ∈ ℤ, 𝑏 ∈ ℤ∗ } is the set of rational numbers and the structure (ℚ, +, ⋅) is a field. And now let’s formally introduce the notion of a field (and we will review the definitions of ring and semiring in the notes below). A field is a triple (𝐹, +, ⋅), where 𝐹 is a set and + and ⋅ are binary operations on 𝐹 satisfying (1) (𝐹, +) is a commutative group. (2) (𝐹 ∗ , ⋅) is a commutative group. (3) ⋅ is distributive over + in 𝐹. That is, for all 𝑥, 𝑦, 𝑧 ∈ 𝐹, we have 𝑥 ⋅ (𝑦 + 𝑧) = 𝑥 ⋅ 𝑦 + 𝑥 ⋅ 𝑧 and (𝑦 + 𝑧) ⋅ 𝑥 = 𝑦 ⋅ 𝑥 + 𝑧 ⋅ 𝑥. (4) 0 ≠ 1. We will refer to the operation + as addition, the operation ⋅ as multiplication, the additive identity as 0, the multiplicative identity as 1, the additive inverse of an element 𝑥 ∈ 𝐹 as – 𝑥, and the multiplicative inverse of an element 𝑥 ∈ 𝐹 as 𝑥 −1. We will often abbreviate 𝑥 ⋅ 𝑦 as 𝑥𝑦. Notes: (1) Recall from Lesson 3 that (𝐹, +) a commutative group means the following: • (Closure) For all 𝑥, 𝑦 ∈ 𝐹, 𝑥 + 𝑦 ∈ 𝐹. • (Associativity) For all 𝑥, 𝑦, 𝑧 ∈ 𝐹, (𝑥 + 𝑦) + 𝑧 = 𝑥 + (𝑦 + 𝑧). • (Commutativity) For all 𝑥, 𝑦 ∈ 𝐹, 𝑥 + 𝑦 = 𝑦 + 𝑥. • (Identity) There exists an element 0 ∈ 𝐹 such that for all 𝑥 ∈ 𝐹, 0 + 𝑥 = 𝑥 + 0 = 𝑥. • (Inverse) For each 𝑥 ∈ 𝐹, there is – 𝑥 ∈ 𝐹 such that 𝑥 + (– 𝑥) = (– 𝑥) + 𝑥 = 0. (2) Similarly, (𝐹 ∗ , ⋅) a commutative group means the following: • (Closure) For all 𝑥, 𝑦 ∈ 𝐹 ∗ , 𝑥𝑦 ∈ 𝐹 ∗ . • (Associativity) For all 𝑥, 𝑦, 𝑧 ∈ 𝐹 ∗ , (𝑥𝑦)𝑧 = 𝑥(𝑦𝑧). • (Commutativity) For all 𝑥, 𝑦 ∈ 𝐹 ∗ , 𝑥𝑦 = 𝑦𝑥. • (Identity) There exists an element 1 ∈ 𝐹 ∗ such that for all 𝑥 ∈ 𝐹 ∗ , 1𝑥 = 𝑥 ⋅ 1 = 𝑥. • (Inverse) For each 𝑥 ∈ 𝐹 ∗ , there is 𝑥 −1 ∈ 𝐹 ∗ such that 𝑥𝑥 −1 = 𝑥 −1 𝑥 = 1. 50 (3) Recall that 𝐹 ∗ is the set of nonzero elements of 𝐹. We can write 𝐹 ∗ = {𝑥 ∈ 𝐹  𝑥 ≠ 0} (pronounced “the set of 𝑥 in 𝐹 such that 𝑥 is not equal to 0”) or 𝐹 ∗ = 𝐹 ∖ {0} (pronounced “𝐹 with 0 removed”). (4) The properties that define a field are called the field axioms. These are the statements that are given to be true in all fields. There are many other statements that are true in fields. However, any additional statements need to be proved using the axioms. (5) If we replace the condition that “(𝐹 ∗ , ⋅) is a commutative group” by “(𝐹, ⋅) is a monoid,” then the resulting structure is called a ring. The most wellknown example of a ring is ℤ, the ring of integers. See Lesson 4 for details about ℤ and rings in general. We also do not require 0 and 1 to be distinct in the definition of a ring. If 0 = 1, we get the zero ring, which consists of just one element, namely 0 (Why?). The operations of addition and multiplication are defined by 0 + 0 = 0 and 0 ⋅ 0 = 0. The reader may want to verify that the zero ring is in fact a ring. The main difference between a ring and a field is that in a ring, there can be nonzero elements that do not have multiplicative inverses. For example, in ℤ, 2 has no multiplicative inverse. So, the equation 2𝑥 = 1 has no solution. (6) If we also replace “(𝐹, +) is a commutative group” by “(𝐹, +) is a commutative monoid,” then the resulting structure is a semiring. The most wellknown example of a semiring is ℕ, the semiring of natural numbers. The main difference between a semiring and a ring is that in a semiring, there can be elements that do not have additive inverses. For example, in ℕ, 1 has no additive inverse. Thus, the equation 𝑥 + 1 = 0 has no solution. Technical note: For a semiring, we include one additional axiom: For all 𝑥 ∈ 𝐹, 0 ⋅ 𝑥 = 𝑥 ⋅ 0 = 0. (7) Every field is a commutative ring. Although this is not too hard to show (you will be asked to show this in Problem 6 below), it is worth observing that this is not completely obvious. For example, if (𝐹, +, ⋅) is a ring, then since (𝐹, ⋅) is a monoid with identity 1, it follows that 1 ⋅ 0 = 0 ⋅ 1 = 0. However, in the definition of a field given above, this property of 0 is not given as an axiom. We are given that (𝐹 ∗ , ⋅) is a commutative group, and so, it follows that 1 is an identity for 𝐹 ∗ . But 0 ∉ 𝐹 ∗ , and so, 1 ⋅ 0 = 0 ⋅ 1 = 0 needs to be proved. Similarly, in the definition of a field given above, 0 is excluded from associativity and commutativity. These need to be checked. (8) You were asked to verify that (ℚ, +, ⋅) is a field in Problems 9 and 11 from Lesson 3 and Problem 11 from Lesson 4. 𝑎 Subtraction and Division: If 𝑎, 𝑏 ∈ 𝐹, we define 𝑎 − 𝑏 = 𝑎 + (– 𝑏) and for 𝑏 ≠ 0, 𝑏 = 𝑎𝑏 −1 . 51 Ordered Rings and Fields We say that a ring (𝑅, +, ⋅) is ordered if there is a nonempty subset 𝑃 of 𝑅, called the set of positive elements of 𝑅, satisfying the following three properties: (1) If 𝑎, 𝑏 ∈ 𝑃, then 𝑎 + 𝑏 ∈ 𝑃. (2) If 𝑎, 𝑏 ∈ 𝑃, then 𝑎𝑏 ∈ 𝑃. (3) If 𝑎 ∈ 𝑅, then exactly one of the following holds: 𝑎 ∈ 𝑃, 𝑎 = 0, or – 𝑎 ∈ 𝑃. Note: If 𝑎 ∈ 𝑃, we say that 𝑎 is positive and if – 𝑎 ∈ 𝑃, we say that 𝑎 is negative. Also, we define 𝑅 + = 𝑃 and 𝑅 – = {𝑎 ∈ 𝑅  – 𝑎 ∈ 𝑃}. Example 5.1: Let 𝑅 = ℤ and let 𝑃ℤ = {1, 2, 3, … }. It’s easy to see that properties (1), (2), and (3) are satisfied. It follows that (ℤ, +, ⋅) is an ordered ring. Theorem 5.1: (ℚ, +, ⋅) is an ordered field. Note: The proof of this result is a bit technical, but I am including it for completeness. The student just starting out in pure mathematics can feel free to just accept this result and skip the proof. 𝑚 Recall: (1) Rational numbers have the form 𝑛 , where 𝑚 and 𝑛 are integers and 𝑛 ≠ 0. (2) Two rational numbers 𝑚 (3) For rational numbers 𝑚 𝑛 𝑝 ⋅𝑞 = 𝑚𝑝 𝑛𝑞 𝑛 𝑝 and 𝑞 are equal if and only if 𝑚𝑞 = 𝑛𝑝. 𝑚 𝑛 𝑝 𝑚 𝑞 𝑛 and , we define addition and multiplication by 𝑝 𝑚𝑞+𝑛𝑝 𝑞 𝑛𝑞 + = and . (4) The additive inverse of 𝑚 𝑛 𝑚 is – 𝑛 = –𝑚 𝑛 . Analysis: Before writing out the proof in detail, let’s think about how we would go about it. First of all, we already know from Problem 11 in Lesson 4 that (ℚ, +, ⋅) is a field. So, we need only show that it is ordered. To do this, we need to come up with a set 𝑃 of positive elements from ℚ. The natural choice would be to take the set of quotients whose numerator (number on the top) and denominator (number on the bottom) are both positive integers. In other words, we will let 𝑃ℚ be the set of all the rational 𝑚 numbers of the form 𝑛 , where 𝑚 and 𝑛 are both elements of 𝑃ℤ (as defined in Example 5.1 above). –𝑚 𝑚 Since –𝑛 = 𝑛 (because (– 𝑚)𝑛 = (– 𝑛)𝑚), we must automatically be including all quotients whose numerator and denominator are both negative integers as well. With this definition of 𝑃ℚ , it is straightforward to verify properties (1) and (2) of an ordered field. To verify property (3), we need to check three things. (i) For any rational number 𝑎, 𝑎 is positive, zero, or negative (𝑎 ∈ 𝑃ℚ , 𝑎 = 0, or – 𝑎 ∈ 𝑃ℚ ). We will show this by assuming 𝑎 ∉ 𝑃ℚ and 𝑎 ≠ 0, and then proving that we must have – 𝑎 ∈ 𝑃ℚ . 52 (ii) For any rational number 𝑎, 𝑎 cannot be both positive and negative. We will show this by assuming 𝑎 ∈ 𝑃ℚ and – 𝑎 ∈ 𝑃ℚ , and then deriving a contradiction. (iii) A positive or negative rational number is not zero, and a rational number that is zero is not positive or negative. This is straightforward to check. Let’s write out the details. Proof of Theorem 5.1: By Problem 11 from Lesson 4, (ℚ, +, ⋅) is a field. Let 𝐹 = ℚ and let 𝑃ℚ = {𝑥 ∈ ℚ  𝑥 = with 𝑎 = 𝑚 𝑛 𝑝 𝑚 𝑛 with 𝑚, 𝑛 ∈ 𝑃ℤ }. Let 𝑎, 𝑏 ∈ 𝑃ℚ . Then there are 𝑚, 𝑛, 𝑝, 𝑞 ∈ 𝑃ℤ and 𝑏 = 𝑞 . We have 𝑎 + 𝑏 = 𝑚 𝑛 𝑝 +𝑞 = 𝑚𝑞+𝑛𝑝 𝑛𝑞 . Since 𝑃ℤ satisfies (2) above, we have 𝑚𝑞, 𝑛𝑝, 𝑛𝑞 ∈ 𝑃ℤ . Since 𝑃ℤ satisfies (1) above, we have 𝑚𝑞 + 𝑛𝑝 ∈ 𝑃ℤ . Therefore, 𝑎 + 𝑏 ∈ 𝑃ℚ and (1) 𝑚 𝑝 𝑚𝑝 holds. Also, we have 𝑎𝑏 = 𝑛 ⋅ 𝑞 = 𝑛𝑞 . Since 𝑃ℤ satisfies (2) above, we have 𝑚𝑝, 𝑛𝑞 ∈ 𝑃ℤ , and therefore, 𝑎𝑏 ∈ 𝑃ℚ and (2) holds. 𝑚 Now, suppose 𝑎 ∉ 𝑃ℚ and 𝑎 ≠ 0. Since 𝑎 ∈ ℚ, there are 𝑚 ∈ ℤ and 𝑛 ∈ ℤ∗ such that 𝑎 = 𝑛 . But 𝑎 ≠ 0, and so, we must have 𝑚 ∈ ℤ∗ . Since 𝑎 ∉ 𝑃ℚ , either 𝑚 ∉ 𝑃ℤ or 𝑛 ∉ 𝑃ℤ (or both). If both 𝑚 ∉ 𝑃ℤ 𝑚 –𝑚 and 𝑛 ∉ 𝑃ℤ , then we have 𝑎 = 𝑛 = –𝑛 (because 𝑚(– 𝑛) = 𝑛(– 𝑚)). Then – 𝑚, – 𝑛 ∈ 𝑃ℤ , and so, 𝑎 ∈ 𝑃 ℚ , contrary to our assumption that 𝑎 ∉ 𝑃 ℚ . If 𝑚 ∉ 𝑃ℤ and 𝑛 ∈ 𝑃ℤ , then – 𝑚 ∈ 𝑃ℤ , and therefore, –𝑚 –𝑚 𝑚 –𝑎 = ∈ 𝑃ℚ . If 𝑚 ∈ 𝑃ℤ and 𝑛 ∉ 𝑃ℤ , then – 𝑛 ∈ 𝑃ℤ , and therefore, – 𝑎 = 𝑛 = –𝑛 ∈ 𝑃ℚ . So, at least one 𝑛 of 𝑎 ∈ 𝑃, 𝑎 = 0, or – 𝑎 ∈ 𝑃 holds. If 𝑎 ∈ 𝑃ℚ and – 𝑎 ∈ 𝑃ℚ , then 𝑎 = –𝑎 = –𝑚 –𝑚 𝑛 𝑛 . So, 𝑝 𝑚 𝑛 𝑝 and – 𝑎 = 𝑞 with 𝑚, 𝑛, 𝑝, 𝑞 ∈ 𝑃ℤ . We can also write – 𝑎 as = 𝑞, and thus, (– 𝑚)𝑞 = 𝑛𝑝. Since 𝑛, 𝑝 ∈ 𝑃ℤ , we have 𝑛𝑝 ∈ 𝑃ℤ . Since (– 𝑚)𝑞 = 𝑛𝑝, we must have (– 𝑚)𝑞 ∈ 𝑃ℤ . But – 𝑚 ∉ 𝑃ℤ , and so, – (– 𝑚) ∈ 𝑃ℤ . Since we also have 𝑞 ∈ 𝑃ℤ , we must have – (– 𝑚)𝑞 ∈ 𝑃ℤ . But then by (3) for 𝑃ℤ , (– 𝑚)𝑞 ∉ 𝑃ℤ . This contradiction shows that we cannot have