Definitions

  • A set is a collection \(A\) of objects, called elements.
  • A subset \(B\) of \(A\) is a set with the property that every element of \(B\) is also an element of \(A\)
  • The power set of \(A\) is the set of all subsets of \(A\)
  • A composition of \(n\) is a sequence of positive integers which add up to \(n\)
  • A partition of \(n\) is a decreasing sequence of positive integers which add up to \(n\)
  • A function \(f\) from \(A\) to \(B\) is something which assigns every element \(x\) of \(A\) to an element \(f(x)\) of \(B\)
  • If \(f\) is a function from \(A\) to \(B\) then \(A\) is called the domain and \(B\) is called the codomain.
  • A function \(f\) from \(A\) to \(B\) is injective or one-to-one if given \(x_1,x_2\in A\) with \(x_1\neq x_2\) we must have \(f(x_1)\neq f(x_2)\)
  • A function \(f\) from \(A\) to \(B\) is surjective or onto if for every \(y\in B\) there is some \(x\in A\) with \(f(x) = y\)
  • A function \(f\) from \(A\) to \(B\) is bijective if it is both injective and surjective
  • A set \(A\) has cardinality less than a set \(B\) if there exists an injective function from \(A\) to \(B\).
  • A set \(A\) has cardinality greater than a set \(B\) if there exists a surjective function from \(A\) to \(B\).
  • A set \(A\) has cardinality equal to a set \(B\) if there exists a bijective function from \(A\) to \(B\).
  • A set is called finite if it has finitely many elements
  • A set is called infinite if it has infinitely many elements
  • A set is called countable if it is finite or else has the same cardinality as \(\mathbb N\)
  • A set is called countably infinite if it is both countable and infinite, or equivalently if it has the same cardinality as \(\mathbb N\)
  • A set is called uncountable if it is not countable

Notation

  • \(\mathbb{N}\) is the set of natural numbers
  • \(\mathbb{Z}\) is the set of integers
  • \(\mathbb{Q}\) is the set of rational numbers
  • \(\mathbb{R}\) is the set of real numbers
  • \(x\in A\) means that \(x\) is an element of \(A\)
  • \(A\subseteq B\) means that \(A\) is a subset of \(B\)
  • \(f: A\rightarrow B\) means that \(f\) is a function from \(A\) to \(B\)
  • \(\lvert A\rvert\) means the number of elements in the set \(A\) or the “cardinality” of \(A\)
  • \(\mathcal P(A)\) means the power set of \(A\)