What does x is free for substitution for y in $varphi$, but not for z means?
up vote
0
down vote
favorite
I am studying about first order predicate logic, and I have some difficulties understanding substitution and free variables.
If x is free for substitution for y in $varphi$, but not for z, where $varphi$ is a single formula, what would this mean?
Also x,y and z are variables.
Can you give a formula $varphi$ that satisfies this condition?
logic predicate-logic
add a comment |
up vote
0
down vote
favorite
I am studying about first order predicate logic, and I have some difficulties understanding substitution and free variables.
If x is free for substitution for y in $varphi$, but not for z, where $varphi$ is a single formula, what would this mean?
Also x,y and z are variables.
Can you give a formula $varphi$ that satisfies this condition?
logic predicate-logic
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am studying about first order predicate logic, and I have some difficulties understanding substitution and free variables.
If x is free for substitution for y in $varphi$, but not for z, where $varphi$ is a single formula, what would this mean?
Also x,y and z are variables.
Can you give a formula $varphi$ that satisfies this condition?
logic predicate-logic
I am studying about first order predicate logic, and I have some difficulties understanding substitution and free variables.
If x is free for substitution for y in $varphi$, but not for z, where $varphi$ is a single formula, what would this mean?
Also x,y and z are variables.
Can you give a formula $varphi$ that satisfies this condition?
logic predicate-logic
logic predicate-logic
asked Nov 19 at 21:42
astro_chae
62
62
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Consider the open wff with two free variables
$Fy to forall x Gzx$
Then substituting $x$ for $y$ gives us
$Fx to forall x Gzx$
Again a wff with two free variables (check you understand this claim). The two expressions can in effect be thought of as available to express the same binary relation.
Substituting $x$ for $z$ in the first wff however gives us
$Fy to forall x Gxx$
a wff now with one free variable. What's happened is that, in the second case, what was a free variable gets captured by the quantifier, and so the quantificational structure of the wff is changed. We don't want merely changing the letter we use for a variable to have that sort of effect -- hence, as we say, '$x$' is here not free to be substituted for '$z$' (while preserving quantificational structure).
Thanks for the answer :) What I understood is if we substitute a variable (for instance y to x) and if it is not restricted by the quantifiers, then it is free. Additionally, I was wondering if there is any example of closed formula. Would there be an example?
– astro_chae
Nov 20 at 4:26
Think about $exists z(forall yFy to forall xGxz)$. Which of $y$ and $z$ could be systematically replaced by $x$, and why?
– Peter Smith
Nov 20 at 14:21
Thanks for the reply :) What I am understanding is, If I replace y by x, then y is free because it is not restricted by any quantifiers, but if we replace z by x then because of $exists$x every x in the bracket becomes restricted. I hope I understood correctly. Thank you :)
– astro_chae
Nov 20 at 22:44
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Consider the open wff with two free variables
$Fy to forall x Gzx$
Then substituting $x$ for $y$ gives us
$Fx to forall x Gzx$
Again a wff with two free variables (check you understand this claim). The two expressions can in effect be thought of as available to express the same binary relation.
Substituting $x$ for $z$ in the first wff however gives us
$Fy to forall x Gxx$
a wff now with one free variable. What's happened is that, in the second case, what was a free variable gets captured by the quantifier, and so the quantificational structure of the wff is changed. We don't want merely changing the letter we use for a variable to have that sort of effect -- hence, as we say, '$x$' is here not free to be substituted for '$z$' (while preserving quantificational structure).
Thanks for the answer :) What I understood is if we substitute a variable (for instance y to x) and if it is not restricted by the quantifiers, then it is free. Additionally, I was wondering if there is any example of closed formula. Would there be an example?
– astro_chae
Nov 20 at 4:26
Think about $exists z(forall yFy to forall xGxz)$. Which of $y$ and $z$ could be systematically replaced by $x$, and why?
– Peter Smith
Nov 20 at 14:21
Thanks for the reply :) What I am understanding is, If I replace y by x, then y is free because it is not restricted by any quantifiers, but if we replace z by x then because of $exists$x every x in the bracket becomes restricted. I hope I understood correctly. Thank you :)
– astro_chae
Nov 20 at 22:44
add a comment |
up vote
1
down vote
accepted
Consider the open wff with two free variables
$Fy to forall x Gzx$
Then substituting $x$ for $y$ gives us
$Fx to forall x Gzx$
Again a wff with two free variables (check you understand this claim). The two expressions can in effect be thought of as available to express the same binary relation.
Substituting $x$ for $z$ in the first wff however gives us
$Fy to forall x Gxx$
a wff now with one free variable. What's happened is that, in the second case, what was a free variable gets captured by the quantifier, and so the quantificational structure of the wff is changed. We don't want merely changing the letter we use for a variable to have that sort of effect -- hence, as we say, '$x$' is here not free to be substituted for '$z$' (while preserving quantificational structure).
Thanks for the answer :) What I understood is if we substitute a variable (for instance y to x) and if it is not restricted by the quantifiers, then it is free. Additionally, I was wondering if there is any example of closed formula. Would there be an example?
– astro_chae
Nov 20 at 4:26
Think about $exists z(forall yFy to forall xGxz)$. Which of $y$ and $z$ could be systematically replaced by $x$, and why?
– Peter Smith
Nov 20 at 14:21
Thanks for the reply :) What I am understanding is, If I replace y by x, then y is free because it is not restricted by any quantifiers, but if we replace z by x then because of $exists$x every x in the bracket becomes restricted. I hope I understood correctly. Thank you :)
– astro_chae
Nov 20 at 22:44
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Consider the open wff with two free variables
$Fy to forall x Gzx$
Then substituting $x$ for $y$ gives us
$Fx to forall x Gzx$
Again a wff with two free variables (check you understand this claim). The two expressions can in effect be thought of as available to express the same binary relation.
Substituting $x$ for $z$ in the first wff however gives us
$Fy to forall x Gxx$
a wff now with one free variable. What's happened is that, in the second case, what was a free variable gets captured by the quantifier, and so the quantificational structure of the wff is changed. We don't want merely changing the letter we use for a variable to have that sort of effect -- hence, as we say, '$x$' is here not free to be substituted for '$z$' (while preserving quantificational structure).
Consider the open wff with two free variables
$Fy to forall x Gzx$
Then substituting $x$ for $y$ gives us
$Fx to forall x Gzx$
Again a wff with two free variables (check you understand this claim). The two expressions can in effect be thought of as available to express the same binary relation.
Substituting $x$ for $z$ in the first wff however gives us
$Fy to forall x Gxx$
a wff now with one free variable. What's happened is that, in the second case, what was a free variable gets captured by the quantifier, and so the quantificational structure of the wff is changed. We don't want merely changing the letter we use for a variable to have that sort of effect -- hence, as we say, '$x$' is here not free to be substituted for '$z$' (while preserving quantificational structure).
edited Nov 20 at 0:22
answered Nov 19 at 23:54
Peter Smith
40.3k339118
40.3k339118
Thanks for the answer :) What I understood is if we substitute a variable (for instance y to x) and if it is not restricted by the quantifiers, then it is free. Additionally, I was wondering if there is any example of closed formula. Would there be an example?
– astro_chae
Nov 20 at 4:26
Think about $exists z(forall yFy to forall xGxz)$. Which of $y$ and $z$ could be systematically replaced by $x$, and why?
– Peter Smith
Nov 20 at 14:21
Thanks for the reply :) What I am understanding is, If I replace y by x, then y is free because it is not restricted by any quantifiers, but if we replace z by x then because of $exists$x every x in the bracket becomes restricted. I hope I understood correctly. Thank you :)
– astro_chae
Nov 20 at 22:44
add a comment |
Thanks for the answer :) What I understood is if we substitute a variable (for instance y to x) and if it is not restricted by the quantifiers, then it is free. Additionally, I was wondering if there is any example of closed formula. Would there be an example?
– astro_chae
Nov 20 at 4:26
Think about $exists z(forall yFy to forall xGxz)$. Which of $y$ and $z$ could be systematically replaced by $x$, and why?
– Peter Smith
Nov 20 at 14:21
Thanks for the reply :) What I am understanding is, If I replace y by x, then y is free because it is not restricted by any quantifiers, but if we replace z by x then because of $exists$x every x in the bracket becomes restricted. I hope I understood correctly. Thank you :)
– astro_chae
Nov 20 at 22:44
Thanks for the answer :) What I understood is if we substitute a variable (for instance y to x) and if it is not restricted by the quantifiers, then it is free. Additionally, I was wondering if there is any example of closed formula. Would there be an example?
– astro_chae
Nov 20 at 4:26
Thanks for the answer :) What I understood is if we substitute a variable (for instance y to x) and if it is not restricted by the quantifiers, then it is free. Additionally, I was wondering if there is any example of closed formula. Would there be an example?
– astro_chae
Nov 20 at 4:26
Think about $exists z(forall yFy to forall xGxz)$. Which of $y$ and $z$ could be systematically replaced by $x$, and why?
– Peter Smith
Nov 20 at 14:21
Think about $exists z(forall yFy to forall xGxz)$. Which of $y$ and $z$ could be systematically replaced by $x$, and why?
– Peter Smith
Nov 20 at 14:21
Thanks for the reply :) What I am understanding is, If I replace y by x, then y is free because it is not restricted by any quantifiers, but if we replace z by x then because of $exists$x every x in the bracket becomes restricted. I hope I understood correctly. Thank you :)
– astro_chae
Nov 20 at 22:44
Thanks for the reply :) What I am understanding is, If I replace y by x, then y is free because it is not restricted by any quantifiers, but if we replace z by x then because of $exists$x every x in the bracket becomes restricted. I hope I understood correctly. Thank you :)
– astro_chae
Nov 20 at 22:44
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005561%2fwhat-does-x-is-free-for-substitution-for-y-in-varphi-but-not-for-z-means%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown