6

In relation to his possible worlds analysis of natural language conditionals (e.g. 1975 Indicative Conditionals) Robert Stalnaker posited a function which takes an antecedent proposition and a conversational background as inputs and yields a possible world as its value. The natural language conditional is true if the consequent proposition is true at that world.

I wish to discuss an alternative conditional where the value of said function is not a single world, but rather a set of worlds at each of which the consequent proposition must be true.

As a layperson working outside of my area of expertise (and competence), I wonder whether a function may yield a set as its value (i.e. as its output). My understanding of a function is that it must have a single value; it is, if you like, a many to one relation. Is having a set as its value kind of cheating, as it were?

1

9 Answers 9

9

A function f: A --> B maps each element of the set A to an element of the set B.

Example: Take A the set of natural numbers and B the powerset of A, i.e. elements of B are the subsets of A. For each natural number x from A define

f(x) from B as the set of all natural numbers less or equal x.

Then

f(0) = {0}, f(1) = {0,1}, f(2) = {0,1,2} ...

The function takes as values certain sets of natural numbers.

2
  • 9
    Heck, f(x)={x} also works, and is even simpler.
    – JonathanZ
    Apr 22 at 17:04
  • 1
    There's a whole number of simple yet convincing functions. Another example would be the factors of x. f(12)={1,2,3,4,6,12}.
    – MSalters
    Apr 25 at 9:36
9

In set theory, a “function” is actually a binary relation fulfilling certain properties.

A “binary relation” is any subset of the Cartesian product of two sets.

The Cartesian product of two sets is the set of all ordered pairs of elements from those sets.

For a binary relation to be a function, it has to be defined on all the elements of the first set, and it cannot associate one element from the first set with more than one element from the second set.

In pure set theory, the only thing that exists in a whole universe of mathematics is sets. All mathematical ideas are represented as particular sets, including functions, relations, propositions, patterns, combinations, numbers, truth, equality, space, continuity, limits, algebraic structures, theorems, etc.

This means that not only can the output of a function be a set, it actually must be. In set-theoretic mathematics, nothing exists except sets, so everything that exists is one.

The idea of an “element” is an abstract one. An element is just what the set contains; but it doesn’t say anything about what the element can or cannot be. The elements of a set could be numbers, functions, operators, algebras, topologies, etc.

And yet, all of the above are defined specifically as particular kinds of sets - so that they also are all sets, at the same time.

6
  • 1
    “ The Cartesian product of two sets is the set of all ordered pairs of elements from those sets”—(a,b) where a is in A and b is in B, e.g. no (b,a). “In pure set theory, the only thing that exists in a whole universe of mathematics is sets. All mathematical ideas…”—equality requires logic, e.g. biconditional
    – J Kusin
    Apr 22 at 17:00
  • 2
    There are some set theories that allow sets to have elements that are not sets - sometimes called urelements or atoms. This does not change the fact though that "most" sets have "most" of their elements being other sets.
    – DanishChef
    Apr 23 at 4:51
  • 2
    while literally correct, this is a bit besides the point: is likely that most people (besides philosophers and logicians) do not think of functions as being their graphs, and do not think of all objects of ordinary mathematical discourse as being sets
    – ac15
    Apr 23 at 20:34
  • 1
    People who think that functions are something else than their graphs are just mistaken...
    – Plop
    Apr 25 at 7:27
  • @Plop: On the contrary, believing functions really are just their graphs is like a programmer thinking integers really are their (say) two’s-complement binary representations. Within a given implementation it may be how integers are represented, and it’s a faithful and very useful encoding, but it’s certainly not abstractly/philosophically what integers actually are. Similarly, in set-theoretic foundations functions are represented as their graphs, but in other foundational systems (eg type theories) they may be represented other ways or taken as primitive. Apr 26 at 7:50
7

tl;dr: Almost always, a function has an (implicit or explicit) intended output type; and sometimes that’s sets, but if it’s anything else, then the function’s values must be those things, not sets.

A completely arbitrary function can take any kind of objects as its output values, including sets. However, when you’re speaking of a function, almost always the types of its inputs and outputs are fixed in advance, either explicitly or implicitly. For instance, when a physical model assumes “position is a function of time”, that means the function’s inputs are time values, and its outputs are positions. So then for any time t, f(t) must be a single position, not a set of positions. Or more mathematically, if g is supposed to be a function from real numbers to real numbers, then each value g(x) must be a single real number — not a set of real numbers, or anything else.

On the other hand, set-valued functions certainly do occur very naturally in some situations: e.g. you can consider the function taking each natural number n to the set of all its factors. The output type of this function is “sets of natural numbers”.

In principle, one can also of course have a function with a mixed output types — whose values could include both real numbers and sets of real numbers, for instance. But in practice, this is extremely rare; and when it is used, it’s often arguably a bad choice — a chimerical combination that would be better viewed as several separate functions.

3

Yes, a function can yield a set as its value. This is not cheating or a violation of the definition of a function. A function is a relation that maps each element in the domain to a single element in the range. The range can be a set, even a set with multiple elements.

In mathematics a function is a rule that assigns a unique output to each input. The output can be a single value or a set of values. As long as the function consistently maps each input to a specific set of outputs, it is still considered a valid function.

This is a common and accepted practice in mathematics and computer science. Functions that return sets are useful in many applications, such as finding the set of solutions to an equation or the set of all factors of a number.

So a function can indeed have a set as its output, and this is a standard and valid way to define functions in various fields of study.

2

In simple terms: Functions can indeed operate on sets, by operating on each member of the set individually to produce a second set which contains all the outputs.

2

A function can be defined as a binary relation that matches each element of the domain to one element of the codomain. The domain and co-domain are sets. If the elements of the codomain are themselves sets, then yes, it a set can have a set as an output.

There exist multivalued functions,in mathematics for example the complex logarithm, f(z) = log(z) for some complex number z. There is a plot:

imaginary part of log(z)

As you can see, the full output of the imaginary part is a discrete set of numbers (a consequence of the periodic character if the complex exponential).

However if, as could be the case, you want to define the elements of the co-domain to be strictly numbers then multivalued functions are no longer classed as function but as one-to-many binary relations.

2

Since we're just asking about possibiliies, a single example is enough to proof possibility:

Consider a function that maps any input set (of real numbers) to a two-entry set of it's mean and average.

The function absolutely maps any possible input to a singular specific output.

More formally this basic definition of functions is the following: (emphasis mine)

A function, f, is ordinary understood as a mapping from a domain X to another domain Y. In set-theoretic foundations, X and Y are arbitrary sets.

That an arbitrary set (X and Y) can be a set of sets is self evident because there are no restrictions on these arbitrary sets.

My example function also maps any set of real numbers onto the space of sets comprising of two real numbers (which is clearly a subset of all arbitrary sets). It also clearly displays a many-to-one relation in that any input set obviously only has one average and one mean, resulting in one specific output set.

Edit: I just remembered a far less constructed, real-world* function that may be more common: Think of all the matrix operations. A matrix is nothing but an ordered set of specific size. A matrix multiplication thereby takes two such sets as input and outputs a third, specific, set.

*debateable

3
  • Perfect. Thanks Apr 23 at 16:29
  • 1
    Make sure to restrict the domain to a bounded interval to ensure that the average can be computed. Apr 23 at 16:59
  • @MichalRyszardWojcik niche but absolutely correct caviat. I got a bit lazy on the specifics, including restricting the input domain beyond real numbers
    – Hobbamok
    Apr 24 at 9:38
0

Indeed, it is a form of cheating if you like this wording and find it helpful in coming to terms with this practice in mathematics. However, it is better to appreciate it by an example that you might find accessible. Let the function accept three real parameters a, b, c and return the set of real numbers x which satisfy the quadratic equation ax^2 + bx + c = 0. For some arguments, it returns the empty set, for others it returns a singleton and for others it returns a set with two elements. Moreover, if the arguments satisfy a = b = c = 0, it returns the whole real line.

0

A function is generally used as a binary relationship (for every input, there is a single output), which can take any domain of discourse for domain and codomain, so yes, it can be applied to a domain consisting of sets. A simple example of that is the powerset which is a function that takes a set as an input and returns a set of all possible subsets. From the WP article:

If S is the set {x, y, z}, then all the subsets of S are

{}... {x} {y} {z} {x, y} {x, z} {y, z} {x, y, z}

and hence the power set of S is {{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}.

Thus, in this example, the domain is the set of sets, and the codomain is the set of all possible subsets of a set.

Not the answer you're looking for? Browse other questions tagged .