Let A be a field of subsets of a non-empty set X

Let Form be the set of propositional formulas over a fixed set V of propositional variables. Let us call an arbitrary function $ν : V −→ A$ a valuation in A. By induction on formulas ν can be uniquely extended to a function $¯ν : Form −→ A$ such that for every α, β ∈ Form:

  1. $¯ν(¬α) = X $ \ $ ν¯(α)$,

  2. $¯ν(α ∨ β) = ¯ν(α) ∪ ν¯(β)$,

  3. $¯ν(α ∧ β) = ¯ν(α) ∩ ν¯(β)$,

  4. $¯ν(α ⇒ β) = X$ \ $(ν¯(α)) ∪ ν¯(β)$,

  5. $¯ν(α ⇔ β) = X$ \ $(¯ν(α) - ν¯(β))$.

Prove that if $α ∈ Form$ is a tautology, then $¯ν(α) = X$.

I did the prove for tautology like $A ∨¬A$ but I dont know how to prove it for every tautology, because there re infinite tautologies. With the definition of tautology I just can say that for every valuation v, in fact in v, is true.

  • $\begingroup$ Can you elaborate on what $X$ is supposed to be? $\endgroup$ – Stefan Mesken Nov 1 '16 at 14:52
  • $\begingroup$ The exercise said $X$ but maybe its $A$ I dont know. $\endgroup$ – energy Nov 1 '16 at 15:06
  • $\begingroup$ Replacing $X$ with $A$ doesn't make sense either (in light of the usage of $X \setminus \ldots$). Please edit your post in a way that it fully reflects the exercise you were given. $\endgroup$ – Stefan Mesken Nov 1 '16 at 15:17
  • $\begingroup$ Done, I forgot a line: Let A be a field of subsets of a non-empty set X $\endgroup$ – energy Nov 1 '16 at 15:25
  • $\begingroup$ Okay, that does make sense. $\endgroup$ – Stefan Mesken Nov 1 '16 at 15:28

Let $\alpha \in \operatorname{Form}$ be such that $\bar{\nu}(\alpha) \neq X$. Then there is some $x \in X$ such that $x \not \in \overline{\nu}(\alpha)$. We build an evaluation $\bar{\mu} \colon \operatorname{Form} \to \{ 0,1 \}$ as follows:

For $v \in V$ we let $\mu(v) = 1$ iff $x \in \nu(v)$. This induces a unique evaluation $\bar{\mu} \colon \operatorname{Form} \to \{ 0,1 \}$ such that

  • $\bar{\mu}(v) = \mu(v)$ for all $v \in V$,
  • $\bar{\mu}(\neg \phi) = 1 - \bar{\mu}(\phi)$,
  • $\bar{\mu}(\phi \wedge \psi) = \min \{\bar{\mu}(\phi), \bar{\mu}(\psi) \}$ and
  • $\bar{\mu}(\phi \vee \psi) = \max \{\bar{\mu}(\phi), \bar{\mu}(\psi) \}$

for all $\phi, \psi \in \operatorname{Form}$. By induction on the complexity of $\alpha$ it's now easy to show that $\bar{\mu}(\alpha) = 0$. Hence $\alpha$ is not a tautology.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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