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$