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\ne 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=\mathrm{\varnothing }$. 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\ne Y$. Here we have $\mathrm{\varnothing }=\mathrm{\varnothing }$ so $\mathrm{\varnothing }$ can't be a proper subset of $\mathrm{\varnothing }$.

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 $\mathrm{\varnothing }$. However $\{x\}$ is not a proper subset because it equals the original set, $\{x\}=\{x\}$. What about the other subset, $\mathrm{\varnothing }$? 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\}$ $⟹$ $A$ does not have any non-empty proper subsets.
• $A$ does not have any non-empty proper subsets $⟹$ $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 $\mathrm{\varnothing }$. The first, $\{x\}$ is not a proper subset because it equals $A$. The second, $\mathrm{\varnothing }$ 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\}⟹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=\mathrm{\varnothing }$ 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 $\mathrm{\varnothing }$. However $\{x\}$ is not a proper subset, and $\mathrm{\varnothing }$ 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,\dots \}$. 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}⟹A\text{ is of the form }A=\{x\}$$

By showing both implications, we have shown that 

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

Tao Analysis I - 3.1.12

Exercise 3.1.12

Suppose that $A$, $B$, $A^{\prime }$, $B^{\prime }$ are sets such that $A^{\prime }\subseteq A$ and $B^{\prime }\subseteq B$.

(i) Show that $A^{\prime }\cup B^{\prime }\subseteq A\cup B$ and $A^{\prime }\cap B^{\prime }\subseteq A\cap B$.

(ii) Give a counterexample to show that the statement $A^{\prime }\setminus B^{\prime }\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^{\prime }\cup B^{\prime }\subseteq A\cup B$

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

$$x\in (A^{\prime }\cup B^{\prime })⟺(x\in A^{\prime })\vee (x\in B^{\prime })$$

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

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

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

$$x\in (A^{\prime }\cup B^{\prime })⟹(x\in A)\vee (x\in B)$$

This is equivalent to the statement $A^{\prime }\cup B^{\prime }\subseteq A\cup B$. $◻$

Show that $A^{\prime }\cap B^{\prime }\subseteq A\cap B$

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

$$x\in (A^{\prime }\cap B^{\prime })⟺(x\in A^{\prime })\wedge (x\in B^{\prime })$$

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

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

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

$$x\in (A^{\prime }\cap B^{\prime })⟹(x\in A)\wedge (x\in B)$$

This is equivalent to the statement $A^{\prime }\cap B^{\prime }\subseteq A\cap B$. $◻$

Show $A^{\prime }\setminus B^{\prime }\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^{\prime }=\{2,3\}$, noting that $A^{\prime }\subseteq A$ as required
• $B=\{2,3,4,5\}$, and $B^{\prime }=\{2\}$, noting that $B^{\prime }\subseteq B$ as required

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

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

We have shown $A^{\prime }\setminus B^{\prime }\subseteq A\setminus B$ is false with the above counterexample. $◻$

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^{\prime }$, $B$ and $B^{\prime }$ and every combination of intersection and union.

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

$$\boxed{{\displaystyle (A^{\prime }\setminus B^{\prime })\cap B=\mathrm{\varnothing }}}$$

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

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

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

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

The condition $(A^{\prime }\setminus B^{\prime })\cap B=\mathrm{\varnothing }$ is  $\{3\}\cap \{2,4,6,8\}=\mathrm{\varnothing }$ 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\}⟺P(x,z)\text{ is true for some }x\in 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\in 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 }\}⟺(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)\wedge (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{array}{rl}\{y:P(x,y)\text{ is true for some }x\in A\}& =\{y:x=y\wedge 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{array}$$

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

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)⟺(x\in A)\wedge (x\notin B)$$

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

$$x\in (A\cap B)⟺(x\in A)\wedge (x\in B)$$

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

$$x\in (B\setminus A)⟺(x\in B)\wedge (x\notin 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. $◻$

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)⟺(x\in A)\vee (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$. $◻$