Wednesday, June 15, 2022
HomeMathPartially specified mathematical objects, ambient parameters, and asymptotic notation

# Partially specified mathematical objects, ambient parameters, and asymptotic notation

In orthodox first-order logic, variables and expressions are solely allowed to take one worth at a time; a variable ${x}$, as an example, just isn’t allowed to equal ${+3}$ and ${-3}$ concurrently. We are going to name such variables utterly specified. If one actually desires to take care of a number of values of objects concurrently, one is inspired to make use of the language of set principle and/or logical quantifiers to take action.

Nonetheless, the flexibility to permit expressions to change into solely partially specified is undeniably handy, and likewise relatively intuitive. A traditional instance right here is that of the quadratic formulation:

$displaystyle hbox{If } x,a,b,c in {bf R} hbox{ with } a neq 0, hbox{ then }$

$displaystyle ax^2+bx+c=0 hbox{ if and only if } x = frac{-b pm sqrt{b^2-4ac}}{2a}. (1)$

Strictly talking, the expression ${x = frac{-b pm sqrt{b^2-4ac}}{2a}}$ just isn’t well-formed in line with the grammar of first-order logic; one ought to as a substitute use one thing like

$displaystyle x = frac{-b - sqrt{b^2-4ac}}{2a} hbox{ or } x = frac{-b + sqrt{b^2-4ac}}{2a}$

or

$displaystyle x in left{ frac{-b - sqrt{b^2-4ac}}{2a}, frac{-b + sqrt{b^2-4ac}}{2a} right}$

or

$displaystyle x = frac{-b + epsilon sqrt{b^2-4ac}}{2a} hbox{ for some } epsilon in {-1,+1}$

with a purpose to strictly adhere to this grammar. However none of those three reformulations are as compact or as conceptually clear as the unique one. In an identical spirit, a mathematical English sentence equivalent to

$displaystyle hbox{The sum of two odd numbers is an even number} (2)$

can also be not a first-order sentence; one would as a substitute have to put in writing one thing like

$displaystyle hbox{For all odd numbers } x, y, hbox{ the number } x+y hbox{ is even} (3)$

or

$displaystyle hbox{For all odd numbers } x,y hbox{ there exists an even number } z (4)$

$displaystyle hbox{ such that } x+y=z$

as a substitute. These reformulations should not all that tough to decipher, however they do have the aesthetically displeasing impact of cluttering an argument with short-term variables equivalent to ${x,y,z}$ that are used as soon as after which discarded.

One other instance of partially specified notation is the innocuous ${ldots}$ notation. For example, the assertion

$displaystyle pi=3.14ldots,$

when written formally utilizing first-order logic, would change into one thing like

$displaystyle pi = 3 + frac{1}{10} + frac{4}{10^2} + sum_{n=3}^infty frac{a_n}{10^n} hbox{ for some sequence } (a_n)_{n=3}^infty$

$displaystyle hbox{ with } a_n in {0,1,2,3,4,5,6,7,8,9} hbox{ for all } n,$

which isn’t precisely a sublime reformulation. Equally with statements equivalent to

$displaystyle tan x = x + frac{x^3}{3} + ldots hbox{ for } |x| < pi/2$

or

$displaystyle tan x = x + frac{x^3}{3} + O(|x|^5) hbox{ for } |x| < pi/2.$

Beneath the fold I’ll attempt to assign a proper which means to partially specified expressions equivalent to (1), as an example permitting one to condense (2), (3), (4) to only

$displaystyle hbox{odd} + hbox{odd} = hbox{even}.$

When mixed with one other frequent (however typically implicit) extension of first-order logic, specifically the flexibility to purpose utilizing ambient parameters, we change into in a position to formally introduce asymptotic notation such because the big-O notation ${O()}$ or the little-o notation ${o()}$. We are going to clarify how to do that on the finish of this submit.

— 1. Partially specified objects —

Let’s attempt to assign a proper which means to partially specified mathematical expressions. We now permit expressions ${X}$ to not essentially be a single (utterly specified) mathematical object, however extra usually {a partially} specified occasion of a class ${{X}}$ of mathematical objects. For example, ${pm 3}$ denotes {a partially} specified occasion of the category ${{ pm 3 } = { 3, -3}}$ of numbers consisting of ${3}$ and ${-3}$; that’s to say, a quantity which is both ${-3}$ and ${+3}$. A single utterly specified mathematical object, such because the quantity ${3}$, can now be additionally interpreted because the (distinctive) occasion of a category ${{ 3 }}$ consisting solely of ${3}$. Right here we’re utilizing set notation to explain courses, ignoring for now the well-known challenge from Russell’s paradox that some extraordinarily massive courses are technically not units, as this isn’t the principle focus of our dialogue right here.

For causes that may change into clearer later, we are going to use the image ${==}$ relatively than ${=}$ to indicate the assertion that two partially specified objects vary throughout precisely the identical class. That’s to say, we use ${X==Y}$ as a synonym for ${{X} = {Y}}$. Thus, as an example, it isn’t the case that ${3 == pm 3}$, as a result of the category ${{pm 3}}$ has situations that ${{3}}$ doesn’t.

Any finite sequence ${x_1,dots,x_n}$ of objects can be seen as {a partially} specified occasion of a category ${{x_1,dots,x_n}}$, which I’ll denote $dots$ in analogy with common expressions, thus we now even have a brand new title ${dots}$ for the set ${{x_1,dots,x_n}}$. (One might in truth suggest ${x_1,dots,x_n}$ because the notation for $dots$, as is finished implicitly in assertions equivalent to “${P(n)}$ is true for ${n=1,2,3}$“, however this creates notational conflicts with different makes use of of the comma in arithmetic, such because the notation ${(x_1,dots,x_n)}$ for an ${n}$-tuple, so I’ll use the common expression image  right here to keep away from ambiguity.) For example, $5$ denotes an partially specified occasion from the category ${5={1,3,5}}$, that’s to say a quantity which is both ${1}$, ${3}$, and ${5}$. Equally, we now have

$displaystyle pm 3 == 3|-3 == -3|3$

and

$displaystyle 3 == 3|3.$

One can mimic set builder notation and denote {a partially} specified occasion of a category ${{mathcal C}}$ as ${(x: x in {mathcal C})}$ (or one can substitute ${x}$ by some other variable title one pleases); equally, one can use ${(x in A: P(x))}$ to indicate {a partially} specified factor of ${A}$ that obeys the predicate ${P(x)}$. Thus as an example

$displaystyle (n in {bf Z}: n hbox{ odd})$

would denote {a partially} specified odd quantity. By a slight abuse of notation, we are able to abbreviate ${(x in A: P(x))}$ as ${(x: P(x))}$ or just ${P}$, if the area ${A}$ of ${x}$ is implicitly understood from context. For example, underneath this conference,

$displaystyle hbox{odd} == (n in {bf Z}: n hbox{ odd} )$

refers to an partially specified odd integer, whereas

$displaystyle hbox{integer} == (n: n in {bf Z})$

refers to {a partially} specified integer. Underneath these conventions, it now turns into theoretically potential that the category one is drawing from turns into empty, and instantiation turns into vacuous. For example, with our conventions, ${hbox{odd perfect}}$ refers to {a partially} specified odd good quantity, which is conjectured to not exist. Because it seems, our notation can deal with situations of empty courses with out issue (mainly due to the idea of a vacuous reality), however we are going to keep away from dwelling on this edge case a lot right here since this idea just isn’t intuitive for freshmen. (But when one does wish to confront this risk, one can use a logo equivalent to ${perp}$ to indicate an occasion of the empty class, i.e., an object that has no specs in anyway.

The image  launched above can now be prolonged to be a binary operation on partially specified objects, outlined by the formulation

$displaystyle y == {x} cup {y}.$

Thus as an example

$displaystyle hbox{odd} | hbox{even} == hbox{integer}$

and

$displaystyle x pm y == (x+y) | (x-y).$

One can then outline different logical operations on partially specified objects if one needs. For example, we might outline an “and” operator ${&}$ by defining

$displaystyle { x & y } == {x} cap {y}.$

Thus as an example

$displaystyle (5 pm 3) & (10 pm 2) == 8,$

$displaystyle hbox{odd} & hbox{perfect} == hbox{odd perfect}$

and

$displaystyle hbox{odd} & hbox{even} == perp.$

(Right here we’re deviating from the syntax of normal expression, however I’m not insisting that everything of mathematical notation conform to that syntax, and in any occasion common expressions don’t seem to have a direct analogue of this “and” operation.) We depart it to the reader to suggest different logical operations on partially specified objects, although the “or” operator  and the “and” operator ${&}$ will suffice for our functions.

Any operation on utterly specified mathematical objects ${x}$ could be prolonged to partially specified of mathematical objects ${X}$ by making use of that operation to arbitrary situations of the category ${{X}}$, with the conference that if a category seems a number of instances in an expression, then we permit every occasion of that class to take completely different values. For example, if ${x, y}$ are partially specified numbers, we are able to outline ${x+y}$ to be the category of all numbers fashioned by including an occasion of ${x}$ to an occasion of ${y}$ (that is analogous to the operation of Minkowski addition for units, or interval arithmetic in numerical evaluation). For instance,

$displaystyle 5 pm 3 == 5 + (pm 3) == 2| 8$

and

$displaystyle pm 5 pm 3 == (pm 5) + (pm 3) == -8|-2| 2|8$

(recall that there isn’t any requirement that the indicators right here align). Notice that

$displaystyle (pm 3)^2 == 9$

however that

$displaystyle (pm 3) times (pm 3) == pm 9.$

So we now see the primary signal that some care must be taken with the legislation of substitution; we now have

$displaystyle x times x = x^2$

however we do not have

$displaystyle (pm 3) times (pm 3) == (pm 3)^2.$

Nonetheless, the legislation of substitution works superb so long as the variable being substituted seems precisely as soon as on each side of the equation.

One can have an unbounded variety of partially specified situations of a category, as an example ${sum_{i=1}^n pm 1}$ would be the class of all integers between ${-n}$ and ${+n}$ with the identical parity as ${n}$.

Comment 1 When working with indicators ${pm}$, one typically needs to maintain all indicators aligned, with ${mp}$ denoting the signal reverse to ${pm}$, thus as an example with this notation one would have the geometric collection formulation

$displaystyle (1 pm varepsilon)^{-1} = 1 mp varepsilon + varepsilon^2 mp varepsilon^3 dots$

every time $< 1$. Nonetheless, this notation is tough to position within the framework used on this weblog submit with out inflicting further confusion, and as such we is not going to focus on it additional right here. (The syntax of common expressions does have some instruments for encoding this type of alignment, however in first-order logic we even have the peerlessly servicable device of named variables and quantifiers (or plain outdated mathematical English) to take action additionally.)

One can even lengthen binary relations, equivalent to ${<}$ or ${=}$, to partially specified objects, by requiring that each occasion on the left-hand facet of the relation pertains to some occasion on the right-hand facet (thus binary relations change into ${Pi_2}$ sentences). Once more, if class is instantiated a number of instances, we permit completely different appearances to correspond to completely different courses. For example, the assertion ${5 pm 3 leq 8}$ is true, as a result of each occasion of ${5 pm 3}$ is lower than or equal to ${8}$:

$displaystyle 5 pm 3 == (2|8) leq 8.$

However the assertion ${5 pm 3 leq 6}$ is fake. Equally, the assertion ${8 = 5 pm 3}$ is true, as a result of ${8}$ is an occasion of ${5 pm 3}$:

$displaystyle 8 = (2|8) == 5 pm 3.$

The assertion ${5 pm 3 < 6 pm 3}$ can also be true, as a result of each occasion of ${5 pm 3}$ is lower than some occasion of ${6 pm 3}$:

$displaystyle 5 pm 3 == (2|8) < (3|9) == 6 pm 3.$

The connection between {a partially} specified consultant $dots$ of a category ${dots}$ can then be summarised as

$displaystyle x_1|dots|x_n in dots = {x_1,dots,x_n}.$

Notice how this conference treats the left-hand facet and right-hand facet of a relation involving partially specified expressions asymmetrically. Specifically, for partially specified expressions ${x, y}$, the relation ${x=y}$ is not equal to ${y=x}$; the previous states that each occasion of ${x}$ can also be an occasion of ${y}$, whereas the latter asserts the converse. For example, ${3 = pm 3}$ is a real assertion, however ${pm 3 = 3}$ is a false assertion (a lot as “${3}$ is prime” is a real assertion (or “${3 = hbox{prime}}$ in our notation), however “primes are ${3}$” (or ${hbox{prime} = 3}$ in our notation) is fake). Specifically, we see a distinction between equality ${=}$ and equivalence ${==}$; certainly, ${x == y}$ holds if and provided that ${x=y}$ and ${y=x}$. However, as could be simply checked, the next three fundamental legal guidelines of arithmetic stay legitimate for partially specified expressions ${x,y,z}$:

These conventions for partially specified expressions align nicely with casual mathematical English. For example, as mentioned within the introduction, the assertion

$displaystyle hbox{The sum of two odd numbers is an even number}$

can now be expressed as

$displaystyle hbox{odd} + hbox{odd} = hbox{even}.$

Equally, the even Goldbach’s conjecture can now be acknowledged as

$displaystyle hbox{even number} & (hbox{greater than } 2) = hbox{prime} + hbox{prime},$

whereas the Archimedean property of the reals could be reformulated because the assertion that

$displaystyle hbox{real} leq hbox{natural number} times varepsilon$

for any ${varepsilon > 0}$. Notice additionally how the equality image ${=}$ for partially specified expressions corresponds nicely with the a number of meanings of the phrase “is” in English (take into account as an example “two plus two is 4”, “4 is even”, and “the sum of two odd numbers is even”); the set-theoretic counterpart of this idea could be a type of amalgam of the unusual equality relation ${=}$, the inclusion relation ${in}$, and the subset relation ${subset}$.

There are nevertheless numerous caveats one has to bear in mind, although, when coping with formulation involving partially specified objects. The primary, which has already been talked about, is an absence of symmetry: ${x=y}$ doesn’t suggest ${y=x}$; equally, ${x doesn’t suggest ${y>x}$. The second is that negation behaves very unusually, a lot in order that one ought to mainly keep away from utilizing partially specified notation for any sentence that may finally get negated. For example, observe that the statements ${3 = pm 3}$ and ${3 neq pm 3}$ are each true, whereas ${pm 3 = 3}$ and ${pm 3 neq 3}$ are each false. In actual fact, the negation of such statements as ${x=y}$ or ${x leq y}$ involving partially specified objects often can’t be expressed succinctly in partially specified notation, and one should resort to utilizing a number of quantifiers as a substitute. (Within the language of the arithmetic hierarchy, the negation of a ${Pi_2}$ sentence is a ${Sigma_2}$ sentence, relatively than an one other ${Pi_2}$ sentence.)

One other subtlety, already talked about earlier, arises from our alternative to permit completely different instantiations of the identical class to check with completely different situations, specifically that the legislation of common instantiation doesn’t at all times work if the image being instantiated happens greater than as soon as on the left-hand facet. For example, the id

$displaystyle x - x = 0$

is after all true for all actual numbers ${x}$, but when one naively substitutes within the partially specified expression ${pm 1}$ for ${x}$ one obtains the declare

$displaystyle pm 1 - (pm 1) = 0$

which is a false assertion underneath our conventions (as a result of the 2 situations of the signal ${pm 1, pm 1}$ don’t have to match). Nonetheless, there isn’t any drawback with repeated instantiations on the right-hand facet, so long as there’s at most a single occasion on the left-hand facet. For example, beginning with the id

$displaystyle x = 2x - x$

we are able to validly instantiate the partially specified expression ${pm 1}$ for ${x}$ to acquire

$displaystyle pm 1 = 2(pm 1) - (pm 1).$

A standard observe that helps keep away from these kinds of points is to maintain the partially specified portions on the right-hand facet of 1’s relations, or if one is working with a series of relations equivalent to ${x leq y leq z leq w}$, to maintain the partially specified portions away from the left-most facet (in order that ${y}$, ${z}$, and ${w}$ are allowed to be multi-valued, however not ${x}$). This doesn’t robotically forestall all points (as an example, one should be tempted to “cancel” an expression equivalent to ${pm 1 - (pm 1)}$ that may come up partway by way of a series of relations), however it may possibly scale back the possibility of unintentionally making an error.

One can after all translate any formulation that includes partially specified objects right into a extra orthodox first-order logic sentence by inserting the related quantifiers within the applicable locations – however observe that the variables utilized in quantifiers are at all times utterly specified, relatively than partially specified. For example, if one expands “${x = pm y}$” (for some utterly specified portions ${x,y}$) as “there exists ${epsilon = pm 1}$ such that ${x = epsilon y}$“, the amount ${epsilon}$ is totally specified; it isn’t the partially specified ${pm 1}$. (If ${x}$ or ${y}$ had been additionally partially specified, the first-order translation of the expression “${x = pm y}$” could be extra difficult, as it will want extra quantifiers.)

One can mix partially specified notation with set builder notation, as an example the set ${{ x in {bf R}: x = pm 10 pm 1 }}$ is simply the four-element set ${{ -11, -9, +9, +11}}$, since these are certainly the 4 actual numbers ${x}$ for which the formulation ${x = pm 10 pm 1}$ is true. I’d nevertheless keep away from combining notably heavy makes use of of set-theoretic notation with partially specified notation, as it might trigger confusion.

Our examples above of partially specified objects have been drawn from quantity programs, however one can use this notation for different courses of objects as nicely. For example, inside the class of capabilities ${f: {bf R} rightarrow {bf R}}$ from the reals to themselves, one could make assertions like

$displaystyle hbox{increasing} + hbox{increasing} == hbox{increasing}$

the place ${hbox{increasing}}$ is the category of monotone rising capabilities; equally we now have

$displaystyle - hbox{increasing} == hbox{decreasing}$

$displaystyle hbox{increasing} | hbox{decreasing} == hbox{monotone}$

$displaystyle hbox{positive increasing} cdot hbox{negative increasing} = hbox{negative decreasing}$

$displaystyle hbox{bounded} & hbox{monotone} = hbox{converges at infinity}$

$displaystyle hbox{analytic} = hbox{smooth} = hbox{differentiable} = hbox{continuous} = hbox{measurable}$

$displaystyle hbox{continuous} / hbox{continuous nonvanishing} = hbox{continuous}$

$displaystyle hbox{square integrable} cdot hbox{square integrable} == hbox{absolutely integrable}$

$displaystyle {mathcal F} hbox{square integrable} == hbox{square integrable}$

(with ${{mathcal F}}$ denoting the Fourier rework) and so forth. Or, within the class of topological areas, we now have as an example

$displaystyle hbox{compact} & hbox{discrete} == hbox{finite},$

$displaystyle hbox{continuous}(hbox{compact}) = hbox{compact},$

and

$displaystyle pi_1( hbox{simply connected} ) = hbox{trivial group}$

whereas conversely the classifying house building offers (amongst different issues)

$displaystyle hbox{group} == pi_1( hbox{topological space} ).$

Limiting to metric areas, we now have the well-known equivalences

$displaystyle hbox{compact} == hbox{sequentially compact} == hbox{complete} & hbox{totally bounded}.$

Notice in the previous few examples, we’re genuinely working with correct courses now, relatively than units. Because the above examples hopefully exhibit, mathematical sentences involving partially specified objects can align very nicely with the syntax of casual mathematical English, so long as one takes care to differentiate the uneven equality relation ${=}$ from the symmetric equivalence relation ${==}$.

For example of how such notation is likely to be built-in into an precise mathematical argument, we show a easy and well-known topological outcome on this notation:

Proposition 2 Let ${f: X rightarrow Y}$ be a steady bijection from a compact house ${X}$ to a Hausdorff house ${Y}$. Then ${f}$ is a homeomorphism.

Proof: We’ve got

$displaystyle f( hbox{open subset of }X) = f(X backslash hbox{closed subset of } X)$

$displaystyle = Y backslash f(hbox{closed subset of } X)$

(since ${f}$ is a bijection)

$displaystyle = Y backslash f(hbox{compact subset of } X)$

(since ${X}$ is compact)

$displaystyle = Y backslash (hbox{compact subset of } Y)$

(since ${f}$ is steady)

$displaystyle = Y backslash (hbox{closed subset of } Y)$

(since ${Y}$ is Hausdorff)

$displaystyle = hbox{open subset of } Y.$

Thus ${f}$ is open, therefore ${f^{-1}}$ is steady. Since ${f}$ was already steady, ${f}$ is a homeomorphism. $Box$

— 2. Working with parameters —

To be able to introduce asymptotic notation, we might want to mix the above conventions for partially specified objects with separate frequent adjustment to the grammar of mathematical logic, specifically the flexibility to work with ambient parameters. This can be a particular case of the extra common state of affairs of deciphering logic over an elementary topos, however we is not going to develop the overall principle of topoi right here. As this adjustment is orthogonal to the changes within the previous part, we will for simplicity revert again quickly to the normal notational conventions for utterly specified objects, and never check with partially specified objects in any respect on this part.

Within the formal language of first-order logic, variables equivalent to ${x,n,X}$ are understood to vary in varied domains of discourse (e.g., ${x}$ might vary in the true numbers, ${n}$ might vary within the pure numbers, and ${X}$ within the class of units). One can then assemble varied formulation, equivalent to ${P(x,n,X)}$, wherein contain zero or extra enter variables (often known as free variables), and have a reality worth in ${{ hbox{true}, hbox{false} }}$ for any given alternative of free variables. For example, ${P(x,n,X)}$ is likely to be true for some triples ${x in {bf R}, n in {bf N}, X in mathrm{Set}}$, and false for others. One can create formulation both by making use of relations to numerous phrases (e.g., making use of the inequality relation ${leq}$ to the phrases ${x+y, z+w}$ offers the formulation ${x+y leq z+w}$ with free variables ${x,y,z,w}$), or by combining present formulation along with logical connectives (equivalent to ${wedge, vee, not, implies}$) or quantifiers (${forall}$ and ${exists}$). Formulation with no free variables (e.g. ${forall x forall y: x+y=y+x}$) are often known as sentences; as soon as one fixes the domains of discourse, sentences are both true or false. We are going to check with this first-order logic as orthodox first-order logic, to differentiate it from the parameterised first-order logic we will shortly introduce.

We now generalise this setup by working relative to some ambient set of parameters – some finite assortment of variables that vary in some specified units (or courses) and could also be topic to a number of constraints. For example, one could also be working with some pure quantity parameters ${n,N in {bf N}}$ with the constraint ${n leq N}$; we are going to maintain this explicit alternative of parameters as a working instance for the dialogue under. As soon as one selects these parameters, all different variables into account should not simply single components of a given area of discourse, however relatively a household of such components, parameterised by the given parameters; we are going to refer to those variables as parameterised variables to differentiate them from the orthodox variables of first-order logic. For example, with the above parameters, when one refers to an actual quantity ${x}$, one now refers not simply to a single factor of ${{bf R}}$, however relatively to a perform ${x: (n,N) mapsto x(n,N)}$ that assigns an actual quantity ${x(n,N)}$ to every alternative of parameters ${(n,N)}$; we are going to check with such a perform ${x: (n,N) mapsto x(n,N)}$ as a parameterised actual, and sometimes write ${x = x(n,N)}$ to point the dependence on parameters. Every of the ambient parameters can after all be seen as a parameterised variable, thus as an example ${n}$ can (by abuse of notation) be seen because the parameterised pure quantity that maps ${(n,N)}$ to ${n}$ for every alternative ${(n,N)}$ of parameters.

The particular ambient set of parameters, and the constraints on them, tends to differ as one progresses by way of varied levels of a mathematical argument, with these adjustments being introduced by varied commonplace phrases in mathematical English. For example, if in some unspecified time in the future a proof accommodates a sentence equivalent to “Let ${N}$ be a pure quantity”, then one is implicitly including ${N}$ to the set of parameters; if one later states “Let ${n}$ be a pure quantity such that ${n leq N}$“, then one is implicitly additionally including ${n}$ to the set of parameters and imposing a brand new constraint ${n leq N}$. If one divides into circumstances, e.g., “Suppose now that ${n}$ is odd… now suppose as a substitute that ${n}$ is even”, then the constraint that ${n}$ is odd is quickly imposed, then changed with the complementary constraint that ${n}$ is even, then presumably the 2 circumstances are mixed and the constraint is eliminated utterly. A bit extra subtly, parameters can disappear on the conclusion of a portion of an argument (e.g., on the finish of a proof of a lemma or proposition wherein the parameter was launched), changed as a substitute by a abstract assertion (e.g., “To summarise, we now have proven that every time ${n,N}$ are pure numbers with ${n leq N}$, then …”) or by the assertion of the lemma or proposition in whose proof the parameter was quickly launched. One can even take away a variable from the set of parameters by specialising it to a particular worth.

Any time period that’s well-defined for particular person components of a website, can also be well-defined for parameterised components of the area by pointwise analysis. For example, if ${x = x(n,N)}$ and ${y = y(n,N)}$ are parameterised actual numbers, one can kind the sum ${x+y = (x+y)(n,N)}$, which is one other parameterised actual quantity, by the formulation

$displaystyle (x+y)(n,N) := x(n,N) + y(n,N).$

Given a relation between phrases involving parameterised variables, we are going to interpret the relation as being true (for the given alternative of parameterised variables) if it holds for all obtainable decisions of parameters ${(n,N)}$ (obeying all ambient constraints), and false in any other case (i.e., if it fails for at the least one alternative of parameters). For example, the relation

$displaystyle x leq y$

could be interpreted as true if one has ${x(n,N) leq y(n,N)}$ for all alternative of parameters ${(n,N)}$, and false in any other case.

Comment 3 Within the framework of nonstandard evaluation, the interpretation of reality is barely completely different; the above relation could be thought of true if the set of parameters for which the relation holds lies in a given (non-principal) ultrafilter. The principle purpose for doing that is that it permits for a considerably extra common switch precept than the one obtainable on this setup; nevertheless we is not going to focus on the nonstandard evaluation framework additional right here. (Our setup right here is nearer in spirit to the “low cost” model of nonstandard evaluation mentioned in this earlier submit.)

With this conference an annoying subtlety emerges with regard to boolean connectives (conjunction ${wedge}$, disjunction ${vee}$, implication ${implies}$, and negation ${neg}$), in that one now has to differentiate between inside interpretation of the connectives (making use of the connectives pointwise for every alternative of parameters earlier than quantifying over parameters), and exterior interpretation (making use of the connectives after quantifying over parameters); there’s not a common switch precept from the previous to the latter. For example, the sentence

$displaystyle n hbox{ is odd}$

is fake in parameterised logic, since not each alternative of parameter ${n}$ is odd. However, the inner negation

$displaystyle neg( n hbox{ is odd})$

or equivalently

$displaystyle n hbox{ is even}$

can also be false in parameterised logic, since not each alternative of parameter ${n}$ is even. To place it one other means, the inner disjunction

$displaystyle (n hbox{ is odd}) vee (n hbox{ is even})$

is true in parameterised logic, however the person statements ${n hbox{ is odd}}$ and ${n hbox{ is even}}$ should not (so the exterior disjunction of those statements is fake). To keep up this distinction, I’ll reserve the boolean symbols (${vee, wedge, implies, neg}$) for inside boolean connectives, and reserve the corresponding English connectives (“and”, “or”, “implies”, “not”) for exterior boolean connectives.

Due to this subtlety, orthodox dichotomies and trichotomies don’t robotically switch over to the parameterised setting. Within the orthodox pure numbers, a pure quantity ${n}$ is both odd and even; however a parameterised pure quantity ${n}$ may very well be neither even on a regular basis nor odd on a regular basis. Equally, given two parameterised actual numbers ${x,y}$, it may very well be that not one of the statements ${x, ${x=y}$, ${x>y}$ are true on a regular basis. Nonetheless, one can get better these dichotomies or trichotomies by subdividing the parameter house into circumstances. For example, within the latter instance, one might divide the parameter house into three areas, one the place ${x is at all times true, one the place ${x=y}$ is at all times true, and one the place ${x>y}$ is at all times true. If one can show a single assertion in all three subregions of parameter house, then after all this means the assertion within the unique parameter house. So in observe one can nonetheless use dichotomies and trichotomies in parameterised logic, as long as one is prepared to subdivide the parameter house into circumstances at varied levels of the argument and recombine them later.

There’s a comparable distinction between inside quantification (quantifying over orthodox variables earlier than quantifying over parameters), and exterior quantification (quantifying over parameterised variables after quantifying over parameters); we are going to once more preserve this distinction by reserving the symbols ${forall, exists}$ for inside quantification and the English phrases “for all” and “there exists” for exterior quantification. For example, the assertion

$displaystyle x+y = y+x hbox{ for all } x, y in {bf R}$

when interpreted in parameterised logic, signifies that for all parameterised reals ${x: (n,N) mapsto x(n,N)}$ and ${y: (n,N) mapsto y(n,N)}$, the assertion ${x(n,N)+ y(n,N) = y(n,N) + x(n,N)}$ holds for all ${n,N}$. On this case it’s clear that this assertion is true and is in truth equal to the orthodox sentence ${forall x,y in {bf R}: x+y = y+x}$. Extra usually, we do have a restricted switch precept in that any true sentence in orthodox logic that includes solely quantifiers and no boolean connectives, will switch over to parameterised logic (at the least if one is prepared to make use of the axiom of alternative freely, which we are going to do on this submit). We illustrate this (considerably arbitrarily) with the Lagrange 4 sq. theorem

$displaystyle forall m in {bf N} exists a,b,c,d in {bf N}: m = a^2+b^2+c^2+d^2. (5)$

This sentence, true in orthodox logic, implies the parameterised assertion that for each parameterised pure quantity ${m: (n,N) mapsto m(n,N)}$, there exist parameterised pure numbers ${a: (n,N) mapsto a(n,N)}$, ${b: (n,N) mapsto b(n,N)}$, ${c: (n,N) mapsto c(n,N)}$, ${d: (n,N) mapsto d(n,N)}$, such that ${m(n,N) = a(n,N)^2 + b(n,N)^2 + c(n,N)^2 + d(n,N)^2}$ for all alternative of parameters ${(n,N)}$. To see this, we are able to Skolemise the four-square theorem (5) to acquire capabilities ${tilde a: m mapsto tilde a(m)}$, ${tilde b: m mapsto tilde b(m)}$, ${tilde c: m mapsto tilde c(m)}$, ${tilde d: m mapsto tilde d(m)}$ such that

$displaystyle m = tilde a(m)^2 + tilde b(m)^2 + tilde c(m)^2 + tilde d(m)^2$

for all orthodox pure numbers ${m}$. Then to acquire the parameterised declare, one merely units ${a(n,N) := tilde a(m(n,N))}$, ${b(n,N) := tilde b(m(n,N))}$, ${c(n,N) := tilde c(m(n,N))}$, and ${d(n,N) := tilde d(m(n,N))}$. Equally for different sentences that keep away from boolean connectives. (There are some additional courses of sentences that use boolean connectives in a restricted style that can be transferred, however we is not going to try to provide a whole classification of such courses right here; on the whole it’s higher to work out some examples of switch by hand to see what could be safely transferred and which of them can not.)

Thus far this setup just isn’t considerably rising the expressiveness of 1’s language, as a result of any assertion constructed to this point in parameterised logic could be rapidly translated to an equal (and solely barely longer) assertion in orthodox logic. Nonetheless, one positive aspects extra expressive energy when one permits a number of of the parameterised variables to have a specified sort of dependence on the parameters, and particularly relying solely on a subset of the parameters. For example, one might introduce an actual quantity ${C}$ which is an absolute fixed within the sense that it doesn’t rely upon both of the parameters ${n,N}$; these are a particular sort of parameterised actual, in a lot the identical means that fixed capabilities are a particular sort of perform. Or one might take into account a parameterised actual ${a = a(N)}$ that is determined by ${N}$ however not on ${n}$, or a parameterised actual ${b = b(n)}$ that is determined by ${n}$ however not on ${N}$. (One might additionally place different varieties of constraints on parameterised portions, equivalent to steady or measurable dependence on the parameters, however we is not going to take into account these variants right here.)

By quantifying over these restricted courses of parameterised capabilities, one can now effectively write down a wide range of statements in parameterised logic, of sorts that really happen fairly continuously in evaluation. For example, we are able to outline a parameterised actual ${x = x(n,N)}$ to be bounded if there exists an absolute fixed ${C}$ such that $x$; one can after all write this assertion equivalently in orthodox logic as

$displaystyle exists C forall n,N: ((n leq N) implies (|x(n,N)| leq C).$

One can even outline the stronger notion of ${x}$ being ${1}$-bounded, by which we imply $leq 1$, or in orthodox logic

$displaystyle forall n,N: ((n leq N) implies (|x(n,N)| leq 1).$

In the wrong way, we are able to assert the weaker assertion that ${x = x(n,N)}$ is bounded in magnitude by a amount ${C = C(N)}$ that is determined by ${N}$ however not on ${n}$; in orthodox logic this turns into

$displaystyle forall N exists C forall n leq N: |x(n,N)| leq C.$

As earlier than, every of the instance statements in parameterised logic could be simply translated into an announcement in conventional logic. However, take into account the assertion {that a} parameterised actual ${x = x(n,N)}$ is expressible because the sum ${x = y + z}$ of a amount ${y = y(n)}$ relying solely on ${n}$ and a amount ${z = z(N)}$ relying on ${N}$. (For example, the parameterised actual ${x = (N+n)(N-n) = N^2 - n^2}$ could be of this type, however the parameterised actual ${x = Nn}$ can not.) Now it turns into considerably more durable to translate this assertion into first-order logic! One can nonetheless achieve this pretty readily utilizing second-order logic (wherein one is also permitted to quantify over operators in addition to variables), or through the use of the language of set principle (in order that one can quantify over a set of capabilities of varied types). Certainly if one is parameterising over correct courses relatively than units, it’s even potential to create sentences in parameterised logic which might be non-firstorderisable; see this earlier weblog submit for extra dialogue.

One other delicate distinction that arises as soon as one has parameters is the excellence between “inside” or `parameterised” units (units relying on the selection of parameters), and exterior units (units of parameterised objects). For example, the interval ${[n,N]}$ is an inside set – it assigns an orthodox set ${{ x in {bf R}: n leq x leq N }}$ of reals to every alternative of parameters ${(n,N)}$; components of this set encompass all of the parameterised reals ${x = x(n,N)}$ such that ${n leq x(n,N) leq N}$ for all ${n,N}$. However, the gathering ${{mathcal O}(1)}$ of bounded reals – i.e., parameterised reals ${x = x(n,N)}$ such that there’s a fixed ${C}$ for which $x(n,N)$ for all decisions of parameters ${(n,N)}$ – just isn’t an inside set; it doesn’t come up from taking an orthodox set of reals ${X(n,N)}$ for every alternative of parameters. (Certainly, if it did achieve this, since each fixed actual is bounded, every ${X(n,N)}$ would comprise all of ${{bf R}}$, which might make ${{mathcal O}(1)}$ the set of all parameterised reals, relatively than simply the bounded reals.) To keep up this distinction, we are going to reserve set builder notation equivalent to ${{ x in X: P(x) }}$ for internally outlined units, and use English phrases (equivalent to “the gathering of all bounded parameterised reals”) to indicate exterior units. Specifically, we don’t make sense of such expressions as ${{ x in {bf R}: x hbox{ bounded} }}$ (or ${{ x in {bf R}: x = O(1) }}$, as soon as asymptotic notation is launched). Basically, I’d suggest that one avoids combining asymptotic notation with heavy use of set theoretic notation, except one is aware of precisely what one is doing.

— 3. Asymptotic notation —

We now concurrently introduce the 2 extensions to orthodox first order logic mentioned in earlier sections. In different phrases,

1. We allow the usage of partially specified mathematical objects in a single’s mathematical statements (and particularly, on both facet of an equation or inequality).
2. We permit all portions to rely upon a number of of the ambient parameters.

Specifically, we permit for the usage of partially specified mathematical portions that additionally rely upon a number of of the ambient parameters. This permits us now formally introduce asymptotic notation. There are a lot of variants of this notation, however right here is one set of asymptotic conventions that I for one like to make use of:

Definition 4 (Asymptotic notation) Let ${X}$ be a non-negative amount (probably relying on a number of of the ambient parameters).

• We use ${O(X)}$ to indicate {a partially} specified amount within the class of portions ${Y}$ (that may rely upon a number of of the ambient parameters) that obeys the sure $leq CX$ for some absolute fixed ${C > 0}$. Extra usually, given some ambient parameters ${lambda_1,dots,lambda_k}$, we use ${O_{lambda_1,dots,lambda_k}(X)}$ to indicate {a partially} specified amount within the class of portions ${Y}$ that obeys the sure ${|Y| leq C_{lambda_1,dots,lambda_k}(X)}$ for some fixed ${C > 0}$ that may rely upon the ${lambda_1,dots,lambda_k}$ parameters, however not on the opposite ambient parameters.
• We additionally use ${X ll Y}$ or ${Y gg X}$ as a synonym for ${X = O(Y)}$, and ${X asymp Y}$ as a synonym for ${X ll Y ll X}$. (In some fields of research, ${X lesssim Y}$, ${X gtrsim Y}$, and ${X sim Y}$ are used as a substitute of ${X ll Y}$, ${X gg Y}$, and ${X asymp Y}$.)
• If ${x}$ is a parameter and ${x_*}$ is a limiting worth of that parameter (i.e., the parameter house for ${x}$ and ${x_*}$ each lie in some topological house, with ${x_*}$ an adherent level of that parameter house), we use ${o_{x rightarrow x_*}(X)}$ to indicate {a partially} specified amount within the class of portions ${Y}$ (that may rely upon ${x}$ in addition to the opposite the ambient parameters) that obeys a sure of the shape $leq c(x) X$ for all ${x}$ in some neighborhood of ${x_*}$, and for some amount ${c(x) > 0}$ relying solely on ${x}$ such that ${c(x) rightarrow 0}$ as ${x rightarrow x_*}$. Extra usually, given some additional ambient parameters ${lambda_1,dots,lambda_k}$, we use ${o_{x rightarrow x_*; lambda_1,dots,lambda_k}(X)}$ to indicate {a partially} specified amount within the class of portions ${Y}$ that obey a sure of the shape ${|Y| leq c_{lambda_1,dots,lambda_k}(x) X}$ for all ${x}$ in a neighbourhood of ${x_*}$ (which may additionally rely upon ${lambda_1,dots,lambda_k}$) the place ${c_{lambda_1,dots,lambda_k}(x) > 0}$ is determined by ${lambda_1,dots,lambda_k,x}$ and goes to zero as ${x rightarrow x_*}$. (On this extra common kind, the restrict level ${x_*}$ is now additionally permitted to rely upon the parameters ${lambda_1,dots,lambda_k}$).

Generally (by explicitly declaring one will achieve this) one suppresses the dependence on a number of of the extra parameters ${lambda_1,dots,lambda_k}$, and/or the asymptotic restrict ${x rightarrow x_*}$, with a purpose to scale back litter.

(That is the “non-asymptotic” type of the ${O()}$ notation, wherein the bounds are assumed to carry for all values of parameters. There’s additionally an “asymptotic” variant of this notation that’s generally utilized in some fields, wherein the bounds in query are solely assumed to carry in some neighbourhood of an asymptotic worth ${x_*}$, however we is not going to give attention to that variant right here.)

Thus, as an example, ${n}$ is a free variable taking values within the pure numbers, and ${f(n), g(n), h(n)}$ are portions relying on ${n}$, then the assertion ${f(n) = g(n) + O(h(n))}$ denotes the assertion that ${f(n) = g(n) + k(n)}$ for all pure numbers ${n}$, the place ${k(n)}$ is one other amount relying on ${n}$ such that $leq C h(n)$ for all ${n}$, and a few absolute fixed ${C}$ unbiased of ${n}$. Equally, ${f(n) leq g(n) + O(h(n))}$ denotes the assertion that ${f(n) leq g(n) + k(n)}$ for all pure numbers ${n}$, the place ${k(n)}$ is as above.

For a barely extra refined instance, take into account the assertion

$displaystyle O(n) + O(n^2) leq O(n^2), (6)$

the place once more ${n}$ is a free variable taking values within the pure numbers. Utilizing the conventions for multi-valued expressions, we are able to translate this expression into first-order logic because the assertion that every time ${f(n), g(n)}$ are portions relying on ${n}$ such that there exists a relentless ${C_1}$ such that $f(n)$ for all pure numbers ${n}$, and there exists a relentless ${C_2}$ such that $leq C_2 n^2$ for all pure numbers ${n}$, then we now have ${f(n)+g(n) leq h(n)}$ for all ${n}$, the place ${h}$ is a amount relying on pure numbers ${n}$ with the property that there exists a relentless ${C_3}$ such that $h(n)$. Notice that the first-order translation of (6) is considerably longer than (6) itself; and as soon as one positive aspects familiarity with the big-O notation, (6) could be deciphered rather more rapidly than its formal first-order translation.

It may be instructive to rewrite some fundamental notions in evaluation on this type of notation, simply to get a barely completely different perspective. For example, if ${f: {bf R} rightarrow {bf R}}$ is a perform, then:

Comment 5 One can outline further variants of asymptotic notation equivalent to ${Omega(X)}$, ${omega(X)}$, or ${Theta(X)}$; see this wikipedia web page for some examples. See additionally the associated notion of “sufficiently massive” or “small enough”. Nonetheless, one can often reformulate such notations by way of the above-mentioned asymptotic notations with a bit of little bit of rearranging. For example, the assertion

$displaystyle hbox{For all sufficiently large } n, P(n) hbox{ is true}$

could be rephrased as a substitute:

$displaystyle hbox{If } n hbox{ is a natural number, then } P(n) hbox{, or } n = O(1).$

When used appropriately, asymptotic notation can suppress a variety of distracting quantifiers (“there exists a ${C}$ such that for each ${n}$ one has…”) or short-term notation which is launched as soon as after which discarded (“the place ${C}$ is a continuing, not essentially the identical because the fixed ${C}$ from the previous line…”). It’s notably nicely tailored to conditions wherein the order of magnitude of a amount of curiosity is of extra significance than its precise worth, and may help seize exactly such intuitive notions as “massive”, “small”, “decrease order”, “most important time period”, “error time period”, and many others.. Moreover, I discover that analytic assertions phrased utilizing asymptotic notation are likely to align higher with the pure sentence construction of mathematical English than their logical equivalents in different notational conventions (e.g. first-order logic).

However, the notation could be considerably complicated to make use of at first, as expressions involving asymptotic notation don’t at all times obey the acquainted legal guidelines of mathematical deduction if utilized blindly; however the failures could be defined by the adjustments to orthodox first order logic indicated above. For example, if ${n}$ is a constructive integer (which we are going to assume to be at the least say ${100}$, with a purpose to make sense of portions equivalent to ${loglog n}$), then

• (i) (Asymmetry of equality) We’ve got ${O(n) = O(n^2)}$, however it isn’t true that ${O(n^2) = O(n)}$. In the identical spirit, ${O(n) leq O(n^2)}$ is a real assertion, however ${O(n^2) geq O(n)}$ is a false assertion. Equally for the ${o()}$ notation. This after all stems from the asymmetry of the equality relation ${=}$ that arises as soon as one introduces partially specified objects.
• (ii) (Intransitivity of equality) We’ve got ${n+1 = O(n)}$, and ${n+2 = O(n)}$, however ${n+1 neq n+2}$. That is once more stemming from the asymmetry of the equality relation.
• (iii) (Incompatibility with purposeful notation) ${O(n)}$ usually refers to a perform of ${n}$, however ${O(1)}$ often doesn’t check with a perform of ${1}$ (as an example, it’s true that ${frac{1}{n} = O(1)}$). This can be a barely unlucky consequence of the overloaded nature of the parentheses symbols in arithmetic, however so long as one retains in thoughts that ${O}$ and ${o}$ should not perform symbols, one can keep away from ambiguity.
• (iv) (Incompatibility with mathematical induction) We’ve got ${O(n+1)=O(n)}$, and extra usually ${O(n+k+1)=O(n+k)}$ for any ${k geq 1}$, however one can not blindly apply induction and conclude that ${O(n+k)=O(n)}$ for all ${n,k geq 1}$ (with ${k}$ seen as an extra parameter). It is because to induct on an inside parameter equivalent to ${n}$, one is barely allowed to make use of inside predicates ${P(n)}$; the assertion ${O(n+1)=O(n)}$, which additionally quantifies externally over some implicit constants ${C}$, just isn’t an inside predicate. Nonetheless, exterior induction continues to be legitimate, allowing one to conclude that ${O(n+k)=O(n)}$ for any mounted (exterior) ${k geq 1}$, or equivalently that ${O(n+k) = O_k(n)}$ if ${k}$ is now seen as a substitute as a parameter.
• (v) (Failure of the legislation of generalisation) Each particular (or “mounted”) constructive integer, equivalent to ${57}$, is of the shape ${O(1)}$, however the constructive integer ${n}$ just isn’t of the shape ${O(1)}$. (Once more, this may be mounted by permitting implied constants to rely upon the parameter one is generalising over.) Like (iv), this arises from the necessity to distinguish between exterior (mounted) variables and inside parameters.
• (vi) (Failure of the axiom schema of specification) Given a set ${X}$ and a predicate ${P(x)}$ involving components ${x}$ of ${X}$, the axiom of specification permits one to make use of set builder notation to kind the set ${{ x in X: P(x) }}$. Nonetheless, that is not potential if ${P}$ includes asymptotic notation. For example, one can not kind the “set” ${{ x in {bf R}: x = O(1) }}$ of bounded actual numbers, which one way or the other manages to comprise all mounted numbers equivalent to ${57}$, however not any unbounded free parameters equivalent to ${n}$. (However, if one makes use of the nonstandard evaluation formalism, it turns into potential once more to kind such units, with the necessary caveat that such units at the moment are exterior units relatively than inside units. For example, the exterior set ${{ x in {}^* {bf R}: x = O(1) }}$ of bounded nonstandard reals turns into a correct subring of the ring of nonstandard reals.) This failure is once more associated to the excellence between inside and exterior predicates.
• (vii) (Failure of trichotomy) For non-asymptotic actual numbers ${X,Y}$, precisely one of many statements ${X, ${X=Y}$, ${X>Y}$ maintain. As mentioned within the earlier part, this isn’t the case for asymptotic portions: not one of the three statements $)$, $) > O($, or $sin(n)$ are true, whereas all three of the statements ${O(n) < O(n)}$, ${O(n) = O(n)}$, and ${O(n) > O(n)}$ are true. (This trichotomy can nevertheless be restored through the use of the nonstandard evaluation formalism, or (in some circumstances) by limiting ${n}$ to an applicable subsequence every time obligatory.)
• (viii) (Unintuitive interplay with ${neq}$) Asymptotic notation interacts in unusual methods with the ${neq}$ image, to the extent that combining the 2 collectively just isn’t beneficial. For example, the assertion ${O(n) neq O(n)}$ is a real assertion, as a result of for any expression ${a_n}$ of order ${a_n = O(n)}$, one can discover one other expression ${b_n}$ of order ${b_n = O(n)}$ such that ${a_n neq b_n}$ for all ${n}$. As a substitute of utilizing statements equivalent to ${X neq Y}$ wherein certainly one of ${X,Y}$ comprise asymptotic notation, I’d as a substitute suggest utilizing the completely different assertion “it isn’t the case that ${X=Y}$“, e.g. “it isn’t the case that ${O(n^2)=O(n)}$“. And even then, I’d usually solely use negation of asymptotic statements with a purpose to exhibit the incorrectness of some explicit argument involving asymptotic notation, and never as a part of any constructive argument involving such notations. These points are after all associated to (vii).
• (ix) (Failure of cancellation legislation) We’ve got ${O(n) + O(n) = O(n)}$, however one can not cancel one of many ${O(n)}$ phrases and conclude that ${O(n) = 0}$. Certainly, ${O(n)-O(n)}$ just isn’t equal to ${0}$ on the whole. (For example, ${2n = O(n)}$ and ${n=O(n)}$, however ${2n-n neq 0}$.) Extra usually, ${O(X)-O(Y)}$ just isn’t on the whole equal to ${O(X-Y)}$ and even to $)$ (though there is a vital exception when certainly one of ${X,Y}$ dominates the opposite). Equally for the ${o()}$ notation. This stems from the care one has to soak up the legislation of substitution when working with partially specified portions that seem a number of instances on the left-hand facet.
• (x) (${O()}$, ${o()}$ don’t commute with signed multiplication) If ${X,Y}$ are non-negative, then ${X cdot O(Y) = O(XY)}$ and ${X cdot o_{n rightarrow infty}(Y) = o_{n rightarrow infty}(XY)}$. Nonetheless, these legal guidelines don’t work if ${X}$ is signed; certainly, as at the moment outlined ${O(XY)}$ and ${o_{n rightarrow infty}(XY)}$ don’t even make sense. Thus as an example ${-O(n)}$ can’t be written as ${O(-n)}$. (Nonetheless, one does have $Y)$ and ${X cdot o_{n rightarrow infty}(Y) = o_{n rightarrow infty}(|X| Y)}$ when ${X}$ is signed.) This comes from absolutely the values current within the ${O()}$-notation. For freshmen, I’d suggest not putting any signed portions contained in the ${O()}$ and ${o()}$ symbols if in any respect potential.
• (xi) (${O()}$ needn’t distribute over summation) For every mounted ${k}$, ${k = O(1)}$, and ${sum_{k=1}^n 1 = n}$, however it isn’t the case that ${sum_{k=1}^n k = O(n)}$. This instance appears to point that the assertion ${sum_{k=1}^n O(1) = O( sum_{k=1}^n 1 )}$ just isn’t true, however that’s as a result of we now have conflated an exterior (mounted) amount ${k}$ with an inside parameter ${k}$ (the latter being wanted to outline the summation ${sum_{k=1}^n}$). The extra exact statements (with ${k}$ now constantly an inside parameter) are that ${k = O_k(1)}$, and that the assertion ${sum_{k=1}^n O_k(1) = O( sum_{k=1}^n 1 )}$ just isn’t true, however the assertion ${sum_{k=1}^n O(1) = O( sum_{k=1}^n 1 )}$ continues to be true (why?).
• (xii) (${o()}$ doesn’t distribute over summation, I) Let ${varepsilon_k(n) := exp(exp(n)) 1_{k geq loglog n - 1}}$, then for every mounted ${k}$ one has ${varepsilon_k(n) = o_{n rightarrow infty}(1)}$; nevertheless, ${sum_{k=1}^{loglog n} varepsilon_k(n) geq exp(exp(n))}$. Thus an expression of the shape ${sum_{k=1}^{loglog n} o_{n rightarrow infty}(1)}$ can in truth develop extraordinarily quick in ${n}$ (and particularly just isn’t of the shape ${o_{n rightarrow infty}(loglog n)}$ and even ${O(loglog n)}$). After all, one might substitute ${loglog n}$ right here by some other rising perform of ${n}$. This can be a comparable challenge to (xi); it reveals that the assertion

$displaystyle sum_{k=1}^N o_{n rightarrow infty;k}(1) = o_{n rightarrow infty}(sum_{k=1}^N 1)$

can fail, but when one has uniformity within the ${k}$ parameter then issues are superb:

$displaystyle sum_{k=1}^N o_{n rightarrow infty}(1) = o_{n rightarrow infty}(sum_{k=1}^N 1).$

• (xiii) (${o()}$ doesn’t distribute over summation, II) Within the earlier instance, the ${o_{n rightarrow infty}(1)}$ summands weren’t uniformly bounded. If one imposes uniform boundedness, then one now recovers the ${O()}$ sure, however one can nonetheless lose the ${o()}$ sure. For example, let ${varepsilon_k(n) := 1_{k geq loglog n}}$, then ${varepsilon_k(n)}$ is now uniformly bounded in magnitude by ${1}$, and for every mounted ${k}$ one has ${varepsilon_k(n) = o_{n rightarrow infty}(1)}$; nevertheless, ${sum_{k=1}^n varepsilon_k(n) = n - O(loglog n)}$. Thus, viewing ${k}$ now as a parameter, the expression ${sum_{k=1}^n o_{n rightarrow infty;k}(1)}$ is bounded by ${O(n)}$, however not by ${o_{n rightarrow infty}(n)}$. (Nonetheless, one can write ${sum_{k=1}^n o_{n rightarrow infty}(a_k) = o_{n rightarrow infty}(sum_{k=1}^n |a_k|)}$ since by our conventions the implied decay charges within the ${o_{n rightarrow infty}(a_k)}$ summands are uniform in ${n}$.)
• (xiv) (${o()}$ doesn’t distribute over summation, III) If ${a_k}$ are non-negative portions, and one has a summation of the shape ${sum_{k=1}^n (1+o_{n rightarrow infty}(1)) a_k}$ (noting right here that the decay fee just isn’t allowed to rely upon ${k}$), then one can “issue out” the ${1+o_{n rightarrow infty}(1)}$ time period to put in writing this summation as ${(1 + o_{n rightarrow infty}(1)) (sum_{k=1}^n a_k)}$. Nonetheless that is removed from being true if the sum ${sum_{k=1}^n a_k}$ displays important cancellation. That is most vivid within the case when the sum ${sum_{k=1}^n a_k}$ really vanishes. For one more instance, the sum ${sum_{k=1}^{n} (1 + frac{(-1)^k}{loglog n}) (-1)^k}$ is the same as ${frac{n}{loglog n} + O(1)}$, even if ${1 + frac{(-1)^k}{loglog n} = 1 + o_{n rightarrowinfty}(1)}$ uniformly in ${k}$, and that ${sum_{k=1}^n (-1)^k = O(1)}$. For oscillating ${a_k}$, one of the best one can say on the whole is that

$displaystyle sum_{k=1}^n (1+o_{n rightarrow infty}(1)) a_k = sum_{k=1}^n a_k + o_{n rightarrow infty}( sum_{k=1}^n |a_k| ).$

Equally for the ${O()}$ notation. I see one of these error typically amongst newbie customers of asymptotic notation. Once more, the overall treatment is to keep away from placing any signed portions contained in the ${O()}$ or ${o()}$ notations.

Maybe the quickest solution to develop some fundamental safeguards is to pay attention to sure “purple flags” that point out incorrect, or at the least doubtful, makes use of of asymptotic notation, in addition to complementary “security indicators” that give extra reassurance that the utilization of asymptotic notation is legitimate. From the above examples, we are able to assemble a small desk of such purple flags and security indicators for any expression or argument involving asymptotic notation:

 Crimson flag Security indicator Signed portions in RHS Absolute values in RHS Casually utilizing iteration/induction Explicitly permitting bounds to rely upon size of iteration/induction Casually summing an unbounded variety of phrases Conserving variety of phrases bounded and/or making certain uniform bounds on every time period Casually altering a “mounted” amount to a “variable” or “sure” one Conserving observe of what parameters implied constants rely upon Casually establishing decrease bounds or asymptotics Establishing higher bounds and/or being cautious with indicators and absolute values Signed algebraic manipulations (e.g., cancellation legislation) Unsigned algebraic manipulations ${X neq Y}$ Negation of ${X=Y}$; or, higher nonetheless, avoiding negation altogether Swapping LHS and RHS Not swapping LHS and RHS Utilizing trichotomy of order Not utilizing trichotomy of order Set-builder notation Not utilizing set-builder notation (or, in non-standard evaluation, distinguishing inside units from exterior units)

After I say right here that some mathematical step is carried out “casually”, I imply that it’s executed with none of the extra care that’s obligatory when this step includes asymptotic notation (that’s to say, the step is carried out by blindly making use of some mathematical legislation which may be legitimate for manipulation of non-asymptotic portions, however could be harmful when utilized to asymptotic ones). It also needs to be famous that many of those purple flags could be disregarded if the portion of the argument containing the purple flag is freed from asymptotic notation. For example, one might have an argument that makes use of asymptotic notation in most locations, besides at one stage the place mathematical induction is used, at which level the argument switches to extra conventional notation (utilizing specific constants relatively than implied ones, and many others.). That is in truth the other of a purple flag, because it reveals that the creator is conscious of the potential risks of mixing induction and asymptotic notation. Equally for the opposite purple flags listed above; as an example, the usage of set-builder notation that conspicuously avoids utilizing the asymptotic notation that seems elsewhere in an argument is reassuring relatively than suspicious.

If one finds oneself attempting to make use of asymptotic notation in a means that raises a number of of those purple flags, I’d strongly suggest understanding that step as rigorously as potential, ideally by writing out each the hypotheses and conclusions of that step in non-asymptotic language (with all quantifiers current and within the right order), and seeing if one can really derive the conclusion from the speculation by conventional means (i.e., with out specific use of asymptotic notation ). Conversely, if one is studying a paper that makes use of asymptotic notation in a fashion that casually raises a number of purple flags with none obvious try and counteract them, one needs to be notably skeptical of those parts of the paper.

As a easy instance of asymptotic notation in motion, we give a proof that convergent sequences additionally converge within the Césaro sense:

Proposition 6 If ${vec x = (x_n)_{n in {bf N}}}$ is a sequence of actual numbers converging to a restrict ${L}$, then the averages ${frac{1}{N} sum_{n=1}^N x_n}$ additionally converge to ${L}$ as ${N rightarrow infty}$.

Proof: Since ${x_n}$ converges to ${L}$, we now have

$displaystyle x_n = L + o_{n rightarrow infty; vec x}(1)$

so particularly for any ${M geq 1}$ we now have

$displaystyle x_n = L + o_{M rightarrow infty; vec x}(1)$

every time ${n > M}$. For ${N geq M}$, we thus have

$displaystyle frac{1}{N} sum_{n=1}^N x_n = frac{1}{N} ( sum_{n=1}^M x_n + sum_{n=M+1}^N x_n)$

$displaystyle = frac{1}{N}( O_{M,vec x}(1) + sum_{n=M+1}^N (L + o_{M rightarrow infty; vec x}(1)))$

$displaystyle = frac{1}{N}( O_{M,vec x}(1) + (N-M) L + o_{M rightarrow infty; vec x}(N))$

$displaystyle = O_{M,vec x}(1/N) + L - O_{M,L}(1/N) + o_{M rightarrow infty; vec x}(1)$

$displaystyle = L + o_{M rightarrow infty; vec x}(1) + o_{N rightarrow infty; vec x, M, L}(1)$

every time ${N geq M}$. Setting ${M}$ to develop sufficiently slowly to infinity as ${N rightarrow infty}$ (for mounted ${vec x, vec L}$), we might simplify this to

$displaystyle frac{1}{N} sum_{n=1}^N x_n = o_{N rightarrow infty; vec x, L}(1)$

for all ${N geq 1}$, and the declare follows. $Box$

RELATED ARTICLES