# What does ∈ mean in the exponent?

I'm having troubles understanding the following proof: \begin{align*} &\text{Proof: } \forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log_a(n) \\ &\Longrightarrow \ln(a(n)) = \log_2(e)\ln^2(n) \ll n^{0.01} = \ln(d(n)) \\ &\Longrightarrow a(n) \ll d(n) \end{align*} The topic is Big O comparisons. The proof is about $a(n)= n^{\log_2 n}$ and $d(n) = e^{n^{0.01}}$. The proof is very heavy in mathematical notation. I'm not sure what ∈ means in the example. I know that it denotes set membership in a more usual case, but have never seen it in the exponential position.

• en.wikipedia.org/wiki/… – jmite Sep 13 '18 at 22:45
• @jmite knowing that it is called set membership in a more usual case, but never seen it in the exponential position. – CCOthers Sep 13 '18 at 22:51
• whoops, I only saw the $\in \mathbb{Z}$. That there is just $\epsilon$, the greek letter Epsilon. Like most symbols in math, it doesn't "mean" anything. Here it's just a placeholder for any positive real number. – jmite Sep 13 '18 at 22:57
• @jmite Well, it would be very unusual for $\epsilon$ to be used for anything other than a positive real number in a context where "it's a positive real number" would make sense. Indeed, more strongly, it's usually a small positive real. That's a lot of meaning, really. – David Richerby Sep 14 '18 at 13:47

That's not $\in$ but $\epsilon$: that is, a lowercase Greek letter epsilon. It's normally written $\varepsilon$ instead for clarity, but this author chose to use the "lunate" form for unknown reasons.

In this case, epsilon is being used as a shorthand for "an arbitrarily small but positive real number". This should probably be explained in the proof, but it's a fairly common shorthand in mathematics (for example, delta-epsilon proofs, floating-point epsilon…).

In other words, it's saying that the log of $n$ is always asymptotically smaller than $n$ raised to any positive power. In the next line it substitutes in a definite value, 0.01, for epsilon.

• The "unknown reason" is most likely simply that LaTeX uses \epsilon for $\epsilon$ and \varepsilon for $\varepsilon$, which is more typing. And, honestly, $\epsilon$ and $\in$ are plenty distinct enough -- you only need to be told once to know that they're not just "the same thing in different fonts." (Though, historically, $\varepsilon$ was also used for the set membership relation.) – David Richerby Sep 14 '18 at 13:45

It's a variable name, like any other. In your property you could rename it to (e.g.) $b$, turning $$\forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log_a(n)$$ into $$\forall b \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^b \gg \log_a(n)$$

That's it.

Why calling it $\epsilon$, then, instead of a more common variable name?

In maths, it is common to call such variable $\epsilon$ when you could restrict its range to any positive interval $(0,x)$ with $x>0$ and get a completely equivalent statement, no matter how small the interval is. That is, instead of proving $\forall b \in \mathbb{R}^+$ we could only prove $\forall b \in (0,10^{-8})$ and that would be just as good. Indeed, once it is proven for the small interval, it's easy to extend the result to all positive reals.

In a nutshell it conveys the idea that "only small positive values actually matter".

This is a sort-of implicit statement which is suggested every time $\epsilon$ is used. You can safely neglect this "hint" to the reader, and take the statement as it is.