1. ## 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?

2. Originally Posted by Flemming
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 $\displaystyle 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 $\displaystyle 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 $\displaystyle 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 $\displaystyle A_k$ be $\displaystyle A_{k+1}$ with U removed. Then $\displaystyle 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 $\displaystyle A_k$ is non-empty. Let X be that intersection.

Let V be any set other than U and let $\displaystyle B_k$ be $\displaystyle 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 $\displaystyle A_k$ and U is a member of $\displaystyle B_k$. And, since k is at least three, there exist a third set, W, which is in both $\displaystyle A_k$ and $\displaystyle 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 $\displaystyle A_{k+1}$ is non-empty.

3. 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 $\displaystyle X \subset W^{+}$ and $\displaystyle Y \subset W^{-}$). What am I misunderstanding?

I hope you are willing to clarify even further.

Best regards,

4. 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!

5. 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!

6. Originally Posted by HallsofIvy
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 $\displaystyle 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 $\displaystyle 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 $\displaystyle 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 $\displaystyle A_k$ be $\displaystyle A_{k+1}$ with U removed. Then $\displaystyle 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 $\displaystyle A_k$ is non-empty. Let X be that intersection.

Let V be any set other than U and let $\displaystyle B_k$ be $\displaystyle 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 $\displaystyle A_k$ and U is a member of $\displaystyle B_k$. And, since k is at least three, there exist a third set, W, which is in both $\displaystyle A_k$ and $\displaystyle 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 $\displaystyle A_{k+1}$ is non-empty.
This does not hold. For instance, taking $\displaystyle a, b, c, d$ to be arbitrary elements of $\displaystyle \mathbb{R}^2$, then,

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

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

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

$\displaystyle \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 $\displaystyle \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 $\displaystyle k$ of your sets, that $\displaystyle \cap _i^{k}C_i \neq \emptyset$. Then, let $\displaystyle x_i \in \displaystyle\bigcap_{i=1, i\neq j}^{k+1}C_i$. That is, let $\displaystyle x_i$ be in every set, except maybe $\displaystyle C_i$.

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

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

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

That is hopefully enough machinery for you to finish it all off with!

7. 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 $\displaystyle \mathbb R^{n}$, as i see it an important part of the proof is that there is more points than 3 in both $\displaystyle S_{1}$ and $\displaystyle 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.

8. Originally Posted by Flemming
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 $\displaystyle \mathbb R^{n}$, as i see it an important part of the proof is that there is more points than 3 in both $\displaystyle S_{1}$ and $\displaystyle 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 $\displaystyle \mathbb{R}^n$ if you have a set with at least $\displaystyle n+2$ points, and that is the only part which uses $\displaystyle \mathbb{R}^2$ in the proof.