predicate calculus

solakis

Given the following :

1)[itex]\forall x\forall y\forall z G(F(F(x,y),z),F(x,F(y,z)))[/itex]


2)[itex]\forall xG(F(x,c),x)[/itex]


3)[itex]\forall x\exists yG(F(x,y),c)[/itex]


4)[itex]\forall x\forall yG(F(x,y),F(y,x))[/itex].


5) [itex]\forall x\forall y\forall z ( G(x,y)\wedge G(x,z)\Longrightarrow G(y,z))[/itex]

Where G is a two place predicate symbol. F ,is a two place term symbol and c is a constant.


Prove :[itex]\exists! y\forall xG(F(x,y),x)[/itex]

[itex]\exists ! y[/itex] means : there exists a unique y

praeclarum

Is this a homework question, or just for fun, or what?

And I am assuming that E! x ph <-> E. y A. x ( x = y <-> ph ), right?

solakis

This is a problem given to me by a friend ,that i could not solve out.

This two place predicate and term is very confusing.

praeclarum

Is "c" a constant or a variable? Because if it is a variable, then you can prove a contradiction given the conclusion and given that there are at least 2 distinct values of x.

We could prove that A. y A. x G ( F ( x , y ) x ) given 2, which contradicts the conclusion.

solakis

I have mention it already in my opening post that c is a constant

xxxx0xxxx

Well, existence is straight forward:

From 2) and c

[tex]\exists c \wedge \forall x G(F(x,c),x) \Rightarrow \exists y \forall x G(F(x,y),x)[/tex]

uniqueness is left as an exercise:

[tex]\forall u(\forall x G(F(x,u),x) \Rightarrow u=c)[/tex]

micromass

When you take G the equality, then your list of axioms is that of a commutative group. The thing you need to prove is that the identity element is unique.

Take two identity's c and c', then

3) G(F(c',c),c')

and

3) G(F(c,c'),c)

and

4) G(F(c,c'),F(c',c))

So by (5), we get that G(c,c')

But that doesn't give equality, however...

micromass

OK, what about this counterexample:

Take [itex]\mathbb{Z}_0[/itex] as universe. Take

[itex]G(x,y)~\text{if and only if}~\frac{x}{y}\geq 0[/itex]

and F(x,y)=x*y and c=1.

Then y=1 and y=2 both satisfy the hypothesis.