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.










share|cite|improve this question


























    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.










    share|cite|improve this question
























      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.










      share|cite|improve this question













      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






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Oct 28 at 17:44









      Pinocchio

      1,85821753




      1,85821753



























          active

          oldest

          votes











          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "69"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          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






























          active

          oldest

          votes













          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes
















          draft saved

          draft discarded




















































          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.




          draft saved


          draft discarded














          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





















































          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







          Popular posts from this blog

          QoS: MAC-Priority for clients behind a repeater

          Ивакино (Тотемский район)

          Can't locate Autom4te/ChannelDefs.pm in @INC (when it definitely is there)