Mar 1, 2026
Mathematics is all about thinking clearly and following your nose, but it turns out to be remarkably difficult to do this in a rigorous manner.
Euclid introduced the notion of truth that could be proved from axioms that were assumed to be true. The Sophists before him were concerned with using language to shape reality. They figured out how to shut someone down by pointing out their argument was not valid.
Euclid was wrong. The Sophists were right(er). He lead humanity on a two millenium wild goose chase with his fifth postulate:
If a straight line falling on two straight lines makes the interior angles on the same side less than two right angles, then the two straight lines—if extended indefinitely—meet on that side on which the angles are less than two right angles.
Perhaps in the context of Euclid’s time this was lucid. A more modern statement by Playfair
In a plane, given a line and a point not on it, at most one line parallel to the given line can be drawn through the point.
An astounding amount of human brain power went into attempts to prove this from Euclid’s other axioms. One way to show a statement is not true is to provide a counterexample.
It is possible to have no, or infinitely many, parallel “lines” in a “plane” through a “point” not on a given line where “point”, “line”, and “plane” that satisfy all of Euclids other axioms.
Human brains did not evovle to think is terms of axioms and rules of inference.
In classical mathematics everything is a set, a bag of distinct elements. Logicians are wont to say “The language of set theory is epsilon.” If you know first order logic and what a language is, this makes perfect sense. So does the Dao De Jing if you are already enlightened.
The first attempt at defining modern Set Theory is due to Frege. He defined a set by giving a rule for membership. Bertrand Russell showed that entailed a contradiction. Let S be the set of all sets x where it is not the case x\in x, S = \{x\mid x\notin x\}.
Exercise. Show S\in S implies S\notin S and S\notin S implies S\in S.
Some call this Russell’s Paradox but it is actually an antinomy: if the assumptions of a theorem lead to a contradiction P and not P then the theorem cannot be true. There are two ways to show a theorem is incorrect: go through the theorem step by step and find an error in the application of the axioms or rules of inferrence, or find a counterexample. The later is usually simpler, and more ego crushing to the incorrect theorem’s author.
It was not easy to fix up Frege’s theory. This led to various schemes to axiomatize what a set is, e.g., Zermelo-Fraenkel, von Neumann, Gödel–Bernays. But they all define two sets are equal, A = B, if and only if they have the same elements. \forall x (x\in A\color{red}\leftrightarrow\color{black} x\in B)
Exercise. Show A = A, if A = B then B = A, and if A = B, B = C then A = C.
We write A\not= B if it is not the case A = B.
Exercise. Show A\not= B if and only if there exists x\in A with x\not\in B or there exists y\in B with y\not\in A.
Hint: ??? a <-> b iff !a <-> !b
We say A is a subset of B, A\subseteq B, if and only if x\in A implies x\in B \forall x(x\in A\color{red}\rightarrow\color{black} x\in B)
Exercise. Show A = B if and only if A\subseteq B and B\subseteq A.
Hint: For propositions P and Q, P\leftrightarrow Q if and only if P\rightarrow Q and Q\rightarrow P.
Other logical connectives can be used to define new sets from existing sets.
The union of two sets A and B, A\cup B, is the set of all elements belonging to either A or B \exists A\cup B \forall x(x\in A\cup B\leftrightarrow x\in A\color{red}\vee\color{black} x\in B)
The intersection of two sets A and B, A\cap B, is the set of all elements belonging to both A and B \exists A\cap B\forall x(x\in A\cap B\leftrightarrow x\in A\color{red}\wedge\color{black} x\in B) Two sets are disjoint if their intersection does not contain any elements. The empty set axiom states there exists a set with no elements, \emptyset. \exists\emptyset\forall x(x\notin\emptyset)
Exercise. Show A and B are disjoint if and only if A\cap B=\emptyset.
The other axioms are not the first thing you might think of.
The pairing axiom states if x and y are sets then there is a set with elements x and y, \{x,y\}. Every element of \{x,y\} is either x or y. \forall x\forall y\exists \{x,y\}\forall z (z\in \{x,y\} \leftrightarrow (z = x\vee z = y) At this point we only have the empty set. Using pairing we get \{\emptyset,\emptyset\}.
Exercise. Show \{\emptyset,\emptyset\ =\{\emptyset\}.
By definition \emptyset\in\{\emptyset\}.
Exercise. Show \emptyset\not=\{\emptyset\}.
Now we have a set with one element, the emptyset \emptyset. For any set x pairing gives us singleton \{x\} = \{x,x\}.
Exercise. Show for any set x we have x\not=\{x\}.
Exercise. Construct the set \{\{\emptyset\}\}.
Hint. Use pairing with \{\emptyset\}.
This can be repeated to any finite level of nesting. It is possible to identify {\emptyset, \{\emptyset\}, \{\{\emptyset\}\},\ldots} with the natural numbers \boldsymbol{{N}}= {0,1,2\ldots} but that is not the preferred encoding. The von Neumann encoding starts by identifying \emptyset with 0 and for any n define n + 1 = n\cup\{n\}. We have 1 = \{\emptyset\} and 2 = 1 + 1 = \{\emptyset\},\{\{\emptyset\}\}\}.
Exercise. Write 3 = (1 + 1) + 1 in terms of \emptyset.
Exercise. Show n \not= n+1. ???
Hint. Show n\not= n\cup\{n\}. ???
Exercise. Show n + m = n\cup\{m\}.
Hint: Clearly n + 0 = n\cup\{0\} ???
The axiom of foundation addresses the Russell counterexample.
Exercise. Let S = \{\cdots\{\emptyset\}\cdots\} be an infinite level of nesting. Show S\in S.
Hint: You cannot prove or disprove this with the axioms discussed so far.
It may seem plausible that removing the outside pairing of a countably infinite number of brackets leaves a countably infinite number of brackets, but always be wary of proofs involving \cdots.
There are some set theories where this is true, and some where it is not. In ZF set theory the axiom of foundation states every set has an element not in the set. \forall x\exists y(y\not\in x) This unobvious axiom has several implications. First of all it does not tell you how to compute the element not in the set. One of them being x\not\in x for any set x.
Exercise. Show y\not\in x if and only if y\cap\{x\}=\emptyset.
Exercise. Show for every set x we have x\not\in x.
We have seen an example of an infinite ascending chain x_0\in x_1 \in x_2\in \cdots. It is not possible to have in infinite descending chain \cdot\in x_{-2}\in x_{-1} \in x_0.
Two ordered pairs (a,b) and (c,d) are equal if and only if a = c and b = d. We can’t define (a,b) by the set \{a,b\} since \{a,b\} = \{b,a\} have the same elements.
Kazimierz Kuratowski improved Norbert Wiener’s definition of an ordered pair (a,b)\in A\times B as the set \{a,\{a,b\}\}.
Exercise. Show \cap\{a,\{a,b\}\} = \{a\} and \cup\{a,\{a,b\}\} = \{a,b\}.
Hint For any set A, \cap A is the intersection \cap\{x\mid x\in A\}; x belongs to \cap A if and only if x is a member of every element of A. For any set A, \cup A is the union \cup\{x\mid x\in A\}; x belongs to \cup A if and only if x is a member of some element of A.
The product of sets A and B is the set of ordered pairs of elements of A$ and B, A\times B = \{(a,b)\mid a\in A, b\in B\}.
The product of A, B, and C is A\times B\times C = (A\times B)\times C. This can be extended to any finite product of sets.
A simple solution to this is to only define subsets of an existing set that satisfy a rule. For any set S and a predicate P on S we can stay out of trouble by defining \{x\in S\mid P(x)\}. A predicate is a function from elements of a set that returns either true or false.
A set is just a bag of things (elements) with no structure. Two sets are equal if they contain the same elements. Using epsilon and first order logic this is written A = B if and only if (\forall a\in A\ a\in B)\wedge(\forall b\in B\ b\in A).
If A = B then they have the same number of elements. A weaker notion is two sets have the same cardinality if they have the same number of elements. If A and B are infinite this becomes a bit tricky to define. The sets A = \{1, 2, 3,\ldots\} and B = \{2, 4, 6, \ldots\} are both infinite and clearly B\subset A but B\not=A. They have the same cardinality because we can associate n\in A with 2n\in B. The function f\colon A\to B defined by f(n) = 2n is one-to-on and onto.
A relation on sets A and B is a subset of their product R\subseteq A\times B. We write aRb for (a,b)\in R. The domain of R is \operatorname{dom}R = A and the codomain of R is \operatorname{cod}R = B. The left coset of b\in B is Rb = \{a\in A: aRb\}\subseteq A. The right coset of a\in A is aR = \{b\in B: aRb\}\subseteq B.
Relations can be composed. If {R\subset A\times B} and {S\subset B\times C} then SR = \{(a,c)\mid aRb \text{\ and\ }bSc \text{\ for\ some\ } b\in B\}\subseteq A\times C. This is closely related to the definition of the SQL join of tables in a database.
The transpose of a relation R\subseteq A\times B is R^T = \{(b,a)\mid (a,b)\in R\}\subseteq B\times A.
Exercise. _Show (SR)^T = R^T S^T.
If A = B we can define properties to characterize a relation R\subseteq A\times A.
The notion of equality can be generalize to equivalence.
reflexive aRa, a\in A
symmetric aRb implies bRa, a,b\in A
transitive aRb and bRc imply aRc, a,b,c\in A.
A relation with these three properties is an equivalence relation. If R is an equivalence relations then aR = Ra, a\in A, and for a,b\in A either aR = bR or aR\cap bR = \emptyset.
Exercise. _Show aR = Ra, a\in A, if R is symmetric.
Exercise. Show the cosets of an equivalence relation form a partition of A.
Hint: \{A_i\}_{i\in I} is a partition of A if \cup_{i\in I} A_i = A and A_i\cap A_j = \emptyset if A_i\not= A_j.
Equivalence relations express partial information. Full information corresponds to the partition of singletons \{\{a\}\mid a\in A\}. No information corresponds to the singleton partition \{A\}. Partial information is knowing which element of the partition A_i that a\in A is an element of.
A function f\colon A\to B is a relation with domain A where every right coset is a singleton. Since af = \{b\} for all a\in A and some b\in B we can write f(a) = b since b is unique.
The set exponential B^A = \{f\colon A\to B\} is the set of all functions from A to B. We also write this as \{A\to B\}.
If we omit the condition the domain is A we have a partial function. Partial functions are more ubiquitous than functions. For example f\colon\boldsymbol{{R}}\to\boldsymbol{{R}} where f(x)=1/x is not defined at x = 0. Partial functions can be turned into a function by defining f(a) = b if (a,b)\in f and f(a) = \bot otherwise, where \bot is some element not in B.
Exercise. Show the codomain of the fixed up partial function is B\cup\{\bot\}_.
Function composition is relation composition.
Exercise. Show if f\colon A\to B and g\colon B\to C are functions then (gf)(a) = g(f(a)).
Hint: If f(a) = b and g(b) = c then the right coset a(gf) = \{c\}
A function f\colon A\to B is 1-1, or injective, if f(a) = f(a') implies a = a'.
Exercise. Show f is injective if and only if there exists g\colon B\to A with gf = 1_A.
Hint: If gf = 1_A and f(a) = f(a') then gf(a) = gf(a').
A function f\colon A\to B is onto, or surjective, if for every b\in B there exists a\in A with f(a) = b.
Exercise. Show f is surjective if and only if there exists h\colon B\to A with fh = 1_B.
Hint: If fh = 1_B then f(a) = b when a = h(b).
A function that is 1-1 and onto is bijective. It is also called a 1-1 correspondence.
The sets are eqivalent if there is a bijection between them.
Show A\cong B is an equivalence relation.
\{A\times B\}\to C\} \cong \{A\to\{B\to C\}\}.