Setting a family of sets equal to the empty/null set?

1. Aug 25, 2014

pandaBee

1. The problem statement, all variables and given/known data
Suppose A is a set, and for every family of sets F, if ∪F = A then
A ∈ F.
Prove that A has exactly one element. (Hint: For both the existence
and uniqueness parts of the proof, try proof by contradiction.)

2. Relevant equations

3. The attempt at a solution
Let A be an arbitrary set
Suppose ∀F(∪F=A⇒A∈F)

Want to prove:
∃!x(x∈A) (A has a single, unique element.)

Existence:
Want to prove:
∃x(x∈A)

I use the Hint and use proof by contradiction, we add the assumption that
∀x(x∉A) into our list of givens.
But this means that A = ∅; then plugging this into our other given:

∀F(∪F=∅⇒∅∈F)
Let F' be the family set F' = ∅
then ∪F'=∅ and thus ∅∈F'
but this is a contradiction, since ∅∈F'=∅ is False.

Is this a legal move - setting F to the empty set?
If I don't set F to the empty set, then ∀F(∪F=∅⇒∅∈F) is true as far as I can tell, and there is no contradiction in assuming the negated goal.
is F is a family of empty sets, then since the empty sets contain no elements the union of the family set of empty sets is just the empty set.
However, is F IS an empty set then ∅∈F'=∅ and we've found our contradiction.

Any insight on this?

3. The attempt at a solution

2. Aug 25, 2014

Fredrik

Staff Emeritus
It looks correct to me. If we write $F=\{F_i|i\in I\}$, we can write $\bigcup F=\bigcup_{i\in I}F_i$. If $F=\varnothing$, this rewrite still works. We just have to take $I=\varnothing$. So when $F=\varnothing$, we have $$\bigcup \varnothing =\bigcup F=\bigcup_{i\in\varnothing} F_i.$$ Now what's a union with an empty index set? Does it make sense? I think it does, because $x\in \bigcup_{i\in\varnothing}$ implies $\exists i\in\varnothing~~ x\in F_i$, which is false. So $\bigcup_{i\in\varnothing}F_i$ must be empty. We simply have $\bigcup \varnothing=\varnothing$.

Also, the problem statement says "for every family of sets". What is a family of sets? It's just a set, right? We use the word "family" only because "set of sets" can sound weird. And a set of sets is just a set, because all elements of all sets are sets. So "for every family of sets F" should mean "for all sets F". I don't see a reason to exclude the empty set, unless this book defines "family" in an unexpected way.

3. Aug 26, 2014

andrewkirk

The question seems to be posed in a misleading way. Is that really the exact way it was written in the text or assignment sheet? The way it is written confuses the issue of whether F is an index set for the family or a member of the family of sets. This in turn confuses x with {x}, which is at the heart of the problem and so makes progress very difficult.

I presume what the problem is really asking is to prove that, given

$$\forall\mathscr{F}(\bigcup_{S\in\mathscr{F}}S=A\rightarrow(A\in \mathscr{F} ))$$

$A$ must have exactly one element.

We can then re-write your working as:

$$\forall\mathscr{F}(\bigcup_{S\in\mathscr{F}}S=\emptyset \rightarrow(\emptyset \in \mathscr{F} ))$$

We then instantiate $\emptyset$ for $\mathscr{F}$ in this to get:

$$\bigcup_{S\in\emptyset}S=\emptyset \rightarrow(\emptyset \in \emptyset )$$

The consequent is well-defined and FALSE.
The antecedent is
$$\emptyset=\bigcup_{S\in\emptyset}S\equiv\{x\vert\exists S(S\in\emptyset\wedge x\in S)\}$$
This is TRUE because $S\in\emptyset$ is false for all $S$.
Hence the implication is FALSE and the contradiction is obtained.

4. Aug 26, 2014

Fredrik

Staff Emeritus
Andrewkirk, are you objecting against the notation $\bigcup F$? That's a fairly common notation for the union of all the sets that are elements of F. So if $F=\{F_i|i\in I\}$, we have $\bigcup F=\bigcup_{i\in I} F_i$.

5. Aug 26, 2014

andrewkirk

Interesting. I haven't come across that notation. There is no strict logical objection to formally defining the symbol string $\bigcup F$ to mean that but it seems unnecessarily obscure to me and, unless the definition is provided, it will mislead. One expects the operands on which any union operator operates to be the sets whose union is being taken, so it seems to me that unnecessary confusion is fostered by this presentation in which the operand $F$ is instead the set of sets whose union is being taken - ie the index set. Index sets have always, in my experience, been in the subscript to union operators, as in $\bigcup_{S\in\mathscr{F}}S$. Apart from being clearer, this notation has the advantage of not using any conventions other than those that are universally recognised in ZF set theory.

My notation generally follows that of Munkres in 'Topology - a First Course' but most of what I come across on wikipedia, Wolfram and stackexchange seems to follow those same conventions.

6. Aug 29, 2014

pandaBee

Thanks for the feedback guys, here's the rest of the proof just for the sake of completeness:

Continuing from the first post:
However, if F IS an empty set then ∅∈F'=∅ and we've found our contradiction; therefore ∃x(x∈A)

Now I prove Uniqueness:

let P(x) = ∃x(x∈A)

We assume P(x) and P(y) and try to prove that x = y; that is that x is unique.

Givens:
x∈A
y∈A
∀F(∪F=A⇒A∈F)

Goal: x=y

I define the family set F={X,Y,Z_1,Z_2.....Z_n} to correspond with A(defined in the next line) where X={x}, Y={y}, Z_1={z_1}, so on so forth

A is a set that contains x and y of the form A={x,y,z_1,z_2,.......z_n} (Spans all possibilities for A)***

but then ∪F = {x,y,z_1,z_2,.....z_n}, therefore ∪F = A
but it is clear that A∉F, which is a contradiction: therefore x=y.

Therefore ∃!x(x∈A) and the proof is complete.

I kind of feel sketchy about the *** part of the proof, if there's a better way to write it out I'd love to see it. Thanks again.

And sorry about the messy symbols, I'm in the process of learning Latex and I've been using an online math symbol typer to cope in the meanwhile. Is there perhaps a better way of typing out symbols than latex or is learning latex the best thing to do?

Last edited: Aug 29, 2014
7. Aug 29, 2014

andrewkirk

You can write the *** part as:

Define $C\equiv A-\{x,y\}$, $X\equiv\{x\}, Y\equiv\{y\}$. Then $A=X\cup Y\cup C$.

By the way, in maths one needs to avoid statements like 'It is clear that' (two lines below ***). If it is clear, a reason can be given, and should be.

Here is a somewhat similar approach to yours that avoids that sort of problem.

We have already proven that there is at least one element of $A$. Let us call it $x$.

Define $C\equiv A-\{x\}$, $X\equiv\{x\}$. Then $A=X\cup C$ and $x\in A-C$..

Then we just have to prove that $C$ is empty.

Consider the set (or 'family') $\mathscr{F}=\{X,C\}$.

we have $\bigcup_{S\in\mathscr{F}}S=X\cup C=A$ hence, by the original premise, $A\in\mathscr{F}=\{X,C\}$.
So we have $A=X\vee A=C$. Now we know the latter is false because $x\in A-C$. So the former must be true: $A=X=\{x\}$. So $y\in X\to y=x$.