# Proof in the sequent calculus

I have to prove the following in the sequent calculus:

Given

(a) $\forall x: x \leq x$

(b) $\forall x \forall y \forall z [(x \leq y \wedge y \leq z) \rightarrow x \leq z]$

(c) $\forall x \forall y \exists z [x \leq z \wedge y \leq z]$

$\Gamma := \{(a), (b), (c)\}$

Show that: $\Gamma \vdash \forall x \forall y \forall z \exists w [x \leq w \wedge y \leq w \wedge z \leq w]$

(Common rules like $\forall$-introduction and elimination and $\exists$-introduction and elimination ... etc. can be used)

I know how to prove it intuitively, (with (a) and (c), (b) is not necessary if I am not mistaken), but I have no idea for a formal proof.

Basically it should work if I got to

$\exists w [ x \leq w \wedge y \leq w \wedge z \leq w ]$

(Then I could use 3* $\forall$-introduction)

Can anyone give me a hint?

P.S.: If I eliminate the $\forall$'s:

(a) $x \leq x$

(b) $(x \leq y \wedge y \leq z) \rightarrow x \leq z$

(c) $\exists z [x \leq z \wedge y \leq z]$

-
(b) is needed. Otherwise take the relation on $3$: $\{(0,0),(1,1),(2,2),(3,3),(0,1),(1,2),(2,0)\}$. There is no element above or equal to $0,1,2$. Rethink your intuitive proof. First eliminate the universal quantifiers. You will end up with various existential sentences. Eliminate one by one the existential quantifiers to reach a conclusion with an new existential quantifier. –  Apostolos May 17 '12 at 18:30
but your relation does not satisfy (c), because for $x=2$ and $y=3$ there is no $z$ s.t. $x \leq z$ and $y \leq z$ –  ChristianL May 17 '12 at 18:50
Disregard $(3,3)$, that's not supposed to be there. So the relation is actually $\{(0,0),(1,1),(2,2),(0,1),(1,2),(2,0)\}$ and the domain is $3=\{0,1,2\}$. Is your system natural deduction? –  Apostolos May 17 '12 at 19:11
Ok, I got that, thank you. But I still don't know how I can "reach a conclusion with an new existential quantifier", because I don't know how to get the required (additional) $z \leq w$ into the (substituted) $\exists$-statement of (c). –  ChristianL May 17 '12 at 19:20
First of all you have that $\exists w(x\leq w\land y\leq w)$ and you have $\exists u(y\leq u\land z\leq u)$ and $\exists a(u\leq a\land w\leq a)$. These are direct implications of the third axiom. Now using we have that $(x\leq a\land y\leq a\land z\leq a)$ implied by the second axiom and $(x\leq w\land y\leq w)$, $(y\leq u\land z\leq u)$, $(u\leq a\land w\leq a)$ (you get these by eliminating the existential quantifiers). Then introduce an existential quantifier $\exists a(x\leq a\land y\leq a\land z\leq a)$. Then introduce the universal quantifiers. This is a sketch of the argument. –  Apostolos May 17 '12 at 19:27