Vacuous Cases, Empty Sets, and Empty Functions
Date: 04/10/2004 at 08:38:12 From: Dua Subject: vacuous case, empty set, empty function I am having difficulty understanding 'vacuous' situations as in, if A is an empty set and B is a non-empty set then (i) there is one function f: A \to B namely the empty function but (ii) there is no function f: B \to A. An empty set is a set with no element but what is an empty function? There is a function from an empty set to a non-empty set (how) but not vice-versa. I am used to the case A and B are non-empty so A x B does not go against (my) intuition. In the case A is empty and B is non-empty, A x B is non-empty but B x A is empty?
Date: 04/12/2004 at 08:16:36 From: Doctor Jacques Subject: Re: vacuous case, empty set, empty function Hi Dua, There are two ideas involved here: * Logical statements about the empty set * The definition of a function Let us first consider a statement about the elements of a set A. Assume S(x) is a statement about the object x (a logical proposition): depending on the particular object x, S(x) is either true or false. We can make a statement S(A) about the set A, by asserting that S(x) is true for every element of A : S(A) ::= "For all x in A, S(x) is true". For example, assume that x represents a ball, and S(x) is the statement "the ball x is red". Now, if A is a bag of balls, S(A) would mean: "For all balls x in the bag A, the ball x is red" or, more simply said: "All the balls in A are red" The question is now, what does this mean if A is empty? S(A) can only be false if you can find in A a ball that is not red. If A is empty, this is impossible, so S(A) cannot be false, and we conclude that S(A) is true--if the bag is empty, all the balls in it are red (although there are no balls at all). Note that it is also true that all the balls in the bag are black--there is no contradiction in this if the bag is empty. In a more abstract way, if S(A) is a statement of the form: For all x in A, S(x) is true then, whenever A is empty, S(A) is true--this does not depend on the particular form of the statement S(x). We can also see it in another way--S(A) means that A is a subset of the set of objects such that S(x) is true. Now, the empty set is a subset of any set, so, if A is empty, A is indeed a subset of the set of objects that verify S(x), and S(A) is true. The second aspect is the definition of a function. A function f : A -> B is merely a _set_, namely a set of ordered pairs (a,b) with a in A and b in B, and such that every element of A appears in exactly one pair. Like any set, a function can be empty. If A is empty, there are no ordered pairs (a,b), since there are no elements a to pick from A. The only possible function is then the empty function--(the empty set). To see that it is indeed a function, let f be the empty set. We must verify that: "For all a in A, a appears in exactly one element of f" As this statement is of the form "for all a in A, (whatever)", it is always true if A is empty. Now, if A is not empty, and B is empty, we can choose an element a in A. If the set f is to be a function, it must contain exactly one element (a,b) for the given a and some b in B. As there are no b in B available, this is impossible. Note that, if both A and B are empty, the empty set is also a function from A to B. If A and B are finite sets, of m and n elements respectively, then each of the m elements of A must appear in one pair (a,b), and there are n elements of B to choose from. This means that there are a total of n^m possible functions from A to B. If A is empty and B is not, n^m = n^0 = 1--there is one function from A to B. If A is not empty and B is empty, n^m = 0^m = 0--there are no functions from A to B. This breaks down if both A and B are empty, because it depends on how you define 0^0--this is essentially a matter of convention. In this case, we must define 0^0 = 1, which is not the most commonly accepted convention. Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum