Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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...

share|improve this question
Is $R'$ supposed to be the derivative of $R$, or is it supposed to be just another function? –  Thomas Andrews Dec 5 '12 at 14:31
What exactly does $\inf_{0\le \tau} \{\tau.R(t) \le R'(t + \tau)\}$ mean? The infimum of the set of all $\tau$ with $\tau \ge 0$ and $R(t) \le R'(t+ \tau)$, I suppose? –  martini Dec 5 '12 at 14:35
To Thomas : they are two different functions, To martini: yes, i edited it, is the notation better now ? –  E. Mabille Dec 5 '12 at 14:48
I think "true propositions" is incorrect mathematical language here because a proposition is something you test to see if it is true. I think you mean "assumptions" (or something similar). –  Adam Rubinson Dec 5 '12 at 15:05
@E.Mabille: I have changed the wedge symbol ($\wedge$) to the word "and", as that symbol is also overloaded with the meaning of minimum (i.e. $a\wedge b=\min(a,b)$). I have also replaced the double infimum ($\inf\inf$) in the statement you want to show to single infimum ($\inf$). I hope I didn't misunderstand your question. –  user1551 Dec 5 '12 at 17:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.