Mathematical Writing - Vivaldi Franco 2014
Representations of Sets
Essential Dictionary I
Consider the following geometrical sets:
· The set of triangles with a vertex at the origin.
· The set of triples of mutually tangent circles.
These definitions are easy to grasp, but how are we meant to work with sets of this kind? Suppose that we require a data structure suitable for computer implementation. We must then identify each element of our set with one or more concrete objects, such as numbers or matrices. This identification gives a description of a set in terms of another set, hopefully easier to handle.
Two sets and are said to be equivalent (written ) if there is a bi-unique correspondence between the elements of and the elements of , namely, if there exists a bijective function . A set equivalent to is said to have cardinality , and a set equivalent to is said to be countable or countably infinite. The set is countable, and so is , for any . A set is uncountable if it contains a countably infinite subset , but is not equivalent to . The set is uncountable. We see that characterising the cardinality of infinite sets requires a more sophisticated approach than mere ’counting’.
A representation of a set is any set which is equivalent to . (This is the most general acceptation of the term representation; in algebra, representations are based on a more specialised form of equivalence.)
For instance, the open unit interval and the real line are equivalent, as established by the bijective function
(2.22)
Likewise, the exponential function establishes the equivalence .
Let us consider representations of the set of lines in the plane passing through a given point . The set is uncountable. An element of is an infinite subset of , which we write symbolically as
where is a real number representing the line’s slope. The line is not of this form, and must be treated separately. Collecting all the lines together, we obtain a symbolic description of :
The simple verbal definition of seems to have drowned in a sea of symbols!
We look for a set equivalent to with a more legible structure. An obvious simplification results from representing as a set of cartesian equations:
We have merely replaced the solution set of an equation with the equation itself (cf. Sect. 3.3). This identification provides the desired bi-unique correspondence between the two sets.
We can simplify further. Because and are fixed, there is no need to specify them explicitly; it suffices to give the (possibly infinite) value of the slope. Alternatively, we could identify a line by an angle between and , measured with respect to some reference axis passing through the point . Because the angles 0 and correspond to the same line, only one of them is to be included, resulting in the half-open interval ). The equivalence between and may be achieved with a transformation of the type (2.22), where the included end-point 0 corresponds to the point at infinity.
Finally, any half-open interval may be identified with the circle , by gluing together the end-points of the interval. In our case this is achieved with the function . The essence of our set is now clear:
Exercise 2.9
Consider the phrases displayed in Sect. 2.3.1. Provide an example of each object being defined.
Exercise 2.10
Why are the sets and distinct? What are the elements of the power set ? Explain.
Exercise 2.11
Represent the algebraic sum of sets as a function.
Exercise 2.12
Consider the function that performs the prime factorization of a natural number greater than 1. What would you choose for co-domain? Explain, discussing possible representations.
Exercise 2.13
Represent the following sets:
1.
2.
3.
4.
5.
Exercise 2.14
Prove that the definition
satisfies (2.4). (This shows that an ordered pair can be defined in terms of a set, so there’s no need to introduce a new object.) Hence define an ordered triple in terms of sets.
Footnotes
1
Georg Cantor (German: 1845—1918).
2
Some authors denote the second version by the symbol .
3
Bertrand Russell (British: 1872—1970); Ernst Zermelo (German: 1871—1953).
4
The symbol [ ] indicates that the exercise must be completed without using any mathematical symbol.
5
Below, we’ll replace the term ’rule’ with something more rigorous.
6
Each assignment should contain no mathematical symbols and approximately 50 words.
7
Hermann Minkowski (Polish: 1864—1909).
8
This notation is due to Carl Friedrich Gauss (German: 1777—1855).