Texts:
Topics:
The theory of sets, particularly finite sets, is so simple and straight-forward
that one would think that it would have been formulated in ancient times, but
instead it was not until the last part of the nineteenth century that the
theory of sets was developed by Georg Cantor. And what is more surprising is
that the theory of sets was initially controversial. Furthermore the theory
of sets in its naive form involved some surprising paradoxes.
Before getting into these matters let us consider the basics of set theory.
A set is a collection of elements such as the letters a, b, c. If
this set is named L then L = {a, b, c}. The order in which the elements
of a set are listed does not make a difference. The set {b, c, a}
is the same as the set {a, b, c}. There however cannot be any repetitions
in the listing of elements in set; i.e., {a, b, c, b} is not a properly
described set.
A set A is a subset of a set B if there is no element of A that is not
an element of B. Thus {a, b} is a subset of {a, b, c}. This
means that any set is a subset of itself.
There is a set that contains not elements, φ = { }. This is usually
called the "empty set." φ is a subset of any set A because there is
no element of φ which is not an element of A.
The cardinality is the number of elements in a set. This is usually denoted
by #(set). For example, #({a, b, c}) = 3.
The power set of a set A is the set of all subsets of A. This includes
the empty set φ and the set itself. The number of
elements in the power set of A, pow(A), is 2 raised to the power of the number of
elements of A; i.e.,
Thus the power set of {a, b, c} is
{ φ, {a}, {b}, {c}, {a, b},
{a, c}, {b, c}, {a, b, c}} and the cardinality of this set is 8, which is
23.
In addition is defining a set by listing its elements a set can be
described by the set of elements such that a certain proposition is true;
i.e., C = {x|P(x)}, C is the set of elements x such that the proposition
P(x) is true.
There is the notation for the fact that an element x belongs to a set A;
i.e., x∈A, which is also read as x 'is an element of' A. Note that "belongs to" is a different
concept from "is a subset of." Thus we say x∈A but
we say {x}, the set that contains the single element x, is a subset of A.
The intersection of two sets is the set of elements that belong to both
A and B and is denoted as A∩B. This is equivalent
to
The union of two sets is the set of elements that belong to either A or B
(or both). Thus,
The difference of two sets, A-B, is the set elements that are in A but not
in B. The complement of a set A with respect to some overall set U is the
set of elements of U that are not in A; i.e,,
From these definitions some interesting theorems can be derived:
#(pow(A)) = 2#(A)
A∩B = {x|x∈A and x∈B}.
A∪B = {x|x∈A or x∈B}.
Ac =
{x|x∈ and x 
A}
= U-A
| Theorem | Name |
|---|---|
| (Ac)c = A | The complement of a complement is the original set |
| (A ∪ B) ∪ C =
A ∪ (B ∪ C) |
Associativity of set union |
| (A ∩ B) ∩ C =
A ∩ (B ∩ C) |
Associativity of set intersection |
The Cartesian product of two sets, A and B is the set of ordered pairs (a,b) such that a belongs to A and b belongs to B. For example, if A is the set {red, green} and B is the set {1, 2, 3} then the Cartesian product of A and B is the set { (red, 1), (red, 2), (red, 3), (green, 1), (green, 2), (green, 3)}.
The set of natural numbers; 1,2,3,... ; is infinite and the order of this infinity is denoted as aleph null . Any set such that there exists a one-to-one correspondence with set is said to be countable or denumerable. For example, the set of positive rational numbers is countable. To show this consider the set of all ratios of integers tabulated as follows:
| 1/1 | 1/2 | 1/3 | 1/4 | ..... |
| 2/1 | 2/2 | 2/3 | 2/4 | ..... |
| 3/1 | 3/2 | 3/3 | 3/4 | ..... |
| 4/1 | 4/2 | 4/3 | 4/4 | ..... |
| .. | .. | .. | .. | ...... |
The set of positive rational numbers are found in this table; i.e., the rational numbers consitute a subset of this table. The set of ratios can be counted; i.e. put into a one-to-one correspondence with the natural numbers; by enumerating them in the order shown by the arrows. The positive rationals, being a subset of a denumerable set, cannot have a cardinality greater than aleph null. Since there is no largest rational the cardinality is exactly aleph null.
The real numbers on the other hand are not countable. A proof of this can be given by contradiction. Consider the numbers in the interval from 0 to 1. Suppose they can be listed in sequence, x1,x2,x3,.... Now consider their decimal representations:
x1 = 0.a11 a12 a13 ......
x2 = 0.a21 a22 a23 ......
x3 = 0.a31 a32 a33 ......
..................
where the aij is a digit, {0,1,2,...,9}. Now what about a number
such that b1 is any digit except a11,
b2 is any digit except a22, and so on.
By the method of construction b cannot fit into any place in the sequence because if b=xJ we would have the contradiction that its J-th digit was not equal to its J-th digit.
Therefore the set of real numbers is not countable and is larger than the set of integers.
In theoretical economics, such as general equilibrium analysis, there comes at point where one needs to know whether the solution to a system of equations exists; or, more specifically, under which conditions will a solution necessarily exist. The mathematical analysis usually relies on fixed point theorems. Let f be a function which maps a set S into itself; i.e. f:S->S. A fixed point of the mapping is an element x belonging to S such that f(x)=x. If the system equation for which a solution is sought is g(x)=0, then if the function g can be represented as f(x)-x a fixed point of f is a solution to g(x)=0.
Brouwer's Fixed Point Theorem: A continuous mapping of a convex, closed set into itself necessarily has a fixed point.
Examples:
A continous function that maps [0,1] into itself has a fixed point.
A continuous function that maps a unit disk into itself has a fixed point.
No Retraction Theorem: There is no continuous mapping of all points of the interior of disk onto its boundary circle.
Proof of Brouwer's fixed point theorem for a disk using the No Retraction Theorem.
Assume there is not fixed point and use the intersection of the line from x to f(x) with the boundary circle to map x into the boundary. This would be a continuous mapping of the interior onto the boundary. This is a contradiction of the No Retraction Theorem so the process must break down some where. It breaks down if f(x)=x because there is no unique line defined.
A physical example of a fixed point of a mapping is the whirlpool (or whirlpools) in a cup of tea when it is stirred. You Can't Comb the Hair on a Coconut Without There being a fixed point.
Looking for a solution to g(x)=0 by checking the value of g at a finite number of points in an interval and bracketing the solution point.
Sperner's Lemma (One dimensional version)
Consider a line segment AB subdivided into segments and the end points of the segments labeled with A's and B's arbitrarily. Let a be the number of segments labeled AA and b the number of segments labeled AB, complete segments. The number of end points labeled with A is 2a+b. Let c be the number of internal end points labeled A. If we count A end points segment by segment we get 2c+1. Therefore 2a+b=2c+1, which implies that b=2(c-a)+1 so b, the number of segments labeled AB, is an odd number. Since zero is not an odd number there has to be at least one segment labeled AB.
Two dimensional version. Let a be the number of triangles whose labels read ABA or BAB. Triangles of these two types have two edges labeled AB where as complete triangles have one edge labeled AB. The other types of triangles have no edges labeled AB. The number of AB edges counted triangle by triangle is 2a+b. However, edges inside the original triangle are counted twice since they belong to two triangles. Let c be the number of edges labeled AB inside the original triangle. Let d be the number of edges labeled AB on the outside of the original triangle. Then the number of AB edges counted is 2c+d and this is equal to 2a+b. So 2c+d=2a+b. From the preceding result b must be odd so d also must be odd. Therefore there must be at least one triangle with labeling ABC.
Euler Characteristic of a closed surface. Cube, Tetrahedron, Rhomboid, torus
Stability of fixed points Transversality Condition
Odd Number of fixed points. Lefschetz's fixed point theorem.
Morse Theory
Chaos Theory Logistics Curve
Fractal Theory Julia Sets Mandelbrot Set
Fractional Dimension