Prove: A is a tautology implies A is valid (w/o soundness theorem)

431 Views Asked by At

I'm asked to prove without the soundness theorem that if $A$ is a tautology then $\vDash A $.

Since $A$ is a tautology, every truth valuation $v$ gives $v(A) = \mathbb T$.

So, If $M$ is a structure and $\sigma $ is an assignment of $M$, $\bar \sigma$ is essentially a truth valuation:

If we decompose $A$ to a boolean combination of elementary formulas, $\bar \sigma$ gives some truth value to each one, and it holds the same rules of negation and conjunction as a truth valuation.

But this sounds too simple. Am I missing something?

1

There are 1 best solutions below

1
On BEST ANSWER

HINT

You are working in First-Order Logic; thus, we assume that the formulae are FOL ones, like $P(x) \lor \lnot P(x)$, that is an instance of a tautology, and thus it must be valid.

But this means that we have to consuder the "general case" for the definition of satisfiability, with a structure $M$ and an assignment function $s : V \to |M|$, where $V$ is the set of free variables of the language and $|M|$ is the domain of the strucute.

Having said that, your approach is sound; you have only to add some details.

Starting from a strucutre $M$ and an assignment $s$, we use $s$ to define a truth assignment $v$ on the atomic formulae of the language such that :

$v( \alpha)=T$ iff $M \vDash \alpha[s]$, for any atomic $\alpha$.

The tuth assignment $v$ can be extended to a truth assignment $\overline v$ such that :

$\overline v( \alpha)=T$ iff $M \vDash \alpha[s]$, for any $\alpha$.

The proof is by induction on the complexity of the formula, using - as you say - the rules for negation and conjunction [or disjunction, or conditional] of truth valuations.

Now it is done : if the formula $\alpha$ is a tautology, it will be true for any $\overline v$; thus, it comes out true also for any $M,s$, and so it is valid.


Consider the trivial example above; if for $M,s$ $P(x)[s]$ is satisfied in $M$, it is enough to define $v$ such that $v(P(x))=T$ [if not, set $v(P(x))=F$], and thus we will have :

$\overline v(P(x) \lor \lnot P(x))=T$

showing that : $M \vDash (P(x) \lor \lnot P(x))[s]$.

But this holds for $M,s$ whatever; thus $P(x) \lor \lnot P(x)$ is valid.