Skip to main content
Elementary Foundations:
An introduction to topics in discrete mathematics
Jeremy Sylvestre
x
Search Results:
No results.
☰
Contents
Index
You!
Choose avatar
▻
✔️
You!
😺
👤
👽
🐶
🐼
🌈
Font family
▻
✔️
Open Sans
AaBbCc 123 PreTeXt
Roboto Serif
AaBbCc 123 PreTeXt
Adjust font
▻
Size
12
Smaller
Larger
Width
100
narrower
wider
Weight
400
thinner
heavier
Letter spacing
0
/200
closer
f a r t h e r
Word spacing
0
/50
smaller gap
larger gap
Line Spacing
135
/100
closer
together
further
apart
Light/dark mode
▻
✔️
default
pastel
twilight
dark
midnight
Reading ruler
▻
✔️
none
underline
L-underline
grey bar
light box
sunrise
sunrise underline
Motion by:
✔️
follow the mouse
up/down arrows - not yet
eye tracking - not yet
<
Prev
^
Up
Next
>
🔍
\(\require{cancel} \newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}} \newcommand{\bbrac}[1]{\bigl(#1\bigr)} \newcommand{\Bbrac}[1]{\Bigl(#1\Bigr)} \newcommand{\correct}{\boldsymbol{\checkmark}} \newcommand{\incorrect}{\boldsymbol{\times}} \newcommand{\inv}[2][1]{{#2}^{-{#1}}} \newcommand{\leftsub}[3][1]{\mathord{{}_{#2\mkern-#1mu}#3}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\I}{\mathbb{I}} \newcommand{\abs}[1]{\left\lvert #1 \right\rvert} \DeclareMathOperator{\sqrtop}{sqrt} \newcommand{\lgcnot}{\neg} \newcommand{\lgcand}{\wedge} \newcommand{\lgcor}{\vee} \newcommand{\lgccond}{\rightarrow} \newcommand{\lgcbicond}{\leftrightarrow} \newcommand{\lgcimplies}{\Rightarrow} \newcommand{\lgcequiv}{\Leftrightarrow} \newcommand{\lgctrue}{\mathrm{T}} \newcommand{\lgcfalse}{\mathrm{F}} \newcommand{\boolnot}[1]{{#1}'} \newcommand{\boolzero}{\mathbf{0}} \newcommand{\boolone}{\mathbf{1}} \newcommand{\setdef}[2]{\left\{\mathrel{}#1\mathrel{}\middle|\mathrel{}#2\mathrel{}\right\}} \newcommand{\inlinesetdef}[2]{\{\mathrel{}#1\mathrel{}\mid\mathrel{}#2\mathrel{}\}} \let\emptyword\emptyset \renewcommand{\emptyset}{\varnothing} \newcommand{\relcmplmnt}{\smallsetminus} \newcommand{\union}{\cup} \newcommand{\intersection}{\cap} \newcommand{\cmplmnt}[1]{{#1}^{\mathrm{c}}} \newcommand{\disjunion}{\sqcup} \newcommand{\cartprod}{\times} \newcommand{\words}[1]{{#1}^\ast} \newcommand{\length}[1]{\abs{#1}} \newcommand{\powsetbare}{\mathcal{P}} \newcommand{\powset}[1]{\powsetbare(#1)} \newcommand{\funcdef}[4][\to]{#2\colon #3 #1 #4} \newcommand{\ifuncto}{\hookrightarrow} \newcommand{\ifuncdef}[3]{\funcdef[\ifuncto]{#1}{#2}{#3}} \newcommand{\sfuncto}{\twoheadrightarrow} \newcommand{\sfuncdef}[3]{\funcdef[\sfuncto]{#1}{#2}{#3}} \newcommand{\funcgraphbare}{\Delta} \newcommand{\funcgraph}[1]{\funcgraphbare(#1)} \newcommand{\relset}[3]{#1_{{} #2 #3}} \newcommand{\gtset}[2]{\relset{#1}{\gt}{#2}} \newcommand{\posset}[1]{\gtset{#1}{0}} \newcommand{\geset}[2]{\relset{#1}{\ge}{#2}} \newcommand{\nnegset}[1]{\geset{#1}{0}} \newcommand{\neqset}[2]{\relset{#1}{\neq}{#2}} \newcommand{\nzeroset}[1]{\neqset{#1}{0}} \newcommand{\ltset}[2]{\relset{#1}{\lt}{#2}} \newcommand{\leset}[2]{\relset{#1}{\le}{#2}} \newcommand{\natnumlt}[1]{\ltset{\N}{#1}} \DeclareMathOperator{\id}{id} \newcommand{\inclfunc}[2]{\iota_{#1}^{#2}} \newcommand{\projfunc}[1]{\rho_{#1}} \DeclareMathOperator{\proj}{proj} \newcommand{\funcres}[2]{\left.{#1}\right\rvert_{#2}} \newcommand{\altfuncres}[2]{\left.{#1}\right\rvert{#2}} \DeclareMathOperator{\res}{res} \DeclareMathOperator{\flr}{flr} \newcommand{\floor}[1]{\lfloor {#1} \rfloor} \newcommand{\funccomp}{\circ} \newcommand{\funcinvimg}[2]{\inv{#1}\left({#2}\right)} \newcommand{\card}[1]{\left\lvert #1 \right\rvert} \DeclareMathOperator{\cardop}{card} \DeclareMathOperator{\ncardop}{\#} \newcommand{\EngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \mathrm{c}, \, \dotsc, \, \mathrm{y}, \, \mathrm{z} \}} \newcommand{\ShortEngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \dotsc, \, \mathrm{z} \}} \newcommand{\eqclass}[1]{\left[#1\right]} \newcommand{\partorder}{\preceq} \newcommand{\partorderstrict}{\prec} \newcommand{\npartorder}{\npreceq} \newcommand{\subgraph}{\preceq} \newcommand{\subgraphset}[1]{\mathcal{S}(#1)} \newcommand{\connectedsubgraphset}[1]{\mathcal{C}(#1)} \newcommand{\permcomb}[3]{{#1}(#2,#3)} \newcommand{\permcombalt}[3]{{#1}^{#2}_{#3}} \newcommand{\permcombaltalt}[3]{{\leftsub{#2}{#1}}_{#3}} \newcommand{\permutation}[2]{\permcomb{P}{#1}{#2}} \newcommand{\permutationalt}[2]{\permcombalt{P}{#1}{#2}} \newcommand{\permutationaltalt}[2]{{\permcombaltalt{P}{#1}{#2}}} \newcommand{\combination}[2]{\permcomb{C}{#1}{#2}} \newcommand{\combinationalt}[2]{\permcombalt{C}{#1}{#2}} \newcommand{\combinationaltalt}[2]{{\permcombaltalt{C}{#1}{#2}}} \newcommand{\choosefuncformula}[3]{\frac{#1 !}{#2 ! \, #3 !}} \DeclareMathOperator{\matrixring}{M} \newcommand{\uvec}[1]{\mathbf{#1}} \newcommand{\zerovec}{\uvec{0}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)
Front Matter
Colophon
Author Biography
I
Logic
1
Symbolic language
1.1
Statements
1.2
Converting language to symbols
1.3
Logical analysis
1.4
Tautologies and contradictions
1.5
Activities
1.6
Exercises
2
Logical equivalence
2.1
Equivalence
2.2
Propositional calculus
2.3
Converse, inverse, and contrapositive
2.4
Activities
2.5
Exercises
3
Boolean algebra
3.1
Boolean polynomials
3.2
Disjunctive normal form
3.3
Exercises
4
Predicate logic
4.1
Predicates and quantifiers
4.2
Manipulating quantified statements
4.2.1
Negation of quantified statements
4.2.2
Distributing quantifiers
4.3
Vacuously true statements
4.4
Activities
4.5
Exercises
5
Arguments
5.1
Basics
5.2
Standard arguments
5.2.1
Modus ponens
5.2.2
Modus tollens
5.2.3
Law of Syllogism
5.3
Substituting into an argument
5.4
Activities
II
Logic in Mathematics
6
Definitions and proof methods
6.1
Definitions
6.2
Common mathematical statements
6.3
Direct proof
6.4
Reduction to cases
6.5
Statements involving disjunction
6.6
Proving the contrapositive
6.7
Proof by counterexample
6.8
Proving biconditionals
6.9
Proof by contradiction
6.10
Existence and uniqueness
6.11
Activities
6.12
Exercises
7
Proof by mathematical induction
7.1
Principle of Mathematical Induction
7.2
An application to logic
7.3
Strong form of Mathematical Induction
7.4
Activities
8
Axiomatic systems
8.1
Basics and examples
8.2
Incompleteness of axiomatic systems
8.3
Exercises
III
Set Theory
9
Sets
9.1
Basics
9.2
Defining sets
9.2.1
Listing elements
9.2.2
Candidate-condition notation
9.2.3
Form-parameter notation
9.2.4
Empty set
9.3
Subsets and equality of sets
9.4
Complement, union, and intersection
9.4.1
Universal and relative complement
9.4.2
Union, intersection, and disjoint sets
9.4.3
Rules for set operations
9.5
Cartesian Product
9.5.1
Definition and examples
9.5.2
Visualizing Cartesian products
9.6
Alphabets and words
9.7
Sets of sets
9.8
Activities
9.9
Exercises
10
Functions
10.1
Basics
10.1.1
Terminology and basic concepts
10.1.2
Defining functions
10.1.3
Graph of a function
10.1.4
Undefined and well-defined
10.1.5
Equality of functions
10.1.6
Image of a function
10.2
Properties of functions
10.3
Important examples
10.4
Composition of functions
10.5
Inverses
10.6
Activities
10.7
Exercises
11
Recurrence and induction
11.1
Sequences
11.2
Recurrence relations
11.3
Solving through iteration
11.4
Inductive definitions
11.5
Activities
11.6
Exercises
12
Cardinality
12.1
Finite sets
12.2
Properties of finite sets and their cardinality
12.2.1
Finite sets versus finite sequences
12.2.2
Finite sets versus bijections, subsets, and unions
12.2.3
Cardinality of power sets of finite sets
12.2.4
Infinite sets
12.3
Relative sizes of sets
12.4
Counting elements of finite sets with bijections
12.5
Activities
12.6
Exercises
13
Countable and uncountable sets
13.1
Basics and examples
13.2
Properties
13.3
More about relative sizes of sets
13.4
Activities
IV
Graph Theory
14
Graphs
14.1
Basics and examples
14.2
Properties of graphs
14.2.1
Properties of vertices and edges
14.2.2
Subgraphs
14.2.3
Complete graphs
14.3
Adding information to graphs
14.4
Important examples
14.5
Activities
14.6
Exercises
15
Paths and connectedness
15.1
Motivation
15.2
Walks, trails, and paths
15.3
Connected vertices, graphs, and components
15.4
Articulation vertices, bridges, and edge connectivity
15.5
Activities
15.6
Exercises
16
Trees and searches
16.1
Motivation
16.2
Basics
16.3
Identifying trees
16.4
Depth-first and breadth-first searches
16.5
Spanning trees
16.6
Binary searches
16.7
Activities
16.8
Exercises
V
More Set Theory
17
Relations
17.1
Basics
17.2
Operations on relations
17.3
Properties of relations
17.3.1
Reflexivity
17.3.2
Symmetry and antisymmetry
17.3.3
Transitivity
17.4
Graphing relations
17.5
Activities
17.6
Exercises
18
Equivalence relations
18.1
Motivation
18.2
Basics and examples
18.3
Classes, partitions, and quotients
18.4
Important examples
18.5
Graph for an equivalence relation
18.6
Activities
18.7
Exercises
19
Partially ordered sets
19.1
Motivation
19.2
Definition and examples
19.3
Graph for a partial order
19.4
Total orders
19.5
Maximal/minimal elements
19.6
Topological sorting
19.7
Activities
19.8
Exercises
VI
Combinatorics
20
Counting
20.1
Motivation
20.2
Addition and subtraction rules
20.3
Multiplication rule
20.4
Division rule
20.5
Pigeonhole principle
20.5.1
Regular strength version
20.5.2
Strong version
20.6
Activities
20.7
Exercises
21
Permutations
21.1
Factorials
21.2
Definition
21.3
Counting permutations
21.4
Permutations of subsets
21.5
Activities
22
Combinations
22.1
Motivation
22.2
Basics
22.3
Applications
22.3.1
Distributing/choosing indistinguishable objects
22.3.2
Counting edges in connected graphs
22.4
Properties
22.5
Activities
22.6
Exercises
23
Binomial and multinomial coefficients
23.1
Binomial coefficients
23.2
Multinomial Coefficients
23.3
Applications
23.4
Exercises
Back Matter
A
GNU Free Documentation License
B
Index of Notation
Index
Colophon
Author Biography
Author Biography
Jeremy Sylvestre is Associate Professor of Mathematics at the University of Alberta’s Augustana Campus.