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$

Tao Analysis I - 3.1.13

Exercise 3.1.13

Euclid famously defined a point to be “that which has no part”. This exercise should be reminiscent of that definition. Define a proper subset of a set $A$ to be a subset $B$ of $A$ with $B \neq A$. Let $A$ be a non-empty set. Show that $A$ does not have any non-empty proper subsets if and only if $A$ is of the form $A=\{x\}$ for some object $x$.

Exploration

The wording of the question is not simple. So let's explore the idea behind the question with some examples.

Consider an example set $A=\{1,2,3\}$. This has several subsets, one of which is $\{1,2\}$. This is a non-empty subset. Our aim is to understand when a set has no non-empty subsets. We can see that larger sets, like $A=\{1,2,3,4,5,6\}$ will never have no non-empty subsets, because this one will also have $\{1,2\}$ as subset.

Let's consider the case that $A$ is the empty set, $A=\emptyset$. Although the empty set has no elements, it does have one subset which is the empty set. But the empty set is not a proper subset of the empty set. The question itself explains why; $X$ is a proper subset of $Y$ when $X$ is a subset of $Y$ but $X \neq Y$. Here we have $\emptyset = \emptyset$ so $\emptyset$ can't be a proper subset of $\emptyset$.

For this exercise, $A$ being an empty set is excluded by the question, because A is specified as a non-empty set.

Finally, let's consider $A=\{x\}$, a set with only one element. It has two subsets, $\{x\}$ and $\emptyset$. However $\{x\}$ is not a proper subset because it equals the original set, $\{x\}=\{x\}$. What about the other subset, $\emptyset$? Well it is not a non-empty set. So singleton sets, like $A=\{x\}$ do not have any non-empty proper subsets.

The link to Euclid's definition is that a singleton set is "that which has no part", in the sense there are no smaller (proper) subsets.

Solution

We need to show that $A$ does not have any non-empty proper subsets if and only if $A$ is of the form $A=\{x\}$ for some object $x$.

We can do this by showing both:

• $A$ is of the form $A=\{x\}$ $\implies$ $A$ does not have any non-empty proper subsets.
• $A$ does not have any non-empty proper subsets $\implies$ $A$ is of the form $A=\{x\}$.

Let's consider the first implication.

If $A$ is of the form $A=\{x\}$ then it has only two subsets, $\{x\}$ and $\emptyset$. The first, $\{x\}$ is not a proper subset because it equals $A$. The second, $\emptyset$ is not non-empty. 

Therefore a set A of the form $A=\{x\}$ has no non-empty proper subsets.

$$A \text{ is of the form } A=\{x\} \implies A \text{ has no non-empty proper subsets}$$

Let's now consider the second implication.

By hypothesis $A$ does not have any non-empty proper subsets. There are three cases for the form of $A$: (i) $A$ has zero elements, (ii) $A$ has one element, and (iii) $A$ has at least two elements. Let's consider each case in turn.

(i) The case $A=\emptyset$ is excluded by the question where $A$ is required to be a non-empty set.

(ii) The case $A=\{x\}$. Here $A$ has two subsets, $\{x\}$ and $\emptyset$. However $\{x\}$ is not a proper subset, and $\emptyset$ is not non-empty. Therefore the case $A=\{x\}$ is complies with the requirements of the hypothesis, that is, $A$ does not have any non-empty proper subsets. 

(iii) The case $A$ has at least two elements, $A=\{a,b, \ldots\}$. Then $\{a\}$ is a non-empty proper subset of $A$, so any $A$ with at least two elements does not comply with the requirements of the hypothesis.

Thus a set $A$ does that not have any non-empty proper subsets implies a set with one element.

$$ A \text{ has no non-empty proper subsets} \implies A \text{ is of the form } A=\{x\}$$

By showing both implications, we have shown that 

$$A \text{ is of the form } A=\{x\} \iff A \text{ has no non-empty proper subsets} \; \square$$

Tao Analysis I - 3.1.12

Exercise 3.1.12

Suppose that $A$, $B$, $A'$, $B'$ are sets such that $A' \subseteq A$ and $B' \subseteq B$.

(i) Show that $A' \cup B' \subseteq A \cup B$ and $A' \cap B' \subseteq A \cap B$.

(ii) Give a counterexample to show that the statement $A' \setminus B' \subseteq A \setminus B$ is false. Can you find a modification of this statement involving the set difference operation $\setminus$ which is true given the stated hypotheses? Justify your answer.

Show that $A' \cup B' \subseteq A \cup B$

Let's start by writing down the meaning of $A' \cup B'$ using Axiom 3.5 which defines union.

$$x \in (A' \cup B') \iff (x \in A') \lor (x \in B')$$

The RHS is true in two cases, $x \in A'$ and $x \in B'$. Let's consider each case.

• If $x \in A'$ then, because we're given $A' \subseteq A$, we have $x \in A$.
• If $x \in B'$ then, because we're given $B' \subseteq B$, we have $x \in B$.

Either, or both, of these cases is true, which gives us a disjunctive implication,

$$x \in (A' \cup B') \implies (x \in A) \lor (x \in B)$$

This is equivalent to the statement $A' \cup B' \subseteq A \cup B$. $\square$

Show that $A' \cap B' \subseteq A \cap B$

Again, let's start with the definition of intersection to write down the meaning of $A' \cap B'$.

$$x \in (A' \cap B') \iff (x \in A') \land (x \in B')$$

The RHS is only true if both $(x \in A')$ and $(x \in B')$ are true. Let's consider each statement.

• If $x \in A'$ then, because we're given $A' \subseteq A$, we have $x \in A$.
• If $x \in B'$ then, because we're given $B' \subseteq B$, we have $x \in B$.

Because both have to be true, we have a conjunctive implication.

$$x \in (A' \cap B') \implies (x \in A) \land (x \in B)$$

This is equivalent to the statement $A' \cap B' \subseteq A \cap B$. $\square$

Show $A' \setminus B' \subseteq A \setminus B$ is false

We'll show the statement is false with a counter-example. Consider the following sets:

• $A = \{1,2,3,4\}$, and $A' = \{2,3\}$, noting that $A' \subseteq A$ as required
• $B = \{2,3,4,5\}$, and $B' = \{2\}$, noting that $B' \subseteq B$ as required

Then $A' \setminus B' = \{3\}$, and $A \setminus B = \{1\}$.

Here $A' \setminus B' \subseteq A \setminus B$ means $ \{3\} \subseteq \{1\}$, which is false.

We have shown $A' \setminus B' \subseteq A \setminus B$ is false with the above counterexample. $\square$

Modification

We're asked to consider modifying the statement to make it true. Visualising the Venn diagram can help our thinking.

The following shows the sets $A$, $A'$, $B$ and $B'$ and every combination of intersection and union.

The visualising makes it easier to see that for $A' \setminus B' \subseteq A \setminus B$ to be true, the set $(A' \setminus B') \cap B$ must be empty.

$$\boxed{(A' \setminus B') \cap B = \emptyset}$$

Let's check this with an example. Consider the following sets:

• $A = \{1,2,3,4\}$, and $A' = \{2,3\}$, noting that $A' \subseteq A$ as required
• $B = \{2,4,6,8\}$, and $B' = \{2,4\}$, noting that $B' \subseteq B$ as required

Then $A' \setminus B' = \{3\}$, and $A \setminus B = \{1,3\}$. 

Here $A' \setminus B' \subseteq A \setminus B$ means $ \{3\} \subseteq \{1,3\}$, which is true.

The condition $(A' \setminus B') \cap B = \emptyset$ is  $\{3\} \cap \{2,4,6,8\} = \emptyset$ is true.

Tao Analysis I - 3.1.11

Exercise 3.1.11

Show that the axiom of replacement implies the axiom of specification.

Let's write out these axioms.

Axiom 3.7 (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 ∈ A$$

It is worth noting that this axiom about the existence of the set $\{y\}$.

Axiom 3.6 (Axiom of specification). Let $A$ be a set, and for each $x ∈ A$, let $P(x)$ be a property pertaining to $x$ (i.e., for each $x \in A$, $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 })$$

Again, this is an axiom about the existence of the set $\{y\}$.

Let's consider the Axiom of Replacement, and define the statement $P(x,y)$ as follows:

$$P(x,y) := (x=y) \land (Q(y) \text{ is true })$$

This definition of $P(x,y)$ also satisfies the axiom's requirement that for each $x \in A$ there is at most one $y$ for which $P(x,y)$ is true. This is because $x=y$.

The axiom tells us there exists a set $\{y : P(x, y) \text{ is true for some } x \in A\}$. We can write $P$ in terms of $Q$,

$$\begin{align}\{y : P(x, y) \text{ is true for some } x \in A\} &= \{y : x=y \land Q(y) \text{ is true for some } x \in A\} \\ \\ &= \{y : Q(y) \text{ is true for some } y \in A\}  \\ \\ &= \{y \in A: Q(y) \text{ is true }\}  \end{align}$$

The RHS is equivalent to the Axiom of Specification. Thus we have shown the axiom of replacement implies the axiom of specification. $\square$

Tao Analysis I - 3.1.10

Exercise 3.1.10

Let $A$ and $B$ be sets. Show that the three sets $A \setminus B$, $A \cap B$, and $B \setminus A$ are disjoint, and that their union is $A \cup B$.

To show the three sets $A \setminus B$, $A \cap B$, and $B \setminus A$ are disjoint, we need to show that a member of one is not a member of the other two.

Let's use the definitions in the textbook to write out what these set descriptions mean.

• $(A \setminus B)$ means a member is in $A$ but not in $B$:

$$x \in (A \setminus B) \iff (x \in A) \land (x \not \in B) $$

• $(A \cap B)$ means a member is in both $A$ and $B$:

$$x \in (A \cap B) \iff (x \in A) \land (x  \in B) $$

• $(B \setminus A)$ means a member is in $B$ but not $A$:

$$x \in (B \setminus A) \iff (x \in B) \land (x \not \in A) $$

Now if $x$ is a member of $(A \setminus B)$ then it is not a member of $B$. The descriptions above tell us $x$ is not in $(A \cap B)$, and it is not in (B \setminus A), because both would require it to be in $B$.

If $x$ is a member of $(A \cap B)$ then it is a member of both $A$ and $B$. The descriptions above tell us $x$ is not in $(A \setminus B)$, because that would require $x$ to be in $B$. Also, the descriptions tell us $x$ is not in $(B \setminus A)$, because that would require it to be in $A$.

Finally, if $x$ is a member of $(B \setminus A)$ then it is not in $(A \cap B)$, and it is not in $(A \cap B)$., because both would require it to be in $A$.

We have shown that the three sets $A \setminus B$, $A \cap B$, and $B \setminus A$ are disjoint. $\square$

We now want to show the union of all three $A \setminus B$, $A \cap B$, and $B \setminus A$ is $A \cup B$. To do this we need to show that a member of any of the three sets is in $A \cup B$, and also that a member of $A \cup B$ is in one of the three sets.

First let's remind ourselves of the definition of union.

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

Now, 

• If $x \in (A \setminus B)$ then because by definition $x \in A$ and so $x \in (A \cup B)$.
• If $x \in (A \cup B)$ then because by definition $x \in A$  and $x \in B$, and so $x \in (A \cup B)$.
• If $x \in (B \setminus A)$ then because by definition $x \in B$ and so $x \in (A \cup B)$.

So we have that if $x$ is a member of any of the three sets, then it is a member of $A \cup B$.

Finally, if $x \in (A \cup B)$ then we have two cases, $x \in A$ or $x \in B$:

• $x \in A$. Using the description earlier, this means $x$ is in $(A \setminus B)$ or $x \in (A \cup B)$
• $x \in B$. Using the description earlier, this means $x$ is in $(B \setminus A)$ or $x \in (A \cup B)$

We have shown that a member of any of the three sets is in $A \cup B$, and also that a member of $A \cup B$ is in one of the three sets. Thus we have proved $A \setminus B$, $A \cap B$, and $B \setminus A$ is $A \cup B$. $\square$

Tao Analysis I - 3.1.9

Exercise 3.1.9

Let $A$, $B$, $X$ be sets such that $A \cup B = X$ and $A \cap B = \emptyset$. Show that $A = X \setminus B$ and $B = X \setminus A$.

Show that $A = X \setminus B$

Let's start by writing down the meaning of $A \cup B = X$,

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

and also the meaning of $A \cap B = \emptyset$,

$$\neg \exists x [(x \in A ) \land (x \in B)]$$

This is saying that there is no $x$ that is in both $A$ and $B$. We can write this as two separate statements,

$$x \in A \implies x \not \in B$$

$$x \in B \implies x \not \in A$$

Now, let's consider $A$.  From $x \in X \iff (x \in A) \lor (x \in B)$, we have

$$x \in A \implies x \in X$$

And we already have

$$x \in A \implies x \not \in B$$

These two statements are both be true, so we can write them as

$$x \in A  \implies (a \in X) \land (x \not \in B)$$

This gives us $A \subseteq X \setminus B$. 

We need to show $X \setminus B \subseteq A$. Let's consider $X \setminus B$,

$$(x \in X) \land (x \not \in B)$$

Using $x \in X \iff (x \in A) \lor (x \in B)$, we have two cases,  at least one of which is true,

• $x \in X \implies x \in A$
• $x \in X \implies x \in B$

The first case gives us

$$\begin{align}(x \in X) \land (x \not \in B) &\implies (x \in A) \land (x \not \in B) \\ \\ &\implies (x \in A) \end{align}$$

which confirms $X \setminus B \subseteq A$.

The second case gives us

$$(x \in X) \land (x \not \in B) \implies (x \in B) \land (x \not \in B)$$

which is a contradiction, meaning only the first case is true.

So having shown both $A \subseteq X \setminus B$, and $X \setminus B \subseteq A$, we can conclude $A = X \setminus B$. $\square$

Show that $B = X \setminus A$

We could prove this using the same logic as above, or we could simply use symmetry to argue that interchanging the variables $A$ and $B$ doesn't change the given information and constraints (because union and intersection are commutative), but does lead the desired conclusion. $\square$

Tao Analysis I - 3.1.8

Exercise 3.1.8

Let $A$, $B$ be sets. Prove the absorption laws $A \cap (A \cup B)=A$ and $A \cup (A \cap B)= A$.

Show $A \cap (A \cup B) = A$

Let's write out the LHS using the definitions of intersection and union (Definition 3.1.22, Axiom 3.5).

$$x \in (A \cap (A \cup B)) \iff (x \in A) \land ((x \in A) \lor (x \in B))$$

This tells us the following two statements are both true:

• $(x \in A)$
• $(x \in A) \lor (x \in B)$

Both statements are only true when $(x \in A)$. So we can say $A \cap (A \cup B) \implies A$.

We now need to show $A \implies A \cap (A \cup B)$. 

$$x \in A \implies x \in A \cup B$$

This is because, by definition, $A \subseteq A \cup X$ for any $X$. 

Furthermore, since $x \in A$ is true, we have

$$x \in A \implies (x \in A) \land (x \in A \cup B)$$

This is equivalent to $A \implies A \cap (A \cup B)$.

Having shown both  $A \cap (A \cup B) \implies A$ and $A \implies A \cap (A \cup B)$, we can conclude $A \cap (A \cup B) = A$. $\square$

Show $A \cup (A \cap B) = A$

Let's write out the LHS using the definitions of union and intersection.

$$x \in (A \cup (A \cap B)) \iff (x \in A) \lor ((x \in A) \land (x \in B))$$

This tells us that either, or both, of the following two statements are true:

• $(x \in A)$
• $(x \in A) \land (x \in B)$

These become two cases to consider. 

In the first case, $(x \in A)$, so $A \cup (A \cap B) \implies A$.

In the second case, $(x \in A) \land (x \in B) \implies $(x \in A)$, so again  $A \cup (A \cap B) \implies A$.

Both cases gives us $A \cup (A \cap B) \implies A$.

We now need to show $A \implies A \cup (A \cap B)$. This is straight forward, because $A \implies A \cup X$ for any $X$, by definition. So we have  $A \implies A \cup (A \cap B)$.

So having shown both $A \cup (A \cap B) \implies A$ and $A \implies A \cup (A \cap B)$, we can conclude $A \cup (A \cap B) = A$. $\square$

Note

The proof of the first identity can be shorted as follows:

Let's write out the LHS using the definitions of intersection and union (Definition 3.1.22, Axiom 3.5).

$$x \in (A \cap (A \cup B)) \iff (x \in A) \land ((x \in A) \lor (x \in B))$$

This tells us the following two statements are both true:

• $(x \in A)$
• $(x \in A) \lor (x \in B)$

Both statements are only true if and only if $(x \in A)$. That is,

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

So we can say $A \cap (A \cup B) = A$. $\square$

Tao Analysis I - 3.1.7

Exercise 3.1.7

Let $A$, $B$, $C$ be sets. Show that $A \cap B \subseteq A$ and $A \cap B \subseteq B$. Furthermore, show that $C \subseteq A$ and $C \subseteq B$ if and only if $C \subseteq A \cap B$. In a similar spirit, show that $A \subseteq A \cup B$ and $B \subseteq A \cup B$, and furthermore that $A \subseteq C$ and $B \subseteq C$ if and only if $A \cup B \subseteq C$.

Show $A \cap B \subseteq A$ and $A \cap B \subseteq B$

Let's start with Definition 3.1.22 of intersection,

$$x \in (A \cap B) \iff (x \in A) \land (x \in B)$$

Both $(x \in A)$ and $(x \in B)$ are true. This gives us

$$\begin{align}x \in (A \cap B) &\implies (x \in A) \\ \\ x \in (A \cap B) &\implies (x \in B) \end{align}$$

This is equivalent to the two statements we want to prove $A \cap B \subseteq A$ and $A \cap B \subseteq B$. $\square$

Show $C \subseteq A$ and $C \subseteq B$ if and only if $C \subseteq A \cap B$

Let's start by writing down the meanings of $C \subseteq A$ and $C \subseteq B$,

$$\begin{align}(x \in C) &\implies (x \in A) \\ \\ (x \in C) &\implies (x \in B)  \end{align}$$

Both of these statements are true, so we have

$$(x \in C) \implies (x \in A) \land (x \in B)$$

This gives us $(C \subseteq A) \land (C \subseteq B) \implies C \subseteq (A \cap B)$.

We now need to show $C \subseteq (A \cap B) \implies (C \subseteq A) \land (C \subseteq B)$. Let's apply the definition of intersection to $C \subseteq (A \cap B)$

$$\begin{align}x \in C &\implies x \in (A \cap B) \\ \\ & \implies (x \in A) \land (x \in B)\end{align}$$

This gives us two statements which are true,

$$\begin{align}(x \in C) &\implies (x \in A) \\ \\ (x \in C) &\implies (x \in B)  \end{align}$$

This is equivalent to $C \subseteq (A \cap B) \implies (C \subseteq A) \land (C \subseteq B)$.

Having shown both

$$(C \subseteq A) \land (C \subseteq B) \implies C \subseteq (A \cap B)$$

and

$$C \subseteq (A \cap B) \implies (C \subseteq A) \land (C \subseteq B)$$

we can conclude 

$$(C \subseteq A) \land (C \subseteq B) \iff C \subseteq (A \cap B) \; \square$$

Show $A \subseteq A \cup B$ and $B \subseteq A \cup B$

The definition of union, Axiom 3.5, tells us that $x \in X \implies x \in (X \cup Y)$ for any $Y$. 

So we have

$$\begin{align}x \in A &\implies x \in (A \cup B) \\ \\ x \in B &\implies x \in (A \cup B) \end{align}$$

This immediately gives us $A \subseteq A \cup B$ and $B \subseteq A \cup B$. $\square$

Show $A \subseteq C$ and $B \subseteq C$ if and only if $A \cup B \subseteq C$

Let's start by writing down the meanings of $A \subseteq C$ and $B \subseteq C$,

$$\begin{align}(x \in A) &\implies (x \in C) \\ \\ (x \in B) &\implies (x \in C)  \end{align}$$

Either, or both, statements $(x \in A)$ and $(x \in B)$ implies $(x \in C)$, which we write as

$$(x \in A) \lor (x \in B) \implies (x \in C)$$

This is equivalent to $(A \subseteq C) \lor (B \subseteq C) \implies (A \cup B \subseteq C)$.

We need to show also $(A \cup B \subseteq C) \implies (A \subseteq C) \lor(B \subseteq C)$. Let's apply the definition of union,

$$(x \in A) \lor (x \in B) \implies x \in C$$

This tells us that either, or both, $(x \in A) \implies (x \in C) $ and $(x \in B) \implies (x \in C)$ are true. That is, $(A \subseteq C) \lor(B \subseteq C)$.

Having shown both

$$(A \subseteq C) \lor (B \subseteq C) \implies (A \cup B \subseteq C)$$

and

$$(A \cup B \subseteq C) \implies (A \subseteq C) \lor(B \subseteq C)$$

we can conclude

$$A \subseteq C \land B \subseteq C \iff A \cup B \subseteq C \; \square$$

Tao Analysis I - 3.1.6

Exercise 3.1.6

Prove Proposition 3.1.27. (Hint: one can use some of these claims to prove others. Some of the claims have also appeared previously in Lemma 3.1.12.)

Let's write out Proposition 3.1.27.

Proposition 3.1.27 (Sets form a boolean algebra). Let $A$, $B$, $C$ be sets, and let $X$ be a set containing $A$, $B$, $C$ as subsets.

(a) (Minimal element) We have $A\cup \emptyset = A$ and $A \cap \emptyset = \emptyset$.

(b) (Maximal element)We have $A \cup X = X$ and $A \cap X=A$.

(c) (Identity) We have $A \cap A=A$ and $A \cup A=A$.

(d) (Commutativity) We have $A \cup B=B \cup A$ and $A \cap B=B \cap A$.

(e) (Associativity) We have $(A \cup B) \cup C = A \cup (B \cup C)$ and $(A \cap B) \cap C = A \cap (B \cap C)$.

(f) (Distributivity) We have $A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C)=(A \cup B) \cap (A \cup C)$.

(g) (Partition) We have $A \cup (X \setminus A) = X$ and $A \cap (X \setminus A) = \emptyset$.

(h) (De Morgan laws) We have $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$ and $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$.

Let's prove each in turn.

(a) Minimal Element

We need to show $A\cup \emptyset = A$ and $A \cap \emptyset = \emptyset$.

Let's start with the first and use the definition of a pairwise union, Axiom 3.5.

$$x \in (A \cup \emptyset) \iff (x \in A) \lor (x \in \emptyset)$$

The definition of an empty set, Axiom 3.5, tells us that an empty set has no members. That is, $x \in \emptyset$ is never true. So the above simplifies to

$$x \in (A\cup \emptyset) \iff (x \in A)$$

Thus $A\cup \emptyset = A$. $\square$

Now let's consider $A \cap \emptyset = \emptyset$ and use the definition of intersection, Definition 3.1.22.

$$x \in (A \cap \emptyset) \iff (x \in A) \land (x \in \emptyset)$$

The definition of an empty set, Axiom 3.5, tell us that an empty set has no members. So the expression $(x \in A) \land (x \in \emptyset)$ is always false. That is, $x \in (A\cap \emptyset)$ is never true. 

Thus $A\cap \emptyset = \emptyset$. $\square$

(b) Maximal Element

We  need to show $A \cup X = X$ and $A \cap X=A$.

We have already shown in Exercise 3.1.5 that $A \subseteq B$, $A \cup B=B$, $A \cap B=A$ are logically equivalent. Here we have $A \subseteq X$ and so $A \cup X=X$, $A \cap X=A$ are true. $\square$

(c) Identity

We need to show $A \cap A=A$ and $A \cup A=A$.

Let's use the definition of a pairwise union, Axiom 3.5, and equate $A = B$.

$$\begin{align}x \in (A \cup A) &\iff (x \in A) \lor (x \in A) \\ \\ & \iff (x \in A) \end{align}$$

This gives us $A \cap A=A$. $\square$

Now let's use the definition of intersection, Definition 3.1.22, and equate $A=B$.

$$\begin{align}x \in (A \cap A) &\iff (x \in A) \land (x \in A) \\ \\ & \iff (x \in A) \end{align}$$

This gives us $A \cup A=A$. $\square$

(d) Commutativity

We need to show $A \cup B=B \cup A$ and $A \cap B=B \cap A$.

Let's use the definition of a pairwise union, Axiom 3.5.

$$\begin{align}x \in (A \cup B) &\iff (x \in A) \lor (x \in B) \\ \\ & \iff (x \in B) \lor (x \in A) \end{align}$$

The second line is justified because logical disjunction is commutative.

So we have  $A \cup B=B \cup A$. $\square$

Now let's use the definition of intersection, Definition 3.1.22.

$$\begin{align}x \in (A \cup B) &\iff (x \in A) \land (x \in B) \\ \\ & \iff (x \in B) \land (x \in A)  \end{align}$$

The second line is justified because logical conjunction is commutative.

So we have  $A \cap B=B \cap A$. $\square$

(e) Associativity

We need to show $(A \cup B) \cup C = A \cup (B \cup C)$ and $(A \cap B) \cap C = A \cap (B \cap C)$.

The first identity that union is associative is Lemma 3.1.12 proven in the text. 

Now we turn to the second identity $(A \cap B) \cap C = A \cap (B \cap C)$. Using Definition 3.1.22 of intersection,

$$x \in (A \cap B) \cap C \iff (x \in A \cap B) \land (x \in C)$$

This gives us $x \in C$.

Considering $(A \cap B)$,

$$x \in (A \cap B) \iff (x \in A ) \land (x \in B)$$

This gives us $x \in A$ and $x \in B$.

So in summary we have that all $x \in A$,  $x \in B$ and $x \in C$ are true.

Using $x \in B$ and $x \in C$, and Definition 3.1.22 of intersection,

$$(x \in B) \land (x \in C) \iff x \in (B \cap C)$$

And using $x \in A$,

$$(x \in A) \land (x \in B \cap C) \iff x \in A \cap (B\cap C)$$

That is, $(A \cap B) \cap C = A \cap (B \cap C)$. $\square$

(f) Distributivity

We need to show $A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C)=(A \cup B) \cap (A \cup C)$.

Let's start with the first identity, and use Definition 3.1.22 of intersection,

$$x \in (A \cap (B \cup C)) \iff (x \in A) \land (x \in (B \cup C))$$

This gives us $x \in A$ as true, as well as $x \in (B \cup C)$.

Consider $(B \cup C)$ and use the definition of a pairwise union, Axiom 3.5,

$$x \in (B \cup C) \iff (x \in B) \lor (x \in C)$$

This gives us two combinations, at least one of which must be true

• $(x \in A) \land (x \in B)$
• $(x \in A) \land (x \in C)$

"At least one of which must be true" means a disjunction between the two statements.

$$x \in (A \cap (B \cup C)) \iff (x \in A \land x\in B) \lor (x \in A \land x\in C)$$

This proves the first identity $A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$. $\square$.

Now let's consider the RHS of the second identity, and use Definition 3.1.22 of intersection,

$$x \in ((A \cup B) \cap (A \cup C)) \iff (x \in (A \cup B)) \land (x \in (A \cup C))$$

Applying the definition of union Axiom 3.5, we have two combinations, both of which must be true

• $x \in A \lor x \in B$
• $x \in A \lor x \in C$

If $x \in A$ then both of these statements are true. If $x \not \in A$, then both statements are only true if $x \in B$ and $x \in C$.  That is, $(x \in A) \lor ((x \in B) \land (x \in C))$.

So we have shown, $A \cup (B \cap C)=(A \cup B) \cap (A \cup C)$. $\square$

(g) Partition

We need to show $A \cup (X \setminus A) = X$ and $A \cap (X \setminus A) = \emptyset$.

Let's start with the first identity $A \cup (X \setminus A) = X$, and use Axiom 3.5 which defines union,

$$x \in (A \cup (X \setminus A)) \iff (x \in A) \lor (x \in X \setminus A)$$

Since $A \subseteq X$, we have $x \in A \implies x \in X$, which gives us

$$\begin{align}x \in (A \cup (X \setminus A)) &\implies (x \in X) \lor (x \in X \setminus A) \\ \\ &\implies x \in X\end{align}$$

The last step is true because $x \in X$ is true, or $x \in X \setminus A$ is true, and in both cases $x \in X$.

So we have $A \cup (X \setminus A) \subseteq X$. We now need to show $X \subseteq A \cup (X \setminus A)$.

Consider $x \in X$. Since $A \subseteq X$, we have $(x \in A) \lor (x \not \in A)$. The case $(x \not \in A)$ combined with $x \in X$, which is true by hypothesis, gives us $(x \in X \setminus A)$. So we have

$$x \in X \implies (x \in A) \lor (x \in X \setminus A)$$

That is, $X \subseteq A \cup (X \setminus A)$. 

Having shown both $A \cup (X \setminus A) \subseteq X$, and  $X \subseteq A \cup (X \setminus A)$, we can conclude $A \cup (X \setminus A) = X$. $\square$

Now let's consider the second identity $A \cap (X \setminus A) = \emptyset$, and use Definition 3.1.22 of intersection,

$$x \in (A \cap (X \setminus A)) \iff (x \in A) \land (x \in X \setminus A)$$

So both $(x \in A)$ and $(x \in X \setminus A)$ must be true. However, Definition 3.1.26 for set difference tells us that $(x \in X \setminus A)$ means $(x \not \in A)$. The only solution to this apparent contradiction is if $x \in \emptyset$. 

So we have $A \cap (X \setminus A) = \emptyset$. $\square$

(h) De Morgan's Laws

We need to show $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$ and $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$.

Let's start with the first identity $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$, and use the Definition 3.1.26 for set difference.

$$x \in (X \setminus (A \cup B)) \iff (x \in X) \land (x \not \in (A \cup B))$$

Both statements $(x \in X)$ and $(x \not \in (A \cup B))$ must be true. Let's consider the second statement.

$$\begin{align}(x \not \in (A \cup B)) &\iff \neg((x \in A) \lor (x \in B)) \\ &\iff (x \not \in A) \land (x \not \in B)\end{align}$$

This is because $\neg(P \lor Q) \equiv (\neg P) \land (\neg Q)$.

We can write these as two combined statements, both of which must be true.

• $(x \in X) \land (x \not \in A)$
• $(x \in X) \land (x \not \in B)$

Which is equivalent to $(X \setminus A) \cap (X \setminus B)$.

So we have shown $X \setminus (A \cup B)=(X \setminus A) \cap (X \setminus B)$. $\square$

Now let's consider the second identity $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$, and use the Definition 3.1.26 for set difference.

$$x \in (X \setminus (A \cap B)) \iff (x \in X) \land (x \not \in (A \cap B))$$

Both statements $(x \in X)$ and $(x \not \in (A \cap B))$ must be true. Let's consider the second statement.

$$\begin{align}(x \not \in (A \cap B)) &\iff \neg((x \in A) \land (x \in B)) \\ &\iff (x \not \in A) \lor (x \not \in B)\end{align}$$

This is because $\neg(P \land Q) \equiv (\neg P) \lor (\neg Q)$.

We can write these as two combined statements, at least one of which must be true.

• $(x \in X) \land (x \not \in A)$
• $(x \in X) \land (x \not \in B)$

Which is equivalent to $(X \setminus A) \cup (X \setminus B)$.

So we have shown $X \setminus (A \cap B)=(X \setminus A) \cup (X \setminus B)$. $\square$

Tao Analysis I - 3.1.5

Exercise 3.1.5

Let A, B be sets. Show that the three statements $A \subseteq B$, $A \cup B=B$, $A \cap B=A$ are logically equivalent (any one of them implies the other two).

Approach

There are three statements we need to show are equivalent. 

• $S_1: A \subseteq B$
• $S_2: A \cup B=B$
• $S_3: A \cap B=A$

To show an equivalence between two statements $S_i \iff S_j$ we need to show $S_i \implies S_j$ and $S_j \implies S_i$. This would suggest showing six implications in total. However, we only need to show the following three implications:

• $S_1 \implies S_2$
• $S_2 \implies S_3$
• $S_3 \implies S_1$

This is equivalent to showing equivalence amongst all $S_1$, $S_2$ and $S_3$, because there is a chain of implications between any $S_i$ and $S_j$, and also $S_j$ and $S_i$. For example $S_1 \implies S_2$ and $S_2 \implies S_3 \implies S_1$.

Show $S_1 \implies S_2$

Using $A \subseteq B$, we need to show both $A \cup B \subseteq B$ and $B \subseteq A \cup B$.

Let's start with the definition of $A \cup B$

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

By hypothesis we have $A \subseteq B$, which is defined as

$$(A \subseteq B) \implies [(x \in A) \implies (x \in B)]$$

Or more simply, whenever we have $x \in A$, we can substitute $x \in B$.

So, substituting into the definition of union, we have

$$\begin{align}x \in (A \cup B) &\iff (x \in A) \lor (x \in B) \\ \\ &\implies (x \in B) \lor (x \in B) \\ \\ & \implies x \in B \end{align}$$

So $A \cup B \subseteq B$ if we're given $A \subseteq B$.

Now we need to show $B \subseteq A \cup B$. Let's consider

$$(x \in A) \implies (x \in A) \lor (x \in B)$$

This is true by definition of disjunction. In fact $(x \in A) \implies (x \in A) \lor (x \in C)$ for any $C$.

So $B \subseteq A \cup B$. Notice we didn't need to use $A \subseteq B$ here.

We have shown both $A \cup B \subseteq B$ and $B \subseteq A \cup B$, from which we conclude $A \cup B = B$. So $A \subseteq B \implies A \cup B=B$. $\square$

Show $S_2 \implies S_3$

Using $A \cup B=B$, we need to show $A \cap B = A$. To do this we need to show both $A \cap B \subseteq A$ and $A \subseteq A \cap B$.

Let's start with the definition of $A \cap B$.

$$\begin{align}x \in (A \cap B) &\iff (x \in A) \land (x \in B) \\ \\ &\implies (x \in A)\end{align}$$

Thus $A \cap B \subseteq A$.

Now let's show $A \subseteq A \cap B$.

Using the definition of disjunction, we have $A \subseteq A \cup B$. But by hypothesis, $A \cup B=B$, so we have recovered $S_1: A \subseteq B$.

Now let's consider the following which looks obvious,

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

Using  $S_1: A \subseteq B$, that is $(x \in A) \implies (x \in B)$, we can substitute $x \in B$ for $x \in A$,

$$(x \in A) \implies (x \in A) \land (x \in B)$$

That is, $A \subseteq A \cap B$.

We have shown both $A \cap B \subseteq A$, and $A \subseteq A \cap B$, from which we conclude $A \cap B = A$. $\square$

Show $S_3 \implies S_1$

Using $A \cap B=A$, we need to show $A \subseteq B$. This is not an equality so we don't need to show $B \subseteq A$, which is, in any case, false.

Using the hypotheses $A = A \cap B$, we immediately have

$$\begin{align}(x \in A) &\implies (x \in A) \land (x \in B) \\ \\ &\implies (x \in B)\end{align}$$

That is $A \subseteq B$. $\square$

Conclusion

We have shown the three implications, 

• $S_1 \implies S_2$
• $S_2 \implies S_3$
• $S_3 \implies S_1$

Thereby we have shown the three statements $A \subseteq B$, $A \cup B=B$, $A \cap B=A$ are logically equivalent. 

Tao Analysis I - 3.1.4

Exercise 3.1.4

Prove the remaining claims in Proposition 3.1.17

Let's write out Proposition 3.1.17.

Proposition 3.1.17 (Sets are partially ordered by set inclusion). Let $A$, $B$, $C$ be sets. If $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$. If $A \subseteq B$ and $B \subseteq A$, then $A = B$. Finally, if $A \subsetneq B$ and $B \subsetneq C$ then $A \subsetneq C$.

Note: the symbol $\subsetneq$ means proper subset, that is subset but not equal.

The textbook proofs the first claim. We'll prove the remaining two.

Show that if $A \subseteq B$ and $B \subseteq A$, then $A = B$

Let's write out the antecedent of this claim

$$(A \subseteq B) \land (B \subseteq A)$$

If $x \in A$ then by $(A \subseteq B)$ we have $x \in B$. Similarly, if $x \in B$ then by $(B \subseteq A)$ we have $x \in A$.

So we have the following

$$(x \in A \implies x \in B) \land (x \in B \implies x \in A)$$

That is,

$$x \in A \iff x \in B$$

This is simply stating that $A=B$ by Axiom 3.2 which defines equal sets. Thus we have shown that if $A \subseteq B$ and $B \subseteq A$, then $A = B$. $\square$

Show that if $A \subsetneq B$ and $B \subsetneq C$ then $A \subsetneq C$

To show $A \subsetneq C$ we need to show

• if $x \in A$ then $x \in C$, that is $A \subseteq C$
• but there exists a $y \in C$ that is not in $A$, that is $A \neq B$

Let's start with the first statement. If $x \in A$ then by $A \subsetneq B$ we have $x \in B$. Also, if $x \in B$ then by $B \subsetneq C$ we have $x \in C$. So $x \in A \implies x \in C$.

Now let's address the second statement. $B \subsetneq C$ tells us that there exists a $y \in C$ that is not in $B$. But $A \subsetneq B$ tells us every element $x \in A$ is also in $B$. So every $x \in A$ is in $B$ but not every $y \in C$ is in $B$. That is, there exists a $y \in C$ that is not in $A$.

We have shown  $A \subsetneq B$ and $B \subsetneq C$ then $A \subsetneq C$. $\square$

Tao Analysis I - 3.1.3

Exercise 3.1.3

Prove the remaining claims in Lemma 3.1.12.

Let's write out Lemma 3.1.12.

Lemma 3.1.12 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$.

The textbook provides a proof that union is associative. We'll prove the remaining claims.

Show $\{a,b\}=\{a\} \cup \{b\}$

Axiom 3.4 defining pair sets tells us that the only elements of $\{a,b\}$ are $a$ and $b$. That is

$$x \in \{a,b\} \iff (x=a \lor x=b)$$

Axiom 3.4 defining singletons tells us

$$\begin{align}x \in \{a\} &\iff x=a \\ \\ x \in \{b\} &\iff x=b\end{align}$$

Axiom 3.5 defines pairwise union as follows

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

Thus

$$x \in (\{a\} \cup \{b\}) \iff ((x \in \{a\}) \lor (x \in \{b\}))$$

This is equivalent to the following (Axiom 3.4),

$$x \in (\{a\} \cup \{b\}) \iff ((x = a) \lor (x=b))$$

And by Axiom 3.4 again,

$$x \in (\{a\} \cup \{b\}) \iff ((x = a) \lor (x=b)) \iff x \in \{a,b\}$$

We have shown $\{a,b\}=\{a\} \cup \{b\}$. $\square$

Union is Commutative $A \cup B = B \cup A$

We want to prove $A \cup B = B \cup A$.

By Axiom 3.5 which defines pairwise union we have

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

Because  logical disjunction $\lor$ is commutative, we have

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

By Axiom 3.5, we also have

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

These three statements give us

$$x \in (A \cup B) \iff x \in (B \cup A)$$

That is, $A \cup B = B \cup A$. $\square$

Show  $A \cup A = A \cup \emptyset = \emptyset \cup A = A$

We have already shown that pairwise union is commutative, so we don't need to show again that

$$A \cup \emptyset = \emptyset \cup A \; \square$$

Let's use Axiom 3.5 which defines union to write

$$x \in (A \cup A) \iff ((x \in A) \lor (x \in A))$$

We can simplify the RHS,

$$x \in (A \cup A) \iff (x \in A)$$

This is simply stating that

$$A \cup A = A \; \square$$

All that remains is to show $A \cup \emptyset = A$. Let's again use Axiom 3.5 which defines union to write

$$x \in (A \cup \emptyset) \iff ((x \in A) \lor (x \in \emptyset))$$

Since there is no $x \in \emptyset$ by Axiom 3.3 which defines the empty set, we can simplify the RHS,

$$x \in (A \cup \emptyset) \iff (x \in A)$$

This is simply stating that

$$A \cup \emptyset = A \; \square$$

Tao Analysis I - 3.1.2

Exercise 3.1.2

Using only Axiom 3.2, Axiom 3.1, Axiom 3.3, and Axiom 3.4, prove that the sets $\emptyset$, $\{ \emptyset \}$, $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$ are all distinct (i.e., no two of them are equal to each other).

Let's remind ourselves of Axioms 3.1-3.4,

• Axiom 3.1 (Sets are objects). If A is a set, then A is also an object.
• Axiom 3.2 (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.
• Axiom 3.3 (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 \not \in \emptyset$.
• Axiom 3.4 (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\}$ iff $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\}$ iff $y = a$ or $y = b$; we refer to this set as the pair set formed by $a$ and $b$.

Show $\emptyset$ is different from $\{ \emptyset \}$, $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$.

Let's first show that $\emptyset$ is not equal to any of $\{ \emptyset \}$, $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$. 

Axiom 3.3 defines the empty set as having no members. That means no element of any other set can be a member of $\emptyset$.

The other sets do have members by Axiom 3.4. To be specific, $\emptyset \in \{ \emptyset \}$, $\{ \emptyset \} \in \{\{ \emptyset \}\}$ and $\emptyset \in \{ \emptyset, \{ \emptyset \} \}$. 

Axiom 3.2 on set equality requires equal sets to have all their members in common. So $\emptyset$ is different from all the others - because all the other sets have members, and $\emptyset$ has no members.

Having dealt with $\emptyset$, we can now remove it from the list and consider the remaining sets $\{ \emptyset \}$, $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$.

For the rest of this exercise we won't explicitly state that we're using Axiom 3.4 to say that a singleton set $\{a\}$ has a member $a$, and that a pair set $\{a,b\}$ has members $a$ and $b$.

Show $\{\emptyset\}$ is different from $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$.

Let's show that $\{\emptyset\}$ is not equal to any of $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$. 

The element $\{ \emptyset \}$ of $\{\{ \emptyset \}\}$ is not a member of $\{\emptyset\}$. Similarly, the element $\emptyset$ of $\{ \emptyset, \{ \emptyset \} \}$ is not a member of $\{ \emptyset \}$. So by Axiom 3.2, $\{\emptyset\}$ is not equal to any of $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$.

Having dealt with $\{\emptyset\}$, we can now remove it from the list and consider the remaining sets $\{\{ \emptyset \}\}$ and $\{ \emptyset, \{ \emptyset \} \}$.

Show $\{\{ \emptyset \}\}$ is different from $\{ \emptyset, \{ \emptyset \} \}$.

Let's show that $\{\{ \emptyset \}\}$ is not equal to $\{ \emptyset, \{ \emptyset \} \}$.

We could say the sets are not equal because their cardinalities are different. That is, $|\{\{ \emptyset \}\}|=1$ and $|\{ \emptyset, \{ \emptyset \} \}|=2$. However we haven't covered cardinality in the book yet so we must rely only on the Axioms 3.1-3.4, 

We can see the element $\emptyset$ of $\{ \emptyset, \{ \emptyset \} \}$ is not a member of $\{\{ \emptyset \}\}$. So by Axiom 3.2, $\{\{ \emptyset \}\}$ is not equal to $\{ \emptyset, \{ \emptyset \} \}$.

All the results above show that no two of the given sets are equal. $\square$

Tao Analysis I - 3.1.1

Exercise 3.1.1

Let $a$, $b$, $c$, $d$ be objects such that $\{a, b\} = \{c, d\}$. Show that at least one of the two
statements “$a = c$ and $b = d$” and “$a = d$ and $b = c$” hold.

Let's start with the definition of the equality of two sets.

Axiom 3.2 (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.

Let's apply this definition our scenario:

1. $a$ is a member of $\{c,d\}$. That means $(a=c) \lor (a=d)$ is true.
2. $b$ is a member of $\{c,d\}$. That means $(b=c) \lor (b=d)$ is true.
3. $c$ is a member of $\{a,b\}$. That means $(c=a) \lor (c=b)$ is true.
4. $d$ is a member of $\{a,b\}$. That means $(d=a) \lor (d=b)$ is true.

The key to this exercise is recognising that all four statements must be true.

Let's start by considering the case $a=c$, which makes (1) true. It also makes (3) true. How we ensure (2) and (4) are also true? This is only possible when $b=d$. Thus the statement  “$a = c$ and $b = d$” satisfies the definition of set equality.

Let's consider the case $a=d$ which makes (1) true. It also makes (4) true. How do we ensure (2) and (3) are true? This is only possible when $b=c$. Thus the statement  “$a = d$ and $b = c$” satisfies the definition of set equality.

Can both statements be true at the same time? Let's start with $a=c$ from the first statement. The second statement gives us $b=c$. The first statement then gives us $b=d$. That is, $a=b=c=d$ also satisfies the equality of sets.

We have shown that the set equality $\{a, b\} = \{c, d\}$ means at least one of the statements “$a = c$ and $b = d$” and “$a = d$ and $b = c$” holds. $\square$

Tao Analysis I - 2.3.5

Exercise 2.3.5

Prove Proposition 2.3.9. (Hint: fix q and induct on n.)

 

 Let's write out Proposition 2.3.9.

Proposition 2.3.9 (Euclid’s division lemma). Let $n$ be a natural number, and let $q$ be a positive number. Then there exist natural numbers $m$, $r$ such that $0 \leq r < q$ and $n = mq + r$.

 

Let's follow the hint and prove this by induction. Before we dive in, it is worth noting the point of the proof is to show existence, which can make the proof easier.

Let the proposal $P(n)$ tate that there exist natural numbers $m$, $r$ such that $0 \leq r < q$ and $n = mq + r$.

The inductive hypothesis is that $P(n)$ is true. 

The base case is $P(0)$. That is, there exist natural numbers $m$, $r$ for

$$0 = mq + r$$

where $0 \leq r < q$.

One solution is $m=0$ and $r=0$. The existence of one solution is all we need to show the base case is true. As it happens, it is the only possible solution, but that is not required here.

The inductive step requires us to show that $P(n++)$ is true. That is, there exist natural numbers $m'$, $r'$ for

$$n++ = m'q + r'$$

where $0 \leq r < q'$.

Let's start with the inductive hypothesis.

$$n = mq + r$$

Incrementing both sides,

$$\begin{align} n++ &= (mq + r)++ \\ \\ &= mq + (r++) \\ \\ &= m'q + r' \end{align}$$

The simplest case is where $m'=m$ and $r'=r++$, as long as $r' < q$, that is $r++ < q$.

However, since $r < q$ means $r++ \leq q$ by Proposition 2.2.12, it is possible that $r++ = q$. In this case, using the distributivity of multiplication Proposition 2.3.4,

$$\begin{align} n++ &= mq + q \\ \\ &= (m+1)q + 0\\ \\ &= m'q + r' \end{align}$$

where $m'=m+1$ and $q=0$.

We have shown that $m'$ and $r'$ can always exist for $n++ = m'q + r'$, where $0 \leq r' < q$. This completes the induction step.

By showing the base case $P(0)$ is true, and that $P(n) \implies P(n++)$, by induction we have shown $P(n)$ holds for all natural numbers $n$. That is there exist natural numbers $m$, $r$ such that $0 \leq r < q$ and $n = mq + r$. $\square$

Tao Analysis I - 2.3.4

Exercise 2.3.4

Prove the identity $(a + b)^2 = a^2 + 2ab + b^2$ for all natural numbers $a$, $b$.

We want to show the following.

$$((a++) + b)^2 = (a++)^2 + (2 \times (a++) \times b) + b^2$$

Let's expand the LHS using the Definition 2.3.11 of exponentiation that $x^2=x^1 \times x$,  and the distributive law of Proposition 2.3.4 twice,

$$\begin{align}((a++) + b)^2 &= ((a++) + b) \times ((a++) + b) \\ \\ &= [((a++) + b)\times (a++)] + [((a++)+b) \times b)] \\ \\  &= (a++)^2 + (b \times (a++)) + ((a++)\times b) + b^2\end{align}$$

We now use commutivity of multiplication of Lemma 2.3.2,

$$\begin{align}((a++) + b)^2 &= (a++)^2 + (b \times (a++)) + ((a++)\times b) + b^2 \\ \\ &= (a++)^2 + (b \times (a++)) + (b \times (a++)) + b^2 \\ \\ &= (a++)^2 + (2 \times (a++) \times b) + b^2 \end{align}$$

The last step uses Definition 2.3.1 that $2 \times m = 0 + m + m$.

The final expression is the RHS, and so we have shown that for all natural numbers $(a + b)^2 = a^2 + 2ab + b^2$. $\square$

Tao Analysis I - 2.3.3

Exercise 2.3.3

Prove Proposition 2.3.5. (Hint: modify the proof of Proposition 2.2.5 and use the
distributive law.)

Let's write down Proposition 2.3.5.

Proposition 2.3.5 (Multiplication is associative). For any natural numbers $a$, $b$, $c$, we have $(a \times b) \times c = a \times (b \times c)$.

The question hints that we should modify the proof of Proposition 2.2.5 regarding the associatibity of addition.

Let's use induction on $a$. The proposal $P(a)$ says that $(a \times b) \times c = a \times (b \times c)$

The induction hypothesis is that $P(a)$ is true. That is

$$(a \times b) \times c = a \times (b \times c)$$

The base case $P(0)$ is

$$(0 \times b) \times c = 0 \times (b \times c)$$

We can use Definition 2.3.1, $0 \times m:= 0$, to simplify

$$(0) \times c = 0 \times (b \times c)$$

This simplifies again to $0 = 0$ which is true. So the base case $P(0)$ is true.

The inductive step requires us to show $P(a++)$ is true. That is

$$((a++) \times b) \times c = (a++) \times (b \times c)$$

Let's consider the LHS and use Definition 2.3.1, $( n ++ ) \times m : = ( n \times m ) + m$, and then the distributive law of Proposition 2.3.4.

$$\begin{align}((a++) \times b) \times c &= ((a \times b) + b) \times c \\ \\ &= ((a \times b) \times c) + (b \times c)\end{align}$$

Let's now consider the RHS and use Definition 2.3.1, and the inductive hypothesis,

$$\begin{align}(a++) \times (b \times c) &= (a \times (b \times c)) + (b \times c) \\ \\ &= ((a \times b)\times c)) + (b \times c)\end{align}$$

The LHS and RHS are equivalent, so the inductive step succeeds.

We have shown the base case $P(0)$ is true, and that $P(a) \implies P(a++)$, and so by induction, $(a \times b) \times c = a \times (b \times c)$ is true for all natural numbers $a$. $\square$

Tao Analysis I - 2.3.2

Exercise 2.3.2

Prove Lemma 2.3.3. (Hint: prove the second statement first.)

Let's write down Lemma 2.3.3.

Lemma 2.3.3 (Positive natural numbers have no zero divisors). Let $n$, $m$ be natural numbers. Then $n \times m = 0$ if and only if at least one of $n$, $m$ is equal to zero. In particular, if $n$ and $m$ are both positive, then $nm$ is also positive.

It is worth recalling the definition of a positive number.

Definition 2.2.7 (Positive natural numbers). A natural number $n$ is positive
iff it is not equal to 0.

 

Let's take the hint and prove the second statement first. Let's do it by inducting on $n$ and fixing $m$.

Inductive hypothesis: $(n > 0) \land (m > 0) \implies (nm > 0)$

Base case: $n=0$ give us

$$(0 > 0) \land (m > 0) \implies (0 \times m > 0)$$

This simplifies to $\text{false} \implies \text{false}$, which is true, and so the base case is true.

Although not necessary, it is insightful to see what happens with $n=1$. This gives us

$$(1 > 0) \land (m > 0) \implies (1 \times m > 0)$$

This simplifies to $(m > 0) \implies (m > 0)$, which is also true.

Now let's turn to the induction step. We need to show that

$$((n++) > 0) \land (m > 0) \implies ((n++)\times m > 0)$$

Now, we know that if $n>0$ then $n++ > 0$, because by definition $n = 0 + d$ and  so $n++ = 0 + (d++)$ where $d \neq 0$. 

This gives us

$$(m > 0) \implies ((n++)\times m > 0)$$

Let's focus on $(n++) \times m$. By Definition 2.3.1 this is $nm + m$. And so if $nm > 0$, then $(n++) \times m = nm + m > 0$, because $m>0$ by inductive hypothesis.

So finally $((n++) > 0) \land (m > 0) \implies ((n++)\times m > 0)$ reduces to $\text{true} \implies \text{true}$, which is true, and so the inductive step succeeds.

 By induction, we have shown  $(n > 0) \land (m > 0) \implies (nm > 0)$. $\square$

Now we need to prove the first statement in Lemma 2.3.3, which is

$$(n \times m = 0) \iff (n=0) \lor (m=0)$$

We need to prove this in both directions.

Let's consider left to right, $(n \times m = 0) \implies (n=0) \lor (m=0)$. The contrapositive which is equivalent to the original statement.

$$\neg ( (n=0) \lor (m=0)) \implies \neg (n \times m = 0)$$

This simplifies to

$$ (n >0) \land (m > 0) \implies (n \times m > 0)$$

This is precisely what we have just proved above.

Let's consider right to left.

$$(n=0) \lor (m=0) \implies(n \times m = 0)$$

This covers three cases:

• $n=0$ which gives $0 \times m$ which by Definition 2.3.1 is 0.
• $m=0$ which gives $n \times 0$ which by commutativity of multiplication (Lemma 2.3.2) is also 0.
• $n=m=0$ which is covered by the $n=0$ case.

By proving both directions, we have shown $(n \times m = 0) \iff (n=0) \lor (m=0)$. $\square$

Tao Analysis I - 2.3.1

Thisset of of exercises is about multiplication.

Before we dive in, let's write out the minimal definitions we're given about multiplication.

Definition 2.3.1 (Multiplication of natural numbers). Let $m$ be a natural number. To multiply zero to $m$, we define $0 \times m := 0$. Now suppose inductively that we have defined how to multiply $n$ to $m$. Then we can multiply $n++$ to $m$ by defining $( n ++ ) \times m : = ( n \times m ) + m$. 

We can see this mirrors the definition for addition.

 

Exercise 2.3.1

Prove Lemma 2.3.2. (Hint: modify the proofs of Lemmas 2.2.2, 2.2.3 and Proposition 2.2.4)

Let's write out Lemma 2.3.2.

Lemma 2.3.2 (Multiplication is commutative). Let $n$, $m$ be natural numbers. Then $n \times m = m \times n$.

There are many parallels to the provided proof that addition is commutative, hence the suggestion to modify the proofs of Lemmas 2.2.2, 2.2.3 and Proposition 2.2.4. So let's develop our parallel lemmas based on those.

 

Lemma 1: For any natural number $n$, $n \times 0=0$.

Despite appearing obvious, we need to show it is true because the definition we have is $0 \times m := 0$.

We use induction. The induction hypothesis is that $n \times 0=0$.

The base case $n=0$ gives us $0 \times 0 = 0$. We can use $0 \times m := 0$ from the Definition 2.3.1 with $m=0$ to confirmt the base case is true.

Now let's consider the induction step. We want to show that $(n++) \times 0 = 0$ using the inductive hypothesis. By Definition 2.3.1 $(n++) \times 0 = (n \times 0) + 0$. Now, $(n \times 0)=0$ is the inductive hypothesis, so we have $(n++) \times 0 = 0 + 0 = 0$. So the induction step suceeds. 

Using induction, we have shown $n$, $n \times 0=0$. $\square$

Lemma 2: For any natural numbers $n$ and $m$, $n \times (m++)=(n \times m)+n$.

Despite appearing obvious, we do need to show it, because the definition only gives us $( n ++ ) \times m : = ( n \times m ) + m$.

We induct on $n$ keeping $m$ fixed. The induction hypothesis is $n \times (m++)=(n \times m)+n$.

The base case $n=0$ is $0 \times (m++)=(0 \times m)+0$. The LHS is 0 by Definition 2.3.1. The RHS also uses Definition 2.3.1 to give $(0) +0 = 0$. So the base case is true.

Now let's consider the induction step. We need to show that

$$(n++) \times (m++)=((n++) \times m)+(n++)$$

Let's start with the LHS, and use Definition 2.3.1, and then the induction hypothesis.

$$\begin{align}(n++) \times (m++) &= (n \times m++) + (m++) \\ \\ &= (n \times m) + n + (m++) \\ \\ &= (n \times m) + (n + m)++ \end{align}$$

Now consider the RHS, and use Definition 2.3.1.

$$\begin{align}((n++) \times m)+(n++) &= (n \times m) + m + (m++) \\ \\ &= (n \times m) + (n + m)++ \end{align}$$

The LHS and RHS are equivalent.  And so the induction step succeeds.

By induction we have shown that $n \times (m++)=(n \times m)+n$. $\square$

Lemma 2.3.2

We can now finally establish Lemma 2.3.2 that $n \times m = m \times n$.

Again we use induction on $n$, keeping $m$ fixed.

The induction hypothesis is that $n \times m = m \times n$ for natural numbers $m$ and $n$.

The base case $n=0$ gives us $0 \times m = m \ times 0$. The LHS is 0 by Definition 2.3.1. The RHS is 0 by Lemma 1, proved above. Thus the base case is true.

The induction step requires us to show that

$$(n++) \times m = m \times (n++)$$

Let's consider the LHS.

By Definition 2.3.1 we have

$$(n++) \times m =(n \times m) + m$$

Let's now consider the RHS, and apply Lemma 2, proved above, and then the induction hypothesis.

$$\begin{align}m \times (n++) &= (m \times n) + m \\ \\ &= (n \times m) + m\end{align}$$

The LHS and RHS are equivalent, so the induction step succeeds.

By induction we have shown that multiplication of natural numbers is commutative, $n \times m = m \times n$. $\square$

 

Tao Analysis I - 2.2.7

Exercise 2.2.7

Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m)$ is true, $P(m++)$ is true. Show that if $P(n)$ is true, then $P(m)$ is true for all $m \geq n$. (This principle is sometimes referred to as the principle of induction starting from the base case $n$.)

This looks easier than the last two exercises - let's hope it is!

 

Approach

The first thing to notice is that this scenario is very similar to the standard induction scenario, with the only difference beting that the variable is shifted up, from $m \geq 0$ to $m \geq n)$. This suggests we can reformulate the problem into the standard scenario by variable substitution.

 

Proof

Let's set

$$q = m-n$$

Here $n$ is fixed, and $m$ is free, and both are natural numbers.

If we can show that

• $P(q) \implies P(q++)$
• $P(q=0)$ is true

Then by the induction principle Axiom 2.5, we can say $P(q)$ is true for all natural numbers $q$.

Let's first consider $P(q) \implies P(q++)$. This is true because we are given that $P(m) \implies P(m++)$. The only constraint is that $q$ must be a natural number like $m$, which it is for $m \geq n$.

Let's now consider $P(q=0)$. Setting $q=0$ means $0 = m-n$, that is $n=m$. We are assuming that $P(n)$ is true. So $P(q=0)$ is true.

So we have established that for natural number $q$

• $P(q) \implies P(q++)$
• $P(q=0)$ is true

This is simply Axiom 2.5, so $P(q)$ is true for all natural numbers $q$. That is $P(q \geq 0)$ is true.

Now translating from $q$ back to $m$.

$$P(q \geq 0) \; \text{is true}$$

is the same as

$$P(m-n \geq 0) \; \text{is true}$$

That is,

$$P(m \geq n) \; \text{is true}$$

Thus we have shown $P(m \geq n)$. $\square$

Tao Analysis I - 2.2.6

Exercise 2.2.6

Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $m ≤ n$; this is known as the principle of backwards induction. (Hint: apply induction to the variable $n$.)

The proposal seems intuitively correct and obvious, so the challenge is to prove it using only the building blocks provided by the text up to this point.

In case it isn't obvious, let's illustrate it. If the property $P(5)$ is true, the statement $P(m++) \implies P(m)$ tells us that $P(4)$ is also true. Now we know $P(4)$ is true, we can use $P(m++) \implies P(m)$ again to tell us $P(3)$ is true. We can keep going until we show $P(0)$ is true. So $P(0 \leq m \leq 5)$ is true.

Approach

We might be tempted to use soem form of induction that works backwards, but we can't do that. That is what we're being asked to prove, and we can only use the principle of induction as defined in Axiom 2.5, which goes forward, not backwards. 

As with the previous exercise, we transform the problem from one about $P(m)$ to one which is about $n$ by formulating a statement $Q(n)$. 

$$Q(n) : P(n) \implies P(m \leq n)$$

That is, $Q(n)$ says if $P(n)$ is true, then $P(m)$ is true for all natural numbers up to and including $n$.

 

Induction Proof

Now we can use standard induction on $n$, which we hope will show $Q(n)$ is true for all natural numbers $n$. Before we dive in, let's write out the known facts for clarity.

$$P(m++) \implies P(m)$$

$$P(n) \; \text{is true}$$

Inductive Hypothesis: $Q(n)$ is true.

Base Case: Consider $n=0$, which means

$$\begin{align}Q(0) &: P(0) \implies P(m \leq 0) \\ \\ Q(0) &: P(0) \implies P(0)\end{align}$$

$P(m \leq 0)$ is equivalent to $P(0)$ beccause only $m=0$ satisfies the inequality. 

$Q(0)$ is clearly true because $P(0) \implies P(0)$ is always true ... even if $P(n=0)$ were false, which it is not here.

Inductive Step: We need to show $Q(n) \implies Q(n++)$.

Let's start with $Q(n)$.

$$Q(n) : P(n) \implies P(m \leq n)$$

But we're given $P(n++) \implies P(n)$ so

$$P(n++) \implies P(n) \implies P(m \leq n)$$

We're almost there. $A \implies B$ is equivalent to $A \implies (B \land A)$. In plain English this is saying the implication of $A$ includes $A$. This gives us

$$\begin{align}P(n++) &\implies P(m \leq n) \land P(n++) \\ \\ P(n++) &\implies P(m \leq n++)\end{align}$$

This is $Q(n++)$.

By showing the base case $Q(0)$, and that $Q(n) \implies Q(n++)$, by the induction principle we have shown $Q(n)$ is true for all natural numbers $n$.

Translating back from $Q$ to $P$, we have $P(n) \implies P(m \leq n)$ if $P(n)$ is true, and $P(m++) \implies P(m)$. $\square$

Tao Analysis I - 2.2.5

Review: Weak & Strong Induction

Before we dive in, it is worth reviewing what standard "weak" and strong induction is. The following table summarises the difference (inspired by this).

Here $P(n)$ is a statement, or proposal, about a natural number $n$. For brevity, we've abused notation $P(m \leq n)$ to mean that $P(m)$ is true for all $m \leq n$. 

Weak Induction	Strong Induction
If $P(n_0)$ is true, And $P(n) \implies P(n+1)$ Then $P(n)$ is true for all $n \geq n_0$	If $P(n_0)$ is true, And $P(m \leq n) \implies P(n+1)$ Then $P(n)$ is true for all $n \geq n_0$

 

The only difference is that strong induction broadens the assumption that $P(n)$ is true to $P(m \leq n)$ is true. 

There is some confusion caused by the name "strong" because here it means broader assumptions, which to some ears (including mine), sounds like a weaker statement overall. To me, a theorem that makes fewer assumptions is stronger than an a theorem that requires lots of pre-requisites to be true.

The following visualises the difference between weak and strong induction.

 

Strong induction is used when $P(n)$ being true is insufficient to show $P(n+1)$ is also true. Let's look at an example of each.

Example: Weak Induction

This is the classic example used to illustrate standard, or weak, induction.

Aim: Prove that $1 + 2 + \ldots + n = \frac{n(n+1)}{2}$

Inductive Hypothesis: $P(n) : 1 + 2 + \ldots + n = \frac{n(n+1)}{2}$ is true.

Base Case:  LHS of $P(1)$ is 1. RHS of $P(1) = \frac{1(1+1)}{2}=1$.

Inductive Step: Consider $P(n+1)$. LHS is $1 + 2 + \ldots + n + (n+1)$. Using the inductive hypothesis, this is $\frac{n(n+1)}{2} + (n+1)$. Simple algebra leads to $\frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$. This is the RHS of $P(n+1)$. So $P(n) \implies P(n+1)$.

$P(1)$ being true, and $P(n) \implies P(n+1)$ means, by the principle of induction, $P(n)$ is true for all positive natural numbers $n$. $\square$

Note that we used the inductive hypothesis $P(n)$ to show $P(n+1)$ was true.

 

Example: Strong Induction

This is a classic example used to illustrate strong induction.

Aim: Prove that any natural number $n \geq 2$ is a product of primes. Note that a prime is considered to be a product of one prime.

Inductive Hypothesis: $P(n)$ : Every natural number less than or equal to $n$ is a product of primes.

Base Case: Consider $P(2)$. This states that 2 is a product of primes. We know 2 is a prime, and as such is a product of one prime. So $P(2)$ is true.

Inductive Step: Consider $m$ such that $2 \leq m \leq n$. We assume $P(m)$ is true. That is, we assume every natural number from 2 to $n$ is a product a primes. Now consider $P(n+1)$. Is $(n+1)$ a prime itself? There are two cases, yes and no. If yes, then $P(n+1)$ is true. If no, $(n+1)$ is not a prime, then it is a composite of 2 factors, $(n+1)=x \cdot y$ where $2 \leq x \leq n$ and $y$ are $2 \leq y \leq n$. The strong assumptions tell us that $x$ and $y$ are both products of one or more primes. Therefore $(n+1)$ is a product of primes too, and $P(n+1)$ is true in this second case.

With the base case $P(2)$ being true, and $P(2 \leq m \leq n) \implies P(n+1)$ being true, we have by strong induction shown that $P(n)$ is true for all positive natural numbers $n \geq 2$. 

Notice how we couldn't just use $P(n)$ to show $P(n+1)$. We needed $P(m)$ for $2 \leq m \leq n$.

Reference

This is a really clear summary of weak and strong induction with the classical examples.

• https://www.cs.cornell.edu/courses/cs2800/2011fa/Lectures/induction.pdf
  

 

Exercise 2.2.5

Prove Proposition 2.2.14. (Hint: define $Q(n)$ to be the property that $P(m)$ is true for all $m_0 \leq m < n$; note that $Q(n)$ is vacuously true when $n \leq m_0$.)

Let's write out Proposition 2.2.14.

Proposition 2.2.14 (Strong principle of induction). Let $m_0$ be a natural number, and let $P(m)$ be a property pertaining to an arbitrary natural number $m$. Suppose that for each $m \geq m_0$, we have the following implication: if $P(m')$ is true for all natural numbers $m_0 \leq m' < m$, then $P(m)$ is also true. (In particular, this means that $P(m_0)$ is true, since in this case the hypothesis is vacuous.) Then we can conclude that $P(m)$ is true for all natural numbers $m \geq m_0$.

This is probably the first exercise we encounter in Tao's analysis I which looks difficult (as opposed looking easy but turning out to be difficult). So it is worth taking a step back and thinking about what approach we'll be taking before diving in.

Approach. The question hint suggests we use weak induction to prove strong induction. We want to reformulate strong induction in terms of weak induction. That is, we're solving a more challenging problem by reformulating into a more familiar problem.

Let's rewrite our previous table in terms of the variables given by the question. Note the different endpoints for the range of $m'$.

Weak Induction	Strong Induction
If $Q(n_0)$ is true, And $Q(n) \implies Q(n+1)$ Then $Q(n)$ is true for all $n \geq n_0$	If $P(m_0)$ is true, And $P(m_0 \leq m' < m) \implies P(m)$ Then $P(m)$ is true for all $m \geq m_0$

Before we dive in, let's be clear about what we need to prove, and what we can assume to be true:

• We need to find a base case for $Q(n_0)$ which is true.
• We need to show that if $Q(n)$ is true, then so is $Q(n+1)$.
  
• We can assume $P(m_0)$ is true for the purposes of proving strong induction.
• We can assume  $P(m_0 \leq m' < m) \implies P(m)$ is true for the purposes of proving strong induction.
  

Let's follow the standard template for weak induction over $n$, here using $Q(n)$. 

Inductive Hypothesis: $Q(n)$ is true.  

Let's write what this means in terms of $P(m')$.

$$Q(n) : P(m_0 \leq m' < n)$$

Inductive Step: $Q(n) \implies Q(n+1)$.

Since $P(m_0 \leq m' < n) \implies P(n)$, we have $P(m_0 \leq m' \leq n)$.

This means $Q(n+1)$ is true, because

$$Q(n+1) : P(m_0 \leq m' < n+1) = P(m_0 \leq m' \leq n)$$

So $Q(n) \implies Q(n+1)$.

Base Case: Consider $Q(m_0)$.

$$Q(m_0) : P(m_0 \leq m' < m_0)$$

This is vacuously true since no $m'$ satisfies $m_0 \leq m' < m_0$. 

By weak induction (Axiom 2.5), having shown the base case $Q(m_0)$ to be (vacuously) true, and that $Q(n) \implies Q(n+1)$, we can conclude $Q(n)$ is true for all $n \geq m_0$. 

What does this mean? Referring back to the definition of $Q(n)$,

$$Q(n) : P(m_0 \leq m' < n)$$

$Q(n)$ is true for all $n \geq m_0$ means

$$Q(n \geq m_0) : P(m_0 \leq m')$$

So we have shown $P(m)$ is true for all natural numbers $m \geq m_0$. $\square$

Tao Analysis I - 2.2.4

Exercise 2.2.4

Justify the three statements marked (why?) in the proof of Proposition 2.2.13.

Let's follow the provided proof of Proposition 2.2.13 and fill in the gaps.

Proposition 2.2.13 (Trichotomy of order for natural numbers). Let $a$ and $b$ be natural numbers. Then exactly one of the following three statements is true: 

• $a < b$
• $a = b$
• $a > b$.

The proof is in two parts:

• Part 1 - showing that not more than one of the three statements can hold at the same time
• Part 2 - showing at least one of the three statements must be true
  

Although it feels unusual, proving both of these things is sufficient to show that only one of the three statements can be true.

 

Part 1

Let's work through the cases.

• If $a<b$ then by definition 2.2.11, $a \neq b$. This leaves the possibility of $a>b$.
• If $a>b$ then by definition 2.2.11, $a \neq b$. This leaves the possibility of $a<b$.
• If $a=b$ then by definition 2.2.11, $a \nless b$ and $a \ngtr b$.

We're left to explore the possibility of $a<b$ and $a>b$ both being true. Proposition 2.2.12(c) says that if $a \leq b$ and $a \geq b$, then $a=b$. Our strict inequalities are a special case, and so we are led to $a=b$. But this is a contradiction! So we conclude not more than one of the cases can be simultaneously true.

Part 2

The book uses induction to prove that at least one of the three statements must be true. It fixes $b$ and inducts on $a$. 

When $a=0$, then $0 \leq b$ for all $b$. We're asked why (1). This means either $0 = b$ or $0 < b$ (but not both). This is the induction base case $a=0$.

The inductive hypothesis is that for a given $a$, at least one of the three statements is true. We need to show that if this is true for $a$, then it is also true for $a++$.

• If $a>b$ then $a++ > b$. We're asked why (2).
• If $a=b$ then $a++ > b$. We're asked why (3).
• If $a<b$ then by Proposition 2.2.12(e) we have $a++ \leq b$.This means either $a++ = b$ or $a++ < b$ (but not both). 

This concludes the induction.

We now answer the why questions.

 

Why 1

When $a=0$, then $0 \leq b$ for all $b$. We're asked why. 

The variables $a$ and $b$ are independent of each other, so $a$ does not constrain $b$. 

By definition $b$ is a natural number so it can take values from $b=0$ upwards. This is why $0 \leq b$. $\square$

Some of the other solution sites answered this question by demonstrating why the inequality $0 \leq b$ holds for all natural numbers $b$. Definition 2.2.1 of addition states that $0 + m:=m$, so we have $0 + b = b$. This matches Definition 2.2.11 for order relations, where $b = 0 + b$ means $b \geq 0$, or equivalently $0 \leq b$.

Why 2

If $a>b$ then $a++ > b$. We're asked why.

Let's start with 

$$a>b$$

Proposition 2.2.12(d) that addition preserves order, give us

$$a++ > b++$$

Now $b++ = b + 1$, and $b++ \neq b$ (Axiom 2.4), so by Definition 2.2.11 of order relations gives us

$$b++ > b$$

Since order is transitive by Proposition 2.2.12(b), from

$$a++ > b++ > b$$

we finally have

$$a++ > b$$

 

Why 3

If $a=b$ then $a++ > b$. We're asked why.

Let's start with

$$a = b$$

and increment both sides

$$a++ = b++$$

which we can rewrite as

$$a++ = b + 1$$

This matches Definition 2.2.11 for order relations, giving us the desired

$$a++ > b$$

 

Note

In the last 2 answers we've used $n++ = n + 1$. Although trivially obvious, we might ask how we show it from the basic axioms and lemmas. 

It is a corollary of the following two lemmas

• Lemma 2.2.2 - For any natural number $n$, $n+0=n$.
• Lemma 2.2.3 - For any natural numbers $n$ and $m$, $n+(m++)=(n+m)++$.
  

Here we take $m=0$ so $n+(0++)=(n+0)++$ becomes the desired $n+1=n++$.

Tao Analysis I - A.7.1

Exercise A.7.1

Suppose you have four real numbers $a$, $b$, $c$, $d$ and you know that $a = b$ and $c = d$. Use the above four axioms to deduce that $a + d = b + c$.

Let's remind ourselves of the four equality axioms presented in the book:

• Reflexivity. $x=x$.
• Symmetry. If $x=y$, then $y=x$.
• Transitivity. If $x=y$ and $y=z$, then $x=z$.
• Substitution. If $x=y$, then $f(x)=f(y)$ for all functions or operations $f$. Similarly if $x=y$, then $P(x)=P(y)$ for property $P$.
  

To answer the question, we have to try hard not to fall back to school algebra. The challenge is to go back to fundamentals and only use the axioms given.

Let's start with the given facts.

$$\begin{align} a &= b \\ c &=d \end{align}$$

Now let's use substition on $a=b$ using the function $f(x) = x + d$. This gives us

$$\begin{align} f(a) &= f(b) \\ a + d &=  b + d \end{align}$$

We can use substitution on $c=d$ using the function $g(x) = b + x$. This gives us

$$\begin{align} g(c) &= g(d) \\ b + c &=  b + d \end{align}$$

In preparation for the next step, we use symmetry to say

$$b + c =  b + d \implies b +d = b + c$$

Finally we use transitivity,

$$  (a + d =  b + d) \land (b + d =  b + c)  \implies (a+d = b+c) $$

The proof is complete. $\square$