Results 1 to 8 of 8

Math Help - Convex subgroups

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    8

    Convex subgroups

    Hi!

    This is my first post in this forum, i have scimmed the rules and tried to find the correct place to this post, my problem is that i'm not studying math in english so i'm not quite sure if this question should be in another forum.

    I wanna show that if i have C_1,...,C_m convex subgroups of R^2 where the unity of every group of three is nonempty the unity of them all is nonempty, preferebly the proof should be by induction.

    I hope some of you are willing to help!

    Best Regards,

    p.s. I cannot get that fancy math thing to work, how do i do that?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,992
    Thanks
    1129
    Quote Originally Posted by Flemming View Post
    Hi!

    This is my first post in this forum, i have scimmed the rules and tried to find the correct place to this post, my problem is that i'm not studying math in english so i'm not quite sure if this question should be in another forum.

    I wanna show that if i have C_1,...,C_m convex subgroups of R^2 where the unity of every group of three is nonempty the unity of them all is nonempty, preferebly the proof should be by induction.

    I hope some of you are willing to help!

    Best Regards,

    p.s. I cannot get that fancy math thing to work, how do i do that?
    The "fancy math thing" is LaTex. On this forum surround the LaTex code with [ math ] and [ /math ] (without the spaces). To learn the code itself, look at http://www.mathhelpforum.com/math-help/latex-help/

    You want the word "intersection" of sets, not "unity" (and NOT "union" which was my first guess). Other than that, your English is excellent.

    That "union of any three is non-empty" is interesting. There are any number of examples of bad induction where the error is that you cannot go from n= 1 to n= 2 although it is easy to go from n to n+ 1 for n> 1.

    And, of course, the whole bit about "convex subsets" is irrelevant. What is important is that if the intersection of any three sets in a collection of sets is non empty then the intersection of all of them is non-empty.

    Let A_n be a collection of n sets such that the intersection of any three of them is non-empty. Then n must be at least 3 for that to make sense.

    Base case: n= 3. Since A_3 only contains 3 sets if "the intersection of any 3 is non-empty" then certainly the intersection of all 3 is non-empty.

    Now suppose this is true for n= k. We will show it is true for n= k+1.

    Suppose A_{k+1} is a collection of k+1 sets having the property that the intersection of any 3 of the sets is non-empty.

    Let U be any one of the sets and Let A_k be A_{k+1} with U removed. Then A_k still has the property that the intersection of any three of its sets is non-empty and since we are assuming that the theorem is true for n= k, it is true that the intersection of all sets in A_k is non-empty. Let X be that intersection.

    Let V be any set other than U and let B_k be A_{k+1} with V removed. By the same argument, the intersection of all the remaining sets is non-empty. Let Y be that intersection.

    Now V is a member of A_k and U is a member of B_k. And, since k is at least three, there exist a third set, W, which is in both A_k and B_k (this is the crucial point and why we need that "intersection of any three sets is non-empty) . All of the points in X are in both V and W and all of the points in Y are in both U and W. That means that W contains points of the intersection of X and Y is in W and so that interersection is non-empty. From that, it follows that the intersection of all sets in A_{k+1} is non-empty.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2010
    Posts
    8
    Wow that is a thorough and helpful reply, thank you very much!

    I am wondering about the very last part of the proof;
    All of the points in X are in both V and W and all of the points in Y are in both U and W. That means that W contains points of the intersection of X and Y is in W and so that interersection is non-empty. From that, it follows that the intersection of all sets in is non-empty.
    We have that X and Y (the nonempty intersections of collections of k sets) is in W (i guess since the intersection of sets has to be a subset of them all, and W is in both) and therefore argument that the intersection of X and Y is nonempty. I am not quite sure how to express my question but; I imagine X and Y could be subsets of W with no intersection (like X \subset W^{+} and Y \subset W^{-}). What am I misunderstanding?

    I hope you are willing to clarify even further.

    Best regards,
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jun 2010
    Posts
    8
    I have to bump this thread, because i really don't understand. Even though all X are in W and all Y are in W, I can't see why there have to be an overlap between. Please help by clarifying the last point of the proof.
    It would really be greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jun 2010
    Posts
    8
    Some merciful soul please clarify that little detail about why the intersection of X and Y will be nonempty just because they are both in W, it would be a tremendous help. I have been struggling with this for literally hours and asking several of my fellow students!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by HallsofIvy View Post
    The "fancy math thing" is LaTex. On this forum surround the LaTex code with [ math ] and [ /math ] (without the spaces). To learn the code itself, look at http://www.mathhelpforum.com/math-help/latex-help/

    You want the word "intersection" of sets, not "unity" (and NOT "union" which was my first guess). Other than that, your English is excellent.

    That "union of any three is non-empty" is interesting. There are any number of examples of bad induction where the error is that you cannot go from n= 1 to n= 2 although it is easy to go from n to n+ 1 for n> 1.

    And, of course, the whole bit about "convex subsets" is irrelevant. What is important is that if the intersection of any three sets in a collection of sets is non empty then the intersection of all of them is non-empty.

    Let A_n be a collection of n sets such that the intersection of any three of them is non-empty. Then n must be at least 3 for that to make sense.

    Base case: n= 3. Since A_3 only contains 3 sets if "the intersection of any 3 is non-empty" then certainly the intersection of all 3 is non-empty.

    Now suppose this is true for n= k. We will show it is true for n= k+1.

    Suppose A_{k+1} is a collection of k+1 sets having the property that the intersection of any 3 of the sets is non-empty.

    Let U be any one of the sets and Let A_k be A_{k+1} with U removed. Then A_k still has the property that the intersection of any three of its sets is non-empty and since we are assuming that the theorem is true for n= k, it is true that the intersection of all sets in A_k is non-empty. Let X be that intersection.

    Let V be any set other than U and let B_k be A_{k+1} with V removed. By the same argument, the intersection of all the remaining sets is non-empty. Let Y be that intersection.

    Now V is a member of A_k and U is a member of B_k. And, since k is at least three, there exist a third set, W, which is in both A_k and B_k (this is the crucial point and why we need that "intersection of any three sets is non-empty) . All of the points in X are in both V and W and all of the points in Y are in both U and W. That means that W contains points of the intersection of X and Y is in W and so that interersection is non-empty. From that, it follows that the intersection of all sets in A_{k+1} is non-empty.
    This does not hold. For instance, taking a, b, c, d to be arbitrary elements of \mathbb{R}^2, then,

    \alpha:=\{a, b, c\}

    \beta:=\{b, c, d\}

    \gamma:=\{c, d, a\}

    \delta:=\{d, a, b\}.

    The intersection of three subsets is non-trivial, while the intersection of all four is empty.

    Convexity is needed.

    Now, Flemming, are you familiar with Radon's theorem? (In \mathbb{R}^2) it basically says that if you have a set containing more that 3 points then you can split the set into two (disjoint) sets whose convex hulls intersect.

    So, let us proceed with induction. The base case is obvious, so let us look at the induction step.

    Assume the result holds for any k of your sets, that \cap _i^{k}C_i \neq \emptyset. Then, let x_i \in \displaystyle\bigcap_{i=1, i\neq j}^{k+1}C_i. That is, let x_i be in every set, except maybe C_i.

    Let S be the set of all these elements, S=\{x_1, x_2, \ldots, x_{k+1}\}.

    We now apply Radon's theorem to this set. That is, there exists two sets S_1 and S_2 such that S_1 \cap S_2 = \emptyset and S_1 \cup S_2 = S but their convex hulls intersect non-trivially, \overline{S_1} \cap \overline{S_2} \neq \emptyset. Pick some element from this intersection, a \in \overline{S_1} \cap \overline{S_2}. We wish to prove that this element is in \displaystyle\bigcap_{i=1}^{k+1}C_i, a \in \displaystyle\bigcap_{i=1}^{k+1}C_i.

    So, if x_i \in S_1 then S_2 \subset C_i (why?). As C_i is convex, \overline{S_2} \subset C_i. Thus, a \in C_i. Similarly, if x_i \in S_2 then a \in X_i.

    That is hopefully enough machinery for you to finish it all off with!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jun 2010
    Posts
    8
    Wonderful, thank you! I really couldn't make that other proof make sense.
    Now i wonder whether it is possible to expand the proof to \mathbb R^{n}, as i see it an important part of the proof is that there is more points than 3 in both S_{1} and S_{2} , so if there had to be more than n+2 points in each we would either have to have double as many sets as the dimension of R or we would have to demand more than one point in some of the nonempty intersections.
    Is that generalization possible? I hope i am not abusing the forum's helpfulness, i am just very curious by nature.

    Best regards.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Flemming View Post
    Wonderful, thank you! I really couldn't make that other proof make sense.
    Now i wonder whether it is possible to expand the proof to \mathbb R^{n}, as i see it an important part of the proof is that there is more points than 3 in both S_{1} and S_{2} , so if there had to be more than n+2 points in each we would either have to have double as many sets as the dimension of R or we would have to demand more than one point in some of the nonempty intersections.
    Is that generalization possible? I hope i am not abusing the forum's helpfulness, i am just very curious by nature.

    Best regards.
    I think it would, as Radon's theorem holds in \mathbb{R}^n if you have a set with at least n+2 points, and that is the only part which uses \mathbb{R}^2 in the proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Subgroups and Intersection of Normal Subgroups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: December 1st 2010, 08:12 PM
  2. The union of two convex sets is not convex
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 30th 2010, 03:23 PM
  3. Proving that max{0,f(x)} is convex if f is convex
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: November 5th 2009, 06:16 AM
  4. Proving that f^2 is convex if f is convex and f>=0
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: November 3rd 2009, 09:51 AM
  5. Proving that f^2 is convex if f is convex and f>=0
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 1st 2009, 03:06 PM

Search Tags


/mathhelpforum @mathhelpforum