Tao Analysis I - 3.3.2

Exercise 3.3.2

Let $f: X \mapsto Y$ and $g: Y \mapsto Z$ 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$.

Injective $g \circ f$

By Definition 3.3.17, a function $f$ is injective, one-to-one, if

$$f(x)=f(x') \implies x=x'$$

Let's consider $g \circ f$ being injective,

$$g(f(x)) = g(f(x'))$$

Since $g$ is injective, $g(y)=g(y') \implies y=y'$, which here means

$$f(x) = f(x')$$

Now, since $f$ is injective, $f(x) = f(x') \implies x=x'$.

Thus, we have shown 

$$g(f(x)) = g(f(x')) \implies x=x'$$

which means $g \circ f$ is injective. $\square$

Surjective $g \circ f$

By Definition 3.3.20, a function $f: X \mapsto Y$ is surjective, onto, if

$$(\forall y\in Y)(\exists x \in X)(f(x)=y)$$

In other words, every element of the codomain is mapped to by an element in the domain.

Let's consider $g \circ f$ being surjective. We need to show that every element $z \in Z$ has an element in $x \in X$ such that $g(f(x))=z$.

• Since $g$ is surjective, we know that every element $z \in Z$ has an element $y \in Y$ such that $g(y) = z$.
• Since $f$ is surjective, we know that every element $y \in Y$ has an element $x \in X$ such that $f(x)=y$.

We can use the second statement to rewrite the first as: every element $z \in Z$ has an element $x \in X$ such that $g(f(x)) = z$.

That is, $g \circ f$ is surjective. $\square$

Tao Analysis I - 3.3.1

Exercise 3.3.1

Show that the definition of equality in Definition 3.3.8 is reflexive, symmetric, and transitive. Also verify the substitution property: if $f, \tilde{f}: X \mapsto Y$ and $g, \tilde{g} : Y \mapsto Z$ are functions such that $f = \tilde{f}$ and $g = \tilde{g}$, then $g \circ f = \tilde{g} \circ \tilde{f}$.

Let's remind ourselves of Definition 3.3.8.

Definition 3.3.8 (Equality of functions). Two functions $f : X \mapsto Y$, $g : X' \mapsto Y'$ are said to be equal if their domains and codomains agree (i.e., $X = X'$ and $Y = Y'$ ), and furthermore that $f(x) = g(x)$ for all $x \in X$. If $f(x)$ and $g(x)$ agree for some values of $x$ in the domain, but not others, then we do not consider $f$ and $g$ to be equal. If two functions $f$, $g$ have different domains, or different ranges, we also do not consider them to be equal.

Let's remind ourselves of what reflexive, symmetric, transitive mean:

• https://staff.cdms.westernsydney.edu.au/cgi-bin/cgiwrap/zhuhan/dmath/dm_readall.cgi?page=18&part=2

Reflexive

Let's show the Definition 3.3.8 for equality of functions is reflexive, 

$$f=f$$

Referring to the definition: two functions, $f$ and $g$, are said to be equal if their domains and codomains agree, and furthermore that $f(x) = g(x)$ for all $x$ in the domain of $f$. 

Here, the domains and codomains are the same, if $f$ is also $g$. Furthermore, $f(x) = g(x)$ for all $x$ in the domain of $f$, because $f$ is $g$. 

Therefore, Definition 3.3.8 for equality of functions is reflexive. $\square$

Symmetric

Let's show the Definition 3.3.8 for equality of functions is symmetric,

$$(f=g)\implies (g=f)$$

Referring to the definition: two functions, $f$ and $g$, are said to be equal if their domains and codomains agree, and furthermore that $f(x) = g(x)$ for all $x$ in the domain of $f$. 

So, if $f=g$ then we know their domains and codomains agree. If $g=f$ then their domains and codomains also agree. 

Furthermore, if $f=g$ then we know $f(x) = g(x)$ for all $x$ in the domain of $f$. If $g=f$ then it should be the case that $g(x) = f(x)$ for all $x$ in the domain of $g$. Since the domains of $f$ and $g$ agree, then this is indeed the case.

Thus we have shown $(f=g)\implies (g=f)$, that is, the Definition 3.3.8 for equality of functions is symmetric. $\square$.

Transitive

Let's show the Definition 3.3.8 for equality of functions is transitive,

$$(f=g) \land (g=h) \implies (f=h)$$

Referring to the definition: two functions, $f$ and $g$, are said to be equal if their domains and codomains agree, and furthermore that $f(x) = g(x)$ for all $x$ in the domain of $f$. 

So, if $f=g$ then we know their domains and codomains agree. If $g=h$ then their domains and codomains also agree. Thus the domains and codomains of all $f$, $g$ and $h$ agree.

Furthermore, if $f=g$ then we know $f(x) = g(x)$ for all $x$ in the domain of $f$. Also, if $g=h$ then we know $g(x) = h(x)$ for all $x$ in the domain of $g$. Since the domains of all $f$, $g$ and $h$ agree, we can say $f(x)=g(x)=h(x)$ for all $x$ in their domains, which agree.

From this we conclude the domains and codomains of $f$ and $h$ agree. Furthermore, that $f(x) = h(x)$ for all $x$ in the domain of $f$. 

Thus, we have shown the Definition 3.3.8 for equality of functions is transitive. $\square$.

Substitution Property

We need to verify the substitution property: if $f, \tilde{f}: X \mapsto Y$ and $g, \tilde{g} : Y \mapsto Z$ are functions such that $f = \tilde{f}$ and $g = \tilde{g}$, then $g \circ f = \tilde{g} \circ \tilde{f}$.

Let's start by considering $g \circ f$. The domain of $f$ is $X$, and the codomain is $Y$. The domain of $g$ is $Y$, and the codomain is $Z$. Therefore, the domain of $g \circ f$ is $X$ and. the codomain is $Z$.

The same argument tells us the domain of $\tilde{g} \circ \tilde{f}$ is $X$ and. the codomain is $Z$.

So the domains and codomains of $g \circ f$ and $\tilde{g} \circ \tilde{f}$ agree.

Now let's consider the mappings. Since $f = \tilde{f}$, we know that $f(x) = \tilde{f}(x)$ for all $x$ in the domain of $f$. Similarly, since $g = \tilde{g}$, we know that $g(x) = \tilde{g}(x)$ for all $x$ in the domain of $g$.

Let's consider $g \circ f = g \circ \tilde{f}$. We can say 

$$g(f(x)) = g(\tilde{f}(x))$$

because $f(x) = \tilde{f}(x)$ for all $x$ in the domain of $f$, which agrees with the domain of $\tilde{f}$.

Applying the same argument, 

$$g(f(x)) = g(\tilde{f}(x)) = \tilde{g}(\tilde{f}(x))$$

because $g(x) = \tilde{g}(x)$ for all $x$ in the domain of $g$, which agrees with the domain of $\tilde{g}$.

So, $g \circ f$ and $\tilde{g} \circ \tilde{f}$ have the same domain and codomain, and map $x$ in the same way.

Thus we have shown $g \circ f = \tilde{g} \circ \tilde{f}$. $\square$

Tao Analysis I - 3.2.3

Exercise 3.2.3

Show (assuming the other axioms of set theory) that the universal specification axiom, Axiom 3.9, is equivalent to an axiom postulating the existence of a “universal set” $\Omega$ consisting of all objects (i.e., for all objects $x$ , we have $x \in \Omega$). In other words, if Axiom 3.9 is true, then a universal set exists, and conversely, if a universal set exists, then Axiom 3.9 is true.

For equivalence we need to show the implication in both directions, as stated by the question.

Let's remind ourselves of Axiom 3.9.

Axiom 3.9 (Universal specification, or axiom of comprehension). (Dangerous!) Suppose for every object $x$ we have a property $P(x)$ pertaining to $x$. Then there exists a set $\{x : P(x)\}$ such that for every object $y$,

$$y \in \{x : P(x)\} \iff P(y)$$

Let's formulate an axiom that postulates the existence of a universal set $\Omega$ consisting of all objects.

Axiom 3.10 (Universal set). There exists a universal set $\Omega$ consisting of all objects.

$$\forall x (x \in \Omega)$$

Let's start with Axiom 3.9. If we take $P(x)$ to be true for all objects $x$ then there exists a set which contains every object $x$. This is the definition of the universal set. So Axiom 3.9 implies Axiom 3.10.

Now let's start with Axiom 3.10. It tells us there exists a universal set $\Omega$ consisting of every object $x$. Let's use Axiom 3.6, the axiom of (not universal) specification on the set $\Omega$, with a property $P(x)$ which is true for all objects $x$. This Axiom 3.6 tells us there exists a set

$$\{x \in \Omega: P(x) \}$$

An object $y$ is in this set if $P(y)$ is true, and if $y \in \Omega$. Since every object $y$ is in $\Omega$, we are no longer bound by the set $\Omega$ (this is the key), and so we have universal specification for $x$.

$$ y \in \{x: P(x)\} \iff P(y)$$

So Axiom 3.10 implies 3.9.

We have shown Axiom 3.9 implies 3.10, and Axiom 3.10 implies 3.9, so we can conclude they are equivalent. $\square$

Tao Analysis I - 3.2.2

Exercise 3.2.2

Use the axiom of regularity (and the singleton set axiom) to show that if $A$ is a set, then $A \notin A$. Furthermore, show that if $A$ and $B$ are two sets, then either $A \notin B$ or $B \notin A$ (or both).

Lets' write out the Axiom of Regularity.

Axiom 3.10 (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$.

Show that if $A$ is a set, then $A \notin A$

Using the singleton set axiom, we can create a set $\{A\}$ from $A$.

Now we apply the axiom of regulatory to $\{A\}$. The axiom states that if $\{A\}$ is a non-empty set, then there is at least one element $x=A$ of $\{A\}$ which is either not a set, or is disjoint from $\{A\}$.

Let's consider these two cases:

• $x=A$ is not a set. This case is not true because we are given $A$ as a set.
• $x=A$ is disjoint from $\{A\}$. 

This means $A \cap \{A\} = \emptyset$. If it were true that $A \in A$, then we would have $A=\{A, ...\}$. But $\{A, ..\} \cap \{A\} \neq \emptyset$ since $A$ is a non-empty set. We conclude $A \notin A$. $\square$

This solution is inspired by Issa Rice's solution.

Show that if $A$ and $B$ are two sets, then either $A \notin B$ or $B \notin A$ (or both).

Let's follow a similar strategy and use the pair set axiom to construct a set $\{A,B\}$.

Assuming $A$ and $B$ are non-empty, applying the axiom of regularity tell us that if $\{A,B\}$ is a non-empty set, then there is at least one element of $\{A,B\}$ which is either not a set, or is disjoint from $\{A,B\}$.

Let's consider these two cases:

• At least one of $A$ and $B$ is not a set. This is not true because we are given $A$ and $B $ as sets.
• At least one of $A$ and $B$ is disjoint from $\{A,B\}$.

This gives us two further cases, either or both of which are true:

• $A \cap \{A,B\} = \emptyset$. This means $B \notin A$. If it were, then ${B, ..} \cap \{A,B\} = \emptyset$ is false.
• $B \cap \{A,B\} = \emptyset$. This means $A \notin B$. If it were, then ${A, ..} \cap \{A,B\} = \emptyset$ is false.

So we conclude that, either or both,  $B \notin A$ and  $A \notin B$ are true. $\square$

This solution is inspired by Issa Rice's solution.

Tao Analysis I - 3.2.1

Discussion

Before we dive into the exercise, it is worth comparing the Axiom 3.6 of Specification and this new interesting Axiom 3.9 of Universal Specification. 

Let's write them out:

Axiom 3.6 (Axiom of specification, or axiom of separation). Let $A$ be a set, and for each $x \in A$, let $P(x)$ be a property pertaining to $x$. Then there exists a set, called $\{x \in A : P(x)\}$, 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)\} \iff (y \in A \land P(y))$$

Axiom 3.9 (Universal specification, or axiom of comprehension). (Dangerous!) Suppose for every object $x$ we have a property $P(x)$ pertaining to $x$. Then there exists a set $\{x : P(x)\}$ such that for every object $y$,

$$y \in \{x : P(x)\} \iff P(y)$$

The key differences are:

• Axiom 3.9 says any property over a set of objects can form a set.
• Axiom 3.6 says a set can be formed from an existing set.

Axiom 3.9 leads to Russell's paradox. This is because the assumption that any property $P()$ corresponds to a set is too general. If we chose a property $P(x): x \text{ is a set, and } x\notin x$, then we can form a set $\Omega$ of all sets that are not members of themselves. Asking if $\Omega$ is a member of itself leads to a contradiction. If it does, then $P(\Omega)$ is true, and which means $\Omega$ doesn't contain itself. If it doesn't, then by definition $P(\Omega)$ is true, which means $\Omega \in \Omega$, a contradiction.

The problem is allowing a set to contain itself.

Axion 3.6 does not lead to Russell's paradox because it takes an existing set, and uses $P()$ to create a subset. The basis, an existing set, and the process, subsetting, are sound, and so do not lead to a contradiction.

The textbook presents Axiom 3.10 as a resolution.

Axiom 3.10 (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$.

This axiom essentially rules out any member of $A$ being $A$. That is, prevents a $A$ containing itself.

Exercise 3.2.1

Show that the universal specification axiom, Axiom 3.9, if assumed to be true, would imply Axioms 3.3, 3.4, 3.5, 3.6, and 3.7. (If we assume that all natural numbers are objects, we also obtain Axiom 3.8.) 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.9 is “too good to be true”!

Axiom 3.9 Implies Axiom 3.3 (Empty Set)

If we choose a property $P(x)$ which is always false for any $x$,

$$\forall x (\neg P(x))$$

then no $x$ is a member of the set formed by this property. That set is the empty set. 

Axiom 3.9 states this empty set exists, which is Axiom 3.3. $\square$

Axiom 3.9 Implies Axiom 3.4 (Singleton and Pair Sets)

If we choose a property $P(x)$ which is only true when $x=a$, 

$$P(a)$$

then only $a$ can be a member of the set formed by this property. The set $\{a\}$ is a singleton. If $x\neq a$ then $P(x)$ is not true, and so $x$ is not in the set formed by the property, so only $a$ is a member.

Axiom 3.9 states this set exists, which is Axiom 3.4 for singletons. $\square$

Similarly for pair sets, we can choose a property $P(x)$ which is only true when $x=a$ or $x=b$,

$$P(a) \lor P(b)$$

then only $a$ and $b$ are members of the set formed by this property. The set $\{a,b\}$ is a pair set. 

Axiom 3.9 states this set exists, which is Axiom 3.4 for pair sets. $\square$

Axiom 3.9 Implies Axiom 3.5 (Pairwise Union)

If we choose a property $P(x)$ which is true if $x$ is a member of a set $A$ or is a member of a set $B$,

$$P(x) \iff (x \in A) \lor (x \in B)$$

then the set formed by the property is the pairwise union of sets $A$ and $B$, that is $A \cap B$. This is by the definition of pairwise union, Axiom 3.5.

Axiom 3.9 states this set exists, which is Axiom 3.5. $\square$

Axiom 3.9 Implies Axiom 3.6 (Axiom of Specification)

If we choose a property $P(x)$ which is true when $x$ is a member of a set $A$ and also a property $Q(x)$ is true,

$$P(x) \iff (x \in A) \land Q(x)$$

then the set formed by $P(x)$ is the same as that formed by the Axiom 3.6 with property $Q(x)$ applied to $x\in A$.

Axiom 3.9 states this set exists, which is Axiom 3.6. $\square$

Axiom 3.9 Implies Axiom 3.7 (Replacement)

If we choose a property $P(x,y)$ which is true for at most one $y$, and where $x \in A$, then the set of $y$ formed by this property is the same set formed by the Axiom 3.7. 

Axiom 3.9 states this set exists, which is Axiom 3.7. $\square$