Topic	Name	Description
Course Introduction	Course Syllabus
	Course Terms of Use

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 Ken-Ken.
	Wikipedia: "Latin Square"	Read this article on Latin Squares.

1.2: Ken-Ken	Harold Reiter's "Introduction to Mathematical Reasoning"	This article is optional. If you have an interest in solving Ken-Ken 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 Ken-Ken and complete the exercises in the PDF.
	The New York Times: "Ken-Ken 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 Ken-Ken 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 truth-tellers 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.
	Propositional Logic	Watch this lecture. In particular, focus on the information provided from the 12-minute mark until the 18-minute mark. In this lecture, you will learn which sentences are propositions.

1.5.1: Compound Proposition	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.
	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"	Logical Operations and Truth Tables Properties of Logical Operators Arguments Boolean Algebra 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.
	Propositional Logic, Continued	Watch this lecture.

1.6: Predicate Logic	Predicates and Qualifiers	Watch these lectures.

1.6.1: Modus Ponens and Modus Tollens	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 entry-level 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 Assessment	Donna Roberts' "Logic and Related Conditionals Quiz"	Complete this 10-question 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.

2.1: What Is a Set? Set Builder Notation	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"	Introduction to Set Theory Representation of Sets Basics of Sets Mathematical Reasoning 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 SF-1 through SF-8 for an introduction to sets, set notation, set properties and proofs, and ordering sets.
	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 SF-9 through SF-11 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, $A\cup B=B\cup A$ is a way to say union is commutative in the same way as $x + y = y + x$ 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. Dana-Picard'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. Dana-Picard'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	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	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.

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"	Read the entire webpage on Euclid's proof of the infinitude of primes. Be sure you understand why the prime $P$ is not already in the list of primes; if necessary, re-read this text a few times until you have fully grasped this concept.

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)	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"	Euclid's Algorithm 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 Stankova-Frenkel'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	Modular Arithmetic	Watch these lectures, which address the concepts outlined earlier. Then, if you chose to work through the Ken-Ken material in subunit 1.2, go to section 9 of the paper "Using Ken-Ken to Build Reasoning Skills" from subunit 1.2, and re-read the section to recall how to use modular arithmetic as a strategy for Ken-Ken puzzles.

3.4.1: Division by 3, 9, and 11	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₆ and Z₇"	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"	The Floor or Integer Part Function 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 Sigma-Function, 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"	Euclid's Algorithm An Interactive Illustration Euclid's Game Binary Euclid's Algorithm GCD and the Fundamental Theorem of Arithmetic 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 5-7) 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"	Read the brief text on 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.

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	Rational vs. Irrational Numbers	Watch this video to learn about the difference between rational and irrational numbers.
	Recurring Decimals to Fractions	Watch this video on the conversion of repeating decimals into fractions of the form $\frac{a}{b}$ with $a$ and $b$ integers.

4.3.1: The Square Roots of 2, 3, and 6 are All Irrational Numbers	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?

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"	Read this page, which describes transcendental numbers. Note that both $\pi$ and $e$ are transcendental.

4.4: The Field of Rational Numbers	New York University: Lawrence Tsang's "Real Numbers"	Read pages 1-7 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.

5.1: Mathematical Induction Is Equivalent to the Well-Ordering Property of N	Induction	Watch these videos, which provide informative discussions as to why the well-ordering principle of the natural numbers implies the principle of mathematical induction and discuss why the principle of strong mathematical induction implies the well-ordering principle of the natural numbers.
	Mathematical Induction	Watch this video, which provides an informative discussion on the principle of mathematical induction and the well-ordering principle of the natural numbers. It specifically addresses the notion of strong mathematical induction.

5.2.1: Sums and Products	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	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"	Recursive Definition Recursive Definition of Function 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.
	Hard Inequality	Watch this video, which illustrates using the principle of strong mathematical induction to prove a statement about divisibility of natural numbers.

6.1: Binary Relations on a Set A	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	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	Injections, Surjections, and Bijections	Watch these videos.

6.3: Equivalence Relations	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.

7.1: Cantor Diagonalization Theorem: The Existence of Uncountable Sets of Real Numbers	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.
	Proof: There Are More Real Numbers than Natural Numbers	Watch this video to supplement the written proof of Cantor's Theorem.
	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 Base-3 Connection with the Cantor Ternary Set	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	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"	Please read the paper, paying special attention to examples 2.2.5, 2.2.6, and two functions $a_x$ and $\log_ax$ in the paragraph above example 2.7.1.

8.1: Counting Problems as Sampling Problems with Conditions on the Structure of the Sample	Permutations and Combinations	Watch this introduction to counting.
	Harold Reiter's "Counting"	Read this article. Attempt problems 1-20, starting on page 3. Once you have attempted these problems, check your answers here.

8.2: The Inclusion-Exclusion Principle	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	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: "Inclusion-Exclusion Principle"	Read this article.

8.2.3: Other Examples	Inclusion/Exclusion Examples	Watch these videos, which provide informative illustrations of the use of the inclusion-exclusion formula.

8.3: The Pigeon-Hole Principle (PHP)	Pigeon-Hole Principle	Watch this introduction to the pigeon-hole principle.

8.3.1: The Standard Principle	Pigeon Hole Principle	Watch this video, which provides a careful introduction to the pigeon-hole principle and several examples.

8.3.2: Using the PHP Idea in Other Settings	Pigeon-hole Principle Problem Examples	Watch these videos. The first video provides some an application of the pigeon-hole principle to divisibility and modular arithmetic. The second video provides some applications of the pigeon-hole principle to operations involving integers.
	Basic Pigeon-Hole Principle Problems	Watch this video, which provides some very elementary applications of the pigeon-hole principle.

Course Feedback Survey	Course Feedback Survey