Math 109 Spring 2022
Terminology

Updated 5/17/22

The following terms are taken from your textbook, "An Introduction to Mathematical Reasoning: numbers, sets and functions" by Peter J. Eccles. The terms are organized by chapter.

For each term, you should be able to 1) supply a definition, 2) exhibit an example, and, when appropriate, 3) exhibit a non-example. The vocabulary is fundamental and forms the foundation of this subject.

• Part I: Mathematical statements and proofs
  • Chapter 1: The language of mathematics
    • proposition
    • predicate
      • free variable(s)
    • logical connective
      • or, disjunction
      • and, conjunction
      • negation
    • truth table
  • Chapter 2: Implications
    • implication
      • hypothesis, antecedent
      • conclusion, consequent
    • universal implication
    • existence statement
    • P ⇒ Q
      • If P, then Q.
      • P implies Q.
      • Q if P.
      • P only if Q.
      • Q whenever P.
      • P is sufficient for Q.
      • Q is necessary for P.
    • converse
    • P ⇔ Q
      • P is equivalent to Q.
      • P is necessary and sufficient for Q.
      • P if and only if Q.
      • P precisely when Q.
    • field axioms
      • commutativity
      • associativity
      • distributivity
      • zero, additive identity
      • unity, multiplicative identity
      • subtraction, additive inverse
      • division, multiplicative inverse
  • Chapter 3: Proofs
    • direct proof
    • order axioms
      • trichotomy law
      • addition law
      • multiplication law
      • transitive law
    • proof by cases
    • constructing proofs backwards
  • Chapter 4: Proof by contradiction
    • non-existence result
    • contradiction
    • proving negative statements by contradiction
    • proving implications by contradiction
    • contrapositive
    • proof by contrapositive
    • Notes:
      • A proof by contradiction is also called an indirect proof.
      • A proof by contrapositive is considered to be a direct proof.
  • Chapter 5
    • the induction principle
    • base case
    • inductive step
    • inductive hypothesis
    • definition by induction
    • n!, n factorial, factorial n
    • the strong induction principle
    • Fibonacci numbers
    • Binet formula
• Part II
  • Chapter 6
    • set
    • elements, members, points
    • ∈, is an element of
    • conditional definition of a set
    • constructive definition of a set
    • equality of sets
    • ∅, empty set
    • ⊆, is a subset of
    • ⊂, is a proper subset of
    • ⋂, intersection
    • disjoint
    • ⋃, union
    • A - B, difference of A and B, complement of B in A
    • P(X), power set of X
    • A^c, complement of A
    • associativity
    • commutativity
    • distributivity
    • DeMorgan laws
    • complementation
    • double complement
  • Chapter 7
    • universal statement; universal quantifier
    • existential statement; existential quantifier
    • negation of a universal statement
      • disproving statements of the form ∀ a ∈ A, P(a)
    • negation of an existential statement
      • disproving statements of the form ∃ a ∈ A, P(a)
    • Cartesian product, X × Y
      • ordered pair, coordinates
  • Chapter 8
    • function
    • image, value
    • domain
    • codomain
    • constant function
    • identity function
    • formula
    • modulus function (absolute value function)
    • equal, f = g
    • restriction of f to A
    • composite
    • commutative (or not)
    • sequence
    • null sequence
    • image (of a function)
    • graph (of a function)
  • Chapter 9
    • injection, injective
    • surjection, surjective
    • bijection, bijective
    • pre-image
    • invertible
    • inverse (function)
    • Functions and subsets
    • Peano's axioms
    • successor function
• Part III
  • Chapter 10
    •   cardinality of X,   ∣ X ∣
    •   finite set
    •   infinite set
    •   the addition principle
    •   the multiplication principle
    •   the inclusion-exclusion principle
  • Chapter 11
    •   the pigeonhole principle
    •   minimum element of a set A ⊆ ℝ
    •   maximum element of a set A ⊆ ℝ
  • Chapter 12
    •   Fun(X,y), the set of functions from X to Y
    •   Inj(X,y), the set of injections from X to Y
    •   permutation
    •   cardinality of P(X), the power set of X
    •   r-subset
    •   P_r(X), the set of r-subsets of X
    •   binomial coefficient
    •   the binomial theorem
  • Chapter 13
    •  
  • Chapter 14
    •   equipotent
    •   denumerable, cardinality &alef sym;₀
    •   countable
    •   uncountable
    •   Dedekind's theorem
    •   ℚ is denumerable
    •   ℝ is uncountable
    •   the continuum hypothesis
    •   ∣ X ∣ < ∣ P(X) ∣
• Part IV
  • Chapter 15
    • The division theorem
    • quotient
    • remainder
    • existence theorem
    • uniqueness theorem
  • Chapter 16
    • greatest common divisor, gcd(a,b)
    • Euclidean algorithm
    • Lamé's theorem^*
  • Chapter 17
    • integral linear combination
    • greatest common divisor (alternative definition)
    • coprime
• Part V
  • Chapter 19
    • congruent modulo m
    • reflexive property
    • symmetric property
    • transitive property
    • remainders modulo m, residues modulo m
    • remainder map
  • Chapter 20
    • linear congruence
    • diophantine equation
  • Chapter 21
    • congruence classes modulo m
    • congruence class of a modulo m,   [a]_m
    • set of congruence classes modulo m,   ℤ_m
    • arithmetic of congruence classes
      • addition of elements of ℤ_m
      • subtraction of elements of ℤ_m
      • multiplication of elements of ℤ_m
    • arithmetic of remainders
      • addition of elements of R_m
      • subtraction of elements of R_m
      • multiplication of elements of R_m
    • [a]_m invertible,   a invertible modulo m
    • inverse of [a]_m,   inverse of a modulo m
  • Chapter 22
    •   partition
    •   relation, a ∼ b
    •   reflexive
    •   symmetric
    •   equivalence relation
    •   equivalence class of a, [a]