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.

• Can you elaborate on what $X$ is supposed to be? – Stefan Mesken Nov 1 '16 at 14:52
• The exercise said $X$ but maybe its $A$ I dont know. – energy Nov 1 '16 at 15:06
• 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. – Stefan Mesken Nov 1 '16 at 15:17
• Done, I forgot a line: Let A be a field of subsets of a non-empty set X – energy Nov 1 '16 at 15:25
• Okay, that does make sense. – 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.