> I had no idea where to start interpreting the notation other than maybe attending a class to get the proper starter culture.
More than anything, I think this is the main reason why studying many subfield of mathematics is so difficult, when we spend more time and effort in things like parsing instead of in the actual subject matter.
Even popular subjects may show similar problems. For example, in Sedgewick's Analysis of Algorithms, he gives the following common definition:
> O(f(N)) denotes the set of all g(N)....
In the next page, he presents an exercise:
> Show that f(N) = N lg N + O(N) implies f(N) = ϴ(N log N)
Reader looks at that "N lg N + O(N)" and tries to make sense of the addition of a number to a set of functions. Note, this is in page 5, so many readers unfamiliar with the culture of the area are likely to just abandon the book (and perhaps the study of the subject) as they could not translate to themselves the very first formula presented by the author.
The only clue to anything that could help the newbie to get some answers lies in a couple of references that point to the historical uses of these greek symbols for computational complexity. Within that reference [1], by no other than Knuth, one can find the explanation for such syntax:
> "1+O(n^-1) " can be taken to mean the set of all functions of the form 1+g(n), where |g(n)| < Cn^-1 for some C and all large n.
And then he goes on about the problem of that syntax in respect to one-way equality:
> we write 1+O(n^-1) = O(1) but not O(1) = 1+O(n^-1). The equal sign here really means ⊆ "set inclusion", and this has bothered many people who propose that we not be allowed to use the = sign in this context. My feeling is that we should continue to use one-way equality together with O-notations since it has been common practice of thousands of mathematicians for so many years now, and since we understand the meaning of our existing notation sufficiently well.
The above is not only a reason for logicians to laugh at the pretense that mathematical language is formal, but also an example of things that are likely not to be in books but in an unwritten culture of a field.
--
[1] - Knuth, Big Omicron and big Omega and big Theta
More than anything, I think this is the main reason why studying many subfield of mathematics is so difficult, when we spend more time and effort in things like parsing instead of in the actual subject matter.
Even popular subjects may show similar problems. For example, in Sedgewick's Analysis of Algorithms, he gives the following common definition:
> O(f(N)) denotes the set of all g(N)....
In the next page, he presents an exercise:
> Show that f(N) = N lg N + O(N) implies f(N) = ϴ(N log N)
Reader looks at that "N lg N + O(N)" and tries to make sense of the addition of a number to a set of functions. Note, this is in page 5, so many readers unfamiliar with the culture of the area are likely to just abandon the book (and perhaps the study of the subject) as they could not translate to themselves the very first formula presented by the author.
The only clue to anything that could help the newbie to get some answers lies in a couple of references that point to the historical uses of these greek symbols for computational complexity. Within that reference [1], by no other than Knuth, one can find the explanation for such syntax:
> "1+O(n^-1) " can be taken to mean the set of all functions of the form 1+g(n), where |g(n)| < Cn^-1 for some C and all large n.
And then he goes on about the problem of that syntax in respect to one-way equality:
> we write 1+O(n^-1) = O(1) but not O(1) = 1+O(n^-1). The equal sign here really means ⊆ "set inclusion", and this has bothered many people who propose that we not be allowed to use the = sign in this context. My feeling is that we should continue to use one-way equality together with O-notations since it has been common practice of thousands of mathematicians for so many years now, and since we understand the meaning of our existing notation sufficiently well.
The above is not only a reason for logicians to laugh at the pretense that mathematical language is formal, but also an example of things that are likely not to be in books but in an unwritten culture of a field.
--
[1] - Knuth, Big Omicron and big Omega and big Theta