3
$\begingroup$

I am stuck on this problem for a while now, any help would be appreciated. I am working on the proof of a Network Calculus theorem, and I would like to show that the infimum is reached in the horizontal deviation of two functions. I simplified the problem, and left only what is essential I think :

Let $f$ : $\mathbb{R}^+ \rightarrow \mathbb{R}^+ \:;\: a\in\mathbb{R}^+ \:;\: t\in\mathbb{R}^+ \:;\: d\in\mathbb{R}^+$. Here are a few assumptions that I have :

  • $f$ is non-decreasing: $x\leq y \rightarrow f(x) \leq f(y)$.
  • $f(0)=0$.
  • $\inf \{\tau: \tau\ge0 \textrm{ and } a \leq f(t+\tau)\} \leq d$.
  • $\exists \theta\geq 0,\ a \leq f(t+\theta)$.
  • Also, I am pretty sure that we need : $f$ is continuous.

Let $A = \{\tau: \tau\ge0 \textrm{ and } a \leq f(t+\tau)\}$

I want to prove that: $\inf A \in A$.

Thank you


I did some work and came up with the following. But there are still some gaps left.... $0 \le \inf A \textrm{ and } a = f(t+ \inf A) \longrightarrow \inf A \in A$

Proving $0 \leq \inf A$ is trivial, since all elements of A are positive.

Next, let us show that $a = f(t+ \inf A)$ by contradiction:

Let us assume that $a \neq f(t+ \inf A) \, ,$

hence: $0 < |f(t + \inf A) - a| \, ,$

with the density of reals we can obtain an $ε$ where $0 < ε \text{ and } ε < |f(t + \inf A) - a| \, . \qquad (1)$

Moreover, $a \in \mathbb{R}^+ \text{ and } f(0) = 0 \longrightarrow f(0) \leq a$

With this and the assumption about the existence of $\theta$, we can use the theorem of intermediate values to obtain $c$ where $0 \leq c \text{ and }c \leq t + \theta \text{ and } f(c) = a \, .$

With (1), we have: $ε < |f(t + \inf A) - f(c)| \, . \qquad (2)$

And from the continuity of f, we can obtain an $η$ where : $∀x. |(t + \inf A) - x| < η ⟶ |f (t + \inf A) - f(x)| < ε$

Now, I am not sure if euclidean division can be used with real, so I used this construction which is an equivalent of the reminder of an euclidean division: $x_η = c - \lfloor {c - (t+\inf A) \over η} \rfloor \times η \, ,$

We then obtain: $t + \inf A \leq x_η\, \qquad (3.1)$ $x_η \leq c \, \qquad (3.2)$ $|(t + \inf A) - x_η| < η \, \qquad (3.3).$

With the definition of $η$, we have: $|f (t + \inf A) - f(x_η)| < ε$

I need to prove $f(x_η) = f(c)$, which would allow us to conclude, with (2).

From 3.2 and f incresing, we easily obtain $f(x_η) \leq f(c)$.

But from 3.1 and f increasing, all I can get, is that $a \leq f(t + x_η)$. I need to prove that $t + \inf A = \inf \{\tau: t \leq \tau \text{ and } a \leq f(\tau)\}$ But I have no clue on how to prove this...

  • 0
    I was not sure where to put my draft of proof, if someone knows better feel free to edit it...2012-12-11

1 Answers 1

1

All you need to understand is that, $f$ being order-preserving and continuous (and actually you can replace continuity by upper semicontinuity), one has $\inf_{x \in X} f(x) = f(\inf_{x \in X})$ for every $X \subset \mathbb{R}_+$. Then $\inf_{\tau \in A} f(t + \tau) = f(\inf_{\tau \in A} (t + \tau)) = f(t + \inf_{\tau \in A} \tau) = f(t + \inf A)$, which implies $\inf A \in A$.