Set

static/images/sets_of_numbers.jpg

A Venn diagram depicting the relationship between the real numbers, the rational numbers, the integers, and the natural numbers.

A set (from Latin secta "a following") is an unordered collection of distinct objects. For example, the natural numbers (N), the integers (Z), the primes (P), the rational numbers (Q), the real numbers (R), the complex numbers, (C), a geometric figure, an alphabet_, the Cantor set, the points on a plane, the colors, the Presidents.

Contents

1   Etymology

from Latin secta "a following"

set - a collection of things sect section

from Latin sedere "sit"

sessile - pertaining to sitting session sedate sedentary seance - sitting set (v.) - to cause to sit setback settle - long bench settle (v.) - come to rest settler - one who sets assess - to sit beside; ad "to" obsess - to sit against; ob "against" supersede - to sit above insidious - deceitful, cunning, ambush; to sit in dissident - to sit apart subsidy - help, aid; to sit behind subsidiary - serving to assist or supplement subside - to sit down reside - to sit again siege - a seat besieged - to surround with hostile forces soot - what settles saddle - seat for a rider

2   Cantor set

The Cantor set is a set of point lying on a single line segment that has a number of remarkable properties.

It was discovered in 1874 by Henry John Stephen Smith and introduced by German mathematician George Cantor in 1883.

Has the same number of elements as the unit interval and has size 0.

C = C_1 & C_2 & ... & C_inf

C1 = [0, 1] - (1/3, 2/3)

u(C1) = 2/3

C2 = C1 - (1/9, 2/9) - (7/9, 8/9)

u(C2) = 4/9

u(C) = 2/3 ** n for all n = 0

.022222.... = 2 * 1/ 9 + 2 * 1 / 27 + 2 * 1 / 81
= 2/9 * sum(1/3 ^ n) = 2/9 * 1 / (1 - 1/3) = 1 /3

What is Cn base 3?

C2 = {x in [0, 1] | x = (u, a2-)_3, where a1, a2 != 1}

C_n = {x in [0, 1] | x = (a1 ... an-)_3, where a1, ..., an != 1}

C = {x in [0, 1] | x = (a1, ...) where ai != 1}

The cantor set is in bijection with the collection of all inifteint strings of 0's and 2's.

3   Study

The study of sets is called set theory, a branch of mathematics.

4   Form

The objects in a set are called its elements or members.

Sets may be defined intensionally or extensionally.

4.1   Partition

A partition of a set is a set of nonempty sets such that any two of them are disjoint and the union of all of them is the original set. Formally, a partition \(P\) of a set \(S\) is a set of subsets with the following properties: no subset is empty, all subsets are disjoint, and the union of all subsets cover the original.

\begin{equation*} \forall s_i \in P, s_i \neq \emptyset \end{equation*}
\begin{equation*} \forall s_i, s_j \in P, i \neq j \rightarrow s_i \cap s_j = \emptyset \end{equation*}
\begin{equation*} U_{i=1} s_i = S \end{equation*}

For example, let A be the set of all even integers and B the set of all odd integers. Then {A, B} is a partition of the set of all integers.

5   Properties

5.1   Countable

A set is countable iff it has same cardinality as some subset of the set of natural numbers otherwise it is called uncountable.

5.2   Ordering

A set A is partially (or totally) ordered by R if R is an ordering on A.

A set is well-ordered if it has a least element, e.g. the natural numbers but not the integers. A well-ordering property is necessary for induction.

A partially ordered set (= poset) consists of a set along with an ordering relation.

static/images/Hasse_diagram_of_powerset_of_3.svg

Hasse diagram, powerset of {x,y,z} ordered by inclusion.

5.3   Closure

A set has closure under an operation if performance of that operation on members of the set always produces a member of the same set.

For example, the integers are closed under subtraction, but the natural numbers are not (since 0 - 1 is not a natural number).

5.4   Identity element

The identity element of a set under some operation is some element of that set that leaves other elements unchanged when combined with them.

\begin{equation*} \exists e \in A, \forall x \in A, R(e, x) = R(x, e) = x \end{equation*}

6   Classification

6.1   Empty set

The empty set is the set with no members. It is denoted as "0".

6.2   Singleton

A singleton or unit set is a set with exactly one element.

6.3   Collection

A collection (= family) is a set of sets.

7   Axioms

7.1   Comprehension

The axiom of comprehension states that any collection of objects of any sort that you can list or clearly describe may be considered to form a set.

\begin{equation*} \forall P, \exists A, A = \{ x \mid P(x) \} \end{equation*}

7.1.1   Separation

The axiom of separation states {x | x in A and P(x)}. More limited than comprehension.

7.2   Extensionality

The axiom of extensionality states that sets have no other characteristics than being a collection of things. (Therefore, if two sets have exactly the same elements, then they must be equal being there is nothing else that could distinguish them.)

\begin{equation*} A = B \leftrightarrow \forall x (x \in A \leftrightarrow x \in B) \end{equation*}

In this sense, sets may have duplicate elements, e.g. {x} == {x, x}, and order does not matter, e.g. {x, y} = {y, x}.

8   Operations

To each of the basic connectives in propositional logic, with one exception, there is a corresponding notion in set theory.

Specifically:

For example,

(P and P -> Q) -> Q) is the same as (A & (A | A <= B)) <= B

This duality / connection

8.1   Equality

Two sets are equal if and only if they have the same elements.

8.2   Intersection

The intersection of any two sets is the set:

\begin{equation*} A \cap B \leftrightarrow \{ x \mid x \in A \wedge x \in B \} \end{equation*}
static/images/set_intersection.png

Two sets are called disjoint if their intersection is empty.

Corresponds to conjunction.

Properties:

\begin{equation*} A \cap B \leftrightarrow B \cap A \end{equation*}
\begin{equation*} A \cap (B \cap C) \leftrightarrow (A \cap B) \cap C \end{equation*}
\begin{equation*} A \cap (B \cup C) \leftrightarrow (A \cap B) \cup (A \cap C) \end{equation*}
\begin{equation*} A \cap (B - C) \leftrightarrow (A \cap B) - (A \cap C) \end{equation*}

8.3   Union

The union of any two sets is the set:

\begin{equation*} A \cup B \leftrightarrow \{ x \mid x \in A \vee x \in B \} \end{equation*}
static/images/set_union.png

Properties:

\begin{equation*} A \cup B \leftrightarrow B \cup A \end{equation*}
\begin{equation*} A \cup (B \cup C) \leftrightarrow (A \cup B) \cup C \end{equation*}
\begin{equation*} A \cup (B \cap C) \leftrightarrow (A \cup B) \cap (A \cup C) \end{equation*}

Corresponds to disjunction.

The union of A or the union over A:

\begin{equation*} \bigcup \alpha = \bigcup_{A \in \alpha}^A = \{ x \mid \exists A \in \alpha (x \in A) \} \end{equation*}
\begin{equation*} B \cup (\bigcap_{i \in I} A_i) = \bigcap_{i \in I} (B \cup A_i) \end{equation*}
\begin{equation*} B \cap (\bigcup_{i \in I} A_i) = \bigcup_{i \in I} (B \cap A_i) \end{equation*}
\begin{equation*} (\bigcup_{i \in I} A_i)' = \bigcap_{i \in I} (A_i') \end{equation*}
\begin{equation*} (\bigcap_{i \in I} A_i)' = \bigcup_{i \in I} (A_i') \end{equation*}

8.4   Relative complement

The relative complement of two sets (A - B) is equal to the elements in A that are not in B.

\begin{equation*} A - B \leftrightarrow \{ x \mid x \in A \wedge \neg (x \in B) \} \end{equation*}
static/images/set_complement_relative.png

Properties:

\begin{equation*} A - (B \cap C) \leftrightarrow (A - B) \cup (A - C) \end{equation*}
\begin{equation*} A - (B \cup C) \leftrightarrow (A - B) \cap (A - C) \end{equation*}

8.5   Absolute complement

The absolute complement (= complement of A = A complement) is the relative complement to a certain universe of discourse.

\begin{equation*} A' \leftrightarrow \{ x \mid x \in A \wedge \neg (x \in U) \} \end{equation*}
static/images/set_complement_absolute.png

We cannot define a true absolute complement, since the complement of the empty set would have to include every set, leading to Russel's paradox.

Properties:

\begin{equation*} A \cap A' \leftrightarrow \emptyset \end{equation*}
\begin{equation*} A \cup A' \leftrightarrow U \end{equation*}
\begin{equation*} (A \cap B)' \leftrightarrow A' \cup B' \end{equation*}
\begin{equation*} (A \cup B)' \leftrightarrow A' \cap B' \end{equation*}
\begin{equation*} A - B \leftrightarrow A \cap B' \end{equation*}
\begin{equation*} (A')' \leftrightarrow A \end{equation*}

8.6   Symmetric difference

Definition:

\begin{equation*} A \Delta B \leftrightarrow (A - B) \cup (B - A) \leftrightarrow A \cup B - A \cap B \end{equation*}
http://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Venn0110.svg/200px-Venn0110.svg.png

Properties:

\begin{equation*} A \Delta B \leftrightarrow B \Delta A (Commutativity) \end{equation*}
\begin{equation*} A \Delta (B \Delta C) \leftrightarrow (A \Delta B) \Delta C (Associativity) \end{equation*}
\begin{equation*} A \Delta \emptyset \leftrightarrow A (Identity) \end{equation*}
\begin{equation*} A \Delta A \leftrightarrow \emptyset (Inverse) \end{equation*}
\begin{equation*} A \cap (B \Delta C) \leftrightarrow (A \cap B) \Delta (A \cap C) \end{equation*}

8.7   Comparison

Subset (opposite = superset), proper subset, & equality:

\begin{equation*} A \subseteq B \leftrightarrow \forall x (x \in A \rightarrow x \in B) \end{equation*}
\begin{equation*} A = B \leftrightarrow A \subseteq B \wedge B \subseteq A \end{equation*}
\begin{equation*} A \subset B \leftrightarrow A \subseteq B \wedge \neg (B \subseteq A) \end{equation*}

Properties:

\begin{equation*} \emptyset \subseteq A \subseteq A \end{equation*}
\begin{equation*} \neg (A \subset A) \end{equation*}
\begin{equation*} A \subseteq B \subseteq C \rightarrow A \subseteq C \end{equation*}
\begin{equation*} A \cap B \subseteq A \subseteq A \cup B \end{equation*}
\begin{equation*} A \subseteq B \leftrightarrow A \cup B = B \leftrightarrow A \cap B = A \end{equation*}
\begin{equation*} A \subseteq B \cap C \leftrightarrow A \subseteq B \wedge A \subseteq C \end{equation*}
\begin{equation*} A \cup B \subseteq C \leftrightarrow A \subseteq C \wedge B \subseteq C \end{equation*}
\begin{equation*} A = B \leftrightarrow A \cup B = A \cap B \end{equation*}

8.8   Cardinality

The cardinality of a set A, |A|, is the number of members of A.

The sum rule for counting:

\begin{equation*} |\emptyset| = 0 \end{equation*}
\begin{equation*} |A \cup B| \leftrightarrow |A| + |B| - |A \cap B| \end{equation*}

8.9   Power set

static/images/set_power_set.png

The power set of \(A\), denoted \(\rho(A)\) or \(2^A\), is the set of all subsets of \(A\). That is, \(\rho(A) = 2^A = \{B \mid B \subseteq A\}\). For example:

\begin{equation*} \rho(\{ a, b, c \}) = \{ \emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}\, \{a, c\}\, \{b, c\}\, \{a, b, c\} \} \end{equation*}

Properties:

\begin{equation*} \rho^1(\emptyset) = \{ \emptyset \} \end{equation*}
\begin{equation*} \rho^2(\emptyset) = \{ \emptyset, \{ \emptyset \} \} \end{equation*}
\begin{equation*} \rho^n(\emptyset) = \{ \rho^{n-1}(\emptyset), \{ \rho^{n - 1}(\emptyset) \} \} \end{equation*}
\begin{equation*} \rho(A \cap B) = \rho(A) \cap \rho(B) \end{equation*}
\begin{equation*} A = B \leftrightarrow \rho(A) = \rho(B) \end{equation*}
\begin{equation*} A \subseteq B \leftrightarrow \rho(A) \subseteq \rho(B) \end{equation*}
\begin{equation*} A \subset B \leftrightarrow \rho(A) \subset \rho(B) \end{equation*}
\begin{equation*} |\rho(A)| = 2^{|A|} \end{equation*}

Power sets are used in spelling correctors.

There are multiple algorithms to generate the power set of a set. Because a power set is exponentially larger than its base set, a good algorithm will generate the elements of the power set iteratively and avoid duplicating work.

A recursive solution constructs the power set from subproblems:

def pset(xs):
    try:
        x = next(xs)
    except StopIteration:
        yield ()
    else:
        for y in pset(xs):
            yield (x,) + y
            yield y

Power sets can also be defined as a union of `combinations`_. This solution is also the fastest in Python:

from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

This solution also generates the results in sorted order. A slower, but alternative way to construct the set in sorted order is the following:

def gen_words_by_size(base_word):
    word_lists = [[] for _ in base_word]
    word_lists.append([''])
    for c in base_word:
        for i, word_list in enumerate(word_lists):
            for word in word_list:
                word_lists[i - 1].append(c + word)
    return word_lists

8.10   Cartesian product

The Cartesian product (pronounced "A cross B") is a `binary relation`_ that returns the set of all ordered pairs (a, b) where a in A and b in B:

\begin{equation*} A \times B = \{(x, y) \mid x \in A \wedge y \in B \} \end{equation*}
static/images/set_cartesian_product.png

For example:

\begin{equation*} \{ 1, 2, 3 \} \times \{ 4, 5 \} = \{ (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5) \} \end{equation*}

Properties:

The fundamental counting principle (= product rule for counting):

\begin{equation*} |A \times B| = |A| \times |B| \end{equation*}

A subset of a Cartesian product is called a relation. (Circular definition?)

The Cartesian product is not formally associative, but practically is considered so. Thus:

\begin{equation*} A \times B \times C = \{ (a, b, c) \mid a \in A, b \in B, c \in C \} \end{equation*}

These definitions can be extended to define ordered n-tuples and Cartesian products of any number of sets.

8.11   Jaccard index

The Jaccard index is a statistic used for comparing the similarity and diversity of sample set. The Jacard index of two sets is defined as:

\begin{equation*} \frac{|A \cap B|}{|A \cup B}| = \frac{|A \cap B|}{|A| + |B| - |A \cap B|} \end{equation*}

The Jaccard coefficient measures similarity between finite sample sets, and is defined as the size of the intersection divided by the size of the union of the sample sets

A Jaccard index is used to measure the similarity of sets, which has application in machine learning.

9   Representation

Set may be represented in several ways.

9.1   Interval notation

(a, b) = {x | a <  x <  b}  (Open interval)
[a, b) = {x | a <= x <  b}  (Half-open interval)
(a, b] = {x | a <  x <= b}  (Half-open interval)
[a, b] = {x | a <= x <= b}  (Closed interval)

(a, inf) = {x | x > a}      (Open unbounded interval or ray)
[a, inf) = {x | x > a}      (Close unbounded interval or ray)
...

For example, [1, 10] == {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

9.2   Indexed Families of Sets

It is common to denote the individual sets in the collection with a subscripted variable called an index when describing a collection of sets. For example, we might sets A_n for each natural number n, and then define the collection of all of these sets A_n. In this type of situation, the set N (that is, the set over which the subscript ranges) is referred to as an index set for the collection of sets, and the collection itself is called an indexed family of sets.

10   History

Russel's paradox: Let R be the set of all sets that are not members of themselves. If R is not a member of itself, then its definition dictates that it must contain itself, and if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves. The barber paradox is derived from Russel's paradox: The barber is the "one who shaves all those, and those only, who do not shave themselves." The question is, does the barber shave himself? It was used by Bertrand Russell himself as an illustration of the paradox, though he attributes it to an unnamed person who suggested it to him.

In 1908, two ways of avoiding the paradox were proposed, Russell's type theory and the Zermelo set theory, the first constructed axiomatic set theory.

The theory of types was introduced by Russell in order to cope with some contradictions he found in his account of set theory.

http://plato.stanford.edu/entries/type-theory/

10.1   Naive set theory

Naive set theory is ..

Naive set theory is based completely on the axioms of extensionality and comprehension. However it has some severe problems. For this reasons, this early form of set theory is now called naive set theory.

Bertrand Russell showed that naive set theory is inconsistent. To prove this, he uses the comprehension axiom to form the set of all sets that are not members of themselves.

\begin{equation*} A = \{ B | \neg (B \in B) \} \end{equation*}

Then we ask whether A is a member of itself.

Since naive set theory both does not seem to lead to any contradictions if we avoid defining sets of all sets and is less complex than modern axiomatic set theory, mathematicians use it unless they are trying to be careful or formal or both.

10.2   Zermelo-Frankel set theory

Russel's paradox leads to Zermelo-Fraenkel (ZF) set theory. Godel's incompleteness theory states that the consistently of a "reasonable" mathematical theory cannot be proved without using the postulates that go beyond that theory. That that can be said with ZFC set theory is that nearly a century of experience with it has not produced any contradiction.


In computer science, sets typically must consist of distinct elements. This distinguishes them from multisets, which may contain repeated elements.


Can't remember the name of this game, but the idea is you have two cards representing two numbers from a set of your choosing. Given you can pick the set, can you outsmart an omniscience being? I want the name again, but I think the solution is as simple as choose from a infinite set of 0 to infinity. Since any number you reveal on the first try, n, has n numbers left and infinity numbers right, you should always flip again. Really need the name of this problem.

11   Further reading