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

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

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.

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

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

Sets may be defined intensionally or extensionally.

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.

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

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.

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

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*}

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

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

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

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*}

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

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}`.

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

Specifically:

- (x in A & B) <-> (x in A & x in B)
- (x in A | B) <-> (x in A | x in B)
- (x in A triangle B) <-> (x in A xor x in B)
- (X in A, A <= B) <-> (x in A -> X -> B)

For example,

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

This duality / connection

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

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*}

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*}

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*}

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*}

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*}

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*}

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*}

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*}

Definition:

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

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*}

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*}

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*}

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

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*}

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.

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.

Set may be represented in several ways.

- We use sentence letters, usually from the beginning of the alphabet, to denote sets
- The
*roster method*enumerates the elements inside braces, e.g.`{1, 2, 3}`. For sets where the pattern is clear, an ellipsis may be used for conciseness to represent an infinite number of elements, e.g.`{1, 2, 3, ...}`. - The
*set-builder notation*denotes a set by description, e.g.`{x | P(x)}`or`{ n * n | odd(n)}`. Technically, the latter is an abbreviation for`{x | exists n (x == n * n)}`since formally expressions may not appear on the left. This is equivalent to writing`x in A <=> P(x)`. - Venn diagram

(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}`.

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

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/

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.

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.

Hamlos. Naive Set Theory.

Saw some praise for it on MathExchange.