Intersection of any 2 intervals --> all intervals intersect

[Mr Davis 97]

Homework Statement

Let $\mathscr{F}$ be a finite family of open or closed intervals in the line $\mathbb{R}^1$. Show by an elementary proof that if any $2$ of them intersect, then all of them intersect.

Homework Equations

The Attempt at a Solution

Here is my attempt, where for now I'm just tackling the case for when all of the sets are open.

Since $\mathscr{F}$ is a finite family, let it have cardinality $n$, and let's list the intervals in the family as $F_1,F_2, \dots , F_n$ such that, on the real line, the left bracket of $F_1$ is strictly to the left of the left bracket of $F_2$, whose left bracket is strictly to the left of the left bracket of $F_3$, and so on. Now, for the hypothesis suppose that $F_1 \cap F_i \not = \emptyset$ for $i=2, \dots , n$. Then the right bracket of $F_1$ must be to the right of the left bracket of $F_i$ in order to intersect $F_i$. This necessitates that the right bracket of $F_1$ be to the right of the left bracket of $F_n$. Similarly, the right bracket of $F_2$ must be to the right of the left bracket of $F_n$, and so on, and finally the right bracket of $F_{n-1}$ must be to the right of the left bracket of $F_n$.

So, we see that every right bracket of $F_i$ where $i=1,2, \dots, n-1$ is to the right of the left bracket of $F_n$. Now, the region between the left bracket of $F_n$ and the first right bracket to the right of the left bracket of $F_n$ is a region of intersection for all $F_i$ so that $\bigcap F_i \not = \emptyset$

 

[andrewkirk]

The proof statement must be missing some constraint, because a counterexample is the family $(1,2),(3,5),(4,6)$ for which the last two intersect but the first intersects neither of the other two.

 

[fresh_42]

I assume

if any $2$ of them intersect

means: Let $\mathscr{F}= \{\,I_k\,|\,1\leq k \leq n\,\}$ with $I_k\cap I_m \neq \emptyset$ for all $k,m$.

 

[Mr Davis 97]

I assume

means: Let $\mathscr{F}= \{\,I_k\,|\,1\leq k \leq n\,\}$ with $I_k\cap I_m \neq \emptyset$ for all $k,m$.

That is the correct interpretation. Sorry if it was ambiguous

 

[fresh_42]

That is the correct interpretation. Sorry if it was ambiguous

I think the terminus technicus for left and right bracket should be infimum and supremum.

 

[Mr Davis 97]

I think the terminus technicus for left and right bracket should be infimum and supremum.

Got it. I have a question with what I have. For simplicity in showing the main idea I just assumed that $\inf F_1 < \cdots < \inf F_i < \cdots < \inf F_n$, where the inequalities are strict. The procedure I outlined involves moving sequentially from $F_i$ to $F_{i+1}$. But what if, for example, $\inf F_2 = \inf F_3$? This kind of ruins the procedure because I then don't really know whether to pick $F_2$ or $F_3$ first. This seems like a small issue, but how do I get around?

 

[fresh_42]

I would proceed by induction. The cases $n=1,2$ are trivial. And in the induction step, you just have to add one other interval. Try to write it down for $2 \to 3$ and then it should work $n \to n+1$ as well. Maybe you could use an indirect proof for the induction step. I haven't read your proof though. The many left and rights and the wall of text made me dizzy. The idea to concentrate on open intervals was good, because if it works for the open versions, it will certainly work for the closed ones (I think). But you are right, you cannot assume $\inf I_k < \inf I_m$, only $\inf I_k \leq \inf I_m$. However, I would not order them. It makes things only seemingly easier.

 

[Mr Davis 97]

I would proceed by induction. The cases $n=1,2$ are trivial. And in the induction step, you just have to add one other interval. Try to write it down for $2 \to 3$ and then it should work $n \to n+1$ as well. Maybe you could use an indirect proof for the induction step. I haven't read your proof though. The many left and rights and the wall of text made me dizzy. The idea to concentrate on open intervals was good, because if it works for the open versions, it will certainly work for the closed ones (I think). But you are right, you cannot assume $\inf I_k < \inf I_m$, only $\inf I_k \leq \inf I_m$. However, I would not order them. It makes things only seemingly easier.

Is the following easier to understand? Before I do anything with induction I want to see whether this proof holds up or not.

Since $\mathscr{F}$ is a finite family, let it have cardinality $n$, and let's list the intervals in the family as $F_1,F_2, \dots , F_n$ such that $\inf F_i < \inf F_{i+1}$ (note that such an ordering can always be done). Now, from the hypothesis we can suppose that $F_1 \cap F_i \not = \emptyset$ for $i=2, \dots , n$. Then $\sup F_1 > \inf F_2$ in order for $F_1$ to intersect $F_2$. Since $F_1$ intersects all other intervals as well, we must have that $\sup F_1 > \inf F_i$, and in particular, $\sup F_1 > \inf F_n$. Similarly, $\sup F_i > \inf F_n$ for $i=2,3,\dots , n-1$.

Now, the region between $\inf F_n$ and $\min \{\sup F_i : i=1,2,\dots , n-1 \}$ is a region of intersection for all $F_i$ so that $\bigcap \mathscr{F} \not = \emptyset$

 

[fresh_42]

I'm still skeptic. First, all your inequalities have to be $\leq$ instead of $<$ and $\geq$ instead of $>$. Then it is not clear what happens at the interval broders: You decided to have open intervals, so infinma and suprema are not part of the interval, resp. what happens if they all are closed instead of open, e.g. if $\sup F_1 = \inf F_2$. It might work, but it leaves a lot of open questions.

I would still proceed by induction. $\cap_{k=1}^{n-1} F_k =: I_{n-1}$ is again an interval, and the right border is the supremum of at least one $F_{k_0}$, resp. the left border an infimum of at least one $F_{k_0}$. Now you have only two intervals to discuss: $F_{k_0}$ and $F_n$ and you can consider all open and closed combinations, since there are only two of them.

 

[Mr Davis 97]

Here https://imgur.com/a/UlXhLRB there is a proof that I am trying to understand, before I do any kind of induction. My main question is, what exactly does the minmax and maxmin mean?

 

[fresh_42]

Here https://imgur.com/a/UlXhLRB there is a proof that I am trying to understand, before I do any kind of induction. My main question is, what exactly does the minmax and maxmin mean?

For each pair $(i,j)$ an element $\alpha_{ij}\in J_i\cap J_j$ is chosen. They exist be assumption. Now you can imagine them written as a symmetric matrix $A :=(\alpha_{ij})_{1\leq i,j\leq n}$. Then $\beta_1$ is the highest number of all column minima and $\beta_2$ the smallest number among all column maxima. So first consider each column and determine the smallest and the highest entry of each. Among those determine the highest number among the collection of the smallest, and the smallest among the collection of the highest entries per column. It's possibly easier to see with an example of there or four such intervals.

Note that this proof doesn't operate with strict inequalities nor with open or closed intervals, only with the points in the middle of the intervals.

 

[Mr Davis 97]

View attachment 239289

For each pair $(i,j)$ an element $\alpha_{ij}\in J_i\cap J_j$ is chosen. They exist be assumption. Now you can imagine them written as a symmetric matrix $A :=(\alpha_{ij})_{1\leq i,j\leq n}$. Then $\beta_1$ is the highest number of all column minima and $\beta_2$ the smallest number among all column maxima. So first consider each column and determine the smallest and the highest entry of each. Among those determine the highest number among the collection of the smallest, and the smallest among the collection of the highest entries per column. It's possibly easier to see with an example of there or four such intervals.

Note that this proof doesn't operate with strict inequalities nor with open or closed intervals.

I see what you're saying when you write it out in words, but I don't see clearly how the notation works. What object exactly does $\min a_{ij}$ return? Is $\max$ acting on the $\min a_{ij}$ or is $\max \min$ taken as one object?

 

[fresh_42]

I just constructed a matrix as described, it doesn't say much of the actual intervals, only that e.g. $7 \in J_2\cap J_3$ or $0 \in J_1\cap J_5\,.$ The diagonal is the intersection of an interval with itself. The fact that this intersection is not empty is equivalent that none of the intervals is empty. In my case we have $k \in J_k\,.$
$$
\begin{bmatrix}-&1&4&6&2&0\\ -&4&2&7&8&5\\ -&6&7&3&1&1\\ -&2&8&1&4&9\\ -&0&5&1&9&5\\ \hline \\ min&0&2&1&1&0 \\ \hline \\ \beta_1&&2&&&\\ \hline \\ max&6&8&7&9&9 \\ \hline \\\beta_2&6&&&& \end{bmatrix}
$$

 

[Mr Davis 97]

I just constructed a matrix as described, it doesn't say much of the actual intervals, only that e.g. $7 \in J_2\cap J_3$ or $0 \in J_1\cap J_5\,.$ The diagonal is the intersection of an interval with itself. The fact that this intersection is not empty is equivalent that none of the intervals is empty. In my case we have $k \in J_k\,.$
$$
\begin{bmatrix}-&1&4&6&2&0\\ -&4&2&7&8&5\\ -&6&7&3&1&1\\ -&2&8&1&4&9\\ -&0&5&1&9&5\\ \hline \\ min&0&2&1&1&0 \\ \hline \\ \beta_1&&2&&&\\ \hline \\ max&6&8&7&9&9 \\ \hline \\\beta_2&6&&&& \end{bmatrix}
$$

That helps a lot, but I am still a bit confused. Later in the proof, it says, for example, that $z \le \max_{j=1, \dots, k} \alpha_{ij} \in J_i$. I thought that $\max_{j=1, \dots, k} \alpha_{ij}$ produced a list of the maximum elements in each column, so how could it be a single number?

 

[fresh_42]

I thought that $\max_{j=1, \dots, k} \alpha_{ij}$ produced a list of the maximum elements in each column, so how could it be a single number?

It says for any (each) $i\, : \,\forall \,i \, (z \leq \max_{j=1, \dots, k} \alpha_{ij} \in J_i)$ so the condition involves only one certain index $i$, however, any $i$.