Topic | Name | Description |
---|---|---|
Course Introduction | ||
1.1: Sudoku and Latin Squares | 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. |
|
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. |
||
Read this article on Latin Squares. |
||
1.2: Ken-Ken | 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. |
|
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 | 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 | 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 | 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 | 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 | 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. |
|
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 | Watch this video, which will help you later when you are asked to build proofs of statements about rational numbers and about integers. |
|
Watch this video, which will help you later when you are asked to build proofs of statements about rational numbers and about integers. |
||
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 | 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. |
|
Watch this lecture. |
||
1.6: Predicate Logic | Watch these lectures. |
|
1.6.1: Modus Ponens and Modus Tollens | Watch this lecture. |
|
1.6.2: Proofs by Contradiction | 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 | 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 | Read this article, paying special attention to the parts of converses and contrapositives. |
|
Unit 1 Assessment | 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 | Watch this lecture, which defines sets and will familiarize you with set notation and set language. |
|
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 | Read pages SF-1 through SF-8 for an introduction to sets, set notation, set properties and proofs, and ordering sets. |
|
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 | 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 | Read this page, then test your understanding by working the four problems at the bottom. |
|
2.2.1: Properties of Union, Intersection, and Complementation | 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, |
|
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 | Read this lecture. |
|
2.2.3: Using Characteristic Functions to Prove Properties of Sets | 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 | Read this page for a definition and overview of the Cartesian product of sets. |
|
2.3.1: The Disjoint Union and Addition | Watch this brief lecture on disjoint sets. |
|
2.3.2: The Cartesian Product and Multiplication | 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 | Watch this lecture, which discusses equivalent sets. |
|
2.4.2: The Formula |A| + |B| = |A ⋃ B| + |A ⋂ B| | 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 | 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. |
|
Review this presentation. This information will most likely serve as a review of place value. |
||
3.2: 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. |
|
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 | ||
3.2.2: Conjectures about Primes | 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 | 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 | 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 | Read this article about the Riemann Hypothesis. |
|
3.3: Fundamental Theorem of Arithmetic (FTA) | Watch this brief video, which provides an informative, though far less technical, introduction to 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. |
||
Read this entire article on the fundamental theorem of arithmetic. The article may take more time to read than some others. |
||
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 | 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 | Watch these videos, which will help you understand the divisibility rules for 3, 9, and 11. |
|
3.4.2: Building the Field 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 | 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 | Read these lectures. |
|
3.5.2: The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of Two Integers | Read this page, paying special attention to the relationship between the GCD and LCM. |
|
3.5.3: The Sigma-Function, Summing Divisors | Read this article about the sum of the divisors of a number. |
|
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 |
Read each of these pages for information on the Euclidean Algorithm. |
|
Read this proof of the FTA. |
||
Read this lecture, which provides an introduction to decanting (see the Die Hard example on pages 5-7) and the Euclidean algorithm. |
||
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 | 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 | ||
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 | 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 | Watch this video to learn about the difference between rational and irrational numbers. |
|
4.3.1: The Square Roots of 2, 3, and 6 are All Irrational Numbers | 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 | Read pages 7 through 9, from "Density of Rational Numbers" through "Density of Irrational Numbers." |
|
4.3.3: Algebraic versus Transcendental Numbers | ||
4.4: The Field of Rational 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 | 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. |
|
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 | 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 | 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 | 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. |
|
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 | 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 | 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 | Watch these videos. |
|
6.3: Equivalence 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. |
|
Read this page on equivalence relations. Then, answer the four questions at the bottom of the page. |
||
6.4: Partial Orderings | 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 | Watch this video. Make sure you understand how two sets A and B can be equinumerous. |
|
Watch these lectures to continue your studies on sets. |
||
7.1.1: Proof of the 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. |
|
Watch this video to supplement the written proof of Cantor's Theorem. |
||
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 | 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 | 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 | Watch this video to see a proof that rational numbers are countable. |
|
7.2.1: The Proof | Study the proof on this webpage, which shows that rational numbers are countable. |
|
7.2.2: The Algebraic Numbers Are Countable | Study this proof, which demonstrates that algebraic numbers are countable. |
|
Read this page. |
||
7.3: Other Bijections | ||
8.1: Counting Problems as Sampling Problems with Conditions on the Structure of the Sample | Watch this introduction to 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 | 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 | 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 | Read this article. |
|
8.2.3: Other Examples | Watch these videos, which provide informative illustrations of the use of the inclusion-exclusion formula. |
|
8.3: The Pigeon-Hole Principle (PHP) | Watch this introduction to the pigeon-hole principle. |
|
8.3.1: The Standard 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 | 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. |
|
Watch this video, which provides some very elementary applications of the pigeon-hole principle. |
||
Course Feedback Survey |