Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 37 ยท Getting Started

Sets, Functions and Relations

Review the language of abstract algebra: sets, functions, injective and surjective maps, bijections and equivalence relations, with runnable checkers.

Abstract algebra is written in the language of sets and functions. This lesson reviews exactly the parts you will use again and again: set notation, the properties of functions, and equivalence relations, which are the tool for "gluing together" elements that behave alike.

Sets

A set is a collection of distinct objects, called elements. We write a โˆˆ A for "a is an element of A". Some sets used throughout the course:

Symbol Meaning
โ„ค the integers ..., -2, -1, 0, 1, 2, ...
โ„š the rational numbers (fractions)
โ„ the real numbers
โ„ค_n the integers 0, 1, ..., n-1 (remainders mod n)

For sets A and B, A โІ B means every element of A is in B. The Cartesian product A ร— B is the set of ordered pairs (a, b) with a โˆˆ A and b โˆˆ B. If A has m elements and B has k, then A ร— B has mยทk elements. Operations on a structure are functions out of such products, as you will see in the next lesson.

Functions

A function f: A โ†’ B assigns to each element of A exactly one element of B. A is the domain and B the codomain. Three properties matter:

  • Injective (one-to-one): different inputs give different outputs.
  • Surjective (onto): every element of B is an output.
  • Bijective: both. A bijection pairs up the two sets perfectly, so it has an inverse function.
Python Classify a function on finite sets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first function is onto but not one-to-one (0 and 3 both map to 0). The shift is a bijection. Squaring is one-to-one here but misses most of the codomain.

The composition g โˆ˜ f means "apply f first, then g": (g โˆ˜ f)(x) = g(f(x)). Composition is associative: (h โˆ˜ g) โˆ˜ f = h โˆ˜ (g โˆ˜ f). It is generally not commutative.

Equivalence relations

A relation on a set A is a rule a ~ b that is either true or false for each pair. It is an equivalence relation if it is:

  1. Reflexive: a ~ a for all a.
  2. Symmetric: if a ~ b then b ~ a.
  3. Transitive: if a ~ b and b ~ c then a ~ c.

Congruence mod n is the model example: a ~ b when n divides a - b. An equivalence relation splits the set into disjoint equivalence classes: the class of a is [a] = {x : x ~ a}. Every element is in exactly one class, so the classes form a partition.

Python Check an equivalence relation and list its classes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The relation โ‰ค is reflexive and transitive but not symmetric, so it is not an equivalence relation. Congruence mod 3 passes all three tests and produces exactly three classes.

flowchart TB
    Z["โ„ค"] --> C0["[0] = {..., -3, 0, 3, 6, ...}"]
    Z --> C1["[1] = {..., -2, 1, 4, 7, ...}"]
    Z --> C2["[2] = {..., -1, 2, 5, 8, ...}"]

Congruence mod 3 cuts the integers into three classes.

Whenever you meet a new relation, test the three properties in order. The one that usually fails is symmetry or transitivity, and a single counterexample is enough to disprove it.

Why this matters for algebra

Later you will build new structures by taking equivalence classes. โ„ค_n is exactly the set of classes of integers mod n. Cosets (lesson 15) are classes of an equivalence relation, and quotient groups are groups whose elements are those classes. Bijections that respect an operation, called isomorphisms, tell us when two structures are "the same".

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A function f: A โ†’ B is injective when:

    Injective means one-to-one: f(a) = f(a') forces a = a'.
  2. 2. Which pair of properties makes a function bijective?

    A bijection is both one-to-one and onto, which is exactly when an inverse function exists.
  3. 3. The relation a โ‰ค b on the integers fails to be an equivalence relation because it is not:

    1 โ‰ค 2 holds but 2 โ‰ค 1 does not, so symmetry fails.
  4. 4. How many equivalence classes does congruence mod 7 produce on the integers?

    The classes correspond to the remainders 0 through 6.

Summary

  • Sets, products and functions are the vocabulary of algebra; operations are functions on products.
  • Injective, surjective and bijective describe how a function pairs elements.
  • Composition of functions is associative but usually not commutative.
  • An equivalence relation is reflexive, symmetric and transitive, and partitions a set into classes.

Next: Binary Operations