Need help constructing a proof tree (or truth tree) for the following argument symbolized in predicate logic.

Question

For context, I am a logic simpleton studying for an exam in a graduate-level introduction to symbolic logic.

One of the techniques I'm expected to know is constructing proof trees to test the validity of an argument.

I'm having some difficulty figuring out how to construct a proof/truth tree for the following argument:

$1. (∃x)Fx∨¬(∃y)Gy$

$2. (∀x)(F⟹Gx)$

$/∴ (∀y)Gy$

The reason for my confusion is that the textbook I'm consulting recommends a certain strategy for decomposing the formulae which seems contradictory as it relates to this specific argument. I would appreciate if someone would show me how to go about doing this.

Thank you.

Answer 1

The argument is invalid and you can use Truth tree method to find the counter-example.

The issue is with the left-disjunct of first premise: if there is some $F$ we can deduce from 2nd premise that is a $G$, but this is not enough to conclude that everything is $G$.

For the proof we expand only the left-hand branch of the initial set: $\{ (∃x)Fx \lor ¬(∃y)Gy, (∀x)(Fx \to Gx), \lnot (∀y)Gy \}$ corresponding to $(∃x)Fx$.

1. $∃xFx$

2. $∀x(Fx \to Gx)$

3. $\lnot ∀yGy$

4. $Fa$ --- from 1): $a$ new

5. $\lnot Gb$ --- from 3): $b$ new

6. $Fa \to Ga$ --- from 2)

Now we branch 6L) $\lnot Fa$, this branch closes, and 6R) $Ga$.

Thus:

7. $Fb \to Gb$ --- from 2), and we branch again: 7L) $\lnot Fb$, and 7R) $Gb$, that closes.

This is enough: we read the open branch to define the counter-example: a domain $\{ a, b \}$ with: $Fa, Ga, \lnot Fb, \lnot Gb$.

You can see that the purported conclusion: $\forall y Gy$ is False, and you can easily check that the two premises are True.