Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Predicate calculus

  1. Aug 9, 2011 #1
    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
  2. jcsd
  3. Aug 9, 2011 #2
    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?
  4. Aug 10, 2011 #3
    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.
  5. Aug 10, 2011 #4
    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.
  6. Aug 10, 2011 #5
    I have mention it already in my opening post that c is a constant
  7. Aug 13, 2011 #6
    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]
    Last edited: Aug 13, 2011
  8. Aug 13, 2011 #7
    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')


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


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

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

    But that doesn't give equality, however...
  9. Aug 13, 2011 #8
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook