Question

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.

Answer 1

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.

Answer 2

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.