2

Is this a tautology: $\forall xP(x) \implies Q(x)$ if there's no $x$ such that $P(x)$?

I know that if there was an exists there instead of a for all, the antecedent would be false and thus the implication true. But this one confuses me.

Could someone clarify this form me?

E: This question comes from an exercise I have which says: Let $\Gamma$ be an unsatisfiable set of formulas. Let $\alpha$ be a formula. Does $\alpha\in C(\Gamma) $, where $C(X)$ denotes the consequences of $X$?

The definition of consequence I have says $\alpha\in C(X)$ if $\forall v$ valuation$:v(\Gamma)=\{1\} \implies v(\alpha)=1$. As my $\Gamma$ has no valuations that satisfy it, this should be true, right?

Thanks!

YoTengoUnLCD
  • 13,384
  • 2
    If you're asking whether $\neg \exists xP(x)\to \forall x(P(x)\to Q(x))$ is a tautology, the answer is yes. – Git Gud Sep 03 '15 at 18:48
  • Are you possibly mixing predicate calculus with propositional calculus? – Git Gud Sep 03 '15 at 18:54
  • Hmm, I may be. I had this doubt for this particular exercise, but I wanted to know if this was true for a more general case. Did I extrapolate that incorrectly? – YoTengoUnLCD Sep 03 '15 at 18:57
  • Tautology - in the context of mathematical logic - does not mean "vacuously true". – Mauro ALLEGRANZA Sep 03 '15 at 19:43
  • I don't understand that part, why if some formula is vacuously true isn't it a tautology? – YoTengoUnLCD Sep 03 '15 at 20:01
  • @YoTengoUnLCD I think you did extrapolate incorrectly. How do you define valuations for predicate formulas? – Git Gud Sep 03 '15 at 20:22
  • In all math log textbooks (see e.g. Enderton, page 23) a formula $\varphi$ of propositional logic is defiend as a tautology (written $\vDash \varphi$) when "every truth assignment (for the sentence symbols in $\varphi$ ) satisfies it." If we "extrapolate" this def to a f-o formula, we say that $\varphi$ is valid when every interpretation satisfy it... and this is not the your case. – Mauro ALLEGRANZA Sep 04 '15 at 05:59
  • The following formula of f-o set theory : $x \in \emptyset \to x \ne x$ is vacuously true (for no $x : x \in \emptyset$) but it is not a tautology (i.e. true in every interpretation). – Mauro ALLEGRANZA Sep 04 '15 at 06:28

2 Answers2

3

The formula is a predicate (or first-order) one: in this context, we have two uses of the term tautology :

(i) a f-o formula is called a tautology when it is an "instance" of a propositional tautology. The formula $∀xP(x) \to Q(x)$ is an instance of the propositional formula $p \to q$, which is not a tautology.

(ii) a f-o formula is (sometimes) called a tautology when it is valid (i.e. true in every interpretation). The formula $∀xP(x) \to Q(x)$ is - as you say - true in every interpretation where there are no $P$'s, but of course is not valid.

To verify this, we can interpret the formula in $\mathbb N$ and interpret $Q$ with $x < 0$ and $P$ with $x \ge 0$ : clearly $\forall x (x \ge 0) \to (x < 0)$ is false in $\mathbb N$.

Thus, in both cases, it is not correct to say that the formula is a tautology.

In all mathematical logic textbooks (see e.g. Enderton, page 23) a formula $\varphi$ of propositional logic is defiend as a tautology (written $\vDash \varphi$) when:

every truth assignment (for the sentence symbols in $\varphi$) satisfies it.

If we "extrapolate" this definition to the first-order language, we get the definition of valid formula:

we say that $\varphi$ is valid when every interpretation satisfy it,

and this is not the case of the formula above.

What we have is : $¬∃P(x) \vDash ∀xP(x) \to Q(x)$, that reads :

$¬∃P(x)$ logically (and not : tautologically) implies $∀xP(x) \to Q(x)$.

Regarding the added part, the answer is : YES.

If no truth assignment satisfies every member of $\Gamma$, then for any $\varphi$, it is vacuously true that $\Gamma \vDash \varphi$.

Mauro ALLEGRANZA
  • 94,169
0

Is this a tautology: $\forall x[P(x) \implies Q(x)]$ if there's no $x$ such that $P(x)$? (Inserted presumed brackets.)

Yes.

Disclaimer: This proof probably won't be using exactly the axioms you are allowed, but it should be possible to translate it into your own system.

  1. We have $\forall x: \neg P(x)$

  2. Suppose $P(y)$.

  3. From 1, we have $\neg P(y)$.

  4. From 3, we have $\neg\neg P(y)\implies Q(y)$ since anything follows from a falsehood.

  5. From 4, $P(y)\implies Q(y)$, removing the $\neg\neg$.

  6. From 2 and 5, $Q(y)$ by detachment

  7. From 2 and 6, $P(y)\implies Q(y)$, the conclusion.

  8. Generalizing, $\forall x :[P(x)\implies Q(x)] $

Dan Christensen
  • 14,529