Representations of Sets - Essential Dictionary I

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 $$A$$ and $$B$$ are said to be equivalent (written $$A\sim B\,$$) if there is a bi-unique correspondence between the elements of $$A$$ and the elements of $$B$$, namely, if there exists a bijective function $$f:A\rightarrow B$$. A set equivalent to $$\{1,2,\ldots n\}$$ is said to have cardinality $$n$$, and a set equivalent to $$\mathbb {N}$$ is said to be countable or countably infinite. The set $$\mathbb {Z}$$ is countable, and so is $$m\mathbb {Z}$$, for any $$m\in \mathbb {N}$$. A set $$X$$ is uncountable if it contains a countably infinite subset $$Y$$, but $$X$$ is not equivalent to $$Y$$. The set $$\mathbb {R}$$ is uncountable. We see that characterising the cardinality of infinite sets requires a more sophisticated approach than mere ’counting’.

A representation of a set $$A$$ is any set $$B$$ which is equivalent to $$A$$. (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

$$\begin{aligned} f:\mathbb {R}\rightarrow (0,1)\qquad x\mapsto \frac{1}{\uppi }\arctan (x)+\frac{1}{2}. \end{aligned}$$

(2.22)

Likewise, the exponential function establishes the equivalence $$\mathbb {R}\sim \mathbb {R}^+$$.

Let us consider representations of the set $$L$$ of lines in the plane passing through a given point $$(a,b)$$. The set $$L$$ is uncountable. An element $$\lambda $$ of $$L$$ is an infinite subset of $$\mathbb {R}^2$$, which we write symbolically as

$$ \lambda =\left\{ (x,y)\in \mathbb {R}^2\,:\,y=b+s (x-a)\right\} $$

where $$s$$ is a real number representing the line’s slope. The line $$x=a$$ is not of this form, and must be treated separately. Collecting all the lines together, we obtain a symbolic description of $$L$$:

$$ L=\left\{ \left\{ (x,y)\in \mathbb {R}^2\,:\,y=b+s (x-a)\right\} \,:\, s\in R\right\} \cup \left\{ \left\{ (a,y)\in \mathbb {R}^2\,:\,y\in \mathbb {R}\right\} \right\} . $$

The simple verbal definition of $$L$$ seems to have drowned in a sea of symbols!

We look for a set equivalent to $$L$$ with a more legible structure. An obvious simplification results from representing $$L$$ as a set of cartesian equations:

$$ L\sim \{y=b+s (x-a)\,:\, s\in \mathbb {R}\}\,\cup \,\{x=a\}. $$

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 $$a$$ and $$b$$ 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 $$\theta $$ between $$0$$ and $$\uppi $$, measured with respect to some reference axis passing through the point $$(a,b)$$. Because the angles 0 and $$\uppi $$ correspond to the same line, only one of them is to be included, resulting in the half-open interval $$[0,\uppi $$). The equivalence between $$\mathbb {R}\cup \{\infty \}$$ and $$[0,\,\uppi )$$ 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 $$\mathbb {S}^1$$, by gluing together the end-points of the interval. In our case this is achieved with the function $$\theta \mapsto (\cos (2\theta ),\sin (2\theta ))$$. The essence of our set is now clear:

$$ L\sim \mathbb {R}\cup \{\infty \}\sim [0,\,\uppi )\sim \mathbb {S}^1. $$

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 $$\emptyset $$ and $$\{\emptyset \}$$ distinct? What are the elements of the power set $$\mathbf {P}(\mathbf {P}(\mathbf {P}(\emptyset )))$$? 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

$$ (a,b)\mathop {=}\limits ^\mathrm{def} \{\{a\},\{a,b\}\} $$

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 $$\mathbb {N}_0$$.

3

Bertrand Russell (British: 1872—1970); Ernst Zermelo (German: 1871—1953).

4

The symbol [ $$\not \varepsilon $$ ] 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).