Help with a proof that should be easy

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Help with a proof that should be easy

Postby quintopia » Mon May 18, 2009 3:40 pm UTC

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?
Last edited by quintopia on Mon May 18, 2009 5:20 pm UTC, edited 1 time in total.

Lul Thyme
Posts: 68
Joined: Sun Apr 13, 2008 1:43 pm UTC

Re: Help with a proof that should be easy

Postby Lul Thyme » Mon May 18, 2009 4:45 pm UTC

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.

User avatar
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

Postby jestingrabbit » Mon May 18, 2009 5:16 pm UTC

This strikes me as false. Consider R4. 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.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Help with a proof that should be easy

Postby quintopia » Mon May 18, 2009 5:19 pm UTC

You're right. I mistated the problem. I do mean Rn, 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.

User avatar
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

Postby jestingrabbit » Mon May 18, 2009 5:31 pm UTC

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 Rn 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.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Help with a proof that should be easy

Postby quintopia » Mon May 18, 2009 6:06 pm UTC

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.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Help with a proof that should be easy

Postby quintopia » Mon May 18, 2009 7:14 pm UTC

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?

Lul Thyme
Posts: 68
Joined: Sun Apr 13, 2008 1:43 pm UTC

Re: Help with a proof that should be easy

Postby Lul Thyme » Mon May 18, 2009 7:57 pm UTC

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

Lul Thyme
Posts: 68
Joined: Sun Apr 13, 2008 1:43 pm UTC

Re: Help with a proof that should be easy

Postby Lul Thyme » Mon May 18, 2009 8:19 pm UTC

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.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Help with a proof that should be easy

Postby quintopia » Mon May 18, 2009 8:56 pm UTC

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.)

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Help with a proof that should be easy

Postby quintopia » Tue May 19, 2009 12:00 am UTC

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]

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Help with a proof that should be easy

Postby Nitrodon » Tue May 19, 2009 12:11 am UTC

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

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Help with a proof that should be easy

Postby quintopia » Tue May 19, 2009 12:53 am UTC

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?

hnooch
Posts: 128
Joined: Mon Nov 26, 2007 6:55 pm UTC

Re: Help with a proof that should be easy

Postby hnooch » Tue May 19, 2009 6:01 am UTC

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 v0) 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 v0.

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 v0.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 17 guests