Outlines

Sets

Notion of set as a collection of items with some relevance to each other. No order. No duplicates.
Explicit and implicit definition of sets. How to evaluate set membership conditions (ie how to read and apply a condition like $\{x|x^2-4=0\}$).
Special sets: $\mathbb{Z, Q, R}$. Also $\mathbb{N}$ versus $\mathbb{N}_0$.
Cardinality.
Equal sets. $A=B\Leftrightarrow \forall x\in A, x\in B\ \textrm{and}\ \forall x\in B, x\in A$. Universal quantifier.
Subsets and proper subsets. Powerset. $|\mathcal{P}(A)|=2^{|A|}$.
Union. $A\cup B = \{x|x\in A\ \textrm{or}\ x\in B\}$. Examples: if $A=\{x|x \textrm{is a vowel}\}, B=\{x|x \textrm{is a consonant}\}$, then what is $A\cup B$? If $A=\{x|x \textrm{resident of IL}\}$ and $B=\{x|x \textrm{resident of WI}\}$, then describe $A\cup B$.
Intersection. $A\cap B = \{x|x\in A\ \textrm{and}\ x\in B\}$. Examples. If $A=\{x|x\ \textrm{actor in ST:TOS}\}$ and $B=\{x|x\ \textrm{actor in ST:TNG}\}$, what is $A\cap B$ (cross overs from TOS to TNG include Majel Barrett, Diana Muldaur, DeForest Kelley, Mark Lenard, Leonard Nimoy, and James Doohan).
Venn diagrams.
Cartesian product. $A\times B$: set of all ordered pairs $(x,y): x\in A\ \textrm{and}\ y\in B$. Focus on ordered pairs, $(a,b) \neq (b,a)$ and $(a,b) = (c,d) \Leftrightarrow a=c\ \textrm{and}\ b=d$. Examples. $F=\{\textrm{John},\ \textrm{Jane}\}$, $L=\{\textrm{Smith},\ \textrm{Taylor}\}$ then $F\times L = \{\textrm{(John,Smith)},\ \textrm{(John,Taylor)},\ \textrm{(Jane,Smith)},\ \textrm{(Jane,Taylor)} \}$. Cardinality of a product $|F\times L| = |F|\times |L|$; and in general: $|A\times B\times C\times \ldots| = |A|\times |B|\times |C|\times \ldots$.
Cartesian products as the basis of database queries; the join operation: combine seemingly irrelevant sets based on some common property.

Direct proofs

Mathematical systems: axioms, definitions, undefined terms. Theorems, lemmas, corollaries. Examples.
Direct proofs.

\[\textrm{for all}\ x_1, x_2, \ldots, x_n,\ \textrm{if}\ p(x_1, x_2,\ldots, x_n)\ \textrm{then}\ q(x_1, x_2, \ldots, x_n)\]

Focus on $p\ \textrm{then}\ q$: we assume $p$ is true and we work our way to show that $q$ is true, using the mathematical systems’ axioms, definitions, and already proven theorems.

Examples

if $m$ is odd and $n$ is even then $m+n$ is odd. Here it is implied that we want to prove this for all $n,m\in\mathbb{Z}$. Use definition of odd and even numbers. $m=2k, n=2j+1$ and see what happens when applying these into the expression we want to prove: $m+n = 2k+2j+1 = 2(k+j)+1=2l+1$ with $l=k+j$; showing that $n+m$ is written in the form of an odd number definition (multiple of two plus 1).
the sum of two odd integers is an even integer. Since $a=2m+1$ and $a=2n+1$, their sum can be written as $a+b = (2m+1) + (2n+1) = 2m+2n+2 = 2(m+n+1)$, i.e., a multiple of 2.
If $X\cap Y = X\cap Z$ and $X\cup Y = X\cup Z$ then $Y=Z$. (Hint: if $Y=Z$ then $Y\subseteq Z$ and $Z\subseteq Y$).
$\mathcal{P}(A\cap B)= \mathcal{P}(A)\cap \mathcal{P}(B)$
$(A\cup B)\cup C = A\cup(B\cup C)$
$A\cap B =B\cap A$
If $|A\times B|=1$, what is $|A|$ and $|B|$?
If $|A\times B|=\textit{prime}$, what is $|A|$ and $|B|$?
If $|A\times B|=0$, what is $|A|$ and $|B|$?
If $|A\times B|=n$, with $n>1$ and not a prime number, what is $|A|$ and $|B|$?
Prove that $100\ldots1$, i.e., a number that begins and ends with 1 and has at least $3n-1$ zeros inbetween, with $n>0$, is a composite number. A composite number is the product of other natural numbers, all greater than 1. Hint: $x^3+y^3=(x+y)(x^2-xy+y^2)$.
Show that if $x_1, x_2$ are distinct roots of the polynomial $p(x) = x^2+bx+c$, then $x_1+x_2=-b$ and $x_1 x_2=c$.
If $a$ divides $b$ and $a$ divides $c$ then $a$ divides $b+c$, where $a,b,c\in\mathbb{N}_{>0}$. Remember that for $x,y\in\mathbb{N}$ and $x>0$, we say that $x$ divides $y$ (and we write $x\backslash y$), when $\exists z\in\mathbb{N}: xz=y$.
Prove that an integer divisible by 4 is the difference of two perfect squares.
Prove that $\forall x,y\in\mathbb{R}, x^2+y^2\geq 2xy$.
Prove that the sum of two rational numbers is a rational number.
Prove that if $x_1, x_2, x_3$ are three distinct roots of the polynomial $p(x)= x^3+bx^2+cx+d$ then $x_1 x_2 + x_1 x_3 + x_2 x_3 = c$.

Proof by counterexample

The statement $\forall n \in\mathbb{Z}^+: 2^n+1\ \textrm{is prime}$, can be proven wrong with just one counterexample: for $n=3, 2^3+1 = 9$ which is not a prime.

Common mistakes in proofs

Stoping short of a definition

Definitions are not negotiable! For example, an odd number is $2n+1$, with $n\in\mathbb{Z}$, i.e., a multiple of two plus 1. So if you arrive at the conclusion that some number equals $2n+3$ and you then state this is an odd number, you have not met the rigor of proof. Yes, $2n+3$ looks like an odd number. But within the mathematical system of integer numbers it is not proven to be odd until you can demonstrate that it’s a multiple of two plus one, i.e., $2n+3 = 2n+2+1=2(n+1)+1$.

Of course, in the interest of time you may end up with $2n+5$ and then simply state that “by further factorization, this is $2k+1$”. That’s fine too, as long as you communicate that there is one more step needed, what it involves (“further factorization”, in this example), and where it leads ($2k+1$, the definition of an odd number). In such case, the further step that you narrate instead of executing, needs to be trivial. For example, further factorization of $2n+5$ leads to $2(n+2)+1$ and this is – or should be – obvious to everyone.

Symbology issues

You are asked to prove that the sum of two odd numbers is an even number. You proceed in defining the odd numbers as:

\[\begin{split}a = 2n+1 \\ b = 2n+1\end{split}\]

thinking that because you use different symbols ($a,b$), the two numbers are different. They are not. In fact $a=b$. Yes, they are both odd. More precisely, they are the same odd number. You work through your proof finally concluding that $a+b=2(2n+1)$. Great! You just proved that an odd number, multiplied be two, is an even number. But this is not the same as proving that any two odd numbers add to an even number. Therefore, you need to define your $a$ and $b$ as different numbers, e.g.

\[\begin{split}a = 2n+1,\ \textit{or}\ a = 2n_a+1 \\ b = 2m+1,\ \textit{or}\ b = 2n_b+1\end{split}\]

In other words: do not hesitate to use different symbols.

Attempts at proofs by miracle

Miraculous proofs are known to happen late at night or within seconds before an assignment deadline. Such proofs should be avoided at all cost as they are considered harmful to one’s reputation and detrimental for a final grade.

../_images/miracle.jpg — (Cartoon by Sydney Harris; (C) 1977-2021. Used with the kind permission of the author.)

Attempts at proofs by brute force

Use of violence is often illegal, totally inappropriate, probably grounds for expulsion, and always unconvincing.

../_images/brute_force.jpg — (Cartoon by Sydney Harris; used with the kind permission of the author.)

Indirect proofs

The direct approach, if $p$ then $q$ does not always work.
If $n^2$ is even, then $n$ is even too. Where to start? Writing $n^2=2k$ can takes us only as far as $n=\sqrt{2k}$. We cannot tell if $\sqrt{2k}$ is a multiple of 2. Instead, try: if $(n^2:\textit{even}\Rightarrow n:\textit{odd})$.
In general, $h\Rightarrow c$. If no direct path from $h$ to $c$, then assume $h\Rightarrow \neg c$. Explore $\neg c$. Can we go from $\neg c$ to $h$? If not, the assumption was wrong therefore its opposite (the original statement) must be true.
Example: $n^2:\textit{odd}\Rightarrow n:\textit{odd}$. Identify $h$ and $c$ parts.
Example: $a,b\in\mathbb{Z}\Rightarrow a^2-4b\neq 2$. (Hint: 1 is not an even number).
Example: There is a largest number. ($L\geq x, \forall x\in\mathbb{R}$. Add $L$ to both sides of $1>0$).
Example: $n^3+5:\textit{odd}\Rightarrow n:\textit{even}$.
Example: $\sqrt{2}\not\in\mathbb{Q}$.
Example: $x\in\mathbb{Q}, y\not\in\mathbb{Q} \Rightarrow (x+y)\not\in\mathbb{Q}$.
Example: $x\not\in\mathbb{Q}, m\in\mathbb{Z}\ \Rightarrow mx\not\in\mathbb{Q}$.
Example: $\forall x\in\mathbb{R}: x(1-x)\leq\dfrac{1}{4}$. (Counter example; simple).

Propositional logic

Definition of proposition: statement that can be proved to be true or false but not both.

Example: Chicago is in Illinois

Example: This will be a great year

Example: $\pi$ is not an integer number

Example: Earth is round or Earth is flat

Example: $1+1=3$

Notation: $p:\textit{Chicago is in Illinois}$
Notation: $p:\textit{Earth is round}$, $q:\textit{Earth is flat}$, together $p\ \textit{or}\ q$ and in full notation: $p\vee q$.
Notation: $p:\textit{It's February}$, $q:\textit{It is cold}$, together $p\wedge q$.
Truth tables
More than two propositions
The not operator $\neg$, with examples $\neg (\textit{Earth is flat})$.
Conditional proposition: if $p$ then $q$. Notation: $p\rightarrow q$. Terminology: $p$ hypothesis, $q$ conclusion. (Antecendent and consequent).

Example: $\textsf{You are born in Chicago}\rightarrow\textsf{You are from Illinois}$.

$p:\textsf{You are born in Chicago}$

$q:\textsf{You are from Illinois}$

$p$ can be true or false. $q$ can be true or false. Let’s examine them.

Simple table:

$p$	$q$	$p\rightarrow q$
You are born in Chicago	You are from Illinois	True
You are born in Chicago	You are not from Illinois	False
You are not born in Chicago	You are from Illinois	True
You are not born in Chicago	You are not from Illinois	True

From simple logic functions to biconditional propositions

AND, OR, NOT
Combinations thereof: NAND, NOR
The XOR function
Sneak preview of logic gates
Simple (half) adder
Conditional proposition
Necessary condition: a condition that does not guarantee an outcome, but without it the outcome cannot be achieved. E.g., a necessary condition to visit the Eiffel tower is to travel to France. (Another: win lotto, buy ticket).
Sufficient condition: a condition that guarantees an outcome, even though the outcome is still possible without the condition. A sufficient condition that you traveled to France is that you’ve been to the Eiffel tower.
Biconditional (truth table: TFFT) $p\Leftrightarrow q: (p\rightarrow q)\wedge (q\rightarrow p)$. Example: $x^2-x-12=0 \Leftrightarrow x=-3\ \text{or}\ x=4$
De Morgan’s Laws. Augustus De Morgan, 19th c. Brit. math.

\[\begin{split}\neg (p\vee q) &\equiv \neg p \wedge \neg q \\ \neg (p\wedge q) &\equiv \neg p \vee \neg q\end{split}\]

Java: (x<10 || x>20) $\equiv$ !(x>=10 && x <= 20)
Quantifiers: universal $\forall$; existential $\exists$.

$p: n\ \text{is an odd number}$. We cannot tell is $p$ is T/F without knowing $n$, so as it stands, $p$ is not a proposition. But $\forall n\in\mathbb{Z}, p(n)$ can be true or false, hence $p(n)$, as universaly quantified, is a proposition. In this case $\mathbb{Z}$ is the domain of discourse. To prove $\forall x P(x)$ we must show $P$ is true for every $x$.

Existentially quantified statement: $\exists x P(x)$, provable as long as we find at least one $x$ that satisfied $P(x)$. Example: $\exists x (\dfrac{x}{x^2+1}=\dfrac{2}{5})$, with $x\in\mathbb{R}$

Binary relations (BR)

BR describe how elements from one set relate to elements of another set (or the set itself)
$R: X\mapsto Y: R\subset X\times Y$.
If $(x,y)\in R$ we write $x\ R\ y$, i.e., $x$ is related to $y$.
$X$ is called the domain of $R$. $Y$ is the codomain. (Set of departure and set of destination, respectively).
Infix notation: $(x,y)\in R\equiv x\ R\ y$. Here, $R$ can be replaced with a symbol operationalizing the relation, e.g., if $R$ is the equality over elements of $X$, then $(x,y)\in R \equiv x=y$.
Digraphs for $R:X\mapsto X$: vertices, directed edges, loops.
$R: X\mapsto X$ is reflexive if $(x,x)\in R, \forall x\in X$. Examples of reflexive relations: $\forall x\in\mathbb{Z}, x=x$; $\forall x\in\mathbb{R}, x\geq x$; etc. Non reflexive relations: $x>x`(NB: loop terminating condition); :math:`x\neq x$. Worth noting that $xy:\textrm{even}$ is reflexive in $\mathbb{Z}_{\textrm{even}}$ and irreflexive in $\mathbb{Z}_{\textrm{odd}}$.
$R: X\mapsto X$ is symmetric if $\forall x,y \in X$, if $(x,y)\in R$ then $(y,x)\in R$. Examples of symmetric relations: $\forall x,y\in\mathbb{R}: x=y\Leftrightarrow y=x$; $R=\textrm{sibling of}: x\ R\ y\Leftrightarrow y\ R\ x$. Example of non symmetric relation: $R=\textrm{student of}: x\ R\ y\not\Leftrightarrow y\ R\ x$. Special case, $R=\textrm{student of Leo}: x\ R\ y\Leftrightarrow y\ R\ x$ (I am learning from each and every one of my students).
$R: X\mapsto X$ is antisymmetric if $\forall x,y\in X$, if $(x,y)\in R$ and $(y,x)\in R$ then $x=y$. Example $\forall x,y\in\mathbb{Z}$, if $x\setminus y$ and $y\setminus x$ then $x=y$ (illustrate with $9\setminus 3$ true but $3\setminus 9$ not true. Only $9\setminus 9$ is true; also $3\setminus 3$). Notice that if $x\leq y$ and $y\leq x$ then $x=y$. So the relation $\leq$ is antisymmetric.
Alternative notation for antisymmetric relation: if $x\neq y$ then $(x,y)\not\in R$ or $(y,x)\not\in R$.
Show that a relationship can be both symmetric and antisymmetric. $A=\{1,2\}$; $A\times A = \{(1,1), (1,2), (2,1), (2,2)\}$; $R=\{(1,1), (2,2)\}$; $R\subset A\times A$; $R$ is symmetric, because for every $(x,y)\in R$, $(y,x)$ also in $R$. The relation is also antisymmetric because $(x,y)\in R$ and $(y,x)\in R$ are satisfied only when $x=y$.
$R: X\mapsto X$ is transitive if $\forall x,y,z\in X$, if $(x,y)\in R$ and $(y,z)\in R$ then $(x,z)\in R$. Example: the $>$ operation. If $x>y$ and $y>z$ then $x>z$. Also, if Dayton, Ohio is east of Chicago, Ill., and Chicago, Ill. is east of Denver, Colo., then Dayton is east of Denver. If $a\setminus b$ and $b\setminus c$ then $a\setminus c$.
A reflexive, antisymmetric, and transitive relation is called a partial order.
If $R:X\mapsto Y$, the inverse relation $R^{-1}:Y\mapsto X$ is defined as $R^{-1}=\{(y,x)| (x,y)\in R\}$.
Injective relation: $\forall x,z\in X$, and $\forall y\in Y$, if $xRy$ and $zRy$, then $x=z$ and $Y$ is called the primary key of $R$. Example: student ID in registration records. Mathemagical examples: $y=x$ (linear function); $x=y^2$ (square root).
Functional relation: $\forall x\in X$ and $\forall y,z\in Y$ if $xRy$ and $xRz$ then $y=z$. $X$ is a primary key for $R$. Example $y=x$ (again!); also $y=x^2$.

	injective	not injective
functional	one-to-one	many-to-one
functional	$y=x$	$y=x^2$
not functional	one-to-many	many to many
not functional	$x=y^2$	$x^2+y^2=1$

Induction

Peano’s axioms: 0 is a natural number; $x=x$ (equality reflexive); $x=y\Rightarrow y=x$ (symmetry of equality); $x=y$ and $y=z$ then $x=z$ (equality is transitive); if $a\in\mathbb{N}$ and $a=b$ then $b\in\mathbb{N}$ (closed under equality); $\forall n\in\mathbb{N}, S(n)\in\mathbb{N}$ (closure under $S$); $\forall m,n\in\mathbb{N}$, if $S(n)=S(m)$ then $n=m$ ($S$ is injective); $\not\exists n\in\mathbb{N}: S(n)=0$; if $K$ is a set such that $0\in K$ and $\forall n\in\mathbb{N}: n\in K\Rightarrow S(n)\in\mathbb{K}$ then $K=\mathbb{N}$ (induction).
Climb-the-ladder analogy (Knuth).
Traffic light analogy (unknown).
Everyone’s favorite example: $1+2+\ldots+n = n(n+1)/2$.
Any postage $\geq$ $0.12 with $0.05 and $0.04 stamps.
Sum of odd numbers: $1+3+\ldots + (2n-1) = n^2$.
$5|6^n-1$
$5|11^n-6$
$1^2+2^2+3^2+\ldots +n^2 = n(n+1)(2n+1)/6$
$n=3x+5y, n\geq 8$
$12|(n^4-n^2)$
$1+2+4+\ldots +2^n = 2^{n+1}-1$
$(1+x)^n\geq 1+nx$.