Chapter 1 Sets, functions, relations, permutations

This section begins by introducing informal (“naive”) set theory as a way to reason about unordered collections of objects without repetition. We then look at relations and functions and their properties. Finally we introduce permutations of finite sets for later use both in linear algebra and as a fundamental example in the section on group theory.

Learning objectives for this section:

• Know the meaning of and symbols used for sets, containment, membership, unions, intersections, the empty set, set difference, complement, size/cardinality
• Understand when two sets are equal
• Be able to explain and use the laws of set algebra, including De Morgan’s laws, to compare and evaluate expressions in the language of set theory
• Understand inclusion-exclusion and use it to calculate set sizes
• Know the meaning of the terms relation, function, symmetric, transitive, reflexive, equivalence relation, partition, equivalence class, injective/one-to-one, surjective/onto, bijective, inverse function, left inverse, right inverse
• Explain the connection between equivalence classes and partitions
• Determine properties of functions and relations
• Understand notation used for permutations
• Know the definition of permutation, transposition, cycle, disjoint cycles, orbit of a permutation
• Know and be able to apply the result that permutations can be expressed as products of disjoint cycles, and as products of transpositions
• Be able to define and calculate products/compositions, inverses, signs, and the disjoint cycle decomposition of a permutation