Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose $A$ is a set of propositional formulas, and suppose $\varphi$ is a propositional formula. In my textbook they write $A \models \varphi$, if for every truth assignment $w$ such that $w(\psi) = 1$ for every $\psi \in A$, we also have $w(\varphi)=1$.

They now ask me to show that $\emptyset\models \varphi$ if and only if $\varphi$ is a tautology. But how can I show this? The definition tells us nothing about empty $A$?

share|improve this question
    
If $A=\emptyset$, then every truth assignment $w$ satisfies $w(\psi)=1$ for every $\psi\in A$, because there are no such $\psi$. Thus $\emptyset\models\varphi$ if and only if $w(\varphi)=1$ for every truth assignment $w$. –  walcher Sep 2 '13 at 23:10
    
@walcher, But if there is no such $\psi$ why does $\varphi$ have to be a tautology? –  user92809 Sep 2 '13 at 23:17

2 Answers 2

up vote 3 down vote accepted

Suppose $A = \varnothing$. Then, for any truth value assignment $w$, $w(\psi) = 1$ (vacuously) for each and every $\psi \in A = \varnothing$

Why?
Because there are no $\psi \in A = \varnothing$. So the hypothesis is satisfied vacuously, because it is not possible for there to exist any $\psi \in \varnothing$ such that $w(\psi) \neq 1$.

Hence $\varnothing \models \varphi$ if and only if for each truth value assignment $w$, $w(\varphi) = 1$, too. This holds if and only if $\varphi$ is a tautology.

share|improve this answer

This is a nice opportunity to illustrate for the novice the role of proof strategies in reasoning mathematically about logical claims.

Notice, first of all, that the definition of entailment $\models$, if put in negative terms, says that to prove that $A\models\varphi$ fails to hold one has to find some truth-assignment $v$ that simultaneously satisfies $A$ and does not satisfy $\varphi$. Furthermore, recall that $v$ is said to satisfy a given set of formulas $A$ if $v(\psi)=1$ for every $\psi\in A$; thus, contrapositively, we may say that $A$ is not satisfied by $v$ if there is some $\psi\in A$ that is not satisfied by $v$, that is, such that $v(\psi)=0$.

[Lemma] Any truth-assignment $v$ satisfies the empty set of formulas.
Proof. To assert that the empty set $\emptyset$ is not satisfied by a given truth-assignment $v$ would require us first of all to find some formula $\psi$ in $\emptyset$ with a certain property (namely, the property of not being satisfied by $v$). But this is an impossible task, as there are no formulas in the empty set!
(Incidentally, this is precisely what it means to say that a certain property is vacuously true.)

[Main Claim: one direction] ($\emptyset\models \varphi$) implies that ($\varphi$ is a tautology).
Proof. Suppose, by contraposition, that $\varphi$ is not a tautology, that is, suppose that there is some truth-assignment $w$ such that $w(\varphi)=0$. By the previous Lemma, we alread know that $w$ satisfies the empty set $\emptyset$. Thus, by the definition of entailment, $\emptyset\models \varphi$ fails to hold.

[Main Claim: other direction] ($\varphi$ is a tautology) implies that ($\emptyset\models \varphi$).
Proof. Assume that $\varphi$ is a tautology, that is, assume that $v(\varphi)=1$ for every truth-assignment $v$. Suppose now by reductio that $\emptyset\models \varphi$ fails to hold. It follows, in particular that there is some truth-assignment $w$ such that $w(\varphi)=0$ (the failure of $\emptyset\models \varphi$ also entails, in particular, that such $w$ satisfies $\emptyset$, but that is innocuous and known anyway to be true, from the above Lemma), that is, we are given a truth-assignment that does not satisfy $\varphi$. This immediately contradicts the assumption about the tautological character of $\varphi$.

PS: The exhaustive amount of detail in the above proofs usually reduce to something like one- or two-line arguments as students get more and more experienced in producing them.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.