Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[ConMan]

In my mind, "f(x)" is shorthand for "f is a function whose inputs can be considered as a single object (probably a real number), which we will represent with x for now". That way, when I write "f(x) = O(x^2)", then I can read that as "the function f, when you look at large values of its input x, behaves similarly to the function that maps x to its square".

It may be true that mathematics is formalised with sets, but it is written in shortcuts and abbreviations and notations that are designed to communicate an idea, and much of the point of formalism is to ensure that the ideas behind those shortcuts are valid without needing to always explicitly state everything. It's the same shorthand that means that x and y are usually real numbers, z is typically complex if not combined with other pronumerals, i,j,k,m,n are integers, and most lower case Greek letters are probably representing angles.

With that understanding, I can write something like f(x^2) = O(ln(g(x)) and you can understand the general idea of what I'm trying to communicate, but without it I would need to do something like:

Let F: R -> R be a function such that F(x) = f(x^2), and let G: R -> R be a function such that G(x) = ln(g(x)). Then F = O(G).

And sure that's more accurate, but it doesn't actually convey any information that isn't at least implied in the original statement.

[silverspawn]

I don’t like “the graph of f(x)” either, but in most cases it’s clear what they mean. It’s the same as when someone says “the graph of x^2”, for example, which is also iffy notation but saves a lot of words / formulas.

I find the other example you bring up much more clear cut though. While ideally we would write f=O(g), the truth is that very often g ends up being something like x^2 or n*ln(n) or whatever. I find it nicer to write f(x) = O(x^2) than f = O(x^2), although in both cases the intent of the writer is completely clear. Specifying the variable is even better when you have functions of two or more variables, as Cuzz brought up earlier.

Ultimately, when enough people use a given shorthand, then you just end up having to learn it. This is not the worst case of notation abuse by a long shot. However, I would expect the writer to become more rigorous for contexts in which the distinction between the function and its output is not obvious, such as if you have functions of functions or whatnot.

So, there is this framework that I've found extremely useful (as in, almost always applicable), which says that there are two kinds of mathematicians. For one kind, the most important thing is to have a perfect chain of arguments that leads to any possible step. Like a pyramid. You don't always need to spell out every step in perfect detail, but it's extremely important that you know how to spell out every step in perfect detail if you wanted to. For the other kind, those are details; the important thing is to develop an intuition for important results.

I'm not sure if this tracks the current debate, but I suspect it does. From my PoV of being in the first camp, most of the replies here are just painfully missing the point, which is not about whether or not the notation is understandable, but whether it coherently maps onto a formal statement. The n^2 in "f \in O(n^2)" doesn't bother me because it coherently maps onto a precise set. f is a precisely defined a set, n^2 is a precisely defined set, O is a class function, which makes O(n^2) a precisely defined set and the entire thing a statement about set membership. But f(n) \in O(n^2) is irredeemably unfixably wrong because f(n) doesn't denote a set. it doesn't matter whether I know what the claim is, it's illogical.

I like what ConMan said; if everyone agreed on this, it would make things much less bad (instead of being illogical, it would just be a hideously ugly notation where (n) is used to denote two completely different things, maybe on par with how (a,b) denotes both a two-point set and an interval). But it sure doesn't seem like everyone who writes it precisely agrees on what it means. E.g., you had to think about what it means when I brought it up.

[pacovf]

What I was trying to convey (and, I believe, what Cuzz tried to convey earlier) is exactly the same as what ConMan said. We are discussing notation only, not what the statements refer to. I did not have to look up anything, I was describing common usage in which "f(x)" is often used in the place of "f" because it can be useful to do so (as you have done yourself in some of your posts and ConMan demonstrated in his). Math is written by humans for humans ^{[citation needed]}, abuses of notation are bound to happen even in the most rigorous of proofs as long as the meaning remains clear in context.

I did point out that I did not know if the common usage had been formalized, because it is important to distinguish between proper notation and shorthand for when shorthand becomes ambiguous. One example of shorthand that ended up formalized is the Einstein summation convention. It seems you have encountered a shorthand you're not used to, and are naturally confused. But the meaning in the examples you gave is absolutely clear from context.

[Cuzz]

Yeah I mean if it wasn’t technically “wrong” and “illogical” we’d just call it a “use of notation.”

[heron]

f(x) is the number that you get by applying f to x.

But what is x?

I did point out that you might have this complaint, and also that this complaint makes no sense if you also think that x \in O(x^2) makes perfect sense...

x is any and every real number, the same way it is when you say f(x) = x^2.

[scolapasta]

This recent comic seemed at least partially relevant:



Source

[faust]

So the exact same thing as f?

No, because "f(y)" would be a macro for "y^2-25," and those are two different strings, so they can't both be the exact same thing as f.

But math is formalized in terms of sets*, not strings. And y^2-25 refers to the same function -- and hence the same set -- as x^2-25.

I feel like you want to maintain that there are cases where writing y and x is different. This is true, but this is not one of those cases. And in complexity theory (where I see people using the f(x) =O(g(x)) thing), those cases basically never come up.

* or operators if you like lambda calculus, but the point stands.

I feel like this is the crux of the issue. You approach this from the point of view of a mathematician, where the underlying formalism is using sets. But big-O notation is much more frequent in complexity theory and thus computer science, where the theoretical basis is formal logic, which indeed does deal with strings.

(caveat that I am not an expert in formal logic; my partner is, and I just picked up some things along the way)

In terms of formal logic, "y^2 -25" is a formula with free variable y. f(y) is, as Cuzz said, a shorthand for this. And "f(y) \in O(g(y))" says that this formula is an element of a class generated by another formula. This is all internally consistent and logical.

[GendoIkari]

I feel like programming languages have resolved this a long time ago... "f(x)" tells the program to execute the function called f, and pass the variable already defined as "x" to that function. Thus f(g(x)) tells the program to execute function g, passing in variable x, and then execute function f, passing in the result of the previous function call.

f(x) = x*x is a compiler error; it has no meaning. However,

f(x) => x*x defines a new function, called f, and the x being there is required because in order to tell it to return x*x, you have to have a way of referring to the input from within the function definition.

And finally, DoWork(f()) would first run function f and pass the return value of that function to DoWork. Whereas DoWork(f) would instead not call function f, but it would pass a reference to that function to DoWork, so that DoWork can then call that function if it needs to.

[pubby]

I'm just a lowly programmer but

Code: [Select]

f ∈ O(n^2)does not seem logical or consistent to me. You're using the expression O(n^2) in a totally context-sensitive way. Imagine if O was a a function that returned sets instead of numbers. Then the relation is an ambiguous, no?

I mostly agree with Gendo on this.

[silverspawn]

O returns sets of functions

[SirPeebles]

I came up with a proof that 5 is a prime number.

5x5 = 25 = 4! +1, so 5 is not divisible by 2, 3, or 4.

[anordinaryman]

I came up with a proof that 5 is a prime number.

5x5 = 25 = 4! +1, so 5 is not divisible by 2, 3, or 4.

Using the same type of process, I have proved that 3 is prime.

3x3 = 9 = 2^3 + 1, so 3 is not divisible by 2.

[Cuzz]

Some good math tweets:

https://twitter.com/ImogenBits/status/1428056037815431172?s=20

https://twitter.com/RadishHarmers/status/1427822902179770368?s=20

[GendoIkari]

Has it been proven that Pi contains an equal number of each digit? Or is it theoretically possible that after some number of digits there are simply no more 7s in the decimal anymore?

[ConMan]

Apparently the status is "strongly conjectured, still not proven".

[faust]

I came up with a proof that 5 is a prime number.

5x5 = 25 = 4! +1, so 5 is not divisible by 2, 3, or 4.

Using the same type of process, I have proved that 3 is prime.

3x3 = 9 = 2^3 + 1, so 3 is not divisible by 2.

Now I am left wondering for which primes p the equation

p^k = n x (p-1)! + 1

has an integer solution (k,n).

[Jack Rudd]

There are certainly solutions for 2, 3, 5 and 7. I haven't checked 11 yet.

[MiX]

Now I am left wondering for which primes p the equation

p^k = n x (p-1)! + 1

has an integer solution (k,n).

I can prove such solutions exist for p's that satisfy that for any m < p, there exists k such that m divides p^(2^k)+1. Well, technically each k has to be different for each m, but I don't think that's a problem.

[ehunt]

I came up with a proof that 5 is a prime number.

5x5 = 25 = 4! +1, so 5 is not divisible by 2, 3, or 4.

Using the same type of process, I have proved that 3 is prime.

3x3 = 9 = 2^3 + 1, so 3 is not divisible by 2.

Now I am left wondering for which primes p the equation

p^k = n x (p-1)! + 1

has an integer solution (k,n).

This is true for all p. More generally, given any coprime integers a and b (in your case p and (p-1)! respectively), there is an integer solution (k, n) to the equation

a^k = nb + 1

The proof is not so long with the language of groups/rings. The co-prime assumption means that a is a unit in the ring Z/bZ. Since this ring is finite, so is its group of units, so a has some finite order k, which exactly means that a^k - 1 is divisible by b.

This can be translated into an elementary proof with a little work if you haven't seen groups/rings before -- let me know!

[vidicate]

Ooooo we have a Maths (sic) thread! Threaten me with a good time, will ya?

[Cuzz]

Interesting post possibly addressing some of the year-old discussion from above. Puts some of the ubiquitous informal notation from analysis/complexity theory on more rigorous footing via "partially specified objects."

https://terrytao.wordpress.com/2022/05/10/partially-specified-mathematical-objects-ambient-parameters-and-asymptotic-notation/