There is no set of all functions

[nonequilibrium]

"there is no set of all functions"

Since we are being overly pedantic here, remember that there is no "set of all functions."

Source: https://www.physicsforums.com/archive/index.php/t-190505.html

Can anybody explain this?

 

[gb7nash]

Source: https://www.physicsforums.com/archive/index.php/t-190505.html

Can anybody explain this?

I'm not sure what the person was trying to convey. But looking at the previous posts, they were having a discussion on log(z). A function can only have one value assigned to each input. However, log(z) can have many values for each input if you're allowing complex values. That's why you make a branch cut to be able to "make it" a function. You'll learn more about this concept if you take complex analysis (or maybe you already took it?) I'm not sure what set of functions they're talking about.

 

[nonequilibrium]

I'm taking complex analysis now, and that's how I got onto that page, but the quoted comment doesn't seem related to the concept of multivalued functions. I assumed he literally meant all functions, as that notion is defined (so log(z) wouldn't be an element of that set, not being a single-valued relation).

 

[Stephen Tashi]

There are logical technicalities (that I do not claim to know) which force mathematicians to talk about some collections of objects as "classes" rather than "sets". You often hear professors remark that such a collection is "too large to be a set". Perhaps "all functions" requires such language.

 

[DarthPickley]

strange. it seems that it would be simple to have a set of all functions where a function is a collection of ordered pairs of an element of the domain and of the co-domain, so, given a set of which the domain and co-domain are subsets of, it should be simple to, for each element of the domain set, assign a random element of the co-domain, and then you have a set of sets... but it is somewhat clumsy that way, and it gets more complicated if you have restrictions on continuity or differentiability.

 

[AlephZero]

If you follow Russell and Whitehead's approach to the fundmentals of math, they define a function f(x1,x2, ... xn) as meaning the set of all possible ordered lists of values {x1, x2, ..., xn, f(x)}

The so-called paradox that you cannot define "the set of all sets" without introducing a contradiction is well known. (The classic Russell version of the paradox is: Let S be "the set of all sets that are not members of themselves." Is S a member of itself, or not? If it is, then its definition says that it isn't. If it isn't, then its definition says that it is.).

It follows that "the set of all functions" can not be defined without introducing a contradiction either.

Russell attempted to fix this up by inventing an infinite number of different sorts of things called "classes", such that a "class of type 1" can contain all sets, but is not itself a set, and a "class of type 2" can contain all classes of type 1, but is not a class of type 1, etc.

 

[Fredrik]

There's no set of all functions, but given two sets X and Y, there's the set of all functions from X into Y.

One reason to expect the concept of "the set of all functions" to be problematic is that for each set X, there's exactly one function from X into {∅} (the set that has the empty set as its only member). So informally speaking, there are at least as many functions as there are sets. I'm sure someone who's better than me at set theory could use this to derive a contradiction. I'm not going to try at 3:43 AM.

 

[Stephen Tashi]

strange. it seems that it would be simple to have a set of all functions where a function is a collection of ordered pairs of an element of the domain and of the co-domain

But what domains and co-domains are we talking about? A function can map functions to functions, or sets of functions to functions or sets of functions to sets of functions, etc.

My attempt to apply what AlephZero said about sets to sets of functions:

Suppose S is the set of all functions. We may define a function f as follows:
The domain of f is S and the range of f is S (i.e. it maps a function to another function). For a given s in S, we define f(s) = s if s is a function that does not contain the ordered pair (s,s). Otherwise we define f(x) = g, where g is the constant function g(x) = 1 whose domain is the set of real numbers and whose co-domain is {1}.

For example, let h(x) be the function 6x + 1 whose domain and range are each the set of real numbers. We have f(h) = h because (h,h) is not an ordered pair of h. (Since h is a function rather than a real number, it would not appear in either its domain or range.)

As another example, let u(x) be the function with domain S and range S that maps every function to itself. Then f(u) = g because u contains the ordered pair (u,u).

Now, compute f(f). What does f map itself to?

 

[Fredrik]

The classic Russell version of the paradox is: Let S be "the set of all sets that are not members of themselves." Is S a member of itself, or not? If it is, then its definition says that it isn't. If it isn't, then its definition says that it is.

In other words, if y=\{x|x\notin x\} is a set, then y\in y\Leftrightarrow y\notin y, and this equivalence contradicts itself.

I could be wrong, but I don't think this is the reason why there's no set that contains all sets. I think the above only teaches us that a set of axioms that defines a set theory can't include an axiom that says (roughly) "for all properties p, {x|x has property p} is a set". In ZFC, there's a similar axiom that says (roughly) "for all properties p and all sets y, {x in y|x has property p} is a set".

So Russell's paradox tells us that the first axiom above (which would have allowed the set of all sets to exist) can't be a part of the theory, but it's not obvious that replacing it with the improved axiom gets rid of the set of all sets. We seem to need another argument for that. But now it's 4:10 AM, and I should be asleep already.

 

[pwsnafu]

So Russell's paradox tells us that the first axiom above (which would have allowed the set of all sets to exist) can't be a part of the theory, but it's not obvious that replacing it with the improved axiom gets rid of the set of all sets. We seem to need another argument for that. But now it's 4:10 AM, and I should be asleep already.

The universal set does exist in http://en.wikipedia.org/wiki/New_Foundations" , so...yeah...

 

[Hurkyl]

The universal set does exist in http://en.wikipedia.org/wiki/New_Foundations" , so...yeah...

What happens in NFU is irrelevant to ZFC. And mostly irrelevant to mathematics -- I personally haven't encountered anyone trying to do math in NFU.

 

[Hurkyl]

I think the above only teaches us that a set of axioms that defines a set theory can't include an axiom that says (roughly) "for all properties p, {x|x has property p} is a set". In ZFC, there's a similar axiom that says (roughly) "for all properties p and all sets y, {x in y|x has property p} is a set".

If U is a set of all sets, then those statements are equivalent. The novel direction is because {x|x has property p} is the same thing as {x in U|x has property p}.

 

[Fredrik]

That's a good point. If there's a set of all sets, denoted by U, then

\{x\in U|x\notin x\}​

is a set. Let's denote this set by R. The definition implies that the equivalence

R\in R\Leftrightarrow R\notin R​

is true, but it's obviously false. So we have a contradiction. Therefore, there's no set of all sets.

I was going to continue this by proving that there's no set of all functions, but I'm feeling too lazy to think everything through and type it up right now.

 

[nonequilibrium]

Phew, set theory is interesting...

It's weird that as an undergraduate in math, I'm not getting any schooling in this. At what "level" are these subjects "normally" taught? And under what name(s)?

 

[Hurkyl]

You could probably use the axiom of unions, but the axiom of replacement would be more straightforward:

{f(x) | x in S}​

is a set, for any function f. (where by "function" I mean a function defined by logical symbols, rather than a set of ordered pairs satisfying the vertical line test)

 

[micromass]

Phew, set theory is interesting...

It's weird that as an undergraduate in math, I'm not getting any schooling in this. At what "level" are these subjects "normally" taught? And under what name(s)?

There are some reasons why those subjects are not taught in undergraduate classes:

1) There is more important mathematics to teach. I can safely say that complex analysis is mathematically more important than set theory. (note that I didn't say set theory is unimportant or not fun to do).

2) There is some mathematical maturity needed to grasp set theory.

3) You don't need set theory to understand most mathematics. Especially, since many set theoretic topics can be dealt with by not mentioning them.

Note however, that I disagree with the previous, and that I actually think that set theory is an essential part of mathematics which every undergraduate must have seen.

You will probably see some set theory in grad school, these classes will have names such as "set theory", "fundamentals of mathematics" or "mathematical logic" (however, mathematical logic can also be about very different topics).

 

[Deveno]

There are some reasons why those subjects are not taught in undergraduate classes:

1) There is more important mathematics to teach. I can safely say that complex analysis is mathematically more important than set theory. (note that I didn't say set theory is unimportant or not fun to do).

i disagree with this. complex analysis may be more useful, in the sense that one will use it more often, but if the basic foundations it rests on are shaky, it introduces a certain lack of faith in the results. one would like some re-assurance that the sets referenced constantly as defining entities in complex analysis have some consistent meaning.

2) There is some mathematical maturity needed to grasp set theory.

this is partly true. set theory is not without it's problems. defining "what" a set can and cannot be, leads to a notion that is far more complicated that the intuitive idea appealed to rather glibly in most courses that nevertheless, use sets as if we knew what they were.

3) You don't need set theory to understand most mathematics. Especially, since many set theoretic topics can be dealt with by not mentioning them.

Note however, that I disagree with the previous, and that I actually think that set theory is an essential part of mathematics which every undergraduate must have seen.

You will probably see some set theory in grad school, these classes will have names such as "set theory", "fundamentals of mathematics" or "mathematical logic" (however, mathematical logic can also be about very different topics).

i think that the fact that the foundation of math (if one takes set theory as a foundation) is considerably harder than the math then built upon it, is a serious flaw. it means, as a consequence, that most of what students learn about the subject, has to be "taken on faith" (that someone, presumably more competent than they, has actually worked out the details, and confirmed that all is well). furthermore, to use mathematical tools as a language for describing reality (or what we believe to be real) leaves one feeling that there should be "bedrock" at the bottom, not shifting sand.

and all is NOT well. conflicting set theories abound, and there are a growing number of mathematicans who believe that set theory should just be "a" foundation of math, not "the" foundation of math.

@ original poster: if f is a function f:X-->Y, we have the set dom(f) = f^-1(f(X)) = X. so for any set of functions, F, we have the set {A: A = dom(f), f in F}.

and every set U has the function 1_U defined on U by: 1_U(u) = u, for all u in U.

if we had a set of all functions, G, then the set {A: A = dom(f), f in G}, contains every set U, and thus would be the "set of all sets". this does not exist, so F does not exist.