The Cartesian product is not commutative. In general, A × B ≠ B × A. The pairs are ordered, so switching the components produces a different set.

Some books define A × B × C as ((A × B) × C). Others define it as the set of 3-tuples (a, b, c). Either way, they represent the same information, and there is a natural one-to-one correspondence between ((a, b), c) and (a, b, c). Just be aware of which convention your course uses.

Convention: throughout this module, ℕ = {0, 1, 2, ...} (the natural numbers include 0).

A relation is not the same thing as a function. A relation has no restriction on how many outputs a single input can have, and not every input needs to have an output. Functions add two extra rules, which we cover in the next section.

A function f : A → B is itself a set — specifically a subset of A × B. The pairs in f are points in the plot of f(x). This is why we can talk about function equality using set equality.

Common mistakes when checking if something is a function:

1. Forgetting to check EVERY input — if even one element of A has no output, it is not a function.

2. Thinking two inputs can't share the same output — they can! Only two outputs from the same input is a problem.

3. Thinking every element of B must be "used" — that is not required for a function (though it is required for a surjection, which we cover later).

Two functions are equal if they have the same domain and give the same output for every input. The codomain is part of the declaration but not part of the set of pairs, so it does not affect equality.

In this course, we treat a function mainly by its domain and input→output rule (equivalently, its graph). That is why two functions can count as 'the same' if they agree on every input, even if a textbook lists different codomains.

To prove a function is injective, you can use the contrapositive: a ≠ b implies f(a) ≠ f(b). Sometimes this direction is easier to work with. Both statements say the same thing.

Common mistake: thinking "injective" means every element of B is used. That is surjectivity, not injectivity. Injective is about inputs being distinguishable from their outputs. Elements of B that are not "hit" are perfectly fine for an injection.

A function is surjective if and only if its range equals its codomain. Equivalently: range(f) = B.

Common mistake: confusing surjective with injective.

Injective = no two inputs share an output (look at B: at most one arrow into each element).

Surjective = every output is used (look at B: at least one arrow into each element).

A function can be one without the other, both, or neither.

Note on f(x) = 2x: Over ℝ → ℝ this is a bijection because for every real y, there is a real x = y/2. However, if we consider f : ℤ → ℤ instead, then f(x) = 2x is injective but not surjective (for example, 1 has no integer preimage under doubling). The choice of domain and codomain matters!

This is a great way to remember the difference:

Injection → "no sharing" (each office has at most 1 teacher)

Surjection → "no empties" (each office has at least 1 teacher)

Bijection → "no sharing and no empties" (each office has exactly 1 teacher)

This is a common exam technique: if a function fails to be bijective, the question may ask you to adjust the domain or codomain to make it work. The key is to:

1. Identify whether the problem is with injectivity (domain too big) or surjectivity (codomain too big).

2. Restrict the appropriate set to match the function's actual behavior.

Key requirement: Only bijections have inverse functions.

If f is not a bijection, then f⁻¹ is not a function.

- If f is not injective: some output y came from two different inputs. Then f⁻¹(y) would need to produce two values, violating Rule 2.

- If f is not surjective: some element y ∈ B was never reached. Then f⁻¹(y) has no value, violating Rule 1.

Common mistake: writing f⁻¹ for a function that is not a bijection. Always check that f is both injective and surjective before claiming f⁻¹ exists as a function.

Also note: f⁻¹ is NOT the same as 1/f(x). The notation f⁻¹ means the inverse function, not the reciprocal.

Important notes about composition:

1. The order matters: f ∘ g means "apply g first, then f." Read it right-to-left.

2. f ∘ g is only defined when the range of g is compatible with the domain of f. Specifically, g maps into B, and f takes inputs from B.

3. f ∘ g may exist even when g ∘ f does not.

Common mistake: reading f ∘ g as "f then g." It is the opposite! f ∘ g means g first, then f. The function closest to x in f(g(x)) is applied first.

The bijectivity theorem follows directly from the other two: if both components are injective (so the composition is injective) and both are surjective (so the composition is surjective), then the composition is bijective.

The result (f ∘ g)⁻¹ = g⁻¹ ∘ f⁻¹ is sometimes called the "socks and shoes" rule. To undo putting on socks then shoes, you take off shoes first, then socks. The order reverses!

The Cantor-Schröder-Bernstein theorem is especially useful for infinite sets, where constructing an explicit bijection can be very difficult. Finding two injections (one in each direction) is often much easier.

Summary of cardinality results:

Countably infinite (same size as ℕ): ℕ, ℤ⁻, ℤ, ℚ

Uncountably infinite (strictly bigger than ℕ): ℝ

The key idea: |ℕ| = |ℤ| = |ℚ| < |ℝ|.

It seems surprising that ℤ and ℚ are the "same size" as ℕ, but this is what the formal definition via bijections gives us.

Common mistake: assuming that because ℤ or ℚ "looks bigger" than ℕ, it must have a larger cardinality. Cardinality is about the existence of bijections, not about how the sets "look." As long as you can pair up all the elements one-to-one, the sets have the same cardinality.

Exam tips for functions:

1. Always state which rule is violated when something is not a function (Rule 1 or Rule 2).

2. To disprove a statement, one counterexample is enough.

3. To prove injectivity, start with "Assume f(a) = f(b)" and show a = b.

4. To prove surjectivity, start with "Let y ∈ B" and find an x ∈ A with f(x) = y.

5. For composition, always check domain/range compatibility before computing.

6. Remember: f⁻¹ only exists when f is a bijection.

7. Check the domain carefully — a formula might look problematic but be safe on the given domain (like (x² − 2)⁻¹ on ℤ).