Deduction of ##\forall x \in S \cup T (x \le b)## using first order logic rules.

[Mr Davis 97]

Homework Statement

Show that $\forall x \in S \cup T (x \le b)$ implies that $\forall s \in S (s \le b) \wedge \forall t \in T (t \le b)$

Homework Equations

The Attempt at a Solution

How can I perform this deduction using the rules of first order logic? This is how far I can get:

$\forall x \in S \cup T (x \le b)$
$(x \in S \cup T \implies x \le b)$
$(x \in S \lor x \in T \implies x \le b)$

 

[fresh_42]

I would write it $s\in S \stackrel{def.}{\Longrightarrow} s \in S \cup T \stackrel{\text{ given cond. }}{\Longrightarrow} s \leq b$ and $t \in T \ldots$

 

[Mr Davis 97]

I would write it $s\in S \stackrel{def.}{\Longrightarrow} s \in S \cup T \stackrel{\text{ given cond. }}{\Longrightarrow} s \leq b$ and $t \in T \ldots$

I see, that makes sense. Just wondering, are the two statements I gave logically equivalent? That is, is there a way to derive one from the other using manipulations from first order logic?

 

[fresh_42]

Yes they are equivalent. We already have from left to right. From right to left is equivalent to non left implies non right. Assume $\lnot [(\forall x)(x\in S\cup T)\Rightarrow(x \leq b)]$. That is $(\exists x)(x \in S\cup T)\wedge (x>b)$. So $x\in S$ or $x\in T$ and still $x>b$ which is non right:
$[((\exists x)(x\in S) \wedge (x>b)) \vee ((\exists x)(x\in T) \wedge (x>b))] = \lnot [((\forall x)(x\in S)\Rightarrow(x\leq b)) \wedge ((\forall x)(x\in T)\Rightarrow(x\leq b))]$