Proving Uniqueness in Predicate Calculus with G and F Functions

  • Thread starter solakis
  • Start date
  • Tags
    Calculus
In summary: So this counterexample does not prove that c is not a constant.In summary, given the following, we can prove that c is not a constant.
  • #1
solakis
19
0
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
 
Physics news on Phys.org
  • #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?
 
  • #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.
 
  • #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.
 
  • #5
I have mention it already in my opening post that c is a constant
 
  • #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:
  • #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')

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...
 
  • #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.
 

1. What is "Proving Uniqueness in Predicate Calculus with G and F Functions"?

"Proving Uniqueness in Predicate Calculus with G and F Functions" is a concept in mathematical logic that involves using the G and F functions to prove the existence and uniqueness of a solution to a predicate calculus formula.

2. How do G and F functions work in "Proving Uniqueness in Predicate Calculus with G and F Functions"?

The G and F functions, also known as greatest fixed point and least fixed point functions, respectively, are used to define recursive functions in predicate calculus. These functions are essential in proving the existence and uniqueness of a solution to a formula.

3. Why is proving uniqueness important in predicate calculus?

Proving uniqueness in predicate calculus is important because it ensures that there is only one solution to a given formula. This is crucial in mathematical proofs, as it allows for precise and unambiguous conclusions to be drawn.

4. What are some common techniques used in "Proving Uniqueness in Predicate Calculus with G and F Functions"?

Some common techniques used in proving uniqueness with G and F functions include induction, contradiction, and direct proof. These techniques are used to show that the G and F functions have unique solutions and that these solutions satisfy the given formula.

5. How can "Proving Uniqueness in Predicate Calculus with G and F Functions" be applied in real-world situations?

Proving uniqueness in predicate calculus with G and F functions has applications in various fields, such as computer science, economics, and linguistics. It can be used to prove the existence and uniqueness of solutions in optimization problems, game theory, and natural language processing, among others.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
912
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
827
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
884
  • Calculus and Beyond Homework Help
Replies
1
Views
414
Replies
5
Views
269
Replies
0
Views
287
Back
Top