0
$\begingroup$

Are there many definitions of sets and classes in mathematics, as given in Formal definion of the notations used in measuring time complexity? And in particular, why the notation given in Fedja's comment gives a class rather than a set?

Fedja's comment:

I have a colleague (a very fine mathematician, by the way), who insists that the way the $ o()$ and $ O()$ notation is currently used is nothing but an abuse of mathematical language. His argument is that $ =$ should always be an equivalence relation and $ \sin x = O(1)$ and $ 1 = O(1)$ imply neither $ O(1) = \sin x$, nor $ \sin x = 1$. Besides, the same symbol $ O(x)$ means a lot of different things. The formally correct approach to the big and little O notation, in his opinion, should be the following. Given a positive $ g$ defined in a punctured neighborhood of $ x_0$, denote by $ O_{x_0}(g)$ the class of all functions $ f$ such that the ratio $ f/g$ is bounded in some punctured neighbourhood of $ x_0$. This is a perfectly meaningful mathematical object with unique meaning. Now, instead of writing $ f(x) = O(g(x))$ as $ x\to x_0$, write $ f\in O_{x_0}(g)$. If you understand the arithmetic operations over classes of functions in the sense of Minkowski, i.e., $ A*B = \{f*g: f\in A,g\in B\}$ where $ *$ is any of the four arithmetic operations, then you can elaborate upon this idea and instead of writing $ 1 + \sin x = 1 + O(|x|) = 1 + o(1)$ as $ x\to 0$, write the formally correct $ 1 + \sin x\in 1 + O_0(|x|)\subset 1 + o_0(1)$. And so on, and so forth. I find his logic irrefutable but I do not think he has a big chance to win his crusade :)

$\endgroup$
  • $\begingroup$ Could you quote the content from the links directly into your question? $\endgroup$ – Ali Caglayan Aug 29 '14 at 9:33
  • 4
    $\begingroup$ Abuse of notation isn't always a problem. I don't think I'd agree with saying it is 'nothing but' abuse of notation. It is still useful, even if we don't write everything the way maybe it should formally. $\endgroup$ – Jessica B Aug 29 '14 at 9:59
  • $\begingroup$ In this context one use the word "class" as in "equivalence class", but it is actually a set. $\endgroup$ – Siméon Aug 29 '14 at 12:19
  • 1
    $\begingroup$ @Siméon Big $O$, it isn't equivalence classes. $O(\log n)$ is contained in $O(n)$. Neither is little $o$. $\endgroup$ – Thomas Andrews Aug 29 '14 at 12:21
  • $\begingroup$ @ThomasAndrews: indeed, my comment was confusing. $\endgroup$ – Siméon Aug 29 '14 at 12:27
3
$\begingroup$

There is no difference in meaning between "class" and "set" in this particular usage.

He is correct on the right way to formalize these notations, but the shorthand is so much easier to read, and, as long as everybody knows what you mean, it is acceptable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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