2

I am having a hard time with this (simple) excercise in logic:

First, let us define the set $M$ which contains all possible evaluations.

Then, for each proposition sentence $A$, we define a set $[A] = \{ v \in M | v(A) = 1 \}$

So, the task is to show that $[A\rightarrow B]=M$ if and only if $[A]\subseteq[B]$

The reason why I am having a hard time understanding this is that imho M should contain every evaluation, including the one where $v(A)=1$ and $v(B)=0$. But, already the definition of $[A\rightarrow B]$ means that it can contain only those evaluations for which $v(A\land B)=1$.

So, even without the condition of $[A]\subseteq[B]$, how could $[A\rightarrow B]$ ever be the same group as the entire of $M$ if it by definition can't contain those evaluations in which it is not true?

I do not need a solution but simply an explanation of what I am not getting in this excercise...

Remolod Domelor
  • 55
  • 1
  • 4

4 Answers4

3

You are not getting the following: When $A$ and $B$ are non single propositional variables, but setences as it is written, it may be possible, that $A \to B$ is a tautology, for example $A = p\land q$ and $B = p$, to give a trivial one. This is - that is what you should prove - always the case if $[A]\subseteq [B]$, which means the following: Every valuation $v$, which makes $A$ true, i. e. is an element of $[A]$, is an element of $[B]$, i. e. makes $[B]$ true, so there cannot be a $v$ such that $v(A) = 1$ and $v(B) = 0$. This $v$ would be an element of $[A] - [B]$.

martini
  • 84,101
3

A valuation $v$ satisfies a conditional $\phi\to\psi$ when: if $v$ satisfies $\phi$, then $v$ satisfies $\psi$. Equivalently, $v$ satisfies $\phi\to\psi$ if it satisfies $\lnot\phi$ or satisfies $\psi$. (This is the equivalence between $\phi\to\psi$ and $\lnot\phi\lor\psi$.)

Suppose that the set of valuations that satisfy a sentence $\phi$, that is, $[\phi]$ is a subset of the set of valuations that satisfy a sentence $\psi$, that is, $[\psi]$. Symbolically,

$$ [\phi] \subseteq [\psi] \tag{1}$$

Now pick an arbitrary valuation $v_0$. If it satisfies $\phi$, then it is an element of $[\phi]$, and so, by (1), also of $[\psi]$. Then since $v_0$ makes both $\phi$ and $\psi$ true, it makes $\phi\to\psi$ true as well. On the hand, if $v_0$ does not satisfy $\phi$, then it also makes $\phi\to\psi$ true, because a conditional is true in the case that the antecedent is false. Since $v_0$ is arbitrary, we conclude that every valuation satisfies $\phi\to\psi$.

We started with the assumption that $[\phi] \subseteq [\psi]$, so our final conclusion is a conditional:

If the set of all valuations that make $\phi$ true is a subset of the set of all valuations that make $\psi$ true, that is, $[\phi] \subseteq [\psi]$, then every valuation in $M$ satisfies $\phi\to\psi$.

That's one direction of the final biconditional. The other direction is proved by supposing that $[\phi\to\psi] = M$. You are right in observing that for some $\phi$ and $\psi$, it is impossible that this is actually the case, but for others it is quite possible, even when $\phi$ and $\psi$ are propositional variables. For instance, consider the case $P \to P$, where $\phi$ is $P$ and $\psi$ is $P$. At any rate, the proof would proceed by asking what it means that every $[\phi\to\psi] = M$. It means that for every $v \in M$, $v$ satisfies $\phi\to\psi$. What does that mean? … And so on, until reaching the conclusion that if $v$ is in $[\phi]$, then $v$ is in $[\psi]$, which implies that $[\phi] \subseteq [\psi]$. (You said you didn't need a whole proof, so you can fill in the “…”.) This direction concludes that

If every valuation in $M$ satisfies $\phi\to\psi$, then the set of all valuations that make $\phi$ true is a subset of the set of all valuations that make $\psi$ true, that is, $[\phi] \subseteq [\psi]$.

Then the two are combined, and the biconditional is proven.

Joshua Taylor
  • 2,481
  • 16
  • 35
1

The existence of a $v$ such that $v(A)=1$ and $v(B)=0$ also depends on $A$ and $B$. For example, if $A=p$ and $B=p\lor q$ for some propositional letters $p,q$, then $v(A)=1$ implies $v(B)=1$. And that is the situation the exercise is talking about.

Berci
  • 90,745
  • I'm sorry but I'm not sure I understand. Am I right to assume that $M$ does contain also the $v$ in which $v(A)=1$ and $v(B)=0$? And if this isn't the case, why? – Remolod Domelor Jun 08 '13 at 22:13
  • 1
    $A$ and $B$ are sentences, and the evaluation can be freely given only on propositional letters such as $p$ and $q$ in my example. A sentence can also contain logical connectives such as $\lor$ or $\land$ and $\lnot$. $\quad$ So, once $p$ is evaluated as 'true' by $v$, then the sentence $p\lor q$ must be also evaluated as 'true' by $v$. We can say that $v$ is a kind of homomorphism of Boolean algebras. – Berci Jun 08 '13 at 22:18
1

Propositional valuations can assign truth values completely arbitrarily to the propositional variables, but the resulting values for compound sentences are then determined via the truth tables of the connectives, so they are not at all arbitrary. For example, if $p$ is a propositional variable, then some valuations $v$ will have $v(p)=0$ and others will have $v(p)=1$, but for the compound formula $p\lor\neg p$, all valuations will have $v(p\lor\neg p)=1$.

Andreas Blass
  • 71,833