\( \newcommand{\vect}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

M01.6 · Sets, logic and proof techniques

A free, illustrated module of 4 lessons and one interactive in M01 Math Foundations: Sets and Venn diagrams; Statements and logic: and, or, not, if-then; Direct proof and counterexample; Contradiction and induction.

M01.6 L0 · Foundation 4 lessons · about 100 min Live · in review

Part of M01 Math Foundations in the Mathematics track.

A training set and a test set must share no example, a filter on a table must keep exactly the right rows, and a claim about every input must hold for inputs nobody has tried. These four lessons give the language and the tools for all three: sets drawn as regions of a Venn diagram, statements combined with and, or, not and if-then, and four ways of proving a claim for good, by a direct chain of reasoning, by cases, by contradiction and by induction, with a single counterexample to sink a claim that is false.

What you need first. The kinds of numbers, the order of operations, inequalities and the expansion of (a + b) squared (M01.1). A little Python for the code sections: loops, functions, importing a module, and lists, tuples and sets (P01.3 to P01.6), each line of which is explained as it appears.

Lessons

Sets and Venn diagrams M01.6.1 25 min

A set is a collection with no order and no repeats. Learn to write sets down, to combine two of them by union, intersection, difference and complement, to see each result as a region of a Venn diagram, and to check De Morgan’s laws region by region.
Statements and logic: and, or, not, if-then M01.6.2 25 min

A statement is either true or false. Learn and, or, not and if-then through their truth tables, why a converse can fail while a contrapositive cannot, and why logic is the algebra of sets, so that De Morgan’s laws repair a broken filter on a table of data.
Direct proof and counterexample M01.6.3 25 min

Forty examples in a row can still mislead. Learn the difference between claims about every case and claims that some case exists, why one counterexample is enough to sink a claim about every case, and how a direct proof chains definitions to a conclusion with every link justified.
Contradiction and induction M01.6.4 25 min

Two more ways to settle a claim about infinitely many cases: suppose it false and reach the impossible, or climb from each case to the next. Prove that the square root of 2 is not a fraction and that the first n odd numbers add up to n squared, and see how induction shows a loop is correct.

The interactive

M01.6-X1 · Venn and truth-table explorer. Pick an expression in A and B, such as a union, a complement or either side of De Morgan’s laws, or tap regions of the diagram yourself. The matching regions shade, the numbers 1 to 8 sort into the set or out of it, the matching rows of the truth table light up, and the read-out names the set in symbols and in words. It lives in Statements and logic: and, or, not, if-then.