Proving Primitive Symbols with Axioms

[solakis1]

Given :

A) primitive symbols : (1, *) and

B) The axioms:

1) \(\displaystyle \forall x\forall y[x*=y*\Longrightarrow x=y]\)

2) \(\displaystyle \forall x[x*\neq 1]\)

3) \(\displaystyle [P(1)\wedge\forall x(P(x)\Longrightarrow P(x*))]\Longrightarrow\forall xP(x)\)

Then prove:

\(\displaystyle \forall x[x=1\vee \exists y(y*=x)]\)

 

[jvicens]

First, we will use axiom 2 to show that 1 is not equal to any other primitive symbol. Assume the opposite, that 1 is equal to some primitive symbol x. By axiom 1, this means that 1* = x*. But this contradicts axiom 2, since 1* = 1 and we know that 1 ≠ 1. Therefore, 1 is not equal to any other primitive symbol.

Next, we will prove the statement \forall x[x=1\vee \exists y(y*=x)] by contradiction. Assume the opposite, that there exists some x such that x ≠ 1 and for all y, y* ≠ x. This means that there is no primitive symbol that can be multiplied by another primitive symbol to get x. This contradicts axiom 3, since it states that if P(1) is true and for all x, P(x) implies P(x*), then P(x) is true for all x. In this case, P(1) is true (since 1 ≠ 1 is false) and for all x, x ≠ 1 implies x* ≠ x (since we assumed this to be true). Therefore, by axiom 3, \forall x[x=1\vee \exists y(y*=x)] must be true.

In conclusion, by using the given axioms, we have proven that \forall x[x=1\vee \exists y(y*=x)]. This means that for any primitive symbol x, either x is equal to 1 or there exists some primitive symbol y such that y* = x.