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$$