2. Sets and Relations

Sets and relations are the most fundamental parts of mathematics . Informally, sets are simply collections of objects. From sets we build every other discrete structure, including, but not limited to, combinations, functions, relations, and graphs.

In this chapter we will explore the much of what sets has to offer. Sets as collections, sets as objects themselves, and relations as sets of pairs.

Much as how propositional and predicate logic has set the framework for the semantics of mathematical language, sets set (no pun intended) the framework for mathematical objects. Both logic and sets are the foundation on which the rest of discrete mathematics is built.

• 2.1. Sets and Set Theory
  • 2.1.1. Set Construction
    • Roster Method
    • Set Builder
    • Natural language description
    • Interval Notation
  • 2.1.2. Set Properties
    • Membership and Equality
    • Special Sets: Empty and Universal
    • Subsets
    • Size of a Set
    • Power Set
  • 2.1.3. Operations on Sets
    • Union and Intersection
    • Difference and Complement
      • Symmetric Difference
    • Cartesian Product
      • Tuples
  • 2.1.4. Proofs with Sets
    • Distribution
    • De Morgan’s Laws
  • 2.1.5. Exercises
• 2.2. Relations
  • 2.2.1. Binary Relations
    • Relations as Predicates
    • Constructing relations
  • 2.2.2. Properties of Relations
    • Reflexivity
    • Symmetry
    • Antisymmetry
    • Transitivity
  • 2.2.3. Equivalence Relations
    • Equivalence Classes
  • 2.2.4. Posets: Partially Ordered Sets
    • Total order
    • Hasse Diagram
  • 2.2.5. Exercises