Why do finite restrictions of members of back and forth system are also back and forth systems and not just...
up vote
0
down vote
favorite
I was trying to show the following (from these notes pg 65):
Define a finite restriction of a bijection γ : X → Y to be a map γ|E : E → γ(E)
with finite E ⊆ X. If Γ is a back-and-forth system from A to B, so is the set of
finite restrictions of members of Γ.
However, as I was going through the proof I realized that I didn't actually need finiteness and restriction of subset was enough. I assume that must be wrong otherwise such a specific exercise/theorem wouldn't be asked to be done. Why is finiteness required?
I will try to sketch my proof.
Consider a back and forth system from $mathcal A to mathcal B$. Recall the forth direction:
$$ forall gamma in Gamma, forall a in A, exists gamma': gamma subseteq_{Ex} gamma' land a in D_{gamma'}$$
where $D_{gamma'} = Domain(gamma')$ and $gamma subseteq_{Ex} gamma'$ means $gamma'$ extends $gamma$ (so it respects the original L-structure and potentially introduces new structure with the same symbols in the language L) and $gamma,gamma'$ are partial isomorphism. I define extension formally as follows:
First $D_{gamma} subseteq D_{gamma'}$. For all relation symbols $R in L^R$, (for simplicity say its of arity 2) we have $a_1, a_2 in D_{gamma} cup D_{gamma'} setminus D_{gamma} $:
$$ R(a_1,a_2) in R^{mathcal A} iff R(gamma' a_1, gamma' a_2 ) in R^{mathcal B}$$
We can worry about function symbols later.
Now if we have what the question wants then we consider $E subseteq D_{gamma'}$. Now to check if it extends $E$ we consider $a_1, a_2 in E cup D_{gamma'} setminus E $. If both $a_1,a_2$ are in $E$ then they are in the original isomorphism $D_{gamma}$ so they satisfy the structure. If one is not in E (but is in $D_{gamma'}$ and the other is in $E$ then it must satisfy the relation structure because $gamma'$ extends the original $gamma$ and so the element is in $D_{gamma}$. If both are not in $E$ it must work because $gamma'$ introduces its own new relations that satisfy what we need. Therefore, do I never need to invoke finiteness for the extension to work. Furthermore, every subset $E subseteq D_{gamma}$ can use as the "forth element" that satisfies $a in D_{gamma'}$ by using the $a$ that worked for the original isomorphism $gamma$. The argument is the symmetrical for the back direction. So I don't understand why we need to use finiteness.
Do we really or does my argument have flaw somewhere? In fact, it feels my argument is better because funciton and relation symbols have some maximum arity, so we'd need to restrict to that cardinality at least or things won't work while mine does not. Though, I assume I must be missing something or my definition notation or way of thinking about extensions must be flawed.
proof-verification logic first-order-logic model-theory
add a comment |
up vote
0
down vote
favorite
I was trying to show the following (from these notes pg 65):
Define a finite restriction of a bijection γ : X → Y to be a map γ|E : E → γ(E)
with finite E ⊆ X. If Γ is a back-and-forth system from A to B, so is the set of
finite restrictions of members of Γ.
However, as I was going through the proof I realized that I didn't actually need finiteness and restriction of subset was enough. I assume that must be wrong otherwise such a specific exercise/theorem wouldn't be asked to be done. Why is finiteness required?
I will try to sketch my proof.
Consider a back and forth system from $mathcal A to mathcal B$. Recall the forth direction:
$$ forall gamma in Gamma, forall a in A, exists gamma': gamma subseteq_{Ex} gamma' land a in D_{gamma'}$$
where $D_{gamma'} = Domain(gamma')$ and $gamma subseteq_{Ex} gamma'$ means $gamma'$ extends $gamma$ (so it respects the original L-structure and potentially introduces new structure with the same symbols in the language L) and $gamma,gamma'$ are partial isomorphism. I define extension formally as follows:
First $D_{gamma} subseteq D_{gamma'}$. For all relation symbols $R in L^R$, (for simplicity say its of arity 2) we have $a_1, a_2 in D_{gamma} cup D_{gamma'} setminus D_{gamma} $:
$$ R(a_1,a_2) in R^{mathcal A} iff R(gamma' a_1, gamma' a_2 ) in R^{mathcal B}$$
We can worry about function symbols later.
Now if we have what the question wants then we consider $E subseteq D_{gamma'}$. Now to check if it extends $E$ we consider $a_1, a_2 in E cup D_{gamma'} setminus E $. If both $a_1,a_2$ are in $E$ then they are in the original isomorphism $D_{gamma}$ so they satisfy the structure. If one is not in E (but is in $D_{gamma'}$ and the other is in $E$ then it must satisfy the relation structure because $gamma'$ extends the original $gamma$ and so the element is in $D_{gamma}$. If both are not in $E$ it must work because $gamma'$ introduces its own new relations that satisfy what we need. Therefore, do I never need to invoke finiteness for the extension to work. Furthermore, every subset $E subseteq D_{gamma}$ can use as the "forth element" that satisfies $a in D_{gamma'}$ by using the $a$ that worked for the original isomorphism $gamma$. The argument is the symmetrical for the back direction. So I don't understand why we need to use finiteness.
Do we really or does my argument have flaw somewhere? In fact, it feels my argument is better because funciton and relation symbols have some maximum arity, so we'd need to restrict to that cardinality at least or things won't work while mine does not. Though, I assume I must be missing something or my definition notation or way of thinking about extensions must be flawed.
proof-verification logic first-order-logic model-theory
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I was trying to show the following (from these notes pg 65):
Define a finite restriction of a bijection γ : X → Y to be a map γ|E : E → γ(E)
with finite E ⊆ X. If Γ is a back-and-forth system from A to B, so is the set of
finite restrictions of members of Γ.
However, as I was going through the proof I realized that I didn't actually need finiteness and restriction of subset was enough. I assume that must be wrong otherwise such a specific exercise/theorem wouldn't be asked to be done. Why is finiteness required?
I will try to sketch my proof.
Consider a back and forth system from $mathcal A to mathcal B$. Recall the forth direction:
$$ forall gamma in Gamma, forall a in A, exists gamma': gamma subseteq_{Ex} gamma' land a in D_{gamma'}$$
where $D_{gamma'} = Domain(gamma')$ and $gamma subseteq_{Ex} gamma'$ means $gamma'$ extends $gamma$ (so it respects the original L-structure and potentially introduces new structure with the same symbols in the language L) and $gamma,gamma'$ are partial isomorphism. I define extension formally as follows:
First $D_{gamma} subseteq D_{gamma'}$. For all relation symbols $R in L^R$, (for simplicity say its of arity 2) we have $a_1, a_2 in D_{gamma} cup D_{gamma'} setminus D_{gamma} $:
$$ R(a_1,a_2) in R^{mathcal A} iff R(gamma' a_1, gamma' a_2 ) in R^{mathcal B}$$
We can worry about function symbols later.
Now if we have what the question wants then we consider $E subseteq D_{gamma'}$. Now to check if it extends $E$ we consider $a_1, a_2 in E cup D_{gamma'} setminus E $. If both $a_1,a_2$ are in $E$ then they are in the original isomorphism $D_{gamma}$ so they satisfy the structure. If one is not in E (but is in $D_{gamma'}$ and the other is in $E$ then it must satisfy the relation structure because $gamma'$ extends the original $gamma$ and so the element is in $D_{gamma}$. If both are not in $E$ it must work because $gamma'$ introduces its own new relations that satisfy what we need. Therefore, do I never need to invoke finiteness for the extension to work. Furthermore, every subset $E subseteq D_{gamma}$ can use as the "forth element" that satisfies $a in D_{gamma'}$ by using the $a$ that worked for the original isomorphism $gamma$. The argument is the symmetrical for the back direction. So I don't understand why we need to use finiteness.
Do we really or does my argument have flaw somewhere? In fact, it feels my argument is better because funciton and relation symbols have some maximum arity, so we'd need to restrict to that cardinality at least or things won't work while mine does not. Though, I assume I must be missing something or my definition notation or way of thinking about extensions must be flawed.
proof-verification logic first-order-logic model-theory
I was trying to show the following (from these notes pg 65):
Define a finite restriction of a bijection γ : X → Y to be a map γ|E : E → γ(E)
with finite E ⊆ X. If Γ is a back-and-forth system from A to B, so is the set of
finite restrictions of members of Γ.
However, as I was going through the proof I realized that I didn't actually need finiteness and restriction of subset was enough. I assume that must be wrong otherwise such a specific exercise/theorem wouldn't be asked to be done. Why is finiteness required?
I will try to sketch my proof.
Consider a back and forth system from $mathcal A to mathcal B$. Recall the forth direction:
$$ forall gamma in Gamma, forall a in A, exists gamma': gamma subseteq_{Ex} gamma' land a in D_{gamma'}$$
where $D_{gamma'} = Domain(gamma')$ and $gamma subseteq_{Ex} gamma'$ means $gamma'$ extends $gamma$ (so it respects the original L-structure and potentially introduces new structure with the same symbols in the language L) and $gamma,gamma'$ are partial isomorphism. I define extension formally as follows:
First $D_{gamma} subseteq D_{gamma'}$. For all relation symbols $R in L^R$, (for simplicity say its of arity 2) we have $a_1, a_2 in D_{gamma} cup D_{gamma'} setminus D_{gamma} $:
$$ R(a_1,a_2) in R^{mathcal A} iff R(gamma' a_1, gamma' a_2 ) in R^{mathcal B}$$
We can worry about function symbols later.
Now if we have what the question wants then we consider $E subseteq D_{gamma'}$. Now to check if it extends $E$ we consider $a_1, a_2 in E cup D_{gamma'} setminus E $. If both $a_1,a_2$ are in $E$ then they are in the original isomorphism $D_{gamma}$ so they satisfy the structure. If one is not in E (but is in $D_{gamma'}$ and the other is in $E$ then it must satisfy the relation structure because $gamma'$ extends the original $gamma$ and so the element is in $D_{gamma}$. If both are not in $E$ it must work because $gamma'$ introduces its own new relations that satisfy what we need. Therefore, do I never need to invoke finiteness for the extension to work. Furthermore, every subset $E subseteq D_{gamma}$ can use as the "forth element" that satisfies $a in D_{gamma'}$ by using the $a$ that worked for the original isomorphism $gamma$. The argument is the symmetrical for the back direction. So I don't understand why we need to use finiteness.
Do we really or does my argument have flaw somewhere? In fact, it feels my argument is better because funciton and relation symbols have some maximum arity, so we'd need to restrict to that cardinality at least or things won't work while mine does not. Though, I assume I must be missing something or my definition notation or way of thinking about extensions must be flawed.
proof-verification logic first-order-logic model-theory
proof-verification logic first-order-logic model-theory
asked Oct 28 at 17:44
Pinocchio
1,85821753
1,85821753
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2974998%2fwhy-do-finite-restrictions-of-members-of-back-and-forth-system-are-also-back-and%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