Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/

Associated Topics:
High School Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search