Math 557 Sep 3

Validities

Key Concepts

  • Validity: An \(\mathcal{L}\)-formula \(\psi\) that is valid in any \(\mathcal{L}\)-structure under any assignment \(\alpha\), i.e.

\[\mathcal{M} \models \psi[\alpha] \quad \text{ for any } \mathcal{M}, \alpha.\]

  • Sources of validities:

    • Propositional tautologies – e.g. formulas of the form \(\psi \to \psi\) or \(\psi \vee \neg \psi\)
    • Equality - the way \(=\) is interpreted implies formulas like \(\forall x \; x=x\) are validities.
    • Quantifiers

  • Fundamental questions:

    • Can we characterize the set of validities syntactically?
    • In particular, is there an algorithm that, on input \(\varphi\), determines whether \(\varphi\) is a validity or not?

Problems

Exercise 1 (Warmup)
Determine whether the following formulas are validitites.

  • \(((\varphi_1 \, \to \, (\varphi_2 \, \to \, \varphi_3)) \, \to \, ((\varphi_1 \, \to \, \varphi_2) \, \to \, (\varphi_1 \, \to \, \varphi_3)))\)
  • \(\exists x (\varphi \wedge \psi) \: \leftrightarrow \: (\exists x \varphi \wedge \exists x \psi)\)

Exercise 2
Let \(g ∶ \{0, 1\}^n → \{0, 1\}\) be a Boolean function. Show that there exists a propositional formula \(F(p_1, \dots, p_n)\) such that, for any assignment \(\delta\) to the variables \(p_1, \dots, p_n\),

\[\delta^*(F) = g(\delta(p_1), \dots, \delta(p_n)).\]

Exercise 3
Formally verify that every propositional tautology is a validity.

Exercise 4
Verify, using the definition of the satisfaction relation \(\models\), that

\[\forall x,y (x = y \: \to \: f(x)=f(y)) \quad (\text{$f$ unary function symbol})\]

and \[\forall x ( \varphi \to \psi) \; \to \; (\varphi \to \forall x \psi) \quad (\text{$x$ not free in $\varphi$})\]

are validities.