1
$\begingroup$

How is validity supposed to work with free variables in first order logic?

Let X[ts] mean "There is a connection between variables t and s" in graph G

Would X[xx] be only valid if every node in graph G has a connection to itself? Would X[xy] only be valid if every node in graph G is connected to every node including itself?

And if one of the variable is bound whilst the other one is free, then would the formula only be valid if the bound variable's value (a node) is connected to every node in graph G including itself? For example:

∃xX[xy] would be valid if there exists a node that is connected to every node in graph G including itself?

∀xX[xy] would be valid if every node is connected to every node in graph G including itself?

$\endgroup$
  • $\begingroup$ "If a formula φ has free variables X = (x1,...,xk), φ is valid iff ∀Xφ is valid." Source: cseweb.ucsd.edu/classes/sp07/cse205a/fo.pdf Does this mean that the answer to all of the questions above is "yes"? $\endgroup$ – user2108462 Dec 24 '13 at 12:06
1
$\begingroup$

If a formula φ has free variables X = (x1,...,xk), φ is valid iff ∀Xφ is valid.

So the answer to all the questions is yes.

Generalized answer:

A formula is satisfiable iff its existential closure is true

A formula is valid iff its universal closure is true

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.