Math Foundations from Scratch

We will do all at the same time:

• Mathematics via Problems: Algebra [MPA]
• Mathematics via Problems: Geometry [MPG]
• Mathematics via Problems: Combinatorics (released soon)
  • CMU's Discrete Mathematics problem solving seminars to see strategies
• Essential Linear Algebra [ELA]
• Problems in Real Analysis [PRA]

The author has a free version of algebra and geometry, and the original Russian versions on his school page (including discrete math and other books) or Library genesis exists to get all the books including the two Andreescu books if you can't buy them.

Geometry was used for thousands of years to teach and demonstrate mathematical reasoning. Think of it as a tool for doing math like a framework you can manipulate visually, and a way to learn proofs.

The model for basically all mathematical reasoning:

• AND \(\land\) (conjunction)
• OR \(\lor\) (disjunction)
• NOT \(\neg\)
• Implies \(\implies\) is only false when A is true and B is false
• Iff (if and only if) \(\iff\)

These connectives can of course be used to define each other:

• A \(\implies\) B is \(\neg\) A \(\lor\) B
  • implication is only true when either A is false OR B is true
• Iff is (A \(\implies\) B) \(\land\) (B \(\implies\) A)

Really we should just do what every student of math in history did before us which was to get a classical introduction to categories, logic, causality, and rhetoric, all which teach you how to break down a problem and formulate correct arguments ie: proofs.

You can decide for yourself which ancient civilization's authors are worth reading but be aware of translation quality as some are unreadable without extensive attached commentary.

The Aristoteles Latinus project probably has the best translations they collect all ancient manuscripts like the Boethius translations and then compare them to others, presenting the original Latin, and sometimes ancient Greek with the English translation beside it containing the best estimate of modern language, and a full codex in the index so you can read the Latin yourself. It is definitely worth your time to learn Latin if you speak English. Note the professor in the above video has absolute precision in English despite Dutch being her first language, this is what studying Latin helps you to achieve. Think of it as a model of English to help you learn English.

The same project also translates the ancient Syrian and Islamic empire manuscripts as these civilizations had direct access to many of the original Greek texts, again including the original Syriac or Arabic beside the translation with a codex in the index. Some of these you can find on library genesis otherwise a real library is your only hope, as they are extremely expensive books and exist behind an academic paywall where you need a school login to access the databse.

Some optional lectures on the history of logic from Aristotle to the present state:

• Aristotle and deduction - Brief history of logic MF 251
  • Origins of modern logic
• Stoics and other thinkers - Brief history of logic MF 252
  • Implication, disjunction and conjunction is discussed here
• Islamic/Medieval logic - Brief history of logic MF 253
  • Modal logic origins
• Leibniz to Boole - Brief history of logic MF 254
  • From deduction to induction
  • Notation for relations
  • Boole's book Analysis of Logic
  • De Morgan's laws

To teach yourself logic, you could also try Logic and Computation Intertwined. Described as a short stroll through proof assistants by building one yourself, Prof Ragde explains dependent types, propositional logic, predicate logic, and the constructive style logic used to model a proof and then run eliminations on it to verify it is correct. It uses Racket (Scheme/Lisp) anybody can follow. Fully demystifies how Coq and Agda work. He will also teach you how to prove facts in Agda about programming languages if you want to learn proofs by induction. These notes are filled with ascii casts of him working out the problems in Emacs. The notes follow the Agda book.

If you like this style of logic try a proof theory seminar by Frank Pfenning w/notes to learn more about natural deduction. The Per Martin-Lof lectures nicely accompany the seminar and are probably the best explanations you will ever read with precise clarity of the rules of inference, connectives, judgements and how eliminations work. In this theory a proof is a concrete object you construct and can test like a program. If you can't construct it, it's not a proof.

Numbers are objects you build to act like the concept of a number. Here we begin to construct the natural number object.

• YouTube - Arithmetic and Geometry Math Foundations 1 *note these videos eventually get better in quality

• YouTube - Arithmetic and Geometry Math Foundations 2

An interesting explanation of multiplication.

• Laws for addition
  • n + m = m + n (Commutative)
    • Changing the order of the elements.
  • (k + n) + m = k + (m + n) (Associative)
    • Changing the grouping of the elements.
  • n + 1 = s(n) (Successor)
• Laws for multiplication
  • nm = mn (Commutative)
  • (kn)m = k(nm) (Associative)
  • n \(\cdot\) 1 = n (Identity)
• Note the different notation for multiplication:
  • nm
  • n \(\cdot\) m
  • n \(\times\) m
• Distributive laws
  • k(n + m) = kn + km
  • (k + n)m = km + nm

Exercise: Prove why the multiplication and distributive laws work. Since we have no idea what a proof is yet, we can instead try going through some of our own examples.

Identity law: n \(\cdot\) 1 = n.

• We are creating n groups of 1. According to our definition of multiplication |||| \(\cdot\) | would be 4 groups of | or ||||. This is still 4.

Commutative law: nm = mn.

• ||| \(\cdot\) || = || || || or 6. Rearranging this, || \(\cdot\) ||| is ||| ||| which is again 6.

Associative law: (kn)m = k(nm).

• If k = |, and n = ||, and m = ||| and parens expressions are evaluated first:
  • Left side: (kn)m. We first evaluate (kn) as || (2 groups of 1, the identity law), and 2m is ||| ||| (2 groups of 3) for a total of 6.
  • Right side: k(nm): In the parens nm is 2 groups of 3, so ||| |||. k(6) is the identity law, one group of 6. Thus (kn)m = k(nm).

Distributive law: (k + n)m = km + nm.

• If k = ||||, and n = ||, and m = |:
  • Left side: (|||| + ||) is 6, and (6) x 1 is six groups of 1 or 6 according to the identity law.
  • Right side: km + nm: 4 groups of one is 4, plus two groups of 1 is 2 (identity law). Answer is again 6.

• YouTube - Arithmetic and Geometry Math Foundations 3

Wildberger shows another interpretation of multiplication, and walks through the proofs of the laws by rearranging according to the commutative law.

• YouTube - Arithmetic and Geometry Math Foundations 4

Subtraction is the inverse of addition

• If k + m = n then k = n - m
• Note: n - m is only defined if n > m as we are still in the realm of the Naturals and negative numbers/integers aren't yet defined.

+, -, are binary operations and can only do 2 operations at a time

• Laws of Subtraction:
  • n - (m + k) = (n - m) - k
  • n + (m - k) = (n + m) - k
  • n - (m - k) = (n - m) + k
• Distributive laws of subtraction:
  • n(m - k) = nm - nk
  • (n - m)k = nk - mk

Note to remove parens: https://www.themathpage.com/alg/parentheses.htm we can drop the grouping enforcement when using addition (associative law) but must distribute the negative sign, as subtraction is not associative.

• n - (m + k) = (n - m) - k
  • removing grouping: n - m - k = n - m - k

• YouTube - Arithmetic and Geometry Math Foundations 6

A simplified Roman numeral system is introduced to abstract our previous notation of one's so we can manipulate bigger numbers.

• Uses powers of 10
  • 327 = 3 x 10² + 2 x 10¹ + 7 x 10⁰

• YouTube - Arithmetic and Geometry Math Foundations 7

Multiplication with the Hindu-Arabic notation:

• Same laws as before:
  • (ab)c = a(bc)
  • a(b + c) = ab + ac
  • (a + b)(c + d) = ac + ad + bc + bd

A different way of hand multiplication is shown, taking advantage of the fact the notation is using the distributive law.

• YouTube - Arithmetic and Geometry Math Foundations 8

Division is repeated subtraction. Laws of Division:

• 1. \(\frac{k}{m}\) + \(\frac{n}{m}\) = \(\frac{k + n}{m}\)

• 2. \(\frac{k}{m}\) \(\cdot\) \(\frac{n}{l}\) = \(\frac{kn}{ml}\)

• 3. \(\frac{k/m}{n}\) = \(\frac{k}{mn}\)

• 4. \(\frac{k}{m/n}\) = \(\frac{kn}{m}\)

• YouTube - Arithmetic and Geometry Math Foundations 9

We're still using only natural numbers.

• Def: A fraction, is an ordered pair (m,n) of natural numbers also written m/n.
  • Fractions m/n and k/l are equal precisely when ml=nk.

• YouTube - Arithmetic and Geometry Math Foundations 10

We're still in the natural numbers, which he defined as beginning with 1 so we aren't working with zeros yet (no division by zero corner cases). The prime notation (the ' character so c', a', b') used in the proof represents another variable. What we are trying to prove is ab' = ba' and cd' = dc'. He introduces some extra notation multiplying both sides by (dd') to help prove this. This is our first experience with a proof strategy: multiply both sides of something linear by a scalar.

• YouTube - Arithmetic and Geometry Math Foundations 11

Wildberger proves the distributive and commutative laws using fractions while still in the natural numbers.

• YouTube - Arithmetic and Geometry Math Foundations 12

He walks through a proof of a-(b-c)=(a-b)+c

• YouTube - Arithmetic and Geometry Math Foundations 13

A rational number is (a-b)/(c-d) according to it's definition but we write them as p/q and in some cases just p if q = 1.

• YouTube - Arithmetic and Geometry Math Foundations 14

The rational number line sits on [0, 1], so you don't end up with a zero denominator which isn't defined. A rational number is a line through the origin [0,0], and an integer lying on point [m,n]. Ford circles are an example of the massive complexity of the rational numbers, which are expanded upon in the next lecture if you're interested..

Wildberger has a basic introduction lecture using natural numbers that assumes you know nothing about exponents and reviews the hindu-arabic notation, showing how to convert a decimal to a fraction. The second lecture introduces rational number decimals and their visualization.

His definition is a decimal number is a rational number a/b, where b is a power of 10 (hence deca/decimal), then shows various examples how you can manipulate rational numbers like 1/2 to be 5/10, or 0.50, we also find out why 1/3 is not a decimal number. In binary, which is a base-2 system, the only prime factor is 2. If you load up any language interpreter and try and add 0.1 + 0.2 you will get surprising results, typically this number: https://0.30000000000000004.com/ because of the way floating point is used to represent decimals.

At 36:00 arithmetic w/decimals is covered, showing how the rational number and decimal number arithmetic methods are the same so you can just stay w/rational numbers if you want converting back to decimals at anytime.

Let's start with Poh-Shen Loh's problem seminars. It's discrete combinatorics so no background needed.

The first lecture begins ~14:30 mins. Note what's going on, you are just throwing out little ideas for strategies and writing them all down investigating as you go, making yourself examples. His advice: "If the order matters, you always have an opportunity to order it another way". @45:18 If you're trying to guess the formula for something, it's useful to prime factorize whatever values you are getting. If you start seeing other small primes then you know the answer is a factorial or n choose k binomial coefficient. At the end his general form for E_n includes n+ (-1)ⁿ for alternating rounding, something we will see in the problem books.

If you forgot or have never seen factorials/binomial coefficients, he has a middle school seminar on basic combinatorics here for n choose k and Wildberger has a full explanation on Pascal's array and the Binomial Theorem here completely working through Newton's generalized binomial formula.

These problem books are designed for grade 9 - 11 Russian national math competition training if you read the author's page. They are given a few sheets from the book to try and solve by themselves at home, then once a week meet either at the Moscow Center for Continuous Mathematical Education or in the woods outside, what he calls 'math walks' where they hike to a local lake and do math outdoors, a good idea. Afterwards they work on unsolved research problems accessible to highschool students. Keep in mind the target audience would have already had middleschool competition training so don't be surprised if you can't solve the problems at first, these are not going to be like any highschool math you remember. I will have a lot of text in the beginning walking through everything then can assume a background so this workshop gets more terse and precise over time.

1.1.1 [MPA] State and prove the rules of divisibility by 2,4,5,10,3,9,11. Look at the notation guide in the preface to learn x|n means x divides n, or written as a fraction n/x or there exists an integer k such that n = xk. Recall the Wildberger Hindu-Arabic notation lectures: 392 is the sum of (300) + (90) + 2 or ((10² x 3) + (10¹ x 9) + (10⁰ x 2)). Write your own examples out as tests for each number, if you shave off 2 from 992 then you have 990, which is still divisible by 2. So is 900 if you shave off 92 from 992. Writing more tests you discover if any number ends in 0, 2, 4, 6, 8 or in other words is even, then it's divisible by 2.

The proof is given by the author on the next page, using substitution he rewrites a number n to it's generalized Hindu-Arabic form then subtracts off pieces to reason about the results.

\[n = \pm (10^m \cdot a_m + 10^{m - 1} \cdot a_{m - 1} +..+ 10 \cdot a_1 + a_{0})\]

Where the a in a_m is between 0 and 9, and the m in a_m is just an index denoting the position of the terms.

Input examples: 312 = (10²)3₂ + (10¹)1₁ + 2₀ and 312 - a₀ is 310. Try the divisible by 3 rule, subtract the sum of digits from the number: 123 - 1 - 2 - 3 = 117 and divisible by 3 (since 1 + 1 + 7 = 9). Try the equivalent method: (10² - 1)1 + (10¹ - 1)2 + (10⁰ - 1)3 = 99 + 18 + 0 = 117. The key to the proof is in the observation that if you take 10^k - 1, convert it to it's Hindu-Arabic form and factor out (10 - 1), then the sum is divisible by 3, therefore a number is divisible by 3 if it's a_m digits all add up to a number divisible by 3.

The proof of divisibility by 11 f(n) is the function or algorithm where you alternate signs of each digit a_m and subtract odd digits from even. Using 2728 as an example: 2728 = (10³ x 2) + (10² x 7) + (10¹ x 2) + (10⁰ x 8). 10³ and 10¹ are odd, 10² and 10⁰ are even: f(2728) = 2(-1) + 7(1) + 2(-1) + 8(1) = 11.

Another example: f(9999) = (9-9) + (9-9) and 0 is divisible by 11, or 9999 mod 11 = 0. f(451) = (4-5) + 1 = 0 and again divisible by 11. So for 1.1.1(b) is that number consisting of 1993 ones divisible by 11 (since 111111 is divisible by 11)? Try 111111 x 37 = 4111107 or f(4111107) = (4-1) + (1-1) + (1-0) + 7 = 11 so any number divisible by 111111 follows the same f(n) algorithm rule.

Because f(number-with-1993-1's) has odd number of digits, if we cancel all even with odd there is a remainder: 996 1's subtracted from 997 1's there's 1 left over and not divisible by 11. 1.1.1(c) notice that 37 will divide any number consisting of all 1's if the sum of those digits are divisible by 3 ie: 111 digit sum is 3 and divisible by 37, so is 111111, and 2001 digits all 1's is divisible by 3 as well, so will also be divisible by 37.

You can even write a program to verify 1.1.1(b):

# run this program at https://code.pyret.org/
fun link-ones(n :: Number, l :: List<Number>) -> List<Number>:
  doc: "Make a gigantic list of 1993 1's"
  if n == 1993:
    l
  else:
    link-ones(n + 1, link(1, l))
  end
where:
  link-ones(1, [list: 1]).length() is 1993
  link-ones(0, empty).length() is 1993
end

fun count(n :: Number, l :: List<Number>) -> Number:
  doc: "f(n) algorithm to subtract even/odd digits"
  cases (List) l:
    | empty => 0
    | link(f, r) =>
      if n == 0:
        f + count(1, r)
      else:
        (-1 * f) + count(0, r)
      end
  end
where:
  # begins 10^2 or even
  count(0, [list: 1, 1, 1]) is 1
  # begins 10^3 or odd
  count(1, [list: 1, 1, 1, 1]) is 0
  count(1, [list: 2, 7, 2, 8]) is 11
  # begins 10^5 or odd
  count(1, [list: 5, 9, 3, 2, 7, 4]) is 0
end

check "1993 1's even and odd":
  huge-number = link-ones(1, [list: 1])
  count(0, huge-number) is 1
end

1.1.2 [MPA] A number is divisible by 2, iff (if and only if) the last digit is divisible by 2. A number is only divisible by 4 iff the number formed by it's last two digits are divisible by 4 so we are dealing with (n - 10_a1 - a₀) where 10_a1 + a₀ is not divisible by 4, using the expanded hindu-arabic number notation. Simply google divisors calculator or write your own algorithm and start testing numbers, any number you can think of with this constraint of being even but not divisible by 4 has the same even/odd divisors. Now why is this true? This is an example of one of the problems in the book you can just toss around your mind all day if you looked at it in the morning. If 4|n then we get an even number k as output, and 2|k so there will always be an imbalance in the number of divisors being odd or even. If 2|n and n is not divisible by 4, we always get an odd number as output so the number of divisors are always in pairs (even, odd). This will make more sense when when we learn primes.

TODO

Home