Comment by geocar
1 day ago
> We can't say that a function equals a set
Why not?
Can we not so easily speak of the set of all inputs and the set of all outputs? Why not exactly then is a function not a set of morphisms/arrows?
To me, x->x+1 and {(x,x+1)|x∈R} seem the same[1] but maybe it just seems useful to be able to make statements of the cardinality of that set: If there are a lot of rules, then that set is big, but if there are few rules (like x->x+1), that set is small. This is enough to permit some analysis.
It also preserves "plus" for sets, because a function plus a function is the sum of those rules being considered.
What is it do you think I am missing?
[1]: I understand I don't really mean big-R here because computers have limited precision for fadd/add circuits, so if you'd prefer I said something slightly differently there please imagine I did so.
You miss the point here. Just because functions happen to be sets ZF does not mean sets of functions are functions. O(...) denotes a set of functions.
> Just because functions happen to be sets ZF does not mean sets of functions are functions. O(...) denotes a set of functions.
We can enumerate all programs up to a given length, so up to that limit all sets of functions are functions.
f(x)=O(g(x)) still makes sense in exactly this way: if g(x) is 1, then f(x) is a function that is O(1) right? How do we know g(x) is 1? Because all programs of some length that compute f(x) have that property. Of course there are longer programs that do it, and shorter programs that don't, and other programs still, but we're talking about these ones.
f(x)<O(g(x)) then says that the f(x) must be shorter than that; it isn't a member of the set.
What do you think I am missing?