<p>Intuitively, the theorem says that a line is not a finite union of points, a plane is not a finite union of lines, etc. The simplest proof is to observe, for example, that a finite union of lines has zero area, whereas a plane does not.</p>

<p>More concretely, observe that it is enough to prove the claim for manifolds on $\mathbb{R}^n$ by passing to their closures. Consider an affine manifold $M\subseteq \mathbb{Q}^n$ given by the set of solutions to the linear system $A x = b$; its closure will be precisely the set of solutions to the same system over $\mathbb{R}^n$, hence this step does not affect the dimension of the manifolds involved. Also, the closure of a finite union equals the union of the closures. </p>

<p>Now note that the $d$-dimensional Lebesgue measure of a manifold of dimension $\le d - 1$ is null.  Therefore the $d$-dimensional Lebesgue measure of a finite union of such manifolds is still zero. But the $d$-dimensional measure of an $d$-dimensional manifold is infinite, hence non-zero.</p>

<p>As for your second question, I'm not quite sure what you mean. But if the base field $\mathbb{F}$ is finite, then any $d$-dimensional affine manifold over $\mathbb{F}^n$ contains $|\mathbb{F}|^d$ points. So by a similar counting argument, you need at least $|\mathbb{F}|^d/|\mathbb{F}|^{d-1}=|\mathbb{F}|$ affine spaces of dimension $\le d - 1$ to cover an affine space of dimension $d$.</p>

CC BY-SA 3.0
2012-02-08T01:50:55.433Z
thanks!! this answers both questions. What I've (very unclearly) meant in the second question was "what would happen if instead of an affine manifold we had a finite convex set". But still, your answer cleared my doubts.
Marcos Villagra
CC BY-SA 3.0
2012-02-07T11:27:01.017Z
2012-02-07T11:47:12.030Z
2012-02-07T11:47:12.030Z
david
<p>Here is a measure-free proof which works for affine manifolds over an arbitrary infinite field $\mathbb F$ (the result is false for finite fields).</p>

<p>By induction on $n\ge0$, we will show that an affine manifold $A\subseteq\mathbb F^m$ of dimension $n$ is not a finite union of affine manifolds of dimension less than $n$.</p>

<p>The statement is clear for $n=0$: a point is not a (finite) union of empty sets.</p>

<p>Assume the statement holds for $n$, we will show it for $n+1$. Let $A=\bigcup_{i&lt;k}A_i$, where $\dim(A)=n+1$ and $\dim(A_i)\le n$. Consider an arbitrary affine submanifold $B\subset A$ of dimension $n$. Since $B=\bigcup_i(B\cap A_i)$, the induction hypothesis implies that $\dim(B\cap A_i)=n$ for some $i&lt;k$, i.e., $B=A_i$. Since there are only $k$ sets $A_i$, and $B$ was arbitrary, it follows that $A$ has only finitely many submanifolds of dimension $n$. However, this is a contradiction: if we fix any such submanifold $B_0$ and a vector $v$ parallel to $A$ but not to $B_0$, there are infinitely many affine submanifolds of $A$ of the form $B_0+av$, where $a\in\mathbb F$.</p>

CC BY-SA 3.0
2012-02-08T01:48:13.647Z
nice alternative proof!
Marcos Villagra
CC BY-SA 3.0
2012-02-08T07:49:05.990Z
No, this is *the* proof and the other one is alternative because it drags in measure theory :-)
Andrej Bauer
CC BY-SA 3.0
2012-02-08T10:37:47.510Z
Ahhh I see, good point
Marcos Villagra
CC BY-SA 3.0
2012-02-07T15:10:26.210Z
2012-02-07T15:10:26.210Z
Emil Jeřábek
<p>I'm looking for the proof of Theorem 4 that appears in this paper:</p>
<p><a href="https://doi.org/10.1007/BF01762237" rel="nofollow noreferrer">An Infinite Hierarchy of Intersections of Context-Free Languages</a> by Liu and Weiner.</p>
<blockquote>
<p><strong>Theorem 4:</strong> An <span class="math-container">$n$</span>-dimensional affine manifold is not expressible as a finite union of affine manifolds each of which is of dimension <span class="math-container">$n-1$</span> or less.</p>
</blockquote>
<ol>
<li>Does anyone knows a reference to the proof?</li>
<li>If the manifold is finite and we define a natural order on the elements, is there any similar statement in terms of lattices?</li>
</ol>
<hr />
<p>Some background to understand the theorem:</p>
<p><strong>Definition:</strong> Let <span class="math-container">$\mathbb{Q}$</span> be the set of rational numbers. A subset <span class="math-container">$M\subseteq \mathbb{Q}^n$</span> is an <em>affine manifold</em> if <span class="math-container">$(\lambda x+(1-\lambda)y)\in M$</span> when <span class="math-container">$x\in M$</span>, <span class="math-container">$y\in M$</span>, and <span class="math-container">$\lambda\in\mathbb{Q}$</span>.</p>
<p><strong>Definition:</strong> An affine manifold <span class="math-container">$M'$</span> is said to be parallel to an affine manifold <span class="math-container">$M$</span> if <span class="math-container">$M'=M+a$</span> for some <span class="math-container">$a\in \mathbb{Q}^n$</span>.</p>
<p><strong>Theorem:</strong> Each non-empty affine manifold <span class="math-container">$M\subseteq \mathbb{Q}^n$</span> is parallel to a unique subspace <span class="math-container">$K$</span>. This <span class="math-container">$K$</span> is given by <span class="math-container">$K=\{x-y:x,y\in M\}$</span></p>
<p><strong>Definition:</strong> The <em>dimension</em> of a non-empty affine manifold is the dimension of the subspace parallel to it.</p>
<hr />

CC BY-SA 3.0
2013-02-16T14:16:05.980Z
I know this is quite an old question, but I just happened across it today, and just wanted to ask whether you were reading that paper for any particular reason?  (It happens to be very closely related to some of my research.)
Tara B
<reference-request><fl.formal-languages><linear-algebra><context-free><lattice>
On $n$ dimensional manifolds and lattices
Marcos Villagra
# On $n$ dimensional manifolds and lattices

(Asked by: username_0 on 2012-02-07)

I'm looking for the proof of Theorem 4 that appears in this paper:

[An Infinite Hierarchy of Intersections of Context-Free Languages](https://doi.org/10.1007/BF01762237) by Liu and Weiner.

> **Theorem 4:** An $n$-dimensional affine manifold is not expressible as a finite union of affine manifolds each of which is of dimension $n-1$ or less.

1. Does anyone knows a reference to the proof?
2. If the manifold is finite and we define a natural order on the elements, is there any similar statement in terms of lattices?

---

Some background to understand the theorem:

**Definition:** Let $\mathbb{Q}$ be the set of rational numbers. A subset $M\subseteq \mathbb{Q}^n$ is an *affine manifold* if $(\lambda x+(1-\lambda)y)\in M$ when $x\in M$, $y\in M$, and $\lambda\in\mathbb{Q}$.

**Definition:** An affine manifold $M'$ is said to be parallel to an affine manifold $M$ if $M'=M+a$ for some $a\in \mathbb{Q}^n$.

**Theorem:** Each non-empty affine manifold $M\subseteq \mathbb{Q}^n$ is parallel to a unique subspace $K$. This $K$ is given by $K=\{x-y:x,y\in M\}$

**Definition:** The *dimension* of a non-empty affine manifold is the dimension of the subspace parallel to it.

---

**Tags:** reference-request, fl.formal-languages, linear-algebra, context-free, lattice
> **Comments:**
> **username_1**: I know this is quite an old question, but I just happened across it today, and just wanted to ask whether you were reading that paper for any particular reason?  (It happens to be very closely related to some of my research.)  

---

## 2 answers

### Answer by username_2 on 2012-02-07. Score: 5 | Accepted answer

Intuitively, the theorem says that a line is not a finite union of points, a plane is not a finite union of lines, etc. The simplest proof is to observe, for example, that a finite union of lines has zero area, whereas a plane does not.

More concretely, observe that it is enough to prove the claim for manifolds on $\mathbb{R}^n$ by passing to their closures. Consider an affine manifold $M\subseteq \mathbb{Q}^n$ given by the set of solutions to the linear system $A x = b$; its closure will be precisely the set of solutions to the same system over $\mathbb{R}^n$, hence this step does not affect the dimension of the manifolds involved. Also, the closure of a finite union equals the union of the closures.

Now note that the $d$-dimensional Lebesgue measure of a manifold of dimension $\le d - 1$ is null. Therefore the $d$-dimensional Lebesgue measure of a finite union of such manifolds is still zero. But the $d$-dimensional measure of an $d$-dimensional manifold is infinite, hence non-zero.

As for your second question, I'm not quite sure what you mean. But if the base field $\mathbb{F}$ is finite, then any $d$-dimensional affine manifold over $\mathbb{F}^n$ contains $|\mathbb{F}|^d$ points. So by a similar counting argument, you need at least $|\mathbb{F}|^d/|\mathbb{F}|^{d-1}=|\mathbb{F}|$ affine spaces of dimension $\le d - 1$ to cover an affine space of dimension $d$.

> **Comments:**
> **username_0**: thanks!! this answers both questions. What I've (very unclearly) meant in the second question was "what would happen if instead of an affine manifold we had a finite convex set". But still, your answer cleared my doubts.  

---

### Answer by username_3 on 2012-02-07. Score: 7

Here is a measure-free proof which works for affine manifolds over an arbitrary infinite field $\mathbb F$ (the result is false for finite fields).

By induction on $n\ge0$, we will show that an affine manifold $A\subseteq\mathbb F^m$ of dimension $n$ is not a finite union of affine manifolds of dimension less than $n$.

The statement is clear for $n=0$: a point is not a (finite) union of empty sets.

Assume the statement holds for $n$, we will show it for $n+1$. Let $A=\bigcup\_{i

> **Comments:**
> **username_0**: nice alternative proof!  
> **username_4**: No, this is *the* proof and the other one is alternative because it drags in measure theory :-)  
> **username_0**: Ahhh I see, good point  

---

