Goundoubuf

2022-11-25

What does it mean when x is 'free'?
In the context of first-order logic and resolution (I'm trying to study Skolemization for a midterm tomorrow), I am seeing several references to $x$ being free or not free. What does this mean?
To pull all quantifiers in front of the formula and thus transform it into a prenex form, use the following equivalences, where $x$ is not free in Q:
Edit:
$\mathrm{\forall }xP\left(x\right)\wedge \mathrm{\exists }xQ\left(x\right)\equiv \mathrm{\forall }x\left(P\left(x\right)\wedge \mathrm{\exists }xQ\left(x\right)\right)\equiv \mathrm{\forall }x\left(P\left(x\right)\wedge \mathrm{\exists }yQ\left(y\right)\right)\equiv \mathrm{\forall }x\mathrm{\exists }y\left(P\left(x\right)\wedge Q\left(y\right)\right).$
If the second x is bound by the existential quantifier - why can it be pulled into prenex form if the blurb above says that this can be done only if x is not free? Or am I misunderstanding something?
Edit 2:
OK, i'm clearly not all here at the moment. Ignore that question

Bryson Carlson

Expert

A variable ${x}_{1}$ in a formula $\varphi \left({x}_{1},{x}_{2},\cdots ,{x}_{n}\right)$ is called bound if ${x}_{1}$ is contained in some sub-formula of the form $\mathrm{\forall }{x}_{1}\left(\psi \left({x}_{1},\cdots \right)\right)$. If ia variable is not bound, it is free. That is, a variable is free if it is not being quantified over, so that it is "free" to assume different values. On the other hand, if a variable is being quantified over, it is almost like a placeholder -- it doesn't make sense to try and input different values for that variable.
With regards to your second question, since $x$ is bound it is not free.

armlanna1sK

Expert

$x$ is free in $Q$ if it is not quantified over.
So in the ${L}_{Ring}$ formula $x=1$, $x$ is free.
But in the ${L}_{Ring}$ formula $\mathrm{\forall }x\left(x=1\right)$, $x$ is not free (in which case we call $x$ bound)

Do you have a similar question?