Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
up vote 0 down vote accepted

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

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.