Predicate Logic: Proof of Validity, Satisfiability of Sentences

Question

Suppose we are given a sentence (i.e. it has no free variables) of the form: $\forall x$ $(P(x) \rightarrow Q(x))$
and asked to determine whether it is a tautology, satisfiable or unsatisfiable.

My questions are:

1) Is the sentence, saying that "for all $x$, $(P(x) \rightarrow Q(x))$ is always true? To prove that it is not a tautology, would it then be sufficient to state something like "an interpretation that satisfies $P(x)$ would falsify $(P(x) \rightarrow Q(x))$. Hence, the sentence is not a tautology." ?

2) Does proving that the sentence is a tautology mean the same thing as proving that the sentence is valid? Would this then mean proving that the sentence is true under all interpretations?

The following is how the terms valid, satisfiability and unsatisfiability are defined.

Let $F$ be a formula of the first order language $L$. $F$ is

1) $valid$ if and only if it is satisfied by every interpretation of $L$.
2) $satisfiable$ if an only if it is satisfied by some interpretation of $L$
3) $unsatisfiable$ if and only if it is not satisfied by any interpretation of $L$

Answer 1

First you need to check the terminology being used. Some take "tautology" narrowly, to mean -- in effect -- logically valid by the truth-table test (i.e. logically valid solely in virtue of the way the truth-functional connectives appear in the wff). Some perhaps regrettably employ "tautology" more widely, so that a first-order valid wff counts as a tautology as well.

If you are using tautology in the narrow sense, then quite trivially $\forall x(P(x) \rightarrow Q(x))$ is not a tautology in that sense, as its main logical operator is not a truth-function.

It isn't a tautology in the wider sense either, i.e. it is not a first-order valid wff: to show that you need to think off an interpretation that makes it false. So pick a domain. And now interpret $P$ and $Q$ such that there are objects in the domain which satisfy $P$ but not $Q$.

Answer 2

If, after Peter's answer, you are still using tautology in predicate logic as synonym of valid (i.e. true in all interpretations), then your definitions are the right ones.

Regarding :

2) Does proving that the sentence is a tautology mean the same thing as proving that the sentence is valid? Would this then mean proving that the sentence is true under all interpretations?

Now the answer is : YES. According to the above stipulation, they means the same thing.

But now :

1) Is the sentence, saying that "for all x, (P(x)→Q(x))" is always true? To prove that it is not a tautology, would it then be sufficient to state something like "an interpretation that satisfies P(x) would falsify (P(x)→Q(x)). Hence, the sentence is not a tautology" ?

makes little sense.

To prove that $∀x (P(x)→Q(x))$ is not always true (i.e. not valid) we have to find an interpretation which flasify "for all x, (P(x)→Q(x))".

Again, by Peter's answer, this must be an interpretation with domain $\mathcal U$ such that we have at least one object $a \in \mathcal U$ for which $P$ holds of it and $Q$ does not.

Consider an interpretation with the set $\mathbb N$ of natural numbers as domain and consider the two "predicates" $(x > 0)$ and $(x < 0)$ as interpretation of $P(x)$ and $Q(x)$ respectively.

We have that $1 > 0$ is true while $1 < 0$ is false. Thus :

$(1 > 0) \rightarrow (1 < 0)$ is false [truth-table for $\rightarrow$].

So, we have found a number $n$ such that :

$(n > 0) \rightarrow (n < 0)$ is false in $\mathbb N$

and we can conclude with :

$\forall x[(x > 0) \rightarrow (x < 0)]$ is false in $\mathbb N$.

Conclusion

We have found an interpretation of $∀x (P(x)→Q(x))$ which falsify it; thus, the formula is not valid.