I. Foundations

I. Foundations #

Warm-up problems on proof by induction and on the set theory of images and inverse images that underlies everything to come.

Problem 1 #

A polygon is said to be convex if it contains the line segment connecting any two of its points. A polygon can be triangulated if its vertices can be connected to each other by non-intersecting line segments in such a way that the entire polygon is divided entirely into triangles.

Convex Not convex
In the convex polygon on the left, the segment connecting the two marked points — like the segment connecting any two of its points — stays entirely inside the polygon. The polygon on the right is not convex: the marked points both belong to the polygon, but the dashed portion of the segment connecting them leaves the polygon as it crosses the notch.

(a) Prove that every convex polygon can be triangulated. Hint: Use induction.

(b) Extra Credit: Can every polygon be triangulated? If not, exhibit a counterexample. If so, prove it.

Solutions: Hint · Solution · Long solution

Problem 2 #

The following result will be crucial when we start studying continuous functions. Suppose that we have a function \(f:X \to Y\) and that \(A \subset X\) and \(C \subset Y\). We define the image of \(A\) as the set

$$f(A)=\{\, y \in Y \mid f(x) = y \text{ for some } x \in A \,\},$$

and the inverse image of \(C\) as the set

$$f^{-1}(C) = \{\, x \in X \mid f(x) \in C \,\}.$$

Note that \(f\) need not be an invertible function for \(f^{-1}(C)\) to be defined! The following theorem says that the set operations of union, intersection, and set difference generally “behave well” with images and inverse images, except in two cases.

Theorem. Suppose that \(f: X \to Y\) is a function. Then

(a) if \(A, B \subset X\), then \(f(A \cup B) = f(A) \cup f(B)\);

(b) if \(A, B \subset X\), then \(f(A \cap B) \subset f(A) \cap f(B)\);

(c) if \(A, B \subset X\), then \(f(A \setminus B) \supset f(A) \setminus f(B)\);

(d) if \(C, D \subset Y\), then \(f^{-1}(C \cup D) = f^{-1}(C) \cup f^{-1}(D)\);

(e) if \(C, D \subset Y\), then \(f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)\);

(f) if \(C, D \subset Y\), then \(f^{-1}(C \setminus D) = f^{-1}(C) \setminus f^{-1}(D)\).

Prove that (b) and (c) of the theorem are true, and find a counterexample in each of these two cases that shows we don’t always have equality.

Solutions: Hint · Solution · Long solution