Show that $A$ does not have any non-empty proper subsets if and only if $A=\{x\}$ for some object $x$.

200 Views Asked by At

I've seemingly hit a wall with this exercise, in full it states:

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

This exercise is of the form $P\iff Q$. I'll define $P$ to be the statement: $A$ does not have any non-empty proper subsets, and $Q$ to be $A$ is of the form $A = \{x\}$ for some object $x$. Just to make it a bit easier to talk about each statement.

Assume that $A$ is a non-empty set. Since $A$ is non-empty, let $x\in A$. To prove $Q\implies P$, by contrapositive $(Q\implies P)\iff (\neg P\implies \neg Q)$. Suppose $\neg P$ i.e., $A$ has a non-empty proper subset $A'$. Then $A'\subseteq A$ and $A'\neq A$. Thus $\forall x \in A' \implies x\in A$. Also $\exists y\in A':y\notin A$ or $\exists z \in A :z\notin A'$. If $y \in A'$ then $y\in A$. Suppose $x=y$ then $x\in A\implies y\in A$, a contradiction. Thus $x\neq y$. Thus the set $A$ has at least two elements. If $z\in A$ then $x\in A$ and $z\in A$. Suppose $x=z$ then $z\notin A' \implies x\notin A'$ but I don't know if I can continue with this. If I were to get a contradiction on that last statement then in both cases $A$ has at least two elements and thus would've shown $\neg Q$.

To prove $P\implies Q$, I used contradiction, $P\land \neg Q$ and supposed $\exists t \in A:t\neq x$ and the set $B=\{x,t\}$. Since it is a subset but it can't be proper subset we get $A=B$ but I can't continue.

An argument with contrapositive/contradiction seems very "natural" here because of the "does not have" but I couldn't continue with it and everytime I tried starting over, I couldn't think of anything else other than contradiction. All the steps I did, especially for $Q\implies P$ seemed very natural so assuming everything is correct, there could be a way for it to work, Now for $P\implies Q$, I wouldn't call it very "natural" so I have a bit less faith in that approach. Something that seemed weird about working with $Q$ was that its negations are infinite so I could make other assumptions but the more elaborate I tried to make them, the difficulty in getting a proof remained the same, which was kind of beautiful but also annoying.

Assuming they are correct, could any of my arguments work? If not, what would be another way to go? Could the first sentence about Euclid hint some way of proving this that I didn't see?

2

There are 2 best solutions below

5
On

IN ONE DIRECTION :

Let $A$ be Non-Empty , which means it has at least 1 element.

Let that 1 element be $x$.
Assume $A$ has other elements too.
Let $y$ be some other element in $A$.
We do not have to worry about the further elements.

When $A=\{x,y,\cdots\}$ , we have Sub-Sets $S_1=\{x\}$, $S_2=\{y\}$, $S_3=\{x,y\}$, $S_4=\{\}$.

According to Definition , we do not count $S_4$ , because it is Empty.
We might not be able to count $S_3$ , because it may be the Case that $A=S_3$

No matter , we still have Proper Sub-Sets $S_1$ & $S_2$ : at least 2 !
But we were given that $A$ has no Proper Sub-Sets.
Hence $y$ must not Exist.
That is , $A=\{x\}$

IN OTHER DIRECTION :

When we have $A=\{x\}$ , we see that the Sub-Sets are $S_5=\{\}$ & $S_6=\{x\}$ , which are not Proper Sub-Sets : there are no Proper Sub-Sets in this Case.

BIDIRECTIONAL PROOF IS DONE

0
On

Here is another way to see what is going on, inspired a bit by Euclid's Definition.

Let A be nonempty and let a∈A be arbitrarily chosen.

Claim: If A is a "point" ( A = {x} for some x) then A has "no parts" (nonempty proper subsets)

Proof:

Let B be an arbitrary nonempty subset of A

Then B ≠ ∅ and B ⊆ {x} = A

Then {x} ⊆ B and B = {x} = A

Since the only nonempty subset of A is A, there are no proper nonempty subsets.

Claim: If A has "no parts", then A is a "point"

Proof:

Recall that a∈A and so {a} ⊆ A

As {a} is not a proper subset of A, we have that A = {a}.

Thus A is a point.