Welcome guest
You're not logged in.
249 users online, thereof 0 logged in

Explanation: Connection Between the Power Set and Functions Mapping Sets into a Set with Two Elements

The indicator function is an example of a map of an arbitrary set $X$ into another set with two elements, in this case, the set $\{0,1\}$. The definition of indicator function reveals that all maps of this kind are exactly those maps, whose carriers correspond to exactly the subsets of $X.$

The question, how many characteristic functions for are given set $X$ do exist, is therefore equivalent to the question, how many subsets of $S$ exist. But this is exactly the cardinality $|\mathcal P(X)|,$ where $\mathcal P(S)$ denotes the power set of $S.$ This result can be summarized as follows: $$|\mathcal P(X)|=2^{|X|}.$$ It is true for both, finite or infinite sets $X.$ In the combinatorics, $2^{|X|}$ is the common notation for the cardinality of the power set $\mathcal P(S).$

Despite this argument, the following proposition summarizes this result for finite sets with yet another proof:

| | | | created: 2019-09-06 23:01:22 | modified: 2019-09-07 08:05:43 | by: bookofproofs | references: [8297]

1.Proposition: Number of Subsets of a Finite Set

Edit or AddNotationAxiomatic Method

This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:


Bibliography (further reading)

[8297] Flachsmeyer, Jürgen: “Kombinatorik”, VEB Deutscher Verlag der Wissenschaften, 1972, Dritte Auflage