## Help with a proof that should be easy

**Moderators:** gmalivuk, Moderators General, Prelates

### Help with a proof that should be easy

I'm not the best at algebra/geometry but I am convinced this theorem is true. Could someone give some feedback as to how to set up a proof like this?

All hyperplanes in this description go through the origin.

There are two hyperplanes A and B which divide space into four regions: [imath]G\cap H[/imath], [imath]G^C\cap H[/imath], [imath]G\cap H^C[/imath], and [imath]G^C\cap H^C[/imath]. There are two other half-spaces, X and Y, different from G and H, s.t. [imath]dim(A\cap B\cap X\cap Y)< n-2[/imath] (although their intersection is not empty). But, I know that [imath]G\cap H\cap X\cap Y \neq \phi[/imath], and I want to show that one of the following:

[math]X\cap Y\cap G^C\cap H[/math]

[math]X\cap Y\cap G\cap H^C[/math]

[math]X\cap Y\cap G^C\cap H^C[/math]

IS empty.

Does this seem as true to you as it does to me? And where should I start?

All hyperplanes in this description go through the origin.

There are two hyperplanes A and B which divide space into four regions: [imath]G\cap H[/imath], [imath]G^C\cap H[/imath], [imath]G\cap H^C[/imath], and [imath]G^C\cap H^C[/imath]. There are two other half-spaces, X and Y, different from G and H, s.t. [imath]dim(A\cap B\cap X\cap Y)< n-2[/imath] (although their intersection is not empty). But, I know that [imath]G\cap H\cap X\cap Y \neq \phi[/imath], and I want to show that one of the following:

[math]X\cap Y\cap G^C\cap H[/math]

[math]X\cap Y\cap G\cap H^C[/math]

[math]X\cap Y\cap G^C\cap H^C[/math]

IS empty.

Does this seem as true to you as it does to me? And where should I start?

Last edited by quintopia on Mon May 18, 2009 5:20 pm UTC, edited 1 time in total.

### Re: Help with a proof that should be easy

From your post, it's not really clear what the setting is for your problem.

I'm assuming you are thinking of a real vector space.

The following seems to be a counterexample in R^3 generated by x,y,z.

Let A be the hyperplane x=0 and G be the half-space x>0.

Let B be the hyperplane y=0 and H be the half space y>0.

Let X=Y both be the half space z>0.

The four quadruple intersections you describe are clearly non-empty.

I'm assuming you are thinking of a real vector space.

The following seems to be a counterexample in R^3 generated by x,y,z.

Let A be the hyperplane x=0 and G be the half-space x>0.

Let B be the hyperplane y=0 and H be the half space y>0.

Let X=Y both be the half space z>0.

The four quadruple intersections you describe are clearly non-empty.

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

### Re: Help with a proof that should be easy

This strikes me as false. Consider R

edit: basically what lul thyme said, but with a less edgy counterexample (ie X != Y seems like the next response given lul's counterexample, this counterexample kills that too).

^{4}. Let A be those points with the first coordinate 0, B be those points with the second coordinate 0, X be those points with the third coordinate positive and Y be those points with the fourth coordinate positive. All the relevant quadruples of half spaces have nontrivial intersection it seems to me.edit: basically what lul thyme said, but with a less edgy counterexample (ie X != Y seems like the next response given lul's counterexample, this counterexample kills that too).

Last edited by jestingrabbit on Mon May 18, 2009 5:20 pm UTC, edited 1 time in total.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

### Re: Help with a proof that should be easy

You're right. I mistated the problem. I do mean R

^{n}, but I didn't mean to say [imath]A\cap B \not\subset X\cap Y[/imath]. What I meant was that [imath]dim(A\cap B\cap X\cap Y)< n-2[/imath]. Fixed OP.- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

### Re: Help with a proof that should be easy

Given that you say [imath]dim(A\cap B\cap X\cap Y)=k<n-2[/imath], you seem to be implying that [imath]A\cap B\cap X\cap Y = V[/imath] is a subspace. If so, start with a basis of R

^{n}such that k of the vectors are in V, n-2 are in [imath]A\cap B[/imath], and of the remaining two elements, one is in A and not B, and the other is in B and not A. I think you should be able to work it out from there with a little jiggery pokery.ameretrifle wrote:Magic space feudalism is therefore a viable idea.

### Re: Help with a proof that should be easy

Just to make sure I'm not going crazy:

[imath]dim(A\cap B\cap X\cap Y)< n-2[/imath] is the same as one of [imath]A\cap B\cap X \not\subset Y[/imath] or [imath]A\cap B\cap Y \not\subset X[/imath], amirite?

Because. . .[imath]dim(A\cap B\cap X)[/imath] could be as high as n-2 and so if it were also a subset of Y, its dimension could remain as high as n-2, so asserting that it is smaller is asserting that it's not a subset of Y. But if [imath]dim(A\cap B\cap X)< n-2[/imath] then [imath]dim(A\cap B\cap Y)=n-2[/imath] since Y is not G,H, or X, so the other predicate holds.

Correct?

Oh, I think I need that the half-spaces are open subsets in there somewhere.

[imath]dim(A\cap B\cap X\cap Y)< n-2[/imath] is the same as one of [imath]A\cap B\cap X \not\subset Y[/imath] or [imath]A\cap B\cap Y \not\subset X[/imath], amirite?

Because. . .[imath]dim(A\cap B\cap X)[/imath] could be as high as n-2 and so if it were also a subset of Y, its dimension could remain as high as n-2, so asserting that it is smaller is asserting that it's not a subset of Y. But if [imath]dim(A\cap B\cap X)< n-2[/imath] then [imath]dim(A\cap B\cap Y)=n-2[/imath] since Y is not G,H, or X, so the other predicate holds.

Correct?

Oh, I think I need that the half-spaces are open subsets in there somewhere.

### Re: Help with a proof that should be easy

So let's do a change of basis so that we now have the sets:

G: first coordinate positive

H: second coordinate positive

A: first coordinate zero

B: second coordinate zero

Let S and T be the defining hyperplanes of X and Y resp. (why not?)

So, after the change of basis, I can considered my basis to be the elementary basis.

What I know in addition is that of the n-2 basis vectors with the first two elements zero, at least one has a negative dot product with either S or T.

I also know that both X and Y contain some of the same vectors with the first two coordinates positive.

I want to show from the above that either: No vector in X and Y has both first coordinates negative, or

No vector in X and Y has the first coordinate negative and the second positive, or

No vector in X and Y has the first coordinate positive and the second coordinate negative.

What is the next step in the jiggery pokery?

G: first coordinate positive

H: second coordinate positive

A: first coordinate zero

B: second coordinate zero

Let S and T be the defining hyperplanes of X and Y resp. (why not?)

So, after the change of basis, I can considered my basis to be the elementary basis.

What I know in addition is that of the n-2 basis vectors with the first two elements zero, at least one has a negative dot product with either S or T.

I also know that both X and Y contain some of the same vectors with the first two coordinates positive.

I want to show from the above that either: No vector in X and Y has both first coordinates negative, or

No vector in X and Y has the first coordinate negative and the second positive, or

No vector in X and Y has the first coordinate positive and the second coordinate negative.

What is the next step in the jiggery pokery?

### Re: Help with a proof that should be easy

nt

Last edited by Lul Thyme on Mon May 18, 2009 8:19 pm UTC, edited 1 time in total.

### Re: Help with a proof that should be easy

Your new question is more confusing than ever.

You should really make clear what you mean by a "half-space".

You say these are open sets?

In that case, for any reasonable definition I can think of (for example, one of the two "open sides" of an hyperplane through the origin), a subset of half-space will never be a subspace. For example if X is a half-space, and x is in X, then -x is not in X.

Hence, [imath]dim(A\cap B\cap X\cap Y)[/imath] is not well-defined.

Maybe you mean that X and Y are actually hyperplanes? (that would a lot more sense if you are trying to compute the dimension of the intersection with A and B). Or maybe you are extending the definition of "dimension" to include non-subspaces? I could see how that might make sense but I think you should make this clear if this is the case.

You should really make clear what you mean by a "half-space".

You say these are open sets?

In that case, for any reasonable definition I can think of (for example, one of the two "open sides" of an hyperplane through the origin), a subset of half-space will never be a subspace. For example if X is a half-space, and x is in X, then -x is not in X.

Hence, [imath]dim(A\cap B\cap X\cap Y)[/imath] is not well-defined.

Maybe you mean that X and Y are actually hyperplanes? (that would a lot more sense if you are trying to compute the dimension of the intersection with A and B). Or maybe you are extending the definition of "dimension" to include non-subspaces? I could see how that might make sense but I think you should make this clear if this is the case.

### Re: Help with a proof that should be easy

You're right, I'm not intending it to be a subspace. I'm using dimension to mean the dimension of the affine hull of the subset. So the intersection of two half-spaces is still n-dimensional, but the intersection of two half-spaces and the intersection of two hyperplanes may have dimension n-2 or less.

In three dimensions, this is more easily describable. A line through the origin either passes through the intersection of two half-spaces, or it doesn't (in which case it passes through the intersection of their complements only at the origin.)

In three dimensions, this is more easily describable. A line through the origin either passes through the intersection of two half-spaces, or it doesn't (in which case it passes through the intersection of their complements only at the origin.)

### Re: Help with a proof that should be easy

Okay, I'm sorry I was so confusing in the OP, but trying to phrase things so other people can understand them helps me understand them better myself. So here's a simpler statement of what I'm trying to do.

Given four open half-spaces in [imath]\mathbb{R}^n[/imath], G,H,X, and Y whose defining hyperplane's normals span a four-dimensional space, prove that at least one of the following must be empty:

[math]G\cap H\cap X\cap Y[/math]

[math]G\cap H^C\cap X\cap Y[/math]

[math]G^C\cap H\cap X\cap Y[/math]

[math]G^C\cap H^C\cap X\cap Y[/math]

[math]G\cap H\cap X\cap Y^C[/math]

[math]G\cap H^C\cap X\cap Y^C[/math]

[math]G^C\cap H\cap X\cap Y^C[/math]

[math]G^C\cap H^C\cap X\cap Y^C[/math]

Given four open half-spaces in [imath]\mathbb{R}^n[/imath], G,H,X, and Y whose defining hyperplane's normals span a four-dimensional space, prove that at least one of the following must be empty:

[math]G\cap H\cap X\cap Y[/math]

[math]G\cap H^C\cap X\cap Y[/math]

[math]G^C\cap H\cap X\cap Y[/math]

[math]G^C\cap H^C\cap X\cap Y[/math]

[math]G\cap H\cap X\cap Y^C[/math]

[math]G\cap H^C\cap X\cap Y^C[/math]

[math]G^C\cap H\cap X\cap Y^C[/math]

[math]G^C\cap H^C\cap X\cap Y^C[/math]

### Re: Help with a proof that should be easy

Your "simpler statement" is false. In fact, all of those sets will always be nonempty under the stated conditions.

### Re: Help with a proof that should be easy

Okay, I see why now. Indeed, the other eight regions will be nonempty as well, yes?

I suppose if I were looking at the set of all regions created by n orthogonal hyperplanes in a halfspace, one of those would be empty, yes?

I suppose if I were looking at the set of all regions created by n orthogonal hyperplanes in a halfspace, one of those would be empty, yes?

### Re: Help with a proof that should be easy

That last statement sounds right; change your basis so that the orthogonal hyperplanes have normals along the coordinate axes, and consider the vector normal (call it v

A vector points outside (or along the boundary of) the half-space iff it has non-positive dot product with v

Now note that one of the regions you blocked off only contains vectors where each coordinate has the opposite sign of the corresponding coordinate in v

_{0}) to the boundary of your half-space and pointing inside the half space.A vector points outside (or along the boundary of) the half-space iff it has non-positive dot product with v

_{0}.Now note that one of the regions you blocked off only contains vectors where each coordinate has the opposite sign of the corresponding coordinate in v

_{0}.### Who is online

Users browsing this forum: No registered users and 7 guests