0.1 Mathematical review

Basic set theory

We begin with a quick review of basic set theory from undergraduate courses.

Definition 1 A set is an unordered collection of objects denoted by a capital letter $A$ and written explicitly by listing its elements $A=\{a_1,a_2,...\}$ .

Definition 2 The union of two sets $A$ and $B$ is denoted by $A\cup B:=\{x:x\in A\vee x\in B\}$ . The intersection of two sets $A$ and $B$ is denoted by $A\cap B:=\{x:x\in A\wedge x\in B\}$ .

Definition 3 A set $A$ is contained in another set $B$ , denoted $A\subset B$ , if $x\in A\Rightarrow x\in B$ . Two sets $A$ and $B$ are equal if $x\in A\iff x\in B$ .

Definition 4 The complement of $A$ is the set $\tilde{A}:=\{x:x\notin A\}$ . The empty set is denoted by $\phi :=\left\{\right\}$ .

Definition 5 A set is finite if it has a finite number of elements. A set is countably infinite if there is a one-to-one relationship between its elements and the integers $\mathbb{Z}$ . A set is uncountably infinite if it is not finite or countably infinite.

Convexity

Definition 6 A set $A\subseteq X$ is convex if for all $x,y\in A$ all convex combinations of $x$ and $y$ are in $A$ , i.e., for all $0\le \alpha \le 1$ we have $\alpha x+(1-\alpha )y\in A$ .

Example 1 [link] below shows that the line $\overline{xy}$ (containing all convex combinations of $x$ and $y$ ) is included in $A$ ; since this is true for each $x,y\in A$ then the set $A$ is convex. Conversely, for the set $B$ we can find two points $u,v\in B$ such that the line $\overline{uv}$ is not completely contained in $B$ ; therefore, $B$ is not convex.

Fact 1 If A is convex then $\beta A=\left\{\beta ,X,:,x,\in ,A\right\}$ is convex for $\beta \ge 0$ .

Definition 7 The convex hull of a set $A\subseteq X$ is the smallest convex set S such that $A\subseteq S$

Example 2 Consider the set $A$ in [link] below, which is not convex. By adding to $A$ all points that are convex combinations of elements of $A$ but not in $A$ (i.e., the points in the shaded region), we obtain the convex hull of $A$ .

A set with a single element is always convex.