Topic Name Description
Course Introduction Page Course Syllabus
Page Course Terms of Use
1.1: Sudoku and Latin Squares URL 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.

URL 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.

URL Wikipedia: "Latin Square"

Read this article on Latin Squares.

1.2: Ken-Ken URL 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.

URL 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 URL 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 URL 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 URL 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 URL 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 URL 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.

Page 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 Page 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.

Page 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.

URL 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 URL 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.

Page Propositional Logic, Continued

Watch this lecture.

1.6: Predicate Logic Page Predicates and Qualifiers

Watch these lectures. 

1.6.1: Modus Ponens and Modus Tollens Page Methods of Proof

Watch this lecture. 

1.6.2: Proofs by Contradiction URL 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 URL 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 URL 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 URL 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 Page Sets

Watch this lecture, which defines sets and will familiarize you with set notation and set language.

URL 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 URL 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.

Page 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 URL 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 URL 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 URL 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.

URL 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 URL 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 URL 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 URL 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 Page Disjoint Sets

Watch this brief lecture on disjoint sets.

2.3.2: The Cartesian Product and Multiplication URL 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 Page Equivalent Sets

Watch this lecture, which discusses equivalent sets.

2.4.2: The Formula |A| + |B| = |A ⋃ B| + |A ⋂ B| URL 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 URL 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.

URL 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 URL 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. 

URL 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 URL 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 URL 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. The Twin Prime Conjecture URL 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. Goldbach's Conjecture URL 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. The Riemann Hypothesis URL Wikipedia: "Riemann Hypothesis"

Read this article about the Riemann Hypothesis.

3.3: Fundamental Theorem of Arithmetic (FTA) Page The Fundamental Theorem of Arithmetic

Watch this brief video, which provides an informative, though far less technical, introduction to the Fundamental Theorem of Arithmetic.

URL 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.

URL 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.

URL 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 Page 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 Page 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? URL 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. The Addition of Remainders URL 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 URL 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 URL 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 URL Wikipedia: "Divisor Function"

Read this article about the sum of the divisors of a number.

URL 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 URL Alexander Bogomolny's "The Euclidean Algorithm"
URL Michael Slone, Kimberly Lloyd, and Chi Woo's "Proof of the Fundamental Theorem of Arithmetic"

Read this proof of the FTA.

URL 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.

URL 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 URL 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 URL DavData: "Solving Ax + By = C"

Read the brief text on solving  Ax + By = C .

URL 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 URL 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 Page Rational vs. Irrational Numbers

Watch this video to learn about the difference between rational and irrational numbers.

Page 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 Page 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 URL 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 URL 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 URL 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 Page 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.

Page 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 Page 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 Page 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 URL 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.

Page 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 Page 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 Page 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 Page Injections, Surjections, and Bijections

Watch these videos.

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

URL 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 URL 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 Page Cardinality

Watch this video. Make sure you understand how two sets A and B can be equinumerous.

Page 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 URL 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.

Page Proof: There Are More Real Numbers than Natural Numbers

Watch this video to supplement the written proof of Cantor's Theorem.

Page 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 Page 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 URL 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 Page 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 URL 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 URL Alex Youcis' "Algebraic Numbers Are Countable"

Study this proof, which demonstrates that algebraic numbers are countable.

URL University of St. Andrews: John O'Connor's "Infinity and Infinites"

Read this page.

7.3: Other Bijections URL 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 Page Permutations and Combinations

Watch this introduction to counting. 

URL 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 Page 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 Page 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 URL Wikipedia: "Inclusion-Exclusion Principle"

Read this article.

8.2.3: Other Examples Page 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) Page Pigeon-Hole Principle

Watch this introduction to the pigeon-hole principle.

8.3.1: The Standard Principle Page 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 Page 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.

Page Basic Pigeon-Hole Principle Problems

Watch this video, which provides some very elementary applications of the pigeon-hole principle.

Course Feedback Survey URL Course Feedback Survey