Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this 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
add comment

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.

2 Answers

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|improve this answer
add comment

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|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
add comment

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