A Venn diagram with the ordered pairs of integers,
(x, y), as the universal set. A is a subset of B and
B is a subset of A.
Set notation: V = {a, e, i, o, u}
A set can be infinite, such as N, the set of natural numbers {0, 1, 2, 3, ...}.
There are no duplicates in a set: {1, 3, 3, 5} = {1, 3, 5}, and order does not count.
We often use what is called set builder notation:
O = {x | x is an odd positive integer less than 10}
Here, the "|" symbol is read "such that." The use of English (or any other natural language) in set builder notation can lead to problems arising from ambiguity.
Venn diagrams can be used to represent sets. The background of the diagram, sometimes drawn as a rectangle, represents the objects under discussion (the universe of discourse).
Sets may have other sets as members. For example, if S = {a, b}, the set of all subsets of S is {{}, {a}, {b}, {a, b}}.
The size (cardinality) of a set is the number of elements it contains. Let S = {1, 2, 3}, then |S| = 3.
|{}| = 0
P({}) = {{}}
|P({})| = 20 = 1
|{{}}| = 1
P({{}}) = {{}, {{}}}
|P({{}})| = 21 = 2
The cartesian product of A and B (A X B) is the set of all ordered pairs (a, b) where a is an element of A and b is an element of B:
A X B = {(a, b) | a is an element of A and b is an element of B}.
Suppose A = {1, 2} and B = {a, b, c}:
A X B = {(1,a), (1, b), (1, c), (2, a), (2, b), (2, c)}
Let A = {a, b, c} and let B = {1, 2, 3}. Let C = {A, B} =
{{a, b, c}, {1, 2, 3}}.
Now suppose D = {A, B, C, D} = {A, B, C, {A, B, C, D}} =
{A, B, C, {A, B, C, {A, B, C, D}}} = ...
Hence, a set that contains itself is recursively defined, which is OK so far.
Now suppose that S is a set of sets defined by:
S = {x | x is not an element of x}
Can we say S = {S}?
Recursively expanding:
S = {S} = {{S}} = {{{S}}} = ...
But this contradicts the definition of S (S is an element of S).
Suppose S is not in S, for example,
S = {A, B, C}, where A, B, and C are defined as above.
S contains A which does not belong to itself, it contains B which does not belong to itself, and it contains C, which does not belong to itself.
However, the definition also says S must contain every set that does not belong to itself, so if S itself fulfills that definition, it must belong. But if it does belong, then it fails the definition and can't belong, a contradiction.