Chapter 1 Sets, functions, 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 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 function, injective, one-to-one, surjective, onto, bijective, inverse function, left inverse, right inverse
• Determine properties of functions
• 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