Skip to main content
deleted 2 characters in body
Source Link
David Gao
  • 2.8k
  • 1
  • 6
  • 23

Lemma 3: $\cap_{x \in \mathbb{R}} S(x)$ is a singleton.

Lemma 3: $\cap_{x \in \mathbb{R}} S(x)$ is a singleton.

Lemma: $\cap_{x \in \mathbb{R}} S(x)$ is a singleton.

Shorten the proof using Helly's theorem
Source Link

Lemma 1: If $I_1, I_2, I_3$ are closed intervals s.t. any pair of them intersect nontrivially, then $I_1 \cap I_2 \cap I_3 \neq \varnothing$.

Proof: If any of the intervals contains another, then the result is obvious. Assume that is not the case. Note that if two closed intervals intersect, and if neither of them contains the other, then the intersection is a closed interval which contains one endpoint from each of the original intervals. In particular, $I_1 \cap I_2$ contains an endpoint of $I_1$, and similarly $I_1 \cap I_3$ contains an endpoint of $I_1$. If both contain the same endpoint of $I_1$, the result follows. Otherwise, we may WLOG that $L(I_1) \in I_2$ and $R(I_1) \in I_3$. But then $L(I_2) \leq L(I_1) \leq R(I_1) \leq R(I_3)$, so for $I_2$ and $I_3$ to intersect, we must have $R(I_2) \geq L(I_3)$. We also observe that, since none of the intervals contains each other, we have $R(I_2) < R(I_1) \leq R(I_3)$ and $L(I_3) > L(I_1) \geq L(I_2)$. Thus, $[L(I_3), R(I_2)] = I_2 \cap I_3$ is nonempty and also contained in $I_1$. Hence, $I_1 \cap I_2 \cap I_3 \neq \varnothing$. $\square$

Lemma 2: If $I_1, \cdots, I_n$, $n \geq 2$ are closed intervals s.t. any pair of them intersect nontrivially, then $I_1 \cap \cdots \cap I_n \neq \varnothing$.

Proof: By induction on $n$: The $n = 2$ case is trivial. Assume the result holds for some $n$ and consider the case for $n + 1$. Then $I_1 \cap I_{n + 1}, \cdots, I_n \cap I_{n + 1}$ are $n$ closed intervals. Any pair of them intersect nontrivially, since the intersection of any pair is the intersection of three $I_k$’s, whence it is nonempty by Lemma 1. Thus, by inductive assumption, $I_1 \cap \cdots \cap I_{n + 1} = (I_1 \cap I_{n + 1}) \cap \cdots \cap (I_n \cap I_{n + 1}) \neq \varnothing$. $\square$

As $\varnothing \neq q(x, y) \subset S(x) \cap S(y)$ is nonempty for any $x, y$, Lemma 2Helly's theorem for $d=2$ implies that any finitely many $S(x)$ intersect nontrivially.

Lemma 1: If $I_1, I_2, I_3$ are closed intervals s.t. any pair of them intersect nontrivially, then $I_1 \cap I_2 \cap I_3 \neq \varnothing$.

Proof: If any of the intervals contains another, then the result is obvious. Assume that is not the case. Note that if two closed intervals intersect, and if neither of them contains the other, then the intersection is a closed interval which contains one endpoint from each of the original intervals. In particular, $I_1 \cap I_2$ contains an endpoint of $I_1$, and similarly $I_1 \cap I_3$ contains an endpoint of $I_1$. If both contain the same endpoint of $I_1$, the result follows. Otherwise, we may WLOG that $L(I_1) \in I_2$ and $R(I_1) \in I_3$. But then $L(I_2) \leq L(I_1) \leq R(I_1) \leq R(I_3)$, so for $I_2$ and $I_3$ to intersect, we must have $R(I_2) \geq L(I_3)$. We also observe that, since none of the intervals contains each other, we have $R(I_2) < R(I_1) \leq R(I_3)$ and $L(I_3) > L(I_1) \geq L(I_2)$. Thus, $[L(I_3), R(I_2)] = I_2 \cap I_3$ is nonempty and also contained in $I_1$. Hence, $I_1 \cap I_2 \cap I_3 \neq \varnothing$. $\square$

Lemma 2: If $I_1, \cdots, I_n$, $n \geq 2$ are closed intervals s.t. any pair of them intersect nontrivially, then $I_1 \cap \cdots \cap I_n \neq \varnothing$.

Proof: By induction on $n$: The $n = 2$ case is trivial. Assume the result holds for some $n$ and consider the case for $n + 1$. Then $I_1 \cap I_{n + 1}, \cdots, I_n \cap I_{n + 1}$ are $n$ closed intervals. Any pair of them intersect nontrivially, since the intersection of any pair is the intersection of three $I_k$’s, whence it is nonempty by Lemma 1. Thus, by inductive assumption, $I_1 \cap \cdots \cap I_{n + 1} = (I_1 \cap I_{n + 1}) \cap \cdots \cap (I_n \cap I_{n + 1}) \neq \varnothing$. $\square$

As $\varnothing \neq q(x, y) \subset S(x) \cap S(y)$ is nonempty for any $x, y$, Lemma 2 implies any finitely many $S(x)$ intersect nontrivially.

As $\varnothing \neq q(x, y) \subset S(x) \cap S(y)$ is nonempty for any $x, y$, Helly's theorem for $d=2$ implies that any finitely many $S(x)$ intersect nontrivially.

edited body
Source Link
David Gao
  • 2.8k
  • 1
  • 6
  • 23

Proof: Let $c_0, c_1 \in \cap_{x \in \mathbb{R}} S(x)$. Then because $c_i \in \cap_{x \in \mathbb{R}} S(x) \subset S(c_{1 - i})$, we have $c_1 = p_{c_2}(c_1) = p_{c_1}(c_2) = c_2$$c_1 = p_{c_0}(c_1) = p_{c_1}(c_0) = c_0$. $\square$

Proof: Let $c_0, c_1 \in \cap_{x \in \mathbb{R}} S(x)$. Then because $c_i \in \cap_{x \in \mathbb{R}} S(x) \subset S(c_{1 - i})$, we have $c_1 = p_{c_2}(c_1) = p_{c_1}(c_2) = c_2$. $\square$

Proof: Let $c_0, c_1 \in \cap_{x \in \mathbb{R}} S(x)$. Then because $c_i \in \cap_{x \in \mathbb{R}} S(x) \subset S(c_{1 - i})$, we have $c_1 = p_{c_0}(c_1) = p_{c_1}(c_0) = c_0$. $\square$

added 8 characters in body
Source Link
David Gao
  • 2.8k
  • 1
  • 6
  • 23
Loading
Source Link
David Gao
  • 2.8k
  • 1
  • 6
  • 23
Loading