MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'd like to write down a proof of the following (simple) fact: $\forall x\left(\bigcup\left\{x\right\}=x\right)$. I'd like to use the rules of inference of natural deduction. One could show that if $y\in\bigcup\left\{x\right\}$ then $y\in x$ and vice versa. I managed to show the former implication, but I cannot show the latter.

Let me show you what I accomplished, as an example. You suppose that $t_1\in\bigcup\left\{t_0\right\}$. Then it follows that $\exists x_2\left(x_2\in\left\{t_0\right\}\land t_1\in x_2\right)$. Now you also suppose that $t_2\in\left\{t_0\right\}\land t_1\in t_2$. So $t_2\in\left\{t_0\right\}$, $t_1\in t_2$, $t_2\in\left\{t_0,t_0\right\}$, $t_2=t_0\lor t_2=t_0$, $t_2=t_0$, $t_1\in t_2\leftrightarrow t_1\in t_0$, $t_1\in t_0$. That's the easy part. The problem now is that if I suppose that $t_1\in t_0$ I can't show that $t_1\in\bigcup\left\{t_0\right\}$.

What can I do? Thanks.

share|cite|improve this question

closed as off-topic by Ricardo Andrade, Carlo Beenakker, Andrey Rekalo, Karl Schwede, David White Oct 3 '13 at 22:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Ricardo Andrade, Carlo Beenakker, Andrey Rekalo, Karl Schwede, David White
If this question can be reworded to fit the rules in the help center, please edit the question.

Is this nonstandard notation? – Douglas Zare Feb 27 '10 at 18:01
What in particular you don't understand? – Francesco Turco Feb 27 '10 at 18:59
I must not understand what the union of {x} means. When I write a union like that, I mean a union over a collection of sets with an obvious index. I don't see what collection of sets you mean and how they are indexed. Do you mean something different by the union, or something different from the set containing x? – Douglas Zare Feb 27 '10 at 19:44
Every collection of sets can be indexed by itself. The collection he has in mind consists of one set, namely $x$, indexed by itself. – Andrej Bauer Feb 27 '10 at 19:49
@DouglasZare. The union of x is the set which contains everything the elements of x are made of. For example, if x is finite and contains x_1,\ldots,x_n, then the union of x is equal to x_1\cup\ldots\cup x_n. Of course, the union of x is possible even if x is infinite. It is the operator mentioned by the axiom of union in Zermelo-Fraenkel set theory. – Francesco Turco Feb 27 '10 at 21:26
up vote 4 down vote accepted

Lemma: For any proposition $\phi$ we have $(\exists u \in \lbrace x \rbrace . \phi(u)) \iff \phi(x)$.

Proof: If $\phi(x)$ then we may take $u = x$. Conversely, suppose there is $u \in \lbrace x \rbrace$ such that $\phi(u)$. Then by the definition of the set $\lbrace x \rbrace$ we have $u = x$, therefore $\phi(x)$. QED.

Now your question reduces to: $$u \in \bigcup \lbrace x \rbrace \iff (\exists z \in \lbrace x\rbrace . u \in z) \iff u \in x.$$

I would say such questions are not appropriate for this forum.

share|cite|improve this answer

I found the proof. Just suppose that $\lnot\left(t_0\in\left\{t_0\right\}\right)$; this means that $\lnot\left(t_0=t_0\right)$; since this is false, then $t_0\in\left\{t_0\right\}$ by negation elimination; so $\exists x_2\left(x_2\in\left\{t_0\right\}\land t_1\in x_2\right)$; by definition of union of a set you have that $t_1\in\bigcup\left\{t_0\right\}$.

Sorry for having asked here such a question: I didn't imagine MO wasn't the right place.

share|cite|improve this answer
I think the custom dictates that you accept my answer. I gave you exactly what you want, only better than your proof. For starters, your proof does not work in intuitionistic logic. – Andrej Bauer Feb 28 '10 at 19:48

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