How to show tautologies in FOL using truth definitions?

Question

Anyone know how to prove these tautologies by way of truth definition? I take it that to solve a), I need to disprove a minimal counter example to the formula/sentence given? If so, how to formally construct one? Do I consider the non given premises to be the empty set and is that even relevant? Otherwise, any other suggestions? Well I thaught that one should create a model, in where I can show that the sentence is true. But my question is then how do I expand it so that it is true in all models? I have also tried the approach where I use the fact that the null space _ {-phi} is true and phi is not under a model?

a) ⊨ ∀x∃y(x=y) b) ⊨ ∃x(t=x), where t is a closed term

Cheers!

Answer 1

I'm not sure what you mean by proving a tautology "by way of truth definition", but I'll take a guess. The completeness theorem for first order logic says that an $\mathcal{L}$-sentence $\phi$ can be deduced from an $\mathcal{L}$-theory $T$ if and only if it is true in all models of $T$ (here $\mathcal{L}$ is our language/signature). Taking $T$ to be the empty theory (in the language $\mathcal{L}$), we have that $\phi$ is a tautology (i.e. it can be deduced from no assumptions) if and only if it is true in all $\mathcal{L}$-structures (all $\mathcal{L}$-structures are models of the empty theory).

a) Let $M$ be an $\mathcal{L}$-structure. We want to show that $\forall x\, \exists y\, (x = y)$ is true in $M$. That is, for any $a$ in $M$, we need to find a $b\in M$ such that $a = b$. Easy: take $b$ to be $a$!

b) Let $M$ be an $\mathcal{L}$-structure, and let $t$ be a closed $\mathcal{L}$-term. We need to find $a\in M$ such that $t^M = a$. Easy: take $a$ to be $t^M$!

Answer 2

I assume that your problem is about (first-order) validity, i.e. we want to show "by way of truth definition" that the following formulas :

a) $\vDash \forall x \exists y (x = y)$

and

b) $\vDash \exists x (t = x)$, where $t$ is a closed term

are valid, i.e. true in every interpretation.

In order to show that, "by way of truth definition", we need to apply the definition of validity, i.e.

$\varphi$ is valid iff for every $\mathcal L$-structure $M$ and every interpretation $s: Var \rightarrow |M|$, $M$ satisfies $\varphi$ with $s$

and show that the above formulas have the desired property, i.e. we show that they are true for a "generic" $M$ and for all interpretations of the variables: in this way we conclude that they are valid.

So we must apply the construction of Alex's answer: take an $\mathcal L$-structure $M$ ("generic", i.e. we do not presuppose any specific "characteristic" about it) and show that (for e.g. the formula a)) for every $a \in M$ we can find a $b \in M$ such that $a = b$.

Our "choice" is possible for every interpretation in $M$ because with an interpretation we assign to $x$ a denotation (an object $a \in M$), and we are able, for every $a \in M$ that we may "choose" as denotation for $x$, to assign to $y$ a suitable denotation that satisfy the formula $x = y$; we can do this simply assigning to $y$ $a$ itself.

Being able to do this for every interpretation in $M$, we have showed that a) is true in $M$ (or we can say that $M$ ia a model of the formula) ; but $M$ is "generic", so our conclusion must be true for every $M$, and so we can conclude that a) is valid.