1
$\begingroup$

Background

In elementary set theory the union is taught as a binary operator on two sets, which contains all the elements of both those sets.

$$ A = \{1,2,3\}\\ B = \{2,3,4\}\\ A\cup B = \{1,2,3,4\} $$

In formal set theory this is generalized to a unary operator on one collection of sets, acting on each of the sets in that collection.

$$ \bigcup \{A,B\} = \{1,2,3,4\} $$

And now we can apply the union operator to a collection of not only two, but an arbitrary number of sets …

$$ C = \{1,4,5\}\\ \bigcup \{A,B,C\} = \{1,2,3,4,5\} $$

… even infinitely many.

$$ N_1 = \{1\} \land N_2 = \{2\} \land N_3 = \{3\} \land \cdots\\ \bigcup \{N_1,N_2,N_3,\dots\} = \{1,2,3,\dots\} $$

We can even take the union of a union of sets. $$ D = \{A,B\}\\ E = \{B,C\}\\ \bigcup \bigcup \{D,E\} = \bigcup \{A,B,C\} = \{1,2,3,4,5\} $$


Intermission

Advanced axiomatic set theory teaches the idea that everything is a set, and that the first set guaranteed to exist is the empty set. Other sets must be built from that starting point.

For example the natural number $0$ is the empty set $\emptyset$, the natural number $1$ is constructed as the singleton $\{0\}$, the natural number $2$ can be constructed as the pair $\{0,1\}$ (depending on the author), and so on.

The Axiom of Existence is the only axiom that guarantees that a set—the empty set—exists without the input of other sets. Other sets like ordered pairs and unions can only exist given an input.

The Axiom of Union states, “given a collection of sets, there exists a set who owns any element of any set in that collection” (as opposed to “all elements of all sets in the collection,” which would yield the intersection). The point is, a union set can exist, but the only way to create it is by giving, as an input, an existing set. That existing set could be a pair or a subset or even another union, which also require inputs; or it could be the empty set, which requires no previous set to exist. The bottom line is that the empty set is the foundation upon which all other sets are built.


Question

So finally here’s my question. If you take the union of any set $S$, and then take the union of that set, and keep going, will this process eventually yield the empty set?

$$ \text{hypothesis: } \left(\forall S\right)\left(\bigcup\bigcup\cdots\bigcup S = \emptyset\right) $$

$\endgroup$
  • 1
    $\begingroup$ I'm confused - why do you say "$\bigcup\emptyset$ does not exist"? It exists, and is $\emptyset$, since it's defined as "the set of all sets which are elements of some element of $\emptyset$" which is clearly empty. The intersection of the emptyset, $\bigcap\emptyset$, is the one which doesn't exist. $\endgroup$ – Noah Schweber Jul 29 '16 at 17:31
  • $\begingroup$ @NoahSchweber Well think about what $\bigcup S$ is saying: take all the elements of $S$, open them up, look at their elements, and put them all into a union set. But if there are no elements of $S$, then you cannot do this. However the union $\bigcup \{\emptyset\}$ does exist, and is in fact equal to $\emptyset$. $\endgroup$ – chharvey Jul 29 '16 at 17:34
  • 3
    $\begingroup$ Don't think about what it's saying - it doesn't say anything. Think about the definition. $\endgroup$ – David C. Ullrich Jul 29 '16 at 17:35
  • $\begingroup$ @chharvey, that's incorrect. The union of the emptyset is $\emptyset$ - $S$ having no elements does not make it undefined. Think about it this way: by definition, $a\in\bigcup S$ iff there is some $X\in S$ such that $a\in X$. It's clear by this definition that for no $a$ do we have $a\in\bigcup\emptyset$. Do you understand? (This is essentially an instance of vacuous satisfaction, similar to how e.g. "every element of the emptyset has 16 elements" is a true statement.) $\endgroup$ – Noah Schweber Jul 29 '16 at 17:35
  • 1
    $\begingroup$ 'The Axiom of Union states, “given a nonempty collection of sets..."'. Nope. Look it up: "Formally, the axiom of union states that for any set of sets..." en.wikipedia.org/wiki/… $\endgroup$ – David C. Ullrich Jul 29 '16 at 17:52
5
$\begingroup$

First of all, “eventually” should be rigorously defined. Given a set $S$, and its union $\bigcup S$, and that union $\bigcup\bigcup S$, and so on… let’s say that at some point in that process you do get the empty set $\emptyset$. Then when you take its union, you’ll get the empty set again, and this process will go on forever. Suffice it to say that this process will never stop, because you can take the union of any set.

We’re looking for a set for which this process continues indefinitely, and fails to yield the empty set. It seems that an infinite set is a good candidate. Let’s try the set of Natural Numbers.

Use the method of construction given

\begin{align} 0 &= \emptyset\\ 1 &= \{0\} = \{\emptyset\}\\ 2 &= \{0,1\} = \{\emptyset, \{\emptyset\}\}\\ 3 &= \{0,1,2\} = \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}\\ &\cdots \end{align}

and the set that contains all of these

$$\mathbb{N} = \{0,1,2,3,\dots\}$$

Now the union of $\mathbb{N}$ must contain any element in any set inside $\mathbb{N}$. That is, $\bigcup\mathbb{N}$ contains all the elements in $0$, all the elements in $1$, and in $2$, and in $3$, and so on. Keeping in mind that every set in $\mathbb{N}$ contains all the elements of the set “before” it, let’s start a list:

$$ \bigcup \mathbb{N} = \{0,1,2,3,\dots\} $$

What do you know! This is exactly the set of Natural Numbers! The union of $\mathbb{N}$ really contains all the elements of $\mathbb{N}$.

$$ \bigcup \mathbb{N} = \mathbb{N} $$

This is a perfect counterexample to the hypothesis. You can take as many unions as you want of $\mathbb{N}$ and you will always get $\mathbb{N}$.

$$ \bigcup\bigcup\cdots\bigcup \mathbb{N} = \mathbb{N} \not= \emptyset $$

$\endgroup$
  • 3
    $\begingroup$ Your answer is generally nice, but it erroneously confirms OP's mistaken notion that "you cannot take the union of the empty set". $\endgroup$ – MJD Jul 29 '16 at 17:36
  • 2
    $\begingroup$ @NoahSchweber Self-answering is far from being discouraged. $\endgroup$ – Hagen von Eitzen Jul 29 '16 at 17:44
  • 2
    $\begingroup$ That's a really and truly ... words fail me. If you're interested in learning actual math then it's a hugely less than constructive attitude. I mean really - when you took calculus and you wrote $(t^2)'=t$ instead of $2t$ and it got marked wrong how far did you get explaining that this was your personal system? $\endgroup$ – David C. Ullrich Jul 29 '16 at 17:59
  • 2
    $\begingroup$ @chharvey Except you haven't given any example of a set theory in which the union of the emptyset is not defined. If you want to work in a different set theory, that's fine - but you need to actually articulate what its rules are at some point (note that the non-Euclidean geometers had no problem doing this). The gulf between "most systems" and "literally every system which has so far been studied seriously" is, to put it mildly, a bit large. Let me ask again: do you know of any system - including a system you've invented, perhaps - in which the union of the emptyset does not exist? $\endgroup$ – Noah Schweber Jul 29 '16 at 18:17
  • 2
    $\begingroup$ @chharvey Not really. Like I said repeatedly elsewhere, $\bigcup \emptyset$ is a shorthand for a formula. No axioms are needed to prove that "If $A$ is an emptyset, then $A$ is a union of itself." So I really don't see a way around this, short of barring the existence of the emptyset itself (which seems like a not-very-good fix) or changing how basic logic works (which, again, you can do - but at some point you have to actually do the work of articulating exactly what system you are using, and how it works). I reiterate for the $n$th time: do you know of any system where this happens? $\endgroup$ – Noah Schweber Jul 29 '16 at 18:23
3
$\begingroup$

(This refers to an earlier version of the question, where it was said that $\bigcup\emptyset$ does not exist.)

Your question has been answered. This is just a note to point out that there is no such caveat; there's no problem with $\bigcup\emptyset$. By definition $\bigcup S$ is the set of $x$ such that there exists $y\in S$ with $x\in y$; this applies perfectly well to the empty set and shows that $\bigcup\emptyset=\emptyset$.

As Noah points out, there's no such thing as $\bigcap\emptyset$. Why is that? Well, the definition is that $\bigcap S$ is the set of all $x$ such that $x\in y$ for every $y\in S$. If $x$ is anything at all then $x\in y$ for every $y\in\emptyset$, since there are no such $y$. So if $\bigcap\emptyset$ existed it would be the set of all sets, which leads to contradiction.

(No, there's no mention of this in the axioms. There's no mention of $\bigcap$ at all in the axioms. It's a theorem that if $S$ is nonempty then $\bigcap S$ exists, and the proof doesn't work if $S=\emptyset$.)


The following is really part of a comment that doesn't fit very well into the comment box:

def WrongSum(data):
  res = data[0]
  for j = 1 to len(data)-1:
     res = res + data[j]
  return res

def RightSum(data):
  res = 0
  for j = 0 to len(data)-1:
     res = res + data[j]
  return res

They're the same, except when data is empty, in which case WrongSum crashes and RightSum gives the right answer.

$\endgroup$
  • 1
    $\begingroup$ A comment on the last paragraph (which is quite correct): there isn't even a symbol for $\bigcup$ or $\bigcap$ in the language of set theory. Expressions like "$\bigcup S$" are understood to be shorthand for a set satisfying an appropriate formula - e.g. "$\bigcup S$" is shorthand for a set $x$ satisfying "$\forall a(a\in x\iff \exists b(b\in S\wedge a\in b))$." Axioms are required for showing that such a set exists (Union in this case) or is unique (Extensionality in this case), but note that pure logic alone proves that $\emptyset$ is a union of $\emptyset$. $\endgroup$ – Noah Schweber Jul 29 '16 at 18:11
  • $\begingroup$ continuing the argument here… you may be right if in ZFC there is no mention of $\bigcap$ in the axioms, however you are equally free in an alternate system to provide an axiom for $\bigcap$ and then a theorem for $\subset$ as long as you accept proper classes. $\endgroup$ – chharvey Jul 29 '16 at 18:13
  • $\begingroup$ @chharvey Given that you're so convinced that such a system must exist (and, presumably, be interesting/useful/some positive attribute), why don't you try to explicitly construct one? $\endgroup$ – Noah Schweber Jul 29 '16 at 18:24
  • $\begingroup$ @NoahSchweber Not that this is any of your business but I actually am working on a system of set theoretic axioms in computer programming. and as it turns out, the way that I've defined Union fails to work for empty sets, and instead of making an exception I simply restricted my definition to "the union of any nonempty set is …". As long as I don't attempt to calculate union(emptyset) I should be fine, right? $\endgroup$ – chharvey Jul 29 '16 at 18:29
  • 1
    $\begingroup$ @chharvey " the way that I've defined Union fails to work for empty sets..." I bet you simply did it "wrong". Not wrong, but "wrong". Consider the analogous question of what the sum of no numbers at all should be. Compare WrongSum and RightSum in the edit I just made to my answer - they both work, except for empty data. $\endgroup$ – David C. Ullrich Jul 29 '16 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.