P is a two digits relation-symbol and $\phi$ the formula:
$(\forall x Pxx \wedge \forall x \forall y \forall z(Pxy \wedge P yz \rightarrow P xz) \wedge \forall x \forall y (Pxy \vee Pyx) \rightarrow \exists x \forall y Pxy) $
Proof that, if a structure $\mathcal{M}$ has a finite universe than $\mathcal{M} \models \phi$.
Hello,
To show:$|M|< \infty \rightarrow \mathcal{M} \models \phi$
I try induction on the numbers of elements in the universe. But i don´t know how i should show this formal exact. In the last lecture we talk about the hilbert system,tautologies,modus ponens, quantifier axioms and so on..
For $|M|=1$,$M=\{s\}$:
From $\mathcal{M} \models (\forall x Pxx \wedge \forall x \forall y \forall z(Pxy \wedge P yz \rightarrow P xz) \wedge \forall x \forall y (Pxy \vee Pyx)$ follows in particular $\mathcal{M} \models \forall x Pxx $ After the definition of Tarksi for all $a \in M: (a,a) \in P^{\mathcal{M}}$. So $(s,s) \in P^{\mathcal{M}}$. So also for every $b \in M$ it exists a $ c \in M$ such that $(b,c) \in P^{\mathcal{M}}$. (I pick s as c). This is the definition after Tarski of $ \mathcal{M} \models \exists x \forall y Pxy$.
Now for n elements the statement is true.
$|M|=n+1, M=\{a_1,..,a_n,a_{n+1}\}$
My thoughts about this: For n Elements $a_1,..,a_n$ i know that such a $ a \in \{a_1,..a_n\}$ exists that for all $ b \in \{a_1,..a_n\}: (a,b) \in P^{\mathcal{M}}$. Now beecause of the total order i can say $P(a_{n+1}, a) or (a, a_{n+1})\in P^{\mathcal{M}}$. If $ (a_{n+1},a)\in P^{\mathcal{M}}$ then from the transitivity follows that $(a_{n+1}, b)\in P^{\mathcal{M}}$ for all $b \in M$. If $(a, a_{n+1})\in P^{\mathcal{M}}$ than $(a,b)\in P^{\mathcal{M}}$ for all $b \in M$ because of the hypothesis.
Question: How i can formualisize the idea?