Simplex

A linear surface is constructible through any n regions in Rⁿ. According to the proof in the last post, the only reason a linear surface is not constructible through n+1 regions is that the regions are vertex regions of a simplex. To me that reinforces the importance of simplexes. The proof I supplied for the "Simplex Theorem" in the first post was insufficiently precise. Here is a better proof, preceded by supportive definition, lemma, and theorem. Subspace and region were defined in the first post. Here I define subregion.

If Sⁿ is a subspace of Qⁿ, and R is a region of Sⁿ, then region P, in Qⁿ, is a subregion of R iff R(b)=P(b) for each boundary b in Sⁿ.

Intermediate Region Lemma

If Sⁿ is a subspace of linear space Qⁿ, R is a region in Sⁿ, b extends Qⁿ to a linear space, and b divides R, then b divides a subregion of R in Qⁿ.

Consider the section of Sⁿ by b, S^n-1. Let P be the region in S^n-1 isomorphic to R. By transitivity of isomorphism, the section of Qⁿ by b is isomorphic to an extension of S^n-1. Thus, the subregions of R are isomorphic to the subregions of P. Since at least R is a subregion of R, there is a subregion of P. Therefore, b divides a subregion of R.

Intermediate Region Theorem

If linear space Sⁿ extends to Qⁿ, region R in Sⁿ extends to regions {R₀, R₁, R₂, ...} in Qⁿ, R_a and R_b in {R₀, R₁, R₂, ...} are on opposite sides of both b₀ and b₁, Qⁿ extended by b₂ is linear, and b₂ divides R_a and R_b, then there exists R_c in {R₀, R₁, R₂, ...}, such that b₂ divides R_c, R_c is opposite one of b₀ or b₁ from R_a, and R_c is opposite the other of b₀ or b₁ from R_b.

Suppose b₀ divides R into R₁ and R₂, and b₁ divides R. By the lemma, b₁ divides R₁ or R₂. First suppose b₁ divides only one of R₁ or R₂. Suppose without loss of generality that b₁ divides R₁ into R₃ and R₄. Again without loss of generality, assume R_a is a subregion of R₂ and R_b is a subregion of R₄. Consider the section, S^n-1, of Sⁿ by b₂. Let P, P₂, P₄ in S^n-1 be isomorphic to R, R₂, R₄ in Sⁿ, respectively. Since P is divided by two boundaries, isomorphic to b₀ and b₁, it has at least three subregions, two of which are P₂ and P₄, and the third is isomorphic to R₃. Therefore, b₂ divides R₃. By the lemma, there is subregion R_c of R₃ divided by b₂, completing the proof for the case that b₁ divides only one of R₁ or R₂. Next assume b₁ divides R₁ into R₃ and R₄, and b₁ divides R₂ into R₅ and R₆. Assume without loss of generality R_a is a subregion of R₃ and R_b is a subregion of R₆. Consider the section, S^n-1, of Sⁿ by b₂. Let P, P₃, P₆ in S^n-1 be isomorphic to R, R₃, R₆ in Sⁿ, respectively. Since P is divided by two boundaries, isomorphic to b₀ and b₁, it has at least three subregions, two of which are P₃ and P₆, and the third is isomorphic to either R₄ or R₅. Therefore, b₂ divides either R₄ or R₅. Assume without loss of generality that b₂ divides R₄. By the lemma, there is subregion R_c of R₄ divided by b₂, completing the proof.

Simplex Theorem

If b divides the vertex regions of a simplex in linear space, Sⁿ, then Sⁿ extended by b is not linear.

If the vertexes of a simplex are divided by a boundary, b, then b divides the vertexes of the restriction of Sⁿ to the simplex. Thus, I need only prove the theorem for Sⁿ consisting of a simplex alone. Proceed by induction on the dimension of Sⁿ. If n=1, no boundary divides the vertex regions because no boundary divides more than one region, and a simplex has two vertexes. Make the induction assumption that if the dimension is less than n, then any extension dividing vertex regions is not linear. Let V₀, V₁, ..., V_n be vertex regions of Sⁿ opposite the empty region from boundaries b₀, b₁, ..., b_n, respectively. Suppose for proof by contradiction, that V₀, V₁, ..., V_n are divided by b, and the extension by b is linear. For each b_i in {b₁, b₂, ..., b_n}, let R_i be the region of {b₁, b₂, ..., b_n}-{b_i} containing V_i. V₀ is a subregion of R_i because none of {b₁, b₂, ..., b_n}-{b_i} separates V_i from V₀. Since b divides V_i and V₀, and V_i and V₀ are subregions of R_i, the "Intermediate Region Theorem" applies. Thus, b divides a region U_i in R_i between b_i and b₀. Since only b₀ and b_i divide R_i, and the region opposite b_i from V_i is empty, R_i has only three subregions, V_i, V₀, and U_i. Consider S^n-1, the section by b₀ of Sⁿ with b₀ removed. Since S^n-1 has n boundaries, it is a simplex. For each i in {1, 2, ..., n}, let W_i be the vertex region of S^n-1 opposite b_i from the empty region, P_i be the region containing U_i and V_i as subregions, U_ia and U_ib be the subregions of U_i separated by b, V_ia and V_ib be the subregions of V_i separated by b, P_ia be the region with U_ia and V_ia as subregions, and P_ib be the region with U_ib and V_ib as subregions. Since the region opposite b_i from P_i is V₀, and b₀ does not divide V₀, P_i is isomorphic to W_i. Since b₀ divides both P_ia and P_ib, b divides W_i. By the induction assumption, S^n-1 extended by b is not linear. On the other hand, Sⁿ extended by b is linear by assumption. Thus by the "Section Theorem", S^n-1 extended by b is linear. This contradiction completes the proof.

Constructibility

I am finally able to prove the theorems I left unproved in the first posting of this blog. I'll start with a new approach to the "Independent Boundary Theorem". Then I'll present a few lemmas for the "Constructibility Theorem", introduced as the "if" part of the "Linear Space Theorem" in the first posting. In the following, all regions in Rⁿ are bounded by linear surfaces, so they are closed and convex.

Independent Boundary Theorem

If Sⁿ extended by b₀ is linear and Sⁿ extended by b₁ is linear, then there exists a linear superspace of Sⁿ extended by b₀ and b₁.

If n=1, and b₀ and b₁ divide different regions, then add points such that all regions identical, except for b₀ and b₁, to the regions divided by b₀ and b₁ are nonempty. If n=1, and b₀ and b₁ divide the same region, then add points such that 3 out of 4 of the regions identical, except for b₀ and b₁, to the region divided by b₀ and b₁ are nonempty. If n>1, Proceed by induction on number of boundaries. If Sⁿ is empty, construct all 4 possible regions. Otherwise, choose b₂ from Sⁿ. Consider the section S^n-1 of Sⁿ-{b₂} by b₂. By the "Section Theorem", S^n-1 is linear. Apply the induction hypothesis to get linear Sⁿ-{b₂}+{b₀,b₁}. Apply the induction hypothesis again to extend S^n-1 by the sections of b₀ and b₁ by b₂. Choose sides of b₂ for points in Sⁿ-{b₂}+{b₀,b₁} such that b₂ divides regions isomorphic to S^n-1 extended by the sections of b₀ and b₁ by b₂. Use the "Antisection Theorem" to prove that Sⁿ+{b₀,b₁} is linear.

First Constructibility Lemma

If linear surface s goes through (tangent or dividing) all regions {R₁, R₂, ...}, and no linear surface divides every region from {R₁, R₂, ...}, then s is tangent to at least n+1 of {R₁, R₂, ...}.

If s is tangent to fewer than n+1 of {R₁, R₂, ...}, then a linear surface dividing all of {R₁, R₂, ...} can be constructed by moving s an arbitrarily small amount into the regions from {R₁, R₂, ...} it is tangent to. This contradiction proves that s is tangent to at least n+1 of {R₁, R₂, ...}.

Second Constructibility Lemma

If b₀ is a boundary for all of the regions divided by b₁ in a linear space Sⁿ, Sⁿ is isomorphic to linear surfaces in Rⁿ, b₀ is isomorphic to s₀ in Rⁿ, S^n-1 is the section of Sⁿ by b₁, b₀ in S^n-1 is isomorphic to linear subsurface l₀ in s₀, then there exists linear surface s₁ in Rⁿ isomorphic to b₁.

Choose R₀ in Rⁿ isomorphic to some R₀ divided by b₁. Construct s₁ arbitrarily close to s₀, through l₀, dividing R₀. I must show that the isomorphism between Sⁿ and Rⁿ maps the regions divided by b₁ to the regions divided by s₁. Suppose b₁ divides R₁ in Sⁿ isomorphic to R₁ in Rⁿ. By definition of section, R₀ and R₁ in Sⁿ on the same side of b₀ implies R₀ and R₁ in S^n-1 are on the same side of b₀. Let Qⁿ be Sⁿ with b₀ removed. Since b₀ bounds the regions divided by b₁, b₀ and b₁ divide the same regions in Qⁿ. Thus, b₀ in the section by b₁ is isomorphic to b₁ in the section by b₀. Therefore, R₀ and R₁ on the same side of b₀ in b₁ implies R₀ and R₁ are on the same side of b₁ in b₀. Let Pⁿ be Rⁿ with s₀ removed, then Pⁿ is isomorphic to Qⁿ. Thus, R₀ and R₁ on the same side of b₁ in b₀ implies R₀ and R₁ are on the same side of l₀ in s₀. By similarity of triangles, R₀ and R₁ on the same side of l₀ in s₀, R₀ and R₁ on the same side of s₀ in Rⁿ, s₁ arbitrarily close to s₀, and s₁ dividing R₀ implies s₁ divides R₁. A similar argument applies if R₀ and R₁ in Sⁿ are opposite b₀. Therefore, b₁ dividing R₁ implies s₁ divides R₁ isomorphic to R₁, so s₁ is isomorphic to b₁.

Third Constructibility Lemma

If there is no linear surface through regions {R₁, R₂, ...} in Rⁿ, and there is no linear surface tangent to more than n regions in {R₁, R₂, ...}, then there is a subset of n+1 regions {R₃, R₄, ...} from {R₁, R₂, ...} such that there is no linear surface through {R₃, R₄, ...}.

Any linear surface goes through an empty set of regions, so {R₁, R₂, ...} must be nonempty. Choose {R₅, R₆, ...} and R from {R₁, R₂, ...} such that there is a linear surface through {R₅, R₆, ...}, but no linear surface through {R, R₅, R₆, ...}. Choose linear surface s₀, closest to R that goes through {R₅, R₆, ...}. Because s₀ cannot be moved closer to R without changing whether it goes through {R₅, R₆, ...}, and s₀ is tangent to no more than n regions from {R₅, R₆, ...}, s₀ is tangent to exactly n regions from {R₅, R₆, ...}. Let {R₃, R₄, ...} be the n regions from {R₅, R₆, ...} that s₀ is tangent to, together with R. Suppose there is linear surface s₁ that goes through all of {R₃, R₄, ...}. Move s₀ towards s₁ such that their intersection remains fixed. Since s₀ is closest to R through {R₅, R₆, ...}, it must leave one of {R₅, R₆, ...} before it gets closer to R, and it must get closer to R to get closer to s₁. The only regions s₀ can leave immediately are the ones it is tangent to. Thus, s₀ must leave one of {R₃, R₄, ...}. Since s₀ only moves towards s₁ and the regions are convex, s₀ never returns to that region it leaves. Therefore s₁ does not go through all of {R₃, R₄, ...}, and there is no linear surface through all of {R₃, R₄, ...}.

Fourth Constructibility Lemma

If there is no linear surface through n+1 regions {R₁, R₂, ...} in Rⁿ, then there is a simplex with {R₁, R₂, ...} in the vertex regions.

Fore each R in {R₁, R₂, ...} choose s through all of {R₁, R₂, ...} except R, closest to R. This is possible because it is always possible to construct a linear surface through n regions in Rⁿ. If s were not tangent to n regions from {R₁, R₂, ...}, there would be a linear surface through the same regions as s, but closer to R. Thus, s is tangent to n regions from {R₁, R₂, ...}. For each s, choose t arbitrarily close to s, not through the regions s is tangent to, and still not through R. Thus, t separates R from the other regions in {R₁, R₂, ...}. In this way construct simplex {t₁, t₂, ...} with {R₁, R₂, ...} in the vertex regions.

Constructibility Theorem

If Sⁿ is a linear sidedness space, then there exist non-coincidental linear surfaces in Rⁿ isomorphic to Sⁿ.

If n=1, then construct by choosing boundaries dividing the same regions in R¹ as divided in S¹. This is possible because extensions to S¹ divide nonempty regions. If n>1, proceed by induction on the number of boundaries in Sⁿ. If there are no boundaries in Sⁿ, then the empty set of linear surfaces in Rⁿ is isomorphic. Assume there is a set of non-coincidental linear surfaces isomorphic to every sidedness space with one fewer boundary than Sⁿ. I must prove there is a set of non-coincidental linear surfaces isomorphic to Sⁿ. Assume the contrary. Remove one boundary, b, from Sⁿ. There is a set, {s₁, s₂, ...}, of non-coincidental linear surfaces isomorphic to Sⁿ with b removed. By assumption there is no linear surface dividing the regions, {R₁, R₂, ...}, isomorphic to the regions divided by b. If there exists a linear surface, s, through (tangent or dividing) all of {R₁, R₂, ...}, then by the "First Constructibility Lemma", s is tangent to at least n+1 of {R₁, R₂, ...}. By the induction assumption, the boundaries of the regions are non-coincidental, so s is tangent to no more than n regions unless it is a boundary for all of the regions it goes through. Thus, s is a boundary for all of {R₁, R₂, ...}, or there is R in {R₁, R₂, ...} that s does not go through (neither tangent nor dividing). If s is a boundary, then since n>1, the boundary isomorphic to s in the section of Sⁿ by b is constructible by the induction assumption. By the "Second Constructibility Lemma", if s is a boundary for the regions, then b is constructible. This contradiction shows that for each linear surface s there is some R in {R₁, R₂, ...} that s does not go through. Since the boundaries of {R₁, R₂, ...} are non-coincidental, no linear surface is tangent to more than n of {R₁, R₂, ...}. By the "Third Constructibility Lemma", there is a subset of n+1 of {R₁, R₂, ...}, say {R₃, R₄, ...}, that no linear surface goes through. By the "Fourth Constructibility Lemma", there is a simplex, say {s₃, s₄, ...} of n+1 linear surfaces with {R₃, R₄, ...} in the vertex regions. By the "only if" part of the "Linearity Theorem", and the "Independent Boundary Theorem", Sⁿ with b removed can be extended by boundaries isomorphic to {s₃, s₄, ...}, to spaces extensible by b. Thus, Sⁿ is extensible by a simplex with b dividing the vertex regions. This violates the "Simplex Theorem", so there is a linear surface, s₀, that together with {s₁, s₂, ...}, are isomorphic to Sⁿ. If {s₀, s₁, s₂, ...} are coincidental, then adjust s₀ by an arbitrarily small amount to find non-coincidental linear surfaces isomorphic to Sⁿ.

Note that the proof extends an arbitrary set of linear surfaces with a new surface. Thus, every isomorphic set of linear surfaces can be extended to every superspace. In other words, to obtain a set of linear surfaces isomorphic to a given abstract linear space, linear surfaces can be added to the set in any order, and any linear surface that divides the correct regions suffices. To me this means linear spaces are very easy to construct. On the other hand, I could claim that linear spaces are very rigid. For example, no change in the position of a linear surface sufficient to close a line of sight is possible without changing which equivalence class the linear space is in.