Topic  Name  Description 

Course Introduction  Course Syllabus  
Course Terms of Use  
Unit 1: Logic  Unit 1 Learning Outcomes  
1.1: Sudoku and Latin Squares  Wikipedia: "Sudoku"  Read this article. Try not to get sidetracked looking at variations. Pay special attention to the growth of the number of Latin squares as the size increases. Note that if you want to look ahead at the type of problem you will be asked to solve, check the file "Logic.pdf" at the end of Unit 2. 
Tom Davis' "The Mathematics of Sudoku"  Read Tom Davis' paper, paying special attention to the way he names the cells and to his development of language. Next, if you have not done Sudoku puzzles before, Web Sudoku and Daily Sudoku and are two popular sites. Do one or two before moving on to KenKen. 

Wikipedia: "Latin Square"  Read this article on Latin Squares. 

1.2: KenKen  Harold Reiter's "Introduction to Mathematical Reasoning"  This article is optional. If you have an interest in solving KenKen problems, then you will find this section interesting. Otherwise, omitting it will not hinder your understanding of subsequent material. Read this article for an introduction to KenKen and complete the exercises in the PDF. 
The New York Times: "KenKen Puzzles"  This activity is optional. Attempt to complete one of these puzzles. Note that you can choose the level of difficulty (easier, medium, and harder). After a few practices, challenge yourself to attempt a KenKen puzzle that is at the next level of difficulty. Do not allow yourself to get addicted! 

1.3: SET  Set Enterprises: "Daily Puzzle"  This activity is optional. Read the game rules by clicking on the "daily puzzle rules" link, and play a bit. 
1.4: Other Brain Teasers  Khan Academy: "Brain Teasers"  Pick out a few videos to watch on brain teasers. The puzzle will be introduced to you at the beginning of the video. You should pause the video and attempt to solve the puzzle before viewing the solution. Watch the solutions only if you absolutely cannot solve the puzzle; then, go back and reattempt the problem. 
1.4.1: Truth Tellers and Liars  University of Chicago: Antonio Montalban and Yannet Interian's "Module on Puzzles"  Work on the problems on this webpage: liars and truthtellers puzzles, the Rubik's cube, knots and graphs, and arithmetic and geometry. 
1.4.2: Coin Weighing Puzzles  Alexander Bogomolny's "A Fake Among Eight Coins"  Problems about finding the counterfeit coin among a large group of otherwise genuine coins are quite abundant. Attempt to solve the problem on this webpage. Solutions appear at the bottom of the webpage. If this type of logical thinking interests you, attempt to find similar problems to solve with an online search. 
1.5: Propositional Logic  Hofstra University: Stefan Waner and Steven R. Costenoble's "Introduction to Logic"  Read this page. This text will enable you to see the very close connection between propositional logic and naïve set theory, which you will study in Unit 3. 
Indian Institute of Technology Madras: Dr. Kamala Krithivasan's "Propositional Logic"  Watch this lecture. In particular, focus on the information provided from the 12minute mark until the 18minute mark. In this lecture, you will learn which sentences are propositions. 

1.5.1: Compound Proposition  The University of Aukland: "Boolean Operators"  Watch this video, which will help you later when you are asked to build proofs of statements about rational numbers and about integers. 
Mark Thorsby's "Introduction to Propositional Logic Part I"  Watch this video, which will help you later when you are asked to build proofs of statements about rational numbers and about integers. 

Wikipedia: "Logical Connective"  Read this article, which covers the properties of connectives. While reading, pay special attention to the connection between the Boolean connective and its Venn diagram. 

1.5.2: Truth Tables  University of Cincinnati, Blue Ash: Kenneth R. Koehler's "Logic and Set Theory"  Read these four sections of Koehler's lectures on logic and set theory. A contingency is simply a proposition that is caught between tautology (at the top) and contradiction (at the bottom). In other words, it is a proposition which is true for some values of its components and false for others. For example "if it rains today, it will snow tomorrow" is a contingency, because it can be true or false depending on the truth values of the two component propositions. 
Indian Institute of Technology Madras: Dr. Kamala Krithivasan's "Propositional Logic, Continued"  Watch this lecture. 

1.6: Predicate Logic  Indian Institute of Technology Madras: Dr. Kamala Krithivasan's "Predicates and Qualifiers"  Watch these lectures. 
1.6.1: Modus Ponens and Modus Tollens  Indian Institute of Technology Madras: Dr. Kamala Krithivasan's "Methods of Proof"  Watch this lecture. 
1.6.2: Proofs by Contradiction  California State University, San Bernardino: Peter Williams' "Notes on Methods of Proof"  Read the following sections: "Introduction", "Definition and Theorems", "Disproving Statements", and "Types of Proofs". The types of proofs include Direct Proofs, Proof by Contradiction, Existence Proofs, and Uniqueness Proofs. You may stop the reading here; we will cover the sixth one, Mathematical Induction, later in the course. 
1.6.3: Problem Solving Strategies  Old Dominion University: Shunichi Toida's "Problem Solving"  Read through the examples in the article. The problems are not difficult, but they do serve as clear illustrations of the various aspects of entrylevel problem solving. 
1.6.4: Contrapositive and Equivalent Forms  Gowers' Weblog: "Basic Logical Relationships between Statements, Converses, and Contrapositives"  Read this article, paying special attention to the parts of converses and contrapositives. 
Unit 1 Assessments  Donna Roberts' "Logic and Related Conditionals Quiz"  Complete this 10question quiz on logic and related conditionals. Once you choose an answer, a pop up will tell you if you have chosen correctly or incorrectly. You may also click on the drop down menu for an explanation. 
Unit 2: Sets  Unit 2 Learning Outcomes  
2.1: What Is a Set? Set Builder Notation  Indian Institute of Technology Madras: Dr. Kamala Krithivasan's "Sets"  Watch this lecture, which defines sets and will familiarize you with set notation and set language. 
Old Dominion University: Shunichi Toida's "Set Theory"  Read these pages, which discuss the basics of set theory. Note that there are three ways to define a set. The third method, recursion, will come up again later in the course, but this is a great time to learn it. 

2.1.1: The Empty Set, the Universal Set  University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers, Unit SF: Sets and Functions"  Read pages SF1 through SF8 for an introduction to sets, set notation, set properties and proofs, and ordering sets. 
Kasidej Anchaleenukoon's "Set Theory"  Watch this video for an elementary introduction to set theory. This will be useful to you in case you feel uneasy about the reading above. 

2.1.2: Sets with Sets as Members  University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers, Unit SF: Sets and Functions"  Read pages SF9 through SF11 to learn about subsets of sets. This text also is useful for learning how to prove various properties of sets. 
2.2: Building New Sets from Given Sets  Old Dominion University: Shunichi Toida's "Set Operations"  Read this page, then test your understanding by working the four problems at the bottom. 
2.2.1: Properties of Union, Intersection, and Complementation  Old Dominion University: Shunichi Toida's "Properties of Set Operation"  Read this page. It is important that you become aware that sets combine under union and intersection in very much the same ways that numbers combine under addition and multiplication. For example, is a way to say union is commutative in the same way as says addition is commutative. One difference, however, is that the properties of addition and multiplication are defined as part of the number system (in our development) whereas the properties of sets under the operations we have defined are provable and hence must be proved. 
Simpson College: Lydia Sinapova's "Boolean Algebra"  Read this lecture, paying special attention to the definition of Boolean Algebra and to the isomorphism between the two systems of propositional logic and that of sets. Work the three exercises at the bottom of the PDF and then have a look at the solutions at the end of the document. 

2.2.2: The (Boolean) Algebra of Subsets of a Set  The University of Western Australia: Greg Gamble's "Set Theory, Logic, and Boolean Algebra"  Read this lecture. 
2.2.3: Using Characteristic Functions to Prove Properties of Sets  Jerusalem College of Technology: Dr. DanaPicard's "The Characteristic Function of a Set"  Read this page. This brief text will show you how to use characteristic functions to prove properties of sets. However, there are other reasons to learn how to do this. You will see later in the course that functions (not just characteristic functions play a critical role in the theory of cardinality (set size). 
2.3: The Cartesian Product of Two or More Sets  Jerusalem College of Technology: Dr. DanaPicard's "The Characteristic Function of a Set"  Read this page for a definition and overview of the Cartesian product of sets. 
2.3.1: The Disjoint Union and Addition  American Public University: "Disjoint Sets"  Watch this brief lecture on disjoint sets. 
2.3.2: The Cartesian Product and Multiplication  Nikos Drakos and Ross Moore's "Cartesian Product of Sets"  Read this page, paying special attention to the proof of proposition 3.3.3 at the end of the page. There is a nice proof of this using characteristic functions, which you will be asked to produce later in the course. 
2.4.1: The Cardinality of the Power Set of a Set  American Public University: "Equivalent Sets"  Watch this lecture, which discusses equivalent sets. 
2.4.2: The Formula A + B = A ⋃ B + A ⋂ B  University of Hawaii: G.N. Hile's "Set Cardinality"  Read this page, which demonstrates the basic inclusion/exclusion equation outlined in the title of this subunit. The examples on this webpage are especially interesting; pay attention to example 2, which is about playing cards. 
Unit 3: Introduction to Number Theory  Unit 3 Learning Outcomes  
3.1: Place Value Notation  Harold Reiter's "Fusing Dots"  Read this essay, paying special attention to the exercises at the end. You may find the second half of this reading very difficult. You can access the solutions for selected problems here. Don't worry about understanding all of the details your first time through the reading. Instead, concentrate on the material in the first five sections of the document, and then attempt to generally understand the subsequent sections on Fusing Dots. 
Wisconsin Technical College System: Laurie Jarvis' "Understanding Place Value"  Review this presentation. This information will most likely serve as a review of place value. 

3.2: Prime Numbers  University of St. Andrews: J.J. O'Connor and E.F. Robertson's "Prime Numbers"  Read this page, which includes a good overview of prime numbers and also a list of unsolved problems. Pay special attention to the unsolved problems 1 and 2. 
Wikipedia: "Prime Number"  Read this entry on prime numbers, which will give you an idea of the connections between number theory and other areas of mathematics. 

3.2.1: An Infinitude of Primes  The University of Tennessee at Martin: Chris K. Caldwell's "Euclid's Proof of the Infinitude of Primes"  
3.2.2: Conjectures about Primes  The University of Utah: Peter Alfeld's "Prime Number Problems"  Read this page to get an idea of some of the many unsolved problems about prime numbers. 
3.2.2.1: The Twin Prime Conjecture  Plus Magazine: "Mathematical Mysteries: Twin Primes"  Read this page. Take note of the definition of Brun's constant. Also note that this is related to the Intel's famous $475 million recall of Pentium chips. Please also feel free to click on the link to "Enumeration to 1e14 of the twin primes and Brun's constant" link at the end of the page to read associated content. 
3.2.2.2: Goldbach's Conjecture  Mike James' "Goldbach Conjecture: Closer to Solved?"  Read this brief article to learn about the Goldbach conjecture. Problems like this are the subject of intense work by mathematicians around the world, and progress is made nearly every year towards solving them. 
3.2.2.3: The Riemann Hypothesis  Wikipedia: "Riemann Hypothesis"  Read this article about the Riemann Hypothesis. 
3.3: Fundamental Theorem of Arithmetic (FTA)  Khan Academy: "The Fundamental Theorem of Arithmetic"  Watch this brief video, which provides an informative, though far less technical, introduction to the Fundamental Theorem of Arithmetic. 
Alexander Bogomolny's "Euclid's Algorithm" and "GCD and the Fundamental Theorem of Arithmetic"  Read these pages for information about the Fundamental Theorem of Arithmetic (FTA). Please note that we are going to postpone the proof of FTA until the end of Unit 4. 

Wikipedia: "Fundamental Theorem of Arithmetic"  Read this entire article on the fundamental theorem of arithmetic. The article may take more time to read than some others. 

University of California, Berkeley: Zvezdelina StankovaFrenkel's "Unique and Nonunique Factorization"  Read this page. In particular, focus on the exercise in the reading. Do not be intimidated by the notation in the essay, just read it down to the part on ideals. 

3.4: Modular Arithmetic, the Algebra of Remainders  The Mathsters: "Modular Arithmetic"  Watch these lectures, which address the concepts outlined earlier. Then, if you chose to work through the KenKen material in subunit 1.2, go to section 9 of the paper "Using KenKen to Build Reasoning Skills" from subunit 1.2, and reread the section to recall how to use modular arithmetic as a strategy for KenKen puzzles. 
3.4.1: Division by 3, 9, and 11  Dr. James Tanton's "Divisibility by 3, 9, and 11"  Watch these videos, which will help you understand the divisibility rules for 3, 9, and 11. 
3.4.2: Building the Field Z?  Harold Reiter's "Building the Rings to Z_{6} and Z_{7}"  Read this entire essay, paying special attention to understanding the operations ⊕ and ⊗ (read 'oplus' and 'otimes') in Z? and Z?. Then, work the problems 1 and 4 on Z??. You may check your solutions here. 
3.4.3.1: The Addition of Remainders  The Art of Problem Solving: "2000 AMC 12 Problems"  Try to solve the problem before checking the solution. This problem asks: what is the units' digit of the 2012th Fibonacci number? See if you can work this using your understanding that remainders work perfectly with respect to addition. After you have attempted this problem, review the solution on this page. 
3.5.1: The Floor and the Ceiling Functions  The University of Western Australia: Greg Gamble's "The Floor or Integer Part Function" and "Number Theory 1"  Read these lectures. 
3.5.2: The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of Two Integers  Andy Schultz's "GCD and LCM"  Read this page, paying special attention to the relationship between the GCD and LCM. 
3.5.3: The SigmaFunction, Summing Divisors  Wikipedia: "Divisor Function"  Read this article about the sum of the divisors of a number. 
Harold Reiter's "Just the Factors, Ma'am"  Read this article, paying special attention to Sections 3 and 4, where you will learn about geometry of the divisors of an integer. Complete the problems on the document above, and then check your answers here. 

3.6: The Euclidean Algorithm  Alexander Bogomolny's "The Euclidean Algorithm" 
Read each of these pages for information on the Euclidean Algorithm. 
Michael Slone, Kimberly Lloyd, and Chi Woo's "Proof of the Fundamental Theorem of Arithmetic"  Read this proof of the FTA. 

Massachusetts Institute of Technology: Dr. Srini Devadas and Dr. Eric Lehman's "Number Theory I"  Read this lecture, which provides an introduction to decanting (see the Die Hard example on pages 57) and the Euclidean algorithm. 

Harold Reiter's "Decanting"  Read this paper. This is an easier version of this technique. Solutions to selected problems can be found here. 

3.6.1: Another Look at the Division Algorithm  The University of Western Australia: Greg Gamble's "Number Theory 1"  Review the section on "Division Algorithm" again, and then attempt the 3 sample problems in the lecture. 
3.6.2: Solving Ax + By = C over the Integers  DavData: "Solving Ax + By = C"  
Carnegie Mellon University: Victor Adamchick's "Integer Divisibility"  Read this lecture, which discusses solving an integer divisibility type of equation. You should focus on solving linear Diophantine equations. In particular, you should be able to find a single solution and then generate all solutions from the one you found. 

Unit 4: Rational Numbers  Unit 4 Learning Outcomes  
4.1: Fractions and Rational Numbers Are Not the Same  Harold Reiter's "Fractions"  Read this article. Pay special attention to the five problems on rational numbers at the beginning of the paper. Problem 10 will enable you to appreciate the different between the value of a number and the numeral used to express it. Pay special attention to Simpson's Paradox in the paper. Try the practice problems at the end of the reading. After you have attempted these problems, please check your answers here. 
4.2: Representing Rational Numbers as Decimals  MrCaryMath: "Rational vs. Irrational Numbers"  Watch this video to learn about the difference between rational and irrational numbers. 
Examplayer's "Recurring Decimals to Fractions"  
4.3.1: The Square Roots of 2, 3, and 6 are All Irrational Numbers  University of Missouri  Kansas City: "Proof: The Square Root of 2 Is Irrational"  Watch this video, which shows a proof of the irrationality of the square roots of 2. Can you see how to use these ideas to prove that the square root of 3 and of 6 are also irrational? 
The Math and Physics Channel: "Proof: Square Root of 3 Is Irrational"  Watch this video, which shows a proof that the square root of 3 is irrational. After watching this video, do you think you could prove how the square root of 6 is also irrational? 

4.3.2: Density of Irrational Numbers  New York University: Lawrence Tsang's "Real Numbers"  Read pages 7 through 9, from "Density of Rational Numbers" through "Density of Irrational Numbers." 
4.3.3: Algebraic versus Transcendental Numbers  Dan Sewell Ward's "Transcendental Numbers"  
4.4: The Field of Rational Numbers  New York University: Lawrence Tsang's "Real Numbers"  Read pages 17 of the text. The first 6 pages discuss the field and order axioms for real numbers. The Completeness Axiom on page 6 is what distinguishes the rational numbers from the real numbers  the latter is COMPLETE, while the former is not. 
Unit 5: Mathematical Induction  Unit 5 Learning Outcomes  
5.1: Mathematical Induction Is Equivalent to the WellOrdering Property of N  The Mathsters: "Induction"  Watch these videos, which provide informative discussions as to why the wellordering principle of the natural numbers implies the principle of mathematical induction and discuss why the principle of strong mathematical induction implies the wellordering principle of the natural numbers. 
Julio de la Yncera's "Mathematical Induction"  Watch this video, which provides an informative discussion on the principle of mathematical induction and the wellordering principle of the natural numbers. It specifically addresses the notion of strong mathematical induction. 

5.2.1: Sums and Products  Khan Academy: "Proof by Induction"  Watch this video, which examines how the principle of mathematical induction is used to prove statements involving sums and products of integers. 
5.2.2: Divisibility  David Metzler's "Mathematical Induction, Divisibility Proof"  Watch this video, which illustrates how the principle of strong mathematical induction can prove a statement about divisibility of natural numbers. 
5.2.3: Recursively Defined Functions  Old Dominion University: Shunichi Toida's "Recursive Definition"  Read these essays. Notice the similarities between using recursion to define sets and using recursion to define functions. Then answer the four questions at the end of the first essay. In this type of definition, first a collection of elements to be included initially in the set is specified. These elements can be viewed as the seeds of the set being defined. Next, the rules to be used to generate elements of the set from elements already known to be in the set (initially the seeds) are given. These rules provide a method to construct the set, element by element, starting with the seeds. These rules can also be used to test elements for the membership in the set. 
MathDoctorBob: "Hard Inequality"  Watch this video, which illustrates using the principle of strong mathematical induction to prove a statement about divisibility of natural numbers. 

Unit 6: Relations and Functions  Unit 6 Learning Outcomes  
6.1: Binary Relations on a Set A  MathDoctorBob: "Binary Relations"  Watch this video. It may be worth spending some time watching this video twice. The examples he provides exhibit several properties. These are the defining properties of an equivalence relation (see subunit 6.4) and Partial Ordering (see subunit 6.5). 
6.2.1: Relations that Are Functions  Khan Academy: "Relations and Functions"  Watch this video, which illustrates the notions of relations and functions. This video also provides examples of relations that are functions and some that are not. 
6.2.2: Injections, Surjections, and Bijections  Khan Academy: "Injections, Surjections, and Bijections"  Watch these videos. 
6.3: Equivalence Relations  MathDoctorBob: "Binary Relations"  Watch the last 10 minutes of this video again. It is especially important that you understand the relationship between an equivalence relation and the partition it induces. 
Old Dominion University: Shunichi Toida's "Equivalence Relations"  Read this page on equivalence relations. Then, answer the four questions at the bottom of the page. 

6.4: Partial Orderings  MathVids: "Equivalence Relations and Partial Orders"  Watch this lecture. When you have finished, read the lecture notes and attempt the problems in the problem set. 
Unit 7: Sets, Part II  Unit 7 Learning Outcomes  
7.1: Cantor Diagonalization Theorem: The Existence of Uncountable Sets of Real Numbers  Jeremy Lash, Matt Cerny, Michael Leahy, and Sumedha Pramod's "Cardinality"  Watch this video. Make sure you understand how two sets A and B can be equinumerous. 
American Public University: "Equivalent Sets", "Infinite Sets and Cardinality", and "Subset and Proper Subset"  Watch these lectures to continue your studies on sets. 

7.1.1: Proof of the Theorem  Indian Institute of Technology, Madras: Arindama Singh's "Cantor's Little Theorem"  Read this paper. Spend some time studying the proof of Cantor's Theorem on pages 3 and 4. Even though the proof is quite brief, this idea is new to you, and therefore is likely to be harder to understand. 
University of Missouri, Kansas City: "Proof: There Are More Real Numbers than Natural Numbers"  Watch this video to supplement the written proof of Cantor's Theorem. 

Minute Physics: "How to Count Infinity"  Watch this video about counting finite sets and Cantor's Diagonalization Theorem. 

7.1.2: Even the Cantor Set Is Uncountable, the Base3 Connection with the Cantor Ternary Set  Elvis Zap's "The Cantor Set Is Uncountable"  Watch this video to see a proof that the Cantor middle third set is uncountable. 
7.1.3: Other Examples of Uncountable Subsets of R  Brown University: Rich Schwartz's "Countable and Uncountable Sets"  Read this document to learn about countable and uncountable sets. Focus on the several examples of uncountable subsets of R. 
7.2: The Rational Numbers Are Countable  University of Missouri, Kansas City: "Proof: There Are the Same Number of Rational Numbers as Natural Numbers"  Watch this video to see a proof that rational numbers are countable. 
7.2.1: The Proof  Theorem of the Week: "Theorem 18: The Rational Numbers Are Countable"  Study the proof on this webpage, which shows that rational numbers are countable. 
7.2.2: The Algebraic Numbers Are Countable  Alex Youcis' "Algebraic Numbers Are Countable"  Study this proof, which demonstrates that algebraic numbers are countable. 
University of St. Andrews: John O'Connor's "Infinity and Infinites"  Read this page. 

7.3: Other Bijections  Florida State University: Dr. Penelope Kirby's "Property of Functions"  
Unit 8: Combinatorics  Unit 8 Learning Outcomes  
8.1: Counting Problems as Sampling Problems with Conditions on the Structure of the Sample  Indian Institute of Technology Madras: Kamala Krithivasan's "Permutations and Combinations"  Watch this introduction to counting. 
Harold Reiter's "Counting"  Read this article. Attempt problems 120, starting on page 3. Once you have attempted these problems, check your answers here. 

8.2: The InclusionExclusion Principle  CourseHack: "Inclusion/Exclusion"  Watch these videos for for an introduction to the inclusion/exclusion principle and an example of the principle. Notice that the problem is about As, Bs, and Cs, not As, Bs, and Os as the teacher describes at the start. 
8.2.1: The Case with Just Two Sets  Brian Veitch's "Formula for the Union of Sets  Two Sets and Three Sets"  Watch this video, which provides an informative illustration of the addition formula for the cardinality of the union of two and three sets. 
8.2.2: The Proof  Wikipedia: "InclusionExclusion Principle"  Read this article. 
8.2.3: Other Examples  Course Shack: "Inclusion/Exclusion Examples"  Watch these videos, which provide informative illustrations of the use of the inclusionexclusion formula. 
8.3: The PigeonHole Principle (PHP)  Dr. James Tanton's "PigeonHole Principle"  Watch this introduction to the pigeonhole principle. 
8.3.1: The Standard Principle  Indian Institute of Technology Madras: Kamala Krithivasan's "Pigeon Hole Principle"  Watch the video, which provides a careful introduction to the pigeonhole principle and provides several examples. 
8.3.2: Using the PHP Idea in Other Settings  MathXpress: "Pigeonhole Principle Problem Examples"  Watch these videos. The first video provides some an application of the pigeonhole principle to divisibility and modular arithmetic. The second video provides some applications of the pigeonhole principle to operations involving integers. 
Mr. T's Math Videos: "Basic PigeonHole Principle Problems"  Watch this video, which provides some very elementary applications of the pigeonhole principle. 

Optional Course Evaluation Survey  Optional Course Evaluation Survey  Please take a few moments to provide some feedback about this course. Consider completing the survey whether you have completed the course, you are nearly at that point, or you have just come to study one unit or a few units of this course. Your feedback will focus our efforts to continually improve our course design, content, technology, and general easeofuse. Additionally, your input will be considered alongside our consulting professors' evaluation of the course during its next round of peer review. As always, please report urgent course experience concerns to [email protected] and/or our discussion forums. 