Substitutability in First-Order Logic
up vote
0
down vote
favorite
Here is a definition for substitutability found in a PDF of logic notes by Eric Pacuit:
I am more concerned with the part of the definition squared in red. My question is: Given $(forall y) psi$, does this mean that, since $y$ does not occur free in $(forall y) psi$, is $tau$ substitutable for $y$ in $(forall y) psi$?
logic first-order-logic substitution
asked Nov 18 at 4:42
numericalorange
1,619311
add a comment |
up vote
0
down vote
favorite
Here is a definition for substitutability found in a PDF of logic notes by Eric Pacuit:
I am more concerned with the part of the definition squared in red. My question is: Given $(forall y) psi$, does this mean that, since $y$ does not occur free in $(forall y) psi$, is $tau$ substitutable for $y$ in $(forall y) psi$?
logic first-order-logic substitution
asked Nov 18 at 4:42
numericalorange
1,619311
1
Yes, because the term substitutable means that performing the operation we "cause no troubles". In that case, the operation is allowed simply because it does not change the original formula.
– Mauro ALLEGRANZA
Nov 18 at 12:49
@MauroALLEGRANZA I found another definition for substitutability from the textbook by Arindama Singh: $y$ is free for $x$ in $phi$ iff $x$ does not occur free within the scope of any $forall y$ or $exists y$. Is the negation: $y$ is not free for $x$ in $phi$ iff $x$ occurs free within the scope of any $forall y$ or $exists y$?
– numericalorange
Nov 19 at 4:53
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Here is a definition for substitutability found in a PDF of logic notes by Eric Pacuit:
I am more concerned with the part of the definition squared in red. My question is: Given $(forall y) psi$, does this mean that, since $y$ does not occur free in $(forall y) psi$, is $tau$ substitutable for $y$ in $(forall y) psi$?
logic first-order-logic substitution
asked Nov 18 at 4:42
numericalorange
1,619311
Here is a definition for substitutability found in a PDF of logic notes by Eric Pacuit:
I am more concerned with the part of the definition squared in red. My question is: Given $(forall y) psi$, does this mean that, since $y$ does not occur free in $(forall y) psi$, is $tau$ substitutable for $y$ in $(forall y) psi$?
logic first-order-logic substitution
logic first-order-logic substitution
asked Nov 18 at 4:42
numericalorange
1,619311
asked Nov 18 at 4:42
numericalorange
1,619311
asked Nov 18 at 4:42
numericalorange
1,619311
asked Nov 18 at 4:42
numericalorange
1,619311
asked Nov 18 at 4:42
numericalorange
1,619311
1,619311
1
Yes, because the term substitutable means that performing the operation we "cause no troubles". In that case, the operation is allowed simply because it does not change the original formula.
– Mauro ALLEGRANZA
Nov 18 at 12:49
@MauroALLEGRANZA I found another definition for substitutability from the textbook by Arindama Singh: $y$ is free for $x$ in $phi$ iff $x$ does not occur free within the scope of any $forall y$ or $exists y$. Is the negation: $y$ is not free for $x$ in $phi$ iff $x$ occurs free within the scope of any $forall y$ or $exists y$?
– numericalorange
Nov 19 at 4:53
add a comment |
1
Yes, because the term substitutable means that performing the operation we "cause no troubles". In that case, the operation is allowed simply because it does not change the original formula.
– Mauro ALLEGRANZA
Nov 18 at 12:49
@MauroALLEGRANZA I found another definition for substitutability from the textbook by Arindama Singh: $y$ is free for $x$ in $phi$ iff $x$ does not occur free within the scope of any $forall y$ or $exists y$. Is the negation: $y$ is not free for $x$ in $phi$ iff $x$ occurs free within the scope of any $forall y$ or $exists y$?
– numericalorange
Nov 19 at 4:53
1
1
Yes, because the term substitutable means that performing the operation we "cause no troubles". In that case, the operation is allowed simply because it does not change the original formula.
– Mauro ALLEGRANZA
Nov 18 at 12:49
Yes, because the term substitutable means that performing the operation we "cause no troubles". In that case, the operation is allowed simply because it does not change the original formula.
– Mauro ALLEGRANZA
Nov 18 at 12:49
@MauroALLEGRANZA I found another definition for substitutability from the textbook by Arindama Singh: $y$ is free for $x$ in $phi$ iff $x$ does not occur free within the scope of any $forall y$ or $exists y$. Is the negation: $y$ is not free for $x$ in $phi$ iff $x$ occurs free within the scope of any $forall y$ or $exists y$?
– numericalorange
Nov 19 at 4:53
@MauroALLEGRANZA I found another definition for substitutability from the textbook by Arindama Singh: $y$ is free for $x$ in $phi$ iff $x$ does not occur free within the scope of any $forall y$ or $exists y$. Is the negation: $y$ is not free for $x$ in $phi$ iff $x$ occurs free within the scope of any $forall y$ or $exists y$?
– numericalorange
Nov 19 at 4:53
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
By definition, the answer is yes, $tau$ is substitutable for $y$ in $(forall y)phi$. This happens because there is nothing that to substitute and, therefore, you not change the original formula.
answered Nov 18 at 5:38
Gödel
1,351319
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
By definition, the answer is yes, $tau$ is substitutable for $y$ in $(forall y)phi$. This happens because there is nothing that to substitute and, therefore, you not change the original formula.
answered Nov 18 at 5:38
Gödel
1,351319
add a comment |
up vote
1
down vote
accepted
By definition, the answer is yes, $tau$ is substitutable for $y$ in $(forall y)phi$. This happens because there is nothing that to substitute and, therefore, you not change the original formula.
answered Nov 18 at 5:38
Gödel
1,351319
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
By definition, the answer is yes, $tau$ is substitutable for $y$ in $(forall y)phi$. This happens because there is nothing that to substitute and, therefore, you not change the original formula.
answered Nov 18 at 5:38
Gödel
1,351319
By definition, the answer is yes, $tau$ is substitutable for $y$ in $(forall y)phi$. This happens because there is nothing that to substitute and, therefore, you not change the original formula.
answered Nov 18 at 5:38
Gödel
1,351319
answered Nov 18 at 5:38
Gödel
1,351319
answered Nov 18 at 5:38
Gödel
1,351319
answered Nov 18 at 5:38
Gödel
1,351319
1,351319
add a comment |
add a comment |
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%2f3003141%2fsubstitutability-in-first-order-logic%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
1
Yes, because the term substitutable means that performing the operation we "cause no troubles". In that case, the operation is allowed simply because it does not change the original formula.
– Mauro ALLEGRANZA
Nov 18 at 12:49
@MauroALLEGRANZA I found another definition for substitutability from the textbook by Arindama Singh: $y$ is free for $x$ in $phi$ iff $x$ does not occur free within the scope of any $forall y$ or $exists y$. Is the negation: $y$ is not free for $x$ in $phi$ iff $x$ occurs free within the scope of any $forall y$ or $exists y$?
– numericalorange
Nov 19 at 4:53