Next: Number Theory
Up: Fundamentals
Previous: Algebraic structures
Informally:
- N = { 0,1,... } or N = { 1,2,... }
Wether 0 is in N
depends on where you live and what is your field
of interest. At the informal level it is a religious topic.
- Z = { ..., - 1,0,1,... }
- Q = { p/q | p, q in Z and q != 0 }
- R = { d_0.d_1d_2... | d_0 in Z and 0 <= d_i <= 9 for i > 0 }
- C = { a + b o i | a, b in R and i^2 = -1 }
Formally (following the mainstream in math) the numbers are constructed
from scratch out of the axioms of Zermelo Fraenkel set theory (a.k.a. ZF set
theory) [Enderton77, Henle86, Hrbacek84]. The only things that can be derived
from the axioms are sets with the empty set at the bottom of the hierarchy.
This will mean that any number is a set (it is the only thing you can derive
from the axioms). It doesn't mean that you always have to use set notation
when you use numbers: just introduce the numerals as an abbreviation of the
formal counterparts.
The construction starts with N
and algebraically speaking, N
with its
operations and order is quite a weak structure. In the following constructions
the structures will be strengthen one step at the time: Z
will be an
integral domain, Q
will be a field, for the field R
the order will be
made complete, and field C
will be made algebraically complete.
Before we start, first some notational stuff:
- a pair (a,b) = { { a } , { a,b } } ,
- an equivalence class [a] = { b | a == b } ,
- the successor of a is s(a) = a U { a } .
Although the previous notations and the constructions that follow are the de
facto standard ones, there are different definitions possible.
- { } in N
- if a in N then s(a) in N
- N
is the smallest possible set such that the preceding rules hold.
Informally n = { 0,...,n - 1 } (thus 0 = { } , 1 = { 0 } , 2 = { 0,1 } ,
3 = { 0,1,2 } ). We will refer to the elements of N
by giving them a
subscript _n. The relation <_n on N
is defined as: a_n <_n b_n iff
a_n in b_n. We can define +_n as follows:
- a_n +_n 0_n = a_n
- a_n +_n s(b_n) = s(a_n +_n b_n)
Define *_n as:
- a_n *_n 0_n = 0_n
- a_n *_n s(b_n) = (a_n *_n b_n) +_n a_n
We define an equivalence relation on N x N: (a_n,b_n) ==_z(c_n,d_n) iff a_n +_n d_n = c_n +_n b_n. Note that ==_z
``simulates'' a subtraction in N
. Z = { [(a_n,b_n)]_z | a_n, b_n in N } . We will refer to the elements of Z
by giving them a subscript _z.
The elements of N
can be embedded as follows: embed_n : N --> Z
such that embed_n(a_n) = [(a_n,0_n)]_z. Furthermore we can define:
- [(a_n,b_n)]_z <_z [(c_n,d_n)]_z iff a_n +_n d_n <_n c_n +_n b_n
- [(a_n,b_n)]_z +_z [(c_n,d_n)]_z = [(a_n +_n c_n, b_n +_n d_n)]_z
- [(a_n,b_n)]_z *_z [(c_n,d_n)]_z =
[((a_n *_n c_n) +_n (b_n *_n d_n), (a_n *_n d_n) +_n (c_n *_n b_n))]_z
We define an equivalence relation on Z x (Z { 0_z }):
(a_z,b_z) ==_q (c_z,d_z) iff a_z *_z d_z = c_z *_z b_z. Note that
==_q ``simulates'' a division in Z
. Q = { [(a_z,b_z)]_q | a_z in Z and b_z in Z { 0_z } } . We will refer to the
elements of Q
by giving them a subscript _q. The elements of Z
can be
embedded as follows: embed_z : Z --> Q such that embed_z(a_z) = [(a_z,1_z)]_q. Furthermore we can define:
- [(a_z,b_z)]_q <_q [(c_z,d_z)]_q iff a_z *_z d_z <_z c_z *_z b_z
when 0_z <_z b_z and 0_z <_z d_z
- [(a_z,b_z)]_q +_q [(c_z,d_z)]_q = [((a_z *_z d_z) +_z (c_z *_z b_z), b_z *_z d_z)]_q
- [(a_z,b_z)]_q *_q [(c_z,d_z)]_q = [(a_z *_z c_z, b_z *_z d_z)]_q
The construction of R
is different (and more awkward to understand) because
we must ensure that the cardinality of R
is greater than that of Q
.
Set c is a Dedekind cut iff
- { } subset c subset Q (strict inclusions!)
- c is closed downward:
if a_q in c and b_q <_q a_q then b_q in c
- c has no largest element:
there isn't an element a_q in c such that b_q <_q a_q for all b_q != a_q in c
You can think of a cut as taking a pair of scissors and cutting Q
in two
parts such that one part contains all the small numbers and the other part
contains all large numbers. If the part with the small numbers was cut in such
a way that it doesn't have a largest element, it is called a Dedekind cut.
R = { c | c is a Dedekind cut } . We will refer to the elements of
R
by giving them a subscript _r. The elements of Q
can be embedded as
follows: embed_q : Q --> R such that embed_q(a_q) = { b_q | b_q <_q a_q } . Furthermore we can define:
- a_r <_r b_r iff a_r subset b_r (strict inclusion!)
- a_r +_r b_r = { c_q +_q d_q | c_q in a_r and d_q in b_r }
- -_r a_r = ; { b_q | there exists an c_q in Q such that b_q <_q c_q and (-1)_q *_q c_q in a_r }
- |a_r|_r = a_r U -_r a_r
- *_r is defined as:
- if not a_r <_r 0_r and not b_r <_r 0_r
then a_r *_r b_r = 0_r U { c_q *_q d_q | c_q in a_r and d_q in b_r }
- if a_r <_r 0_r and b_r <_r 0_r then a_r *_r b_r = |a_r|_r *_r |b_r|_r
- otherwise a_r *_r b_r = -_r (|a_r|_r *_r |b_r|_r)
There exists an alternative definition of R
using Cauchy sequences: a
Cauchy sequence is a s : N --> Q such that s(i_n) +_q((-1)_q *_q s(j_n)) can be made arbitrary near to 0_q for all
sufficiently large i_n and j_n. We will define an equivalence relation
==_r on the set of Cauchy sequences as: r ==_r s iff r(m_n) +_q((-1)_q *_q s(m_n)) can be made arbitrary close to 0_q for all
sufficiently large m_n. R = { [s]_r | s is a Cauchy sequence } .
Note that this definition is close to ``decimal'' expansions.
C = R x R. We will refer to the elements of C
by giving them a
subscript _c. The elements of R
can be embedded as follows: embed_r : R --> C such that embed_r(a_r) = (a_r,0_r). Furthermore we can
define:
- (a_r,b_r) +_c (c_r,d_r) = (a_r +_r c_r, b_r +_r d_r)
- (a_r,b_r) *_c (c_r,d_r) = ((a_r *_r c_r) +_r -_r (b_r * d_r), (a_r *_r d_r) +_r (b_r *_r c_r))
There exists an elegant alternative definition using ideals. To be a bit
sloppy: C = R [x]/< (x *_r x) +_r 1_r > , i.e. C
is the resulting
quotient ring of factoring ideal < (x *_r x) +_r 1_r > out of the ring
R [x] of polynomials over R
. The sloppy part is that we need to define
concepts like quotient ring, ideal, and ring of polynomials. Note that this
definition is close to working with i^2 = -1: (x *_r x) +_r 1_r = 0_r can be
rewritten as (x *_r x) = (-1)_r.
At this moment we don't have that N
is a subset of Z
, Z
of Q
,
etc. But we can get the inclusions if we look at the embedded copies of N
,
Z
, etc. Let
- N' = ran embed_r o embed_q o embed_z o embed_n
- Z' = ran embed_r o embed_q o embed_z
- Q' = ran embed_r o embed_q
- R' = ran embed_r
For these sets we have N' subseteq Z' subseteq Q' subseteq R' subseteq C. Furthermore these sets have all the properties that the
``informal'' numbers have.
Well, for some of the more alien parts of math we can extend this standard
number system with some exotic types of numbers. To name a few:
- Cardinals and ordinals
Both are numbers in ZF set theory [Enderton77, Henle86, Hrbacek84] and
so they are sets as well. Cardinals are numbers that represent the
sizes of sets, and ordinals are numbers that represent well ordered
sets. Finite cardinals and ordinals are the same as the natural
numbers. Cardinals, ordinals, and their arithmetic get interesting and
``tricky'' in the case of infinite sets.
- Hyperreals
These numbers are constructed by means of ultrafilters [Henle86] and
they are used in non-standard analysis. With hyperreals you can treat
numbers like Leibnitz and Newton did by using infinitesimals.
- Quaternions and octonions
Normally these are constructed by algebraic means (like the alternative
C
definition that uses ideals) [Shapiro75, Dixon94]. Quaternions are
used to model rotations in 3 dimensions. Octonions, a.k.a. Cayley
numbers, are just esoteric artifacts :-). Well, if you know where they
are used for, feel free to contribute to the FAQ.
- Miscellaneous
Just to name some others: algebraic numbers [Shapiro75], p-adic
numbers [Shapiro75], and surreal numbers (a.k.a. Conway
numbers) [Conway76].
Cardinals and ordinals are commonly used in math. Most mortals won't
encounter (let alone use) hyperreals, quaternions, and octonions.
References
J.H. Conway. On Numbers and Games, L.M.S. Monographs, vol. 6. Academic Press, 1976.
H.B. Enderton. Elements of Set Theory. Academic Press, 1977.
G.M. Dixon. Division Algebras; Octonions, Quaternions, Complex Numbers and the
Algebraic Design of Physics. Kluwer Academic, 1994.
J.M. Henle. An Outline of Set Theory. Springer Verlag, 1986.
K. Hrbacek and T. Jech. Introduction to Set Theory. M. Dekker Inc., 1984.
L. Shapiro. Introduction to Abstract Algebra. McGraw-Hill, 1975.
This subsection of the FAQ is Copyright (c) 1994, 1995 Hans de Vreught.
Send comments and or corrections relating to this part to
J.P.M.deVreught@cs.tudelft.nl
Next: Number Theory
Up: Fundamentals
Previous: Algebraic structures
Alex Lopez-Ortiz
Fri Feb 20 21:45:30 EST 1998