Loading ...
Sorry, an error occurred while loading the content.
 

Alternate proofs in Tutorial 1?

Expand Messages
  • allan.drummond@trilogy.com
    In Tutorial 1 (dynkin systems), Ex. 7, we show in step 1 that, given D is a pi-system and a dynkin system, if A,B in D, then A U B in D. My proof of this
    Message 1 of 5 , Sep 2, 2001
      In Tutorial 1 (dynkin systems), Ex. 7, we show in step 1 that, given
      D is a pi-system and a dynkin system, if A,B in D, then A U B in D.
      My proof of this differs from yours, and I'm not certain it's
      correct. I proceeded as follows (don't know how to really do this in
      ASCII, but below, T means intersection):

      (A T B) in D, because D is a pi-system
      B = B U (A T B) in D
      B U (A T B) = (B U A) T (B U B) = (A U B) T B in D
      thus (A U B) in D, because B in D and D is a pi-system.

      This seems a lot simpler than the given solution, but I'm
      inexperienced in set theory so don't know if I'm doing something
      silly.

      For step 2, I proceeded inductively. My suspicion is that you can't,
      but I can't explain why - again, as a relative newbie, I'm wondering
      if I'm falling into some hidden trap. Here's the reasoning:

      union{n=1->k-1}Bn = union{n=1->k-1}An (induction hypothesis)
      union{n=1->k}Bn = Bk U (union{n=1->k-1}Bn)
      = Bk U (union{n=1->k-1}An)
      = union{n=1->k}An U (union{n=1->k-1}An)
      = (Ak U union{n=1->k-1}An) U (union{n=1->k-1}An)

      But by the associative law, this is just Ak U union{n=1->k-1}An =
      union{n=1->k}An. So now all that's left is to establish the base
      condition, which is just

      union{n=1->1}Bn = union{n=1->1}An

      or A1 = A1, which is certainly true. Thus, by induction it's shown
      that union{n=1->inf}Bn = union{n=1->inf}An. Is this legal?

      Thanks,
      Allan
    • vaillant@probability.net
      Hi Allan, ... in ... Yes ... True ... All this is true, since all these sets are equal to B which is in D ... D being a pi-system tells you that if A and B
      Message 2 of 5 , Sep 3, 2001
        Hi Allan,

        > My proof of this differs from yours, and I'm not certain it's
        > correct. I proceeded as follows (don't know how to really do this
        in
        > ASCII, but below, T means intersection):
        >
        > (A T B) in D, because D is a pi-system

        Yes

        > B = B U (A T B) in D

        True

        > B U (A T B) = (B U A) T (B U B) = (A U B) T B in D


        All this is true, since all these sets are equal to B which is in D

        > thus (A U B) in D, because B in D and D is a pi-system.

        D being a pi-system tells you that if A' and B' are in D, then A'TB'
        is also in D. It does not tell you that if A'TB' is in D and B' is in
        D, then A' is in D... Hence I do not agree with your last line.

        >
        > if I'm falling into some hidden trap. Here's the reasoning:
        >
        > union{n=1->k-1}Bn = union{n=1->k-1}An (induction hypothesis)
        > union{n=1->k}Bn = Bk U (union{n=1->k-1}Bn)
        > = Bk U (union{n=1->k-1}An)
        > = union{n=1->k}An U (union{n=1->k-1}An)
        > = (Ak U union{n=1->k-1}An) U (union{n=1->k-1}An)
        >
        > But by the associative law, this is just Ak U union{n=1->k-1}An =
        > union{n=1->k}An. So now all that's left is to establish the base
        > condition, which is just
        >
        > union{n=1->1}Bn = union{n=1->1}An
        >
        > or A1 = A1, which is certainly true. Thus, by induction it's shown
        > that union{n=1->inf}Bn = union{n=1->inf}An. Is this legal?

        This is a correct induction proof which establishes the equality
        between the finite union \/_1^nAk and \/_1^n Bk. You need one little
        more step to argue that we have equality between the countable unions
        \/Ak and \/Bk

        Regards. Noel.
      • allan.drummond@trilogy.com
        ... Ah - gotcha. Kind of smuggled in my own conclusion, didn t I. ;) Thanks. ... What is that step? I follow your proof, I m just trying to make the leap
        Message 3 of 5 , Sep 3, 2001
          > D being a pi-system tells you that if A' and B' are in D,
          > then A'TB' is also in D. It does not tell you that if A'TB'
          > is in D and B' is in D, then A' is in D... Hence I do not
          > agree with your last line.

          Ah - gotcha. Kind of smuggled in my own conclusion, didn't I. ;)
          Thanks.

          > ...
          > This is a correct induction proof which establishes the equality
          > between the finite union \/k_1^n Ak and \/k_1^n Bk. You need one
          > little more step to argue that we have equality between the
          > countable unions \/Ak and \/Bk.

          What is that step? I follow your proof, I'm just trying to make the
          leap from the inductive-style proofs I'm used to over to the sort you
          use. If the "little more step" is to then do what you've already
          done in the solution, then I suppose my induction was a waste of time.

          Can I simply take a limit? If I've established the result

          (\/k_1^n Ak) \ (\/k_1^n Bk) = 0

          by induction, then can I argue for:

          lim(n->infinity) [(\/k_1^n Ak) \ (\/k_1^n Bk)] = 0?

          This seems to work, since it just becomes lim(n->infinity) [0] which
          is clearly = 0.

          Cheers,
          Allan
        • allan.drummond@trilogy.com
          Er, on self-correction...I guess ( /k_1^n Ak) ( /k_1^n Bk) = 0 only covers ( /k_1^n Bk) = ( /k_1^n Ak) so at least two limits are required, the other being
          Message 4 of 5 , Sep 3, 2001
            Er, on self-correction...I guess (\/k_1^n Ak) \ (\/k_1^n Bk) = 0 only
            covers

            (\/k_1^n Bk) >= (\/k_1^n Ak)

            so at least two limits are required, the other being

            lim (n->inf) [(\/k_1^n Bk) \ (\/k_1^n Ak)] = 0

            to cover (\/k_1^n Bk) <= (\/k_1^n Ak).

            Showing that those two differences both = 0 (the empty set, not zero)
            in the limit n->infinity seems to me to establish the equality of the
            two countable unions...am I wrong? Again, I'm not certain that
            taking such a limit is in fact valid; I'm just working off of the
            intuitive equality of

            (empty set) = lim (n->inf) (empty set)


            > Can I simply take a limit? If I've established the result
            >
            > (\/k_1^n Ak) \ (\/k_1^n Bk) = 0
            >
            > by induction, then can I argue for:
            >
            > lim(n->infinity) [(\/k_1^n Ak) \ (\/k_1^n Bk)] = 0?
            >
            > This seems to work, since it just becomes lim(n->infinity) [0]
            which
            > is clearly = 0.
            >
            > Cheers,
            > Allan
          • vaillant@probability.net
            ... Let x in /Ak. There exists k such that x in Ak. In particular, x in /_1^kAj= /_1^kBj. So x lies in Bj for some j. Hence x lies in /Bk. This shows the
            Message 5 of 5 , Sep 4, 2001
              > > You need one
              > > little more step to argue that we have equality between the
              > > countable unions \/Ak and \/Bk.
              >
              > What is that step?

              Let x in \/Ak. There exists k such that x in Ak. In particular, x in
              \/_1^kAj=\/_1^kBj. So x lies in Bj for some j. Hence x lies in \/Bk.
              This shows the inclusion \/Ak < \/Bk . The reverse inclusion is
              handled likewise.


              > Can I simply take a limit?


              The notion of limits for sets is not a very useful one. It is common
              to handle 'liminf' and 'limsup' for sets, and even limits (when the
              sequence is monotone with respect to imclusion, in which case a lim
              is just a union or an intersection). In general any arguement
              involvng limits of set is bound to be wrong and/or cumbersome and
              unnecessary. Unions and intersections are best handled directly using
              their simple definition:

              x in /\Ai <=> x in Ai for all i
              x in \/Ai <=> x in Ai for some i

              Regards. Noel.
            Your message has been successfully submitted and would be delivered to recipients shortly.