Topic Name Description
Course Introduction Course Syllabus
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"

1.2: Ken-Ken Harold Reiter's "Introduction to Mathematical Reasoning"

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

Introduction to Propositional Logic Part I

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.

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"

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"

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"

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"

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"

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"

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"

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"

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 Z6 and Z7"

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"

3.5.2: The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of Two Integers Andy Schultz's "GCD and LCM"

3.5.3: The Sigma-Function, Summing Divisors Wikipedia: "Divisor Function"

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 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"

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"

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"

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"

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"

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