conservative extension of the theory

332 Views Asked by At

There are two languages $L = \{P\}$ and $L' = \{P, f\}$ with equality. $P$ is binary predicate symbol. $f$ is unary functional symbol.

$\varphi_1 ≡ ∀x P(x, x)$

$\varphi_2 ≡ ∀x∀y((P(x, y) ∧ P(y, x)) → x = y)$

$\varphi_3 ≡ ∀x∀y∀z((P(x, y) ∧ P(y, z)) → P(x, z))$

$\varphi_4 ≡ ∀x∃y(P(x, y) ∧ x \ne y)$

$\varphi_5 ≡ ∀x∀y(P(x, y) ∨ P(y, x))$

$\varphi_6 ≡ ∀x (f(x) \ne x ∧ P(x, f(x)) ∧ ∀y ((P(x,y) ∧ P(y, f(x))) → (y = x ∨ y = f(x))))$

$\varphi_7 ≡ ∀x∀y(f(x) = f(y) → P(x, y))$

$\varphi_8 ≡ ∀x ¬P(f(x), x)$

$\varphi_9 ≡ ∀x∀y((P(f(x),y) → P(x, y)) ∧ (P(x, y) → P(x, f(y))))$

There are theories $T=\{\varphi_1, \varphi_2, \varphi_3, \varphi_4\}$, $U=\{\varphi_1, \varphi_2,\varphi_3,\varphi_4,\varphi_5\}$ of language $L$ and theory $T_1=\{\varphi_2, \varphi_3, \varphi_6, \varphi_7\}$, $T_2=\{\varphi_1, \varphi_3, \varphi_6, \varphi_8 \}$, $T_3=\{\varphi_1, \varphi_2, \varphi_6, \varphi_9 \}$, $T_4 = \{\varphi_1, \varphi_2, \varphi_5, \varphi_6, \varphi_9 \}$ of language $L'$

For each of theories $T_1, T_2, T_3$ I need to find if it is an extension and if it is conservative extension of the theory $T$. Also I need to find and prove if $T_4$ is extension and if it is conservative extension of the theory $U$.

Could somebody suggest me some flow of prove? Thanks for any advice.

1

There are 1 best solutions below

0
On BEST ANSWER

Not a complete answer, too long for a comment.

I don't recall the difference between conservative and extensions, so I'll outline how to make the equivalences when they occur.

It's much easier to understand if you replace $P(x,y)$ with symbols $x\leq y$. Then the axioms have an obvious interpretation. Write $x<y$ to mean $x\leq y\land x\neq y$.

(1)-(3) are "partial order" axioms.

(4) says there is no maximal element - there is always something bigger.

(5) says it is a total order.

(6) says $x<f(x)$ and no $y$ satisfies $x<y<f(x)$. This means that $f(x)$ is a single atom bigger than $x$.

(7) says that if $f(x)=f(y)$ then $x\leq y$.

(8) say that it is never true that $f(x)\leq x$.

(9) says that if $f(x)\leq y$ then $x\leq y$ and that $x\leq y$ implies $x\leq f(y)$.

$T$ is the theory of partial orders without upper bound.

$U$ is the theory of linear orders without upper bounds.

The other ones are harder to interpret, because we don't have all the partial order axioms in them.

$T_1$

(2) and (3) together, without (1), models a partial order with a set of distinguished elements. That is, we can define:

$$x\leq y := P(x,y)\lor x=y\\ Q(x):=P(x,x)$$

These two entirely determine the theory (2),(3).

(7) shows that $P(x,x)$ is always true, since $\forall x(f(x)=f(x))$ is true. So (1) is true in $T_1$.

(6) implies (4) - the first part of (6) shows there is a "bigger" element than every $x$.

So, $T_1$ proves all the axioms of $T$, and $Q$ really adds nothing.


$T_2$

$T_2$ has (1) and (3), which gives us a pre-order. This also makes $f$ more complicated. If $x\neq y$ and $x\leq y$ and $y\leq x$, then we can show that $x\leq y$ and $y\leq f(x)$, so $y=f(x)$. Thus also, $x=f(y)$. In particular, our pre-order equivalence classes can't have more than two elements. But (8) says that $f(x)\leq x$ can't happen, so (6) and (8) together prove (1). So $T_2$ contains all the axioms for $T$.


$T_3$

Having a hard time getting my mind around $T_3$. Without (3), you are slightly stuck.