Lecture 1: Sets, Functions, Logic, and Proofs

1 Sets

1.1 Definition and Operations

A set is a collection of objects which we call elements. We typically denote sets by capital letters and elements by lowercase letters. If $x$ is an element of a set $A$, we write $x\in A$. If $x$ is not an element of $A$, we write $x\notin A$. For example, if $A=\{1,2,3\}$, then $1\in A$ and $4\notin A$.

There are multiple ways to describe a set. One is to list its elements, as in $A=\{1,2,3\}$. Another is to describe a property that characterizes its elements, as in $B=\{x\in\mathbb R:x>0\}$, which is the set of positive real numbers.

Some examples of sets include:

• The empty set $\emptyset$.

• The set of integers $\mathbb Z=\{\ldots,-2,-1,0,1,2,\ldots\}$.

• The set of real numbers $\mathbb R$.

• The set of natural numbers $\mathbb N=\{1,2,3,\ldots\}$.

• The set of rational numbers $\mathbb Q=\{p/q:p\in\mathbb Z,q\in\mathbb Z\setminus\{0\}\}$.

• The set of all subsets of a finite set $S$, called the power set and denoted $2^S$.

For example, the statements $$\{1,2\}\subseteq\{1,2,3\}, \qquad \{1,2,3\}=\{3,2,1\}, \qquad \mathbb Z\subset\mathbb R, \qquad \mathbb N\subset\mathbb Z$$ are all true. Furthermore, for any set $S$, we have $\emptyset\subseteq S$ and $S\subseteq S$.

These operations are called union, intersection, and set difference. They are typically illustrated by Venn diagrams:

Of course, we can also define the union and intersection of more than two sets. Given a collection of sets $\{A_i\}_{i\in I}$ indexed by a set $I$, we define $$\bigcup_{i\in I}A_i=\{x:x\in A_i\text{ for some }i\in I\}, \qquad \bigcap_{i\in I}A_i=\{x:x\in A_i\text{ for every }i\in I\}.$$

The following theorem summarizes some properties of aforementioned set operations. Its proof is left as an exercise.

We say that sets are disjoint if their intersection is empty. For example, the sets of even and odd integers are disjoint. A partition of a set $S$ is a collection of nonempty, pairwise disjoint subsets of $S$ whose union is $S$. For example, the sets of even and odd integers form a partition of $\mathbb Z$.

1.2 Cartesian Product and $\mathbb R^n$

For example, if $A=\{1,2\}$ and $B=\{x,y\}$, then $$A\times B=\{(1,x),(1,y),(2,x),(2,y)\}.$$ The product $A_1\times\cdots\times A_n$ consists of tuples $(a_1,\ldots,a_n)$ satisfying $a_i\in A_i$ for every $i$. An $n$-fold product of a set $A$ with itself is denoted $A^n=A\times\cdots\times A$.

The most commonly used in economics example of an $n$-fold product is $\mathbb R^n$. In this course, we treat elements of $\mathbb R^n$ as column vectors: $$x=\begin{pmatrix}x_1\\\vdots\\x_n\end{pmatrix}\in\mathbb R^n,$$ but that convention is not important until we discuss linear algebra.

Sometimes we need to compare vectors in $\mathbb R^n$. While not all vectors are comparable, we can compare them coordinatewise.

2 Functions

2.1 Vocabulary and properties

For a function $f:X\to Y$, we call $X$ the domain and $Y$ the codomain. For a subset $A \subseteq X$ of the domain, the image of $A$ is the set $$f(A)=\{f(x):x\in A\}\subseteq Y$$ of values taken by $f$ on $A$. In particular, we call $f(X)$ the range of $f$. The preimage of a subset $B\subseteq Y$ of the codomain is the set $$f^{-1}(B)=\{x\in X:f(x)\in B\}\subseteq X$$ of points in the domain that map into $B$. The graph of $f$ is the set of pairs $$\{(x,f(x)):x\in X\}\subseteq X\times Y.$$

Injectivity says that distinct points of the domain have distinct values, and surjectivity says that every $y\in Y$ equals $f(x)$ for at least one $x\in X$. The two conditions are checked in opposite directions: injectivity starts from two points of $X$ and compares their values, while surjectivity starts from a point of $Y$ and asks for a point of $X$ that reaches it.

Note that whether a function is surjective depends on the declared domain and codomain. For example, the function $f(x) = x^2$ is not surjective if $f:\mathbb R\to\mathbb R$ but surjective if $f:\mathbb R\to \mathbb{R}_{+}$. On the other hand, the function $g(x)=x^3$ is surjective if $g: \mathbb{R} \to \mathbb{R}$ or $g: \mathbb{R}_+ \to \mathbb{R}_+$.

2.2 Inverse Function

Let $f:X\to Y$ be a function and let $y\in Y$. Recalling the definition of a preimage, let us consider the set $f^{-1}(\{y\})$, which contains all elements of $X$ that map to the point $y$. In general, this set may be empty, contain one point, or contain multiple points. By Definition 2.2, if $f$ is surjective, then $f^{-1}(\{y\})$ contains at least one point for every $y\in Y$, and if $f$ is injective, then it contains at most one point. Consequently, if $f$ is bijective, then it contains exactly one point. This allows us to slightly abuse notation and define $f^{-1}(y)$ to be the unique point of $X$ that maps to $y$, so that $f^{-1}(\{y\})=\{f^{-1}(y)\}$.

The function $f$ and its inverse $f^{-1}$ undo each other, in the sense that $$f^{-1}(f(x))=x\ \text{ for every }x\in X, \qquad f(f^{-1}(y))=y\ \text{ for every }y\in Y.$$

The theorem below shows that if we tried to define an “inverse” for a function that is not bijective, we would fail.

3 Logic

3.1 Logical Statements and Operations

A statement (also referred to as a proposition or an assertion) is a sentence that is either true or false. For example, “$2+2=4$” is a true statement and “$2+2=5$” is a false one.

Given a statement $P$, its negation $\lnot P$ is true if and only if $P$ is false. Given two statements $P$ and $Q$, their conjunction $P\wedge Q$ is true if and only if both $P$ and $Q$ are true, while their disjunction $P\vee Q$ is true if and only if at least one of $P$ or $Q$ is true. We typically illustrate these logical operations with truth tables: $$\begin{array}{c|c} P&\lnot P\\ \hline T&F\\ F&T \end{array} \qquad \begin{array}{cc|c} P&Q&P\wedge Q\\ \hline T&T&T\\ T&F&F\\ F&T&F\\ F&F&F \end{array} \qquad \begin{array}{cc|c} P&Q&P\vee Q\\ \hline T&T&T\\ T&F&T\\ F&T&T\\ F&F&F \end{array}$$

3.2 Implication and equivalence

Perhaps the most important logical operation is implication. We define it via a truth table as follows: $$\begin{array}{cc|c} P&Q&P\Rightarrow Q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ F&F&T \end{array}$$

The implication $P\Rightarrow Q$ is read “$P$ implies $Q$,” or “if $P$, then $Q$,” or “$P$ is sufficient for $Q$,” or “$Q$ is necessary for $P$.” Its converse is $Q\Rightarrow P$, and its contrapositive is $\lnot Q\Rightarrow\lnot P$. If $P\Rightarrow Q$ and $Q\Rightarrow P$ both hold, we write $P\Leftrightarrow Q$ and say that $P$ and $Q$ are equivalent, or $P$ if and only if (IFF) $Q$.

Our first proof involves showing that an implication and its contrapositive are equivalent.

Note that an implication $P\Rightarrow Q$ and its converse $Q\Rightarrow P$ are not equivalent. Showing that is left as an exercise, along with proving the following negation rules for statements.

3.3 Properties and quantifiers

Given a set $X$, a property on $X$ is a sentence $P(x)$ that becomes either true or false (hence a statement) once a particular $x \in X$ is specified. For instance, if $X = \mathbb{Z}$ and $P(x)$ is “$x$ is even,” then $P(2)$ is true and $P(3)$ is false.

To turn a property into a statement, we use quantifiers. The universal quantifier $\forall$ means “for every” and the existential quantifier $\exists$ means “there exists.” Continuing the example above, the statement $$\forall x\in\mathbb Z,\ P(x)$$ is false, since $3$ is not even, while the statement $$\exists x\in\mathbb Z,\ P(x)$$ is true, since $2$ is even.

For example, $A\subseteq B$ means $\forall x\,(x\in A\Rightarrow x\in B)$. Its negation is $$\exists x\,(x\in A\text{ and }x\notin B).$$

4 Proofs

4.1 What a proof is

A theorem is a statement that has been shown to be true, and a proof is the argument that shows it. Hammack’s Book of Proof describes a proof as follows:

“A proof of a theorem is a written verification that shows that the theorem is definitely and unequivocally true. A proof should be understandable and convincing to anyone who has the requisite background and knowledge.”

A proof is typically written in ordinary prose plus mathematical notation. However, every step in a proof must be justified by something already accepted: a hypothesis of the theorem, a definition, a result established earlier, or a rule of logic. Proofs are often accompanied by pictures, but a picture usually does not replace a formal argument.

4.2 Direct proof

In a direct proof of an implication $P\Rightarrow Q$, we assume $P$ and derive $Q$. In a direct proof of a universal statement $\forall x\in X,\ P(x)$, we let $x\in X$ be arbitrary, meaning that nothing is assumed about $x$ beyond $x\in X$, and derive $P(x)$; since the argument used no property of $x$, it applies to every element of $X$.

Below is one example of a direct proof. It uses the following vocabulary: an integer $n$ is even if $n=2a$ for some $a\in\mathbb Z$, and odd if $n=2a+1$ for some $a\in\mathbb Z$. Every integer is even or odd, and no integer is both; we take that as given.

A proof by contrapositive of $P\Rightarrow Q$ is a direct proof of $\lnot Q\Rightarrow\lnot P$: we assume $\lnot Q$ and derive $\lnot P$. By Theorem 3.1 the two implications are equivalent, so proving either one proves the other. It is worth switching when the negations are the easier statements to work with.

Here is a second proof of Lemma 4.1, this time by contrapositive. Its hypothesis is that $-5n-3$ is not odd, hence even, and its conclusion is that $n$ is not even, hence odd.

4.3 Proof by contradiction

A proof by contrapositive requires the statement to be an implication. A proof by contradiction applies to a statement of any shape. To prove a statement $S$, we assume that $S$ is false, and from that assumption we derive some statement $C$ together with its negation $\lnot C$. Whatever $C$ may be, the statement $C\wedge\lnot C$ is false, so the assumption cannot hold and $S$ is true. The method is also called reductio ad absurdum: supposing the opposite of what we want reduces us to an absurdity.

The proof by contradiction is justified by the equivalence $$S\iff\left(\lnot S\Rightarrow(C\wedge\lnot C)\right),$$ which holds for every statement $C$: showing that $\lnot S$ leads to a contradiction is the same as showing that $S$ is true. Verifying the equivalence with a truth table, as in the proof of Theorem 3.1, is left as an exercise.

When the statement to be proved is an implication $P\Rightarrow Q$, its negation is $P\wedge\lnot Q$ by Theorem 3.2, so the proof begins by assuming both $P$ and $\lnot Q$. Which statement $C$ will do the job is usually not known at the outset: we assume the negation, derive consequences, and stop once some statement and its negation are both on the page. Often the statement contradicted is one assumed at the start, a hypothesis or the negated conclusion, and sometimes it is a fact known independently.

4.4 Proof by induction

Some statements come indexed by the natural numbers: for each $n\in\mathbb N$ there is a statement $P(n)$, and the claim is that $P(n)$ holds for every $n$. The following theorem reduces that claim, which involves infinitely many statements, to two checks.

Condition (1) is the base step and condition (2) is the induction step; the assumption $P(n)$ made while proving the induction step is the induction hypothesis. The two conditions act like a line of dominoes: the first one falls by (1), and each one that falls knocks over the next by (2), so all of them fall.

The induction step is itself a universal implication, so it is proved directly: let $n\in\mathbb N$ be arbitrary, assume $P(n)$, and derive $P(n+1)$.