Collectively exhaustive events

In probability theory and logic, a set of events is jointly or collectively exhaustive if at least one of the events must occur. For example, when rolling a six-sided die, the outcomes 1, 2, 3, 4, 5, and 6 are collectively exhaustive, because they encompass the entire range of possible outcomes.

Another way to describe collectively exhaustive events, is that their union must cover all the events within the entire sample space. For example, events A and B are said to be collectively exhaustive if

where S is the sample space.

Compare this to the concept of a set of mutually exclusive events. In such a set no more than one event can occur at a given time. (In some forms of mutual exclusion only one event can ever occur.) The set of all possible die rolls is both collectively exhaustive and mutually exclusive. The outcomes 1 and 6 are mutually exclusive but not collectively exhaustive. The outcomes "even" (2,4 or 6) and "not-6" (1,2,3,4, or 5) are collectively exhaustive but not mutually exclusive. In some forms of mutual exclusion only one event can ever occur, whether collectively exhaustive or not. For example, tossing a particular biscuit for a group of several dogs cannot be repeated, no matter which dog snaps it up.

One example of an event that is both collectively exhaustive and mutually exclusive is tossing a coin. The outcome must be either heads or tails, or p (heads or tails) = 1, so the outcomes are collectively exhaustive. When heads occurs, tails can't occur, or p (heads and tails) = 0, so the outcomes are also mutually exclusive.

History

The term "exhaustive" has been used in the literature since at least 1914. Here are a few examples:

The following appears as a footnote on page 23 of Couturat 1914:

"As Mrs. LADD·FRANKLlN has truly remarked (BALDWIN, Dictionary of Philosophy and Psychology, article "Laws of Thought"), the principle of contradiction is not sufficient to define contradictories; the principle of excluded middle must be added which equally deserves the name of principle of contradiction. This is why Mrs. LADD-FRANKLIN proposes to call them respectively the principle of exclusion and the principle of exhaustion, inasmuch as, according to the first, two contradictory terms are exclusive (the one of the other); and, according to the second, they are exhaustive (of the universe of discourse)." (italics added for emphasis)

In Stephen Kleene's discussion of cardinal numbers in Kleene 1952, he uses "mutually exclusive" together with "exhaustive":

"Hence, for any two cardinals M and N, the three relationships M < N, M = N and M > N are 'mutually exclusive', i.e. not more than one of them can hold. ¶ It does not appear till an advanced stage of the theory . . . whether they are 'exhaustive' , i.e. whether at least one of the three must hold". (italics added for emphasis, Kleene 1952:11; original has double bars over the symbols M and N).

See also

• Probability theory
• Mutually exclusive events
• Event structure

References

• Louis Couturat, translated by Lydia Gillingham Robinson, 1914, The Algebra of Logic, The Open Court Publishing Company, Chicago and London.
• John G. Kemeney et al. 1958/9, Finite Mathematical Structures, Prentice-Hall, Inc. Englewood Cliffs, N.J. LCCCN: 59-12841.
• Stephen C. Kleene 1952, 6th edition 1971, Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam NY, ISBN 0 7204 2103 9.
• Alfred Tarski 1941, reprint of 1946 2nd edition, Introduction to Logic and to the Methodology of Deductive Sciences, Dover Publicationbs, Inc, NY, ISBN 0-486-28462-X (pbk.)