Schedule

Discussed the syllabus.

Homework 0: Send me a short email with the following information (due by 31 August at Midnight).

• Who are you (preferred name, pronouns if you choose)? What is your major?
• What brings you to my class? Is it your major? Are you just curious? Something else?
• What do you hope to get out of this course?
• Share one fun fact about yourself.

(My Fun Fact: I like to go fishing, and one time I caught a catfish that was this big! /*stretches arms really wide/*)

Also think about the following for the next lecture:

• What do you think "proof" is?
• What kind of reasoning is irrefutable? Why do you think that?

• Truth values.
• Logical connectives.
• Truth tables.

See our textbook on propositional statements and my notes on basic logic.

• Logical equivalence in mathematics and natural language.
• Algebra of logical equivalence (using the basic equivalences).

See Sundstrom's notes on logical equivalence and my notes on basic logic.

• Rules of Inference.
• Overview of natural deduction.
• Replacement rules, i.e., the law of equivalent exchange and simple applications of the rules of inference.

See Logica and my notes for discussion of natural deduction.

I gave extra office hours on Friday, 2 September 2022 in which I showed folks how to get started with the LaTeX typesetting language. Your can read my LaTeX guide, and use the source code as a starter for your homework projects.

I suggest you use Overleaf to write your documents—that way you have access to their help pages and don't have to download any software.

• Proofs in the propositional logic system.
• Some example problems in natural deduction.

Due to a dangerous kindness streak, I wrote a logic study sheet.

• Predicates and quantifiers.
• Sentence translation.
• Negation of statements: DeMorgan for Quantifiers.
• Proving existential statements.

I wrote and recorded videos on predicate logic, including sentence translation with predicates and working with predicates. Also see our textbook's notes on quantified logic.

• Set notations.
• Common sets.
• Set relationships: equal, subset, or neither!
• Set operations.
  • Union.
  • Intersection.
  • Set difference.
• Proofs involving sets.

This week we gave our first proper proofs of some mathematical statements!

See Sundstrom's book concerning sets, set operations, and proofs of set relationships. See Levin's book for a summary of naive set theory from a mostly computational perspective.

• Chasing elements.
• Manipulating predicates.
• Direct proof.

I wrote the following solutions, requested by students:

• Manipulating predicates to prove a set equality.

The first exam is during class time in the usual room on Friday, 23 September 2022. You will have the full time to complete the exam.

• More element chasing.
• More discussion of how to think about proofs.
• More set operations.
  • Powerset.
  • Cartesian product.

See Sundstrom's book on properties of set operations and the cartesian product. See the homework page for exercises on proofs involving power sets and cartesian products.

• General relations.
• A relation \( R \) on set \( A \) is…
  • reflexive when for all \( a \in A \) we have that \( a\, R\, a \).
  • symmetric when for all \( a, b \in A \) we have that \( a\, R\, b \) implies \( b\, R\, a \).
  • antisymmetric when for all \( a, b \in A \) we have that both \( a\, R\, b \) and \( b\, R\, a \) implies \( a = b \).
  • transitive when for all \( a, b, c \in A \) we have that both \( a\, R\, b \) and \( b\, R\, c \) implies \( a\, R\, c \).

See my notes on relations and Sundstrom's book on general relations. See the homework page for exercises on general relations.

• Relations
  • Definition and more examples than anyone wanted.
  • Properties relations may satisfy: reflexivity, symmetry, antisymmetry, transitivity.
  • Equivalence relations: a relation on \( A \) is an equivalence relation when it is reflexive, symmetric, and transitive.
  • Visualizing relations using digraphs (i.e., the "dots-and-arrows").
• Functions

  Injective

  Distinct inputs map to distinct outputs.

  Surjective

  Every element of the codomain is mapped to by some element of the domain.

  Bijective

  Both injective and surjective.

See my notes on functions and relations, and Sundstrom's book on equivalence relations, an introduction to functions, and injectivity, surjectivity, and bijectivity. See the homework page for exercises on equivalence relations, properties satisfied by special relations, and general functions.

• Too many examples proving and disproving injectivity and surjectivity of given functions.
• Composition.
• Image and preimage.
• Inverse functions.
• Many proofs involving functions.

See my notes on funtions; I strongly encourage you to attempt the exercises therein… Also see Sundstrom's book on injectivity, surjectivity, and bijectivity, composition, images and preimages, and inverse functions. Finally, see the homework page for exercises on injectivity and surjectivity, composition, and more injective and surjective functions.

• Basic properties of integer arithmetic.
  • Closure under addition and multiplication.
  • Commutativity of addition and multiplication.
  • Associativity of addition and multiplication.
  • Existence of additive and multiplicative identity.
  • Existence of additive inverses.
  • Notice: division is NOT listed here… So don't try to do that with integers in this class!
• Divisibility
  • Definition.
  • Basic properties.
  • Some proofs involving divisibility.
• The Quotient-Remainder Theorem.

See my notes on elementary number theory. Try the exercises there, and don't forget the homework.

• Using the Quotient-Remainder Theorem.
  • Modular arithmetic.
  • Divisibility and remainders.
  • Well-definition of modular operations.

See my notes on elementary number theory.

The second exam is during class time in the usual room on Friday, 28 October 2022. You will have the full time to complete the exam.

• Greatest common divisor.
  • Elementary properties.
  • Euclid's Algorithm.
  • Solving modular equations.
  • Zero divisors and how to detect them with the GCD.

See my notes on elementary number theory. See Sundstrom's book on the greatest common divisor, prime numbers, and solving linear congruences.

Don't forget to do the homework!

• Prime numbers.
  • Fundamental Theorem of Arithmetic (FTA).
  • Greatest common divisors via the FTA.

This proof method extends our proof methods. It is an application of the Reductio Ad Absurdum rule of logical inference.

We used this to prove the following two results:

1. The square root of two is irrational.
2. The Fundamental Theorem of Arithmetic.

You should do the homework…

• Weak mathematical induction, with many simple example proofs.

You have homework on this topic! See Sundstrom's book for an introduction to induction, alternate induction methods, and recursion.

• Strong mathematical induction
• Recursive definitions
• Fibonacci numbers
• Common pitfalls
• Many examples

See this Mathologer video for a cool consequence of some simple Fibonacci maths :) See Sundstrom's book for an introduction to induction, alternate induction methods, and recursion.

Fibonacci Universality

If \( (A_n)_{n \geq 0} \) satisfies the Fibonacci recursion, then \( A_{n+1} = A_1 F_{n+1} + A_0 F_n \) for all \( n \geq 0 \).

Convolution

For all \( a, b \in \N \) we have \( F_{a+b+1} = F_{a+1} F_{b+1} + F_a F_b \).

Divisibility

For all \( d, n \in \N \), if \( d \mid n \), then \( F_d \mid F_n \).

The Fibonacci numbers are a great example of a recursively defined sequence. See the homework page!

Bijection Principle

If \( f \colon A \to B \) is a bijection, then \( \#A = \#B \).

Sum Principle

If \( A \) and \( B \) are disjoint, then \( \#(A \cup B) = (\#A) + (\#B) \).

Product Principle

\( \#(A \times B) = (\#A)\cdot(\#B) \)

Binomial Coefficients

\( \binom{n}{k} = \#\left\{ S \subseteq [n] : \#S = k \right\} \)

See my notes. Levin's book has an excellent summary of techniques.

Many examples of enumeration techniques, including…

• Permutations of \( n \)-sets
• Anagrams

We also discussed decision trees, for a CS-type description of what our counting procedures actually accomplish.

See my notes. Levin's book has an excellent summary of enumeration techniques and many exercises. See Levin's book for individual discussions of the sum and product principles, binomial coefficients, combinations and permutations, and combinatorial proofs.

Finally, see this video, where an expert in the field of enumeration describes their process (and how they became an expert).