Chapter3

Axiom

  • Axiom 3.1. (Sets are objects). IF \(A\) is a set, then \(A\) is also an object. In particular, given two sets \(A\) and \(B\), it is meaningful to ask whether \(A\) is also an element of \(B\).


  • Axiom 3.2. (Empty set). There exists a set \(\emptyset\), known as the empty set, which contains no elements, i.e., for every object \(x\) we have \(x\notin\emptyset\).


  • Axiom 3.3. (Singleton sets and pair sets). If \(a\) is an object, then there exists a set \(\{a\}\) whose only element is \(a\), i.e., for every object \(y\), we have \(y\in\{a\}\) if and only if \(y=a\); we refer to \(\{a\}\) as the singleton set whose element is \(a\). Furthermore, if \(a\) and \(b\) are objects, then there exists a set \(\{a,b\}\) whose only elements are \(a\) and \(b\); i.e., for every object \(y\), we have \(y\in\{a,b\}\) if and only if \(y=a\) or \(y=b\); we refer to this set as the pair set formed by \(a\) and \(b\).


  • Axiom 3.4. (Pairwise union). Given any two sets \(A,B\), there exists a set \(A\cup B\), called the union of \(A\) and \(B\), which consists of all the elements which belong to \(A\) to \(B\) or both. In other words, for any object \(x\), $$ x\in A\cup B\iff(x\in A~ or~ x\in B). $$


  • Axiom 3.5. (Axiom of specification). Let \(A\) be a set, and for each \(x\in A\), let \(P(x)\) be a property pertaining to \(x\) (i.e., \(P(x)\) is either a true statement or a false statement). Then there exists a set, called \(\{x\in A:~P(x)\text{ is true}\}\) (or simply \(\{x\in A:~P(x)\})\) for short), whose elements are precisely the elements \(x\) in \(A\) for which \(P(x)\) is true. In other words, for any object \(y\), $$ y\in\{x\in A:~P(x)\text{ is true}\}\iff (y\in A \text{ and } P(y)\text{ is true }). $$


  • Axiom 3.6. (Replacement). Let \(A\) be a set. For any object \(x\in A\), and any object \(y\), suppose we have a statement \(P(x,y)\) pertaining to \(x\) and \(y\), such that for each \(x\in A\) there is at most one \(y\) for which \(P(x,y)\) is true. Then there exists a set \(\{y:~P(x,y)\text{ is true for some } x\in A\}\), such that for any object \(z\), $$ z\in\{y:~P(x,y)\text{ is true for some } x \in A\}\iff P(x,z)\text{ is true for some } x\in A. $$


  • Axiom 3.7. (Infinity). There exists a set \(\mathbb{N}\), whose elements are called natural numbers, as well as an object \(0\) in \(\mathbb{N}\), and an object \(n\pp\) assigned to every natural number \(n\in\mathbb{N}\), such that the Peano axioms (Axioms 2.1-2.5) hold.


  • Axiom 3.8. (Univeral specification). (Dangerous!) Suppose for every object \(x\) we have a property \(P(x)\) pertaining to \(x\) (so that every \(x, P(x)\) is either a true statment or a false statement). Then there exists a set \(\{x:P(x)\text{ is true}\}\) such that for every object \(y\), $$ y\in\{x:P(x)\text{ is true}\}\iff P(y)\text{ is true}. $$


  • Axiom 3.9. (Regularity). If \(A\) is a non-empty set, then there is at least one element \(x\) of \(A\) which is either not a set, or is disjoint from \(A\).



  • Axim 3.10 (Power set axiom). Let \(X\) and \(Y\) be sets. Then there exists a set, denoted \(Y^X\), which consists of all the functions from \(X\) to \(Y\), thus $$ f\in Y^X\iff (f\text{ is a function with domain }X\text{ and range }Y) $$



  • Axiom 3.11 (Union). Let \(A\) be a set, all of whose elements are themselves sets. Then there exists a set \(\bigcup A\) whose elements are precisely those objects which are elements of the elements of \(A\), thus for all objects \(x\) $$ x\in\bigcup A\iff(x\in S\text{ for some }S\in A) $$



  • Remark 3.4.12 The axioms of set theory that we have introduced (Axiom 3.1-3.11, excluding the dangerous Axiom 3.8 are known as the Zermelo-Fraenkel axioms of the theory, after Ernest Zermelo (1871-1953) and Abraham Fraenkel (1891-1965). There is one further axiom we will eventually need, the famous axiom of choice (see Section 8.4), giving rise to the Zermelo-Fraenkel-Choice (ZFC) axioms of set theory, but we will not need this axiom for some time.



Definitions

  • Definition 3.1.1 (Informal). We define a set \(A\) to be any unordered collection of objects, e.g., \(\{3,8,5,2\}\) is a set. If \(x\) is an object, we say that \(x\) is an element of \(A\) or \(x\in A\) if \(x\) lies in the collection; otherwise we say that \(x\notin A\). For instance, \(3\in\{1,2,3,4,5\}\) but \(7\notin\{1,2,3,4,5\}\).


  • Definition 3.1.4. (Equality of sets). Two sets \(A\) and \(B\) are equal, \(A=B\) iff every element of \(A\) is an element of \(B\) and vice versa. To put it another way, \(A=B\) if and only if every element \(x\) of \(A\) belongs also to \(B\), and every element \(y\) of \(B\) belongs also to \(A\).



  • Definition 3.1.15 (Subsets). Let \(A,B\) be sets. We say that \(A\) is a subset of \(B\), denoted \(A\subseteq B\), iff every every element of \(A\) is also an element of \(B\), i.e. $$ \text{For any object }x,~~x\in A\implies x\in B. $$ We say that \(A\) is a proper subset of \(B\), denoted \(A\subsetneq B\), if \(A\subseteq B\) and \(A\neq B\).



  • Definition 3.1.23 (Intersections). The intersection \(S_1\cap S_2\) of two sets is defined to be the set $$ S_1\cap S_2:=\{s\in S_1:x\in S_2\}. $$ In other words, \(S_1\cap S_2\) consists of all the elements which belong to both \(S_1\) and \(S_2\). Thus, for all objects \(x\), $$ x\in S_1\cap S_2\iff x\in S_1\text{ and }x\in S_2. $$



  • Definition 3.1.27 (Difference sets). Given two sets \(A\) and \(B\), we define the set \(A-B\) or \(A\setminus B\) to be the set \(A\) with any elements of \(B\) removed: $$ A\setminus B:=\{x\in A:x\notin B\}; $$ for instance, \(\{1,2,3,4\}\setminus\{2,4,6\}=\{1,3\}\). In many cases \(B\) will be a subset of \(A\), but not necessarily.



  • Definition 3.3.1 (Functions). Let \(X,Y\) be sets, and let \(P(x,y)\) be a property pertaining to an object \(x\in X\) and an object \(y\in Y\), such that for every \(x\in X\), there is exactly one \(y\in Y\) for which \(P(x,y)\) is true (this is sometimes known as the vertical line test). Then we define the function \(f:X\to Y\) defined by \(P\) on the domain \(X\) and range \(Y\) to be the object which, given any input \(x\in X\), assigns an output \(f(x)\in Y\), defined to be the unique object \(f(x)\) for which \(P(x,f(x))\) is true. Thus for any \(x\in X\) and \(y\in Y\), $$ y=f(x)\iff P(x,y)\text{ is true. } $$



  • Definition 3.3.7 (Equality of functions). Two functions \(f:X\to Y,~g:X\to Y\) with the same domain and range are said to be equal, \(f=g\) if and only if \(f(x)=g(x)\) for all \(x\in X\). (If \(f(x)\) and \(g(x)\) agree for some values of \(x\), but not others, then we do not consider \(f\) and \(g\) to be equal 1 .)



  • Definition 3.3.10 (Composition). Let \(f:X\to Y\) and \(g:Y\to Z\) be two functions, such that the range of \(f\) is the same set as the domain of \(g\). We then define the composition \(g\circ f:X\to Z\) of two functions \(g\) and \(f\) to be the function defined explicitly by the formula $$ (g\circ f)(x):=g(f(x)) $$ If the range of \(f\) does not match the domain of \(g\), we leave the composition \(g\circ f\) undefined.

  • Definition 3.3.14 (One-to-one functions). A function \(f\) is one-to-one (or injective) if different elements map to different elements: $$ x\neq x'\implies f(x)\neq f(x') $$

    Equivalently, a function is one-to-one if $$ f(x)=f(x')\implies x=x' $$



  • Definition 3.3.17 (Onto functions). A function \(f\) is onto (or surjective) if \(f(X)=Y\), i.e., every element in \(Y\) comes from applying \(f\) to some element in \(X\): $$ \text{For every } y\in Y,\text{ there exists } x\in X \text{ such that } f(x)=y. $$



  • Definition 3.3.20 (Bijective functions). Functions \(f:X\to Y\) which are both one-to-one and onto are also called bijective or invertible.



  • Definition 3.4.1 (Images of sets). If \(f:X\to Y\) is a function from \(X\) to \(Y\), and \(S\) is a set in \(X\), we define \(f(S)\) to be the set $$ f(S):=\{f(x):x\in S\} $$ this set is a subset of \(Y\), and is sometimes called the image of \(S\) under the map \(f\). We sometimes call \(f(S)\) the forward image of \(S\) to distinguish it from the concept of the inverse image \(f^{-1}(S)\) of \(S\), which is defined below.



  • Definition 3.4.4 (Inverse images). If \(U\) is a subset of \(Y\), we define the set \(f^{-1}(U)\) to be the set $$ f^{-1}(U):=\{x\in X: f(x)\in U\} $$ In other words, \(f^{-1}(U)\) consists of all the elements of \(X\) which map into \(U\): $$ f(x)\in U\iff x\in f^{-1}(U) $$ We call \(f^{-1}(U)\) the inverse image of U.



  • Definition 3.5.1 (Ordered pair). If \(x\) and \(y\) are any objects (possibly equal), we define the ordered pair \((x,y)\) to be a new object, consisting of \(x\) as its first component and \(y\) as its second component. Two ordered pairs \((x,y)\) and \((x',y')\) are considered equal if and only if both of their components match, i.e $$ (x,y)=(x',y')\iff(x=x'\text{ and } y=y') $$



  • Definition 3.5.4 (Cartesian product). If \(X\) and \(Y\) are sets, then we define Cartesian product \(X\times Y\) to the collection of ordered pairs, whose first component lies in \(X\) and second component lies in \(Y\), thus $$ X\times Y=\{(x,y):x\in X,y\in Y\} $$ or equivalently $$ a\in(X\times Y)\iff(a=(x,y) \text{ for some } x\in X\text{ and }y\in Y). $$



  • Definition 3.5.7 (Ordered \(n\)-tuple and \(n\)-fold Cartesian product). Let \(n\) be a natural number. An ordered \(n\)-tuple \((x_i)_{1\leq i\leq n}\) (also denoted \((x_1,\cdots,x_n)\)) is a collection of objects \(x_i\), one for every natural number \(i\) between \(1\) and \(n\); we refer to \(x_i\) as the \(i^{th}\) component of the ordered \(n\)-tuple. Two ordered \(n\)-tuples \((x_i)_{1\leq i\leq n}\) and \((y_i)_{1\leq 1\leq n}\) are said to be equal iff \(x_i=y_i\) for all \(1\leq i\leq n\). If \((X_i)_{1\leq i\leq n}\) is an ordered \(n\)-tuple of sets, we define their Cartesian product \(\prod_{1\leq i\leq n}X_i\) (also denoted \(\prod_{i=1}^n X_i\) or \(X_1\times\cdots X_n\)) by $$ \prod_{1\leq i\leq n}X_i:=\{(x_i)_{1\leq i\leq n}:x_i\in X_i\text{ for all }1\leq i\leq n\} $$

Propositions

  • Lemma 3.1.6. (Single choice). Let \(A\) be a non-empty set. Then there exists an objet \(x\) such that \(x\in A\).



  • Lemma 3.1.13 If \(a\) and \(b\) are objects, then \(\{a,b\}=\{a\}\cup\{b\}\). If \(A,B,C\) are sets, then the union operation is commutative (i.e., \(A\cup B= B\cup A\)) and associative (i.e., \((A\cup B)\cup C=A\cup(B\cup C))\). Also, we have \(A\cup A=A\cup\emptyset=\emptyset\cup A=A\).



  • Lemma 3.3.12 (Composition is associative). Let \(f:Z\to W,~g:Y\to Z\), and \(h:X\to Y\) be functions. Then \(f\circ(g\circ h)=(f\circ g)\circ h\).



  • Lemma 3.4.9 Let \(X\) be a set. Then the set $$ \{Y:Y\text{ is a subset of }X\} $$ is a set.



Exercises





  • Exercise 3.2.1. Show that the universal specification axiom, Axiom 3.8, if assumed to be true, would imply Axioms 3.2, 3.3, 3.4, 3.5, and 3.6. (If we assume that all natrual numbers are object, we also obtain Axiom 3.7.) Thus, this axiom, if permitted, would simplify the foundations of set theory tremendously (and can be viewed as one basis for an intuitive model of set theory known as "naive set theory"). Unfortunately, as we have seen, Axiom 3.8 is "too good to be true"!

    Exercise-3.2.1 with solution



  • Exercise 3.3.1. Show that the definition of equality in Definition 3.3.7 is reflexive, symmetric, and transitive. Also verity the substitution property: if \(f,\tilde{f}:X\to Y\) and \(g,\tilde{g}:Y\to Z\) are functions such that \(f=\tilde{f}\) and \(g=\tilde{g}\), then \(g\circ f=\tilde{g}\circ\tilde{f}\).

    Exercise-3.3.1 with solution

  • Exercise 3.3.2. Let \(f:X\to Y\) and \(g:X\to Y\) be functions. Show that if \(f\) and \(g\) are both injective, then so is \(g\circ f\); similarly, show that if \(f\) and \(g\) are both surjective, then so is \(g\circ f\).

    Exercise-3.3.2 with solution





  • Exercise 3.3.8. If \(X\) is a subset of \(Y\) , let \(\imath_{X \to Y} : X → Y\) be the inclusion map from \(X\) to \(Y\) , denoted by mapping \(x \mapsto x\) for all \(x \in X\), i.e., \(\imath_{X \to Y} (x) := x\) for all \(x \in X\). The map \(\imath_{X \to X}\) is in particular called the identity map on \(X\).

    (a) Show that if \(X \subseteq Y \subseteq Z\) then \(\imath_{Y \to Z} \circ \imath_{X \to Y} = \imath_{X \to Z}\) .
    (b) Show that if \(f : A \to B\) is any function, then \(f = f \circ \imath_{A \to A} = \imath_{B \to B} \circ f\) .
    (c) Show that, if \(f : A \to B\) is a bijective function, then \(f \circ f^{-1} = \imath_{B \to B}\) and \(f^{-1} \circ f = \imath_{A \to A}\).
    (d) Show that if \(X\) and \(Y\) are disjoint sets, and \(f : X \to Z\) and \(g : Y → Z\) are functions, then there is a unique function \(h : X \cup Y \to Z\) such that \(h \circ \imath_{X→X \cup Y} = f\) and \(h \circ \imath_{Y \to X \cup Y} = g\).

    Exercise-3.3.8 with solution







Footnotes
1.
In Chapter 11.45, we shall introduce a weaker notion of equality, that of two functions being equal almost everywhere
Links to this page
  • Remark 3.4.12

    Remark 3.4.12 The axioms of set theory that we have introduced (Axiom 3.1-3.11, excluding the dangerous Axiom 3.8) are known as the Zermelo-Fraenkel axioms of the theory, after Ernest Zermelo (1871-1953) and Abraham Fraenkel (1891-1965). There is one further axiom we will eventually need, the famous axiom of choice (see Section 8.4), giving rise to the Zermelo-Fraenkel-Choice (ZFC) axioms of set theory, but we will not need this axiom for some time.

  • Exercise 3.2.1

    Show that the universal specification axiom, Axiom 3.8, if assumed to be true, would imply Axioms 3.2, 3.3, 3.4, 3.5, and 3.6. (If we assume that all natrual numbers are object, we also obtain Axiom 3.7.) Thus, this axiom, if permitted, would simplify the foundations of set theory tremendously (and can be viewed as one basis for an intuitive model of set theory known as "naive set theory"). Unfortunately, as we have seen, Axiom 3.8 is "too good to be true"!