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?

up vote 1 down vote accepted

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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