 |
Set Theory & Logic
(Ashlee of Braithwaite, LA.
2000-05-03
twice)
There is a barber who lives in a small town.
The barber shaves all those men and only those men who do not shave themselves.
Does the barber shave himself?
-
Stay away from the many "cute" answers that do not really address the question:
The barber can't be
a woman (otherwise the term "himself" used in the question would be improper).
It would also be cheating to consider that the barber is a boy (and therefore not a "man")
or any other kind of non-human male creature for that matter...
The dilemma remains (it's not a paradadox, as we shall see):
If the barber doesn't shave himself then he shaves himself.
If he shaves himself, then he doesn't shave himself.
The answer to this classic "problem" is simple:
There cannot possibly be any such barber!
The fact that we are wrongly told at the outset that such a barber exist
just does not make it appear out of thin air in spite of the logical contradictions
his very existence would imply.
This is no more paradoxical than a silly question like:
There's a number whose square is 4 and whose cube is 24. What is it?
Both this and the barber's "problem" are just plain nonsense.
If the existence of something leads to a contradiction,
the thing is thereby shown not to exist and any statements about it are to be considered
either nonsensical or "vacuously true":
Any such barber does shave himself.
Any such barber does not shave himself.
Any such barber has purple hair.
The name of any such barber is Isaac Newton.
All of this is true.
"Vacuously" so.
Russell's Paradox:
More seriously, it is worth pointing out that a fundamental logical
dilemma had to be resolved the same way by the pioneers of set theory:
In what's known as "Russell's paradox", we are asked to consider
the "set" of all sets that are not members of themselves.
Is it a member of itself or not?
Neither answer is acceptable...
Therefore, such a thing can't possibly be called a set!
This paradox was instrumental
in clarifying the (Zermelo-Fraenkel) axioms of modern set theory:
A "set" cannot be just anything we like.
In particular, the axioms imply that no set can be a member of itself.
Therefore, there is no "set of all sets" (it would be a member of itself).
The collection of sets that are not members of themselves thus includes all
sets and it is not a set itself.
That's the way out of Russell's paradox:
"such a set" simply does not exist, exactly like "such a barber"
cannot possibly exist in the barber's dilemma.
Meaningless Statements in Natural Languages:
A related issue about "natural" languages is that there may be
inherently meaningless statements or descriptions in a language
that's allowed to refer to itself.
For example,
"the integers that can be specified in twenty English words or less"
cannot possibly describe any unambiguous set of integers.
Otherwise, there would be such a thing as
"the smallest integer that cannot be specified in less than twenty English words",
which would thus be specified in only 13 English words...
This goes to show that natural or formal languages may include self-contradictory sentences,
not only when they refer to themselves (e.g. "This sentence is false.")
but also when they include other references to the language being used.
Bertrand Russell coined the term Berry paradox
for sentences of this latter type, because of a letter he received from G.G. Berry
in 1906
introducing the earliest such paradox by discussing, among transfinite ordinals:
The first ordinal that cannot be named in a finite number of words.
Even if you don't know what an ordinal is,
you can tell that the above phrase must be meaningless.
Its meaning, if it had any, would be an ordinal.
However, by assuming that such a meaning exists, we see that another
ordinal must be described instead.
Thus, the above can't possibly describe any
specific ordinal.
There's actually no paradox here; just a lack of meaning.
(Melissa of Denver, CO.
2000-11-06)
What is infinity and what does it mean?
(Nagaraj of Anamoose, ND. 2000-11-18)
What is the definition of infinity? Please explain to me in details.
-
Albert Einstein once said that
we can't solve problems by using the same kind of thinking we used
when we created them.
Large
numbers begot the concept,
but they are of no help in the definition of infinity.
Let's try common sense first:
A finite set has n elements, for some nonnegative integer n.
Of course, any set which isn't finite in this sense may be called infinite.
Although this common sense approach is perfectly sound, it would seem that
the basic distinction between finite and infinite sets ought not
to depend explicitely on the properties of something
as complicated as the integers.
A more fundamental approach was indeed first suggested by
Dedekind,
who turned a perceived paradox about infinite sets
into a natural definition of infinity:
An infinite set is equipollent to one of its proper subsets.
A subset
is a set contained in the set being considered
(i.e., all elements of one are elements of the other).
A proper subset is a subset
which is not equal to the entire set.
The empty set is a proper subset of any set
but the empty set itself.
Two sets are said to be equipollent
when there's a one-to-one correspondence between the elements of one and the
elements of the other.
At the most fundamental level (which may not be the most intuitive one)
the existence of infinite sets is built into the
axioms of modern set theory.
Consider the set N of natural integers
{0,1,2,3,4,5,6,...}. One of its proper subsets is the set of
all counting numbers
N* = {1,2,3,4,5,6,7,...}.
Yet, there's a trivial one-to-one correspondence betweeen those two
(the function y = x+1).
There's also a one-to-one correspondence between N and the even numbers,
between N and the squares, etc.
N is thus an example of an infinite set.
The same thing cannot be done with any finite set:
{1,2,3,4,5,6,7} cannot be put in a one-to-one
correspondence with any set of fewer than 7 elements.
Tarski's definition of infinity :
The problem with Dedekind's definition of infinity is that
a proof of its equivalence with the previous definition
(involving integers) requires the
axiom of choice,
which is normally reserved for advanced nonconstructive proofs.
It's undesirable in a context where natural integers
themselves are considered too elaborate.
There are no such problems with a definition proposed in 1924 by
Alfred
Tarski (1902-1983)
using the notion of a minimal element in
a family of sets (a minimal element is a set
not containing another set of the family).
Tarski's Definition of Finite Sets (1924)
A set is finite if, and only if, every nonempty
family of its subsets
has a minimal element.
| |
That clever definition is simply perfect from a theoretical standpoint
(although it certainly does not qualify as an intuitive one).
Infinity as a Limit of Large Numbers
If you allow mentally for the existence of such infinite sets (and you should),
you realize that there is no such thing as the "largest" integer.
The process of building larger integers is never ending.
That's what infinity is all about.
This is like the discovery game children play when trying to name the
"largest" number.
Sooner of later, one of them realizes that the game cannot possibly
be won by either player:
Regardless of what number is named, it's always possible to say something
like "twice that" (or "this plus one") and not concede.
Grasping Infinity
Mathematicians routinely study things whose infinite versions turn out to be
much simpler than the finite ones.
One example is the sum (properly called a "series"):
1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128 + 1/256 + ...
This sum is equal to 1-2-n
when carried out only to its n-th term.
It's simply equal to 1 if all
of the infinitely many terms are added up.
When the ancient Greeks were still wrestling with the concept of infinity,
the above sum was underlying something called Zeno's paradox :
Before an arrow reaches its target it must first travel
half of the distance to it (1/2),
then half of what's left (1/4),
half of what's left after that (1/8), and so forth.
Although there are infinitely many such "steps" the arrow does reach its target...
(Try it!)
ciderspider
(Mark Barnes, UK.
2000-10-11) The Number Line
How do you prove that there are more real numbers than rational ones?
Any set which may be put in a one-to-one correspondence with the integers is
said to be countable (or to have cardinality
Ào).
Infinite sets that are not countable are said to be uncountable.
Cantor used a clever argument to show that real numbers are not countable,
while rational numbers are.
The uncountability of real numbers :
The diagonal argument of Georg Cantor (1845-1918) is the remark that,
with any infinite "list" of real
numbers between 0 and 1 (such a "list" is in one-to-one correspondence with the integers),
an unlisted number may be constructed by choosing for its N-th decimal
a digit that's
different from the N-th decimal of the N-th number listed.
Numbers with
two decimal representations
(ending with infinitely many zeroes or infinitely many nines)
present a problem which is avoided by never choosing a 0 or a 9.
This still leaves 7 valid choices per step.
The number so constructed is not in the list,
since it has only one
decimal expansion and differs from any listed number in at least one decimal digit.
So, any list of reals between 0 and 1 fails to contain all
the reals between 0 and 1.
Therefore, there must be more real numbers than there are integers.
This is one of the simplest and most beautiful proofs of all times.
The countability of rational numbers :
Now, to prove that there are more reals than rationals,
it suffices to show that rationals may be put in a list.
There are neater ways to do so, but we'll describe only a
simple-minded scheme here:
At coordinates (p,q) of a whole planar grid, put the value p/q
[use zero as placeholder, if q is zero].
Starting at the center,
run through the grid along a square spiral like the one pictured at right.
Put in a growing list each ratio you encounter for the first time as you travel
this way through all possible fractions...
Any given rational will eventually appear in that list,
which is another way to say that all of them belong to the list.
(2000-10-11)
Cantor's Ternary Set
Some vanishing sets of reals have as many points as the whole line.
The probability is zero that a randomly chosen real number is rational.
This statement (which could be made precise in the proper context
of Lebesgue measure theory) holds for the set of rational numbers or
any other countable set.
However, not all sets of numbers with zero probability
(or, rather, zero measure in the sense of Lebesgue)
are countable.
It's easy to describe a set of numbers which has zero probability but yet contains
just as many elements as the whole set of real numbers
(which isn't countable).
One such example is the ternary Cantor set
obtained by removing from a segment
(of numbers from 0 to 1, say) its "middle third" and similarly removing the middle third
of any smaller segment that shows up in this (infinite) process.
Cantor's ternary set, introduced by Cantor in 1883, was first considered by
Henry Smith
in 1875. It's thus the earliest mathematical example of
a fractal endowed with self-similarity,
since it actually consists of two copies of itself one third as big.
Its dimension
d is less than 1:
(1/3)d = 1/2
d = log 2 / log 3 = 0.630929753571457437...
Equivalently, you may consider the set of all the numbers
(between zero and one) whose decimal expansions contain
only zeroes and nines.
Its probability is zero, in spite of the fact that this set contains
as many elements as the whole number line
(as sequences of zeroes and nines are in one-to-one correspondence with
sequences of zeroes and ones, which are
at least as numerous as the uncountable
set of numbers between 0 and 1).
The fractal dimension of that decimal version of the Cantor set is a
familiar number
(smaller than the above dimension of the ternary set):
d = log 2 / log 10 = 0.3010299956639811952...
In fact, all self-similar subsets of reals have the same "number of points".
(2002-06-04)
What are the fundamental axioms of Set Theory?
As Russell's paradox once showed,
we cannot simply call a set anything we like.
The "membership" of a set has to be somewhat restricted;
a set simply cannot be a member of itself (or else we'd run into trouble real fast).
On the other hand, infinite sets must be part of the theory,
if it is to be of any use whatsoever.
So, it is postulated at the outset that
some sets exists which may be put in one-to-one correspondence with a proper part
of themselves.
Finally, the last axiom listed below (the so-called Axiom of Choice)
postulates that sets need not be explicitely constructible,
but may instead be postulated
to exist as abstract collections of virtual choices.
This is the most controversial axiom of the bunch.
It has nevertheless been shown that,
if Set Theory is consistent without the Axiom of Choice,
then it is also consistent with it.
Various alternate theories have been formulated
where the axiom of choice is replaced by some weaker statement (which would be
a consequence of the full-fledged Axiom of Choice).
A proof using the Axiom of Choice
(or, possibly, one of its weaker counterparts) is usually called nonconstructive,
and is rejected by constructivists.
However, such a proof may serve to demonstrate [even to constructivists]
that the negation
of a nonconstructive theorem cannot possibly be shown to be true within the framework
of the rest of Set Theory (since the Axiom of Choice must be consistent with it)...
Axioms of Set Theory
Existence of the Empty Set :
The empty set Æ has no elements.
( $ Æ )
( "x )
( x Ï Æ )
Extensionality :
A set is characterized by its elements.
( "x )
( x Î A
Û
x Î B )
Þ A = B
Separability :
Elements of A with a property
b form a subset of A.
( $ B )
( "x )
( x Î B
Û
( x Î A
& b(x) ) )
Pairing :
Two elements form a set.
( $ A )
( "z )
( z Î A
Û
(z = x) Ú (z = y) )
|
Union of a set of sets:
C = |
È |
B |
| BÎA |
( $ C )
( "x )
( x Î C
Û
( $ B Î A )
( x Î B ) )
Power Set :
The power set C = 2 A is the set
of all subsets of A.
( $ C )
( " B )
( B Î C
Û
B Í A )
Regularity :
Set membership is neither reflexive
( A Ï A ) nor circular.
Every nonempty set has an element with which it has no common element.
( " A ¹ Æ )
( $ x Î A )
( " y Î x )
y Ï A
[Zermelo, 1930]
Infinite Sets : One example is
{ Æ, {Æ}, {{Æ}}, {{{Æ}}} ... }
( $ A ¹ Æ )
( " x Î A )
( {x} Î A )
Axiom of Choice :
A set may be formed which contains a single element from every
nonempty set of a given family of pairwise disjoint sets.
( " A Í
2 E )
( "MÎA "NÎA
MÇN=Æ )
Þ
( $ C Í E )
( " B Î
A-{Æ} )
( $ x Î E )
B Ç C = {x}
The Axiom of Choice has been, by far, the most controversial
of the bunch.
In spite of its annoying consequences
(see next section)
some formulations of the Axiom of Choice make it look trivial
and unavoidable
(e.g., "the cartesian product of any collection of nonempty sets is nonempty").
Even if one finds the nonconstructive proofs based on the Axiom of Choice
particularly repugnant, it does impose welcome constraints on
the definitions of key concepts.
For example, in general topology,
the Axiom of Choice is found to be equivalent to
Tychonoff's theorem (the product of compact topological spaces is compact)
only when compactness and product topology are properly defined.
Further Reading & Online References...
(2010-05-06)
Are there sets of real numbers that are not measurable?
The Axiom of Choice guarantees it !
The Lebesgue theory of integration is based on the notion of
measurable sets of real numbers:
The Lebesgue measure is a nonnegative
real function
m defined on measurable
sets, having the following properties:
- It's translation-invariant:
m({x}+A) = m(A)
- The measure of an interval
is equal to its length :
m ( [x,y[ ) = y-x
- It's countably additive :
The measure of a countable union of pairwise disjoint sets
is the (countable) sum of their measures.
Surprisingly enough, the Axiom of Choice
then implies that there are sets
of real numbers that are not measurable. Here's the proof:
Consider the equivalence relation among real numbers in the interval
[0,1[ whereby two numbers are dubbed equivalent when their
difference is a rational number (i.e., the quotient of two integers).
By the Axiom of Choice, we may form a set W
containing one and only one number from every equivalence class.
If W was measurable, then every set Wq =
{ (q+x) mod 1 | x Î W }
would be measurable of measure M, for any rational number q.
Well, M couldn't be positive because the
union of finitely many Wq
(they're all pairwise disjoint)
would then have a measure exceeding unity.
M couldn't be zero either, because that would make
the measure of [0,1[ vanish
(as the union of countably many disjoint sets of measure zero).
Therefore, W cannot be Lebesgue-measurable.
Note that the above relies on the
Archimedean property of real numbers.
If we were investigating surreal measures,
the above would merely establish that some sets of reals must have
infinitesimal nonzero measures...
(2010-09-23)
Functions and applications are special relations.
Some
functions from A to B
are injective, surjective or both.
A function f from set A to set B is something
that associates one and only one element
f (x) of B with every element x of A.
Formally, functions are special relations between
the elements of A and B,
in the sense below.
More precisely, what we just defined should be called an
application. A function from A to B is usually
defined as an
application from some subset of A
(called the range of the function) to set B.
Technically, [binary] relations are subsets of the
cartesian product
A ´ B ,
which is to say that they are sets of ordered pairs (a,b) whose first element
(a) is
in A and whose second element (b) is in B.
Thus, an application f verifies the following characteristic
properties:
f Í
A ´ B
( " x Î A )
( $! y Î B )
( (x,y) Î f )
By convention, the above is expressed with the following notations:
| f : |
A |
¾® B |
| x |
¾® y = f (x) |
A function f from set A
to set B is said to be surjective
when every element of B is the image of some element
of A.
It is said to be injective when no element of
B is the image of more than one element of A.
Both terms were introduced by the very influential
Nicolas Bourbaki
(the collective pen name of a famous ongoing collaboration of industrious
mathematicians, mostly French, founded on January 14, 1935).
A function that's both surjective and injective is said to be
bijective, or "one-to-one".
Functions that are surjective, injective, or bijective are respectively called
surjections, injections, or bijections.
(2005-07-26)
Cantor's Theorem:
Any set is smaller than its powerset.
No
function from A to 2A
can possibly be surjective (1891).
A beautiful proof :
Consider any function
f from set A to its powerset 2A
(by definition, 2A
is the set of all the subsets of A).
Let M be the subset of A consisting of all the
elements x of A such that
x Ï f (x).
Well, M is clearly an element of 2A
which is not the image of any
element x of A.
(HINT: Such an x could be neither in
M nor outside of it.)
Thus, our arbitrary function f is not surjective.
Therefore, there's no surjection from A
to its powerset.
This much seems obvious for finite sets,
but the above proof shows that it holds for all infinite sets as well.
The reader is encouraged to check the above wording for conformity with
the Axioms of Set Theory presented in the
above article,
assuming familiarity with the concept of a function.
The above result is known as Cantor's theorem and it provides
yet another argument (formerly known as the paradox of
Burali-Forti) against the existence of a set of all sets
because the powerset of such a thing could not possibly
be of greater cardinality than itself.
This argument was put forth by
Cesare Burali-Forti
(1861-1931)
in 1896 and predates the formulation of Russell's paradox
(1901).
 (2003-11-10)
Ào
and the transfinite cardinals
On the different sizes of infinite sets.
Two different approaches make sense of actual
infinite numbers which were both investigated by
Georg Cantor (1845-1918).
The cardinal numbers are discussed in this section;
ordinal numbers will be considered later.
Equipollence, Cardinality and Cardinal Numbers
Two sets which can be put in one-to-one correspondence
are said to be equipollent.
This is a fundamental notion which does not require an ability to count
the elements in either set; the ability to pair them up suffices.
Since equipollence is clearly an equivalence relation,
we can give a name to each equivalence class.
Such a name is called a cardinality.
Two sets are equipollent if and only if they
have the same cardinality.
Of course, finite sets, have the same cardinality if and only
if they have the same number of elements.
If you have as many apples as you have oranges,
you may count either the apples or the oranges and you'll
come up with the same number (0 if you have no fruit).
One may thus consider natural integers (0,1,2,3,4 ...) to be
indicative of the
cardinality of either set (apples or oranges).
In that capacity, the natural integers are
called cardinal numbers.
The fancy vocabulary may be intimidating,
but the whole thing is really the most basic kind
of numbers,
only described in a philosophical way which can be extended
to infinite sets...
Can infinite sets be "counted" too?
Well, the finite integers are clearly not up to the task.
But can't we just add one more "number"
(using tentatively the "¥" symbol for it)
and say that "¥" is the number of elements
in any infinite set?
Cantor showed that this won't do,
because there are pairs of infinite sets which cannot
be put into one-to-one correspondence with each other.
To be consistent with the very concept of cardinal numbers presented
above, there has to be more than one "transfinite" cardinal number.
The symbol Ào (pronounced
"aleph zero", "aleph null", or "aleph nought") was introduced by Cantor to
denote the smallest of these;
it's the number of all the [finite] integers.
An infinite set with this many elements is said to be countable.
An uncountable set is an infinite set which is not countable.
Cantor's diagonal argument
shows that the continuum of the real numbers
is uncountable.
Its cardinality (called the power of the continuum)
is the same as that of the powerset of the integers (the set of all sets
of integers)
as can be established directly by observing that
Pierce expansions yield a one-to-one
correspondence between sets of positive integers and the reals between 0 and 1.
By Cantor's theorem,
the powerset of any set has a greater cardinality
than that of the set itself.
Therefore, there must be infinitely many different infinite cardinalities and
infinitely many transfinite cardinals, including, at least, the following
sequence of so-called beth numbers :
| |
Á0 =
À0 |
; Á1 = C =
2 |
Á0 |
; Á2 =
2 |
Á1 |
... Án+1 =
2 |
Án |
... |
Georg Cantor used the notation
C = 2Ào
for the power of the continuum. and
called Àn+1
the smallest transfinite cardinal beyond Àn
(that definition is valid only if the
axiom of choice is retained).
With that notation, in 1877, he conjectured the continuum hypothesis (CH)
which states that there's nothing between
Ào and C :
À1 = C
The generalized continuum hypothesis (GCH) is the deep generalization:
Àn =
Án for any ordinal n
Cantor could not prove or disprove the [restricted] continuum hypothesis,
Neither could anyone else... because this can't be done,
as discussed next.
(2009-04-11)
The Continuum Hypothesis (CH)
Is any uncountable set of real numbers
equipollent to the whole line?
Cantor thought that any uncountable subset of a continuum
was equipollent to the whole continuum.
He formulated this statement, known as the continuum hypothesis,
in 1877 and it bedeviled him till the day he died.
In 1884, Cantor observed that an uncountable
closed set of real numbers must have a subset
equipollent to the Cantor set and, therefore,
must be equipollent to the entire real line.
So, the continuum hypothesis does hold for closed sets and Cantor
saw that as a indication that it might be true for arbitrary sets as well.
However, he could not prove or disprove that statement.
The reason why Cantor failed to prove or disprove
the Continuum Hypothesis is that it cannot be proved or disproved.
It's undecidable...
The axioms of set theory are equally consistent
if we rule in or rule out the existence of transfinite
cardinals strictly between À0
and C.
This was established in 1963 by
Paul Cohen
(1934-2007) who was awarded the
Fields medal for that work, in 1966.
 (2003-11-10)
w
and Cantor's transfinite ordinals (1897)
Counting to infinity and beyond.
The second kind of transfinite numbers introduced by Cantor
are called transfinite ordinals.
They are more complicated than cardinals.
Following von Neumann (1923)
we may start with the following remark:
A natural integer may be represented by
the set of all nonnegative integers before it,
starting with the empty set ({} or Æ)
for 0 (zero) because there are no nonnegative integers before 0.
Then 1 corresponds to {0}, 2 is {0,1}, 3 is {0,1,2}, etc.
For the whole set of nonnegative integers {0,1,2,3...} Cantor introduced the symbol
w.
He did not stop there, since {0,1,2,3...w}
corresponds to another transfinite ordinal, which is best "called"
w+1.
{0,1,2,3...w, w+1} is w+2, etc.
However, you end up doing two different
types of counting if you enumerate a finite set first and an infinite set second or
the other way around...
The addition of ordinals is associative but not commutative:
1 + w
= w
¹ w + 1
Incidentally, the maximum number of different results
which can be obtained by changing the order of the terms in a Cantor-sum of n
ordinals may be tabulated as follows.
(The last pair of lines gives the general pattern,
which has exceptions only below n = 15.)
Number of different ways to add n ordinals
(A005348)
| 0 | 1 | 2 |
3 | 4 |
| 1 | 1 | 2 | 5 | 13 |
| 5 | 6 | 7 | 8 | 9 |
| 33 | 81 | 193 | 449 | 1089 |
| 10 | 11 | 12 | 13 | 14 |
| 2673 | 6561 | 15633 | 37249 | 88209 |
| 5k + 15 | 5k + 16 | 5k + 17 | 5k + 18 | 5k + 19 |
| 33 ´ 81 k+2 |
81 k+3 |
193 ´ 81 k+2 |
193 2 ´ 81 k+1 |
193 3 ´ 81 k |
The addition of infinite numbers such as w
may also be defined in other ways which retain commutativity.
The best such approach was proposed by
John H. Conway,
who defined w essentially as
above, but in the context of so-called surreal numbers,
a very satisfying generalization of the familar concept of "numbers"
(including integers, rationals and real numbers ).
Infinite Numbers among Surreal Numbers :
Expressions like
w-1,
2w,
w2,
Öw,
ww
www, etc.
have consistent meanings in the superb
construction of John Horton Conway presented
next.
(2003-11-10)
Surreal Numbers
What's the most general type of ordered numbers?
The most general type of number line
(as opposed to unordered things like complex numbers
or p-adic numbers) turns out to be
simpler to define than the familiar real numbers.
With the right approach,
it's actually easier to include infinitesimals and transfinite ordinals
than to rule them out...
The approach is inspired by the "Dedekind cuts" introduced by the last doctoral student of
Gauss,
Richard
Dedekind (1831-1916) to define real numbers as gaps
"between" partitions of the rational line
(this was before Georg Cantor identified real numbers with
equivalence classes of Cauchy sequences).
A Dedekind cut consists of two disjoint sets
L and R whose union is the entire set of rationals.
L does not have a greatest element and contains all rationals to the left of any
member of L, whereas R may
have a lowest element and contains any element to the
right of any member of R.
The mnemonic notations L and R ("left" and "right") are due to
J.E.
Littlewood (1885-1977).
The term surreal numbers was coined by
D.E. Knuth
in 1973 to describe the beautiful construct of
John H. Conway,
who gave simultaneously recursive definitions of the numbers
and the ordering among them...
Conway introduces the compact notation
x = { L | R } =
{ x L | x R }
for what is called a
game;
an ordered pair of two sets L and R, given either by name or by listing their
elements, all of which are [simpler] games themselves...
An element of L or R may be called a left or right option of x.
Numbers are then defined as special games whose options are other numbers,
and which lay "between" their own left and right options, in the following
sense, recursively defined:
Part of Conway's notation is standard: If L or x L
is a set, then L+y is universally understood as the set of all elements obtained
by adding y to an element of L, just like E+F is the set whose elements
are sums of an element of E and an element of F.
If desired, the rest of Conway's notation could easily be translated into
the standard notation of set theory,
by stating that a number may stand for a single-element set within
the "first level" of a "{...|...}" notation and that a comma ( , )
is synonymous with the "union" operator
( È ) in that same context.
Here are single-line definitions of some basic arithmetic operations:
- Sum: x + y =
{ x L + y , x + y L |
x R + y , x + y R }
- Opposite of a number: -x =
{ -x R | -x L }
- Product: xy =
{
xL y + xyL -
xL yL ,
xR y + xyR -
xR yR |
xL y + xyR -
xL yR ,
xR y + xyL -
xR yL }
Well, nobody said this was easy to work with, but it sure is beautiful...
As part of a Grothendieck
universe, surreal numbers form a set.
This set is certainly pretty large, but it's not an unwieldy
proper class.
Surreal Numbers
(2005-07-09)
Numbers
From integers to real, surreal, and
hypercomplex numbers.
The most rudimentary numbers are the counting numbers
(1, 2, 3, 4 ...) but it's better to let
the story begin with the natural numbers (0, 1, 2, 3 ...)
although zero
is a sophisticated concept of relatively recent origin.
Unfortunately, the tradition in US education
[1,
2, etc.]
differs from the international conventions described here, following
Bourbaki and other authors.
In US high-schools, "natural numbers" are often understood to exclude
zero, which makes the term synonymous with "counting numbers".
The dubious convention within the US educational system that makes
"whole numbers" include zero but exclude negative integers
is best forgotten by anybody who wants to be understood outside of the US.
You may talk about "positive integers" or "nonnegative integers" instead.
Negative integers originated after the fractions and
constructible numbers which result from the application
of classical rules (compass and straightedge)
to Euclidean geometry.
Algebraic numbers were also considered before negative numbers were accepted
(along with complex numbers, during the Renaissance).
Real numbers were invented in the 19th
century to close all possible "gaps" in the number line.
This is to say that whenever the real numbers are divided into
two sets L and R such that no element of L exceeds
an element of R, there's one element at their common boundary.
(This need not be the case with rational numbers. For example,
there is no rational number at the boundary between the sets of rationals L and R
of rational numbers whose squares are respectively less than 2
and more than 2.)
Archimedes attributes to
Eudoxus
what's now called the Archimedean
property of ordinary numbers:
There's always an integral multiple of any given positive quantity
that exceeds any other prescribed quantity.
The surreal numbers, mentioned above,
are not Archimedean, as they include infinitesimal positive
quantities whose product by any integer can't exceed a
number like 1
(likewise, no integer exceeds an infinite surreal quantity).
The so-called Cayley-Dickson construction doubles
the dimension of a previously established set of numbers,
by considering ordered pairs of such numbers
and defining their sums, products and conjugates in the following way.
(The conjugate of z is denoted z* and the conjugate of a real
number is itself.)
The product of a number and its conjugate is always
a nonnegative real number, equal to the square of that
number's norm, by definition.
|
( a , b ) + ( c , d )
| = |
( a + c , b + d )
| |
( a , b ) ( c , d )
| = |
( a c - d b* ,
a*d + c b )
| |
( a , b )*
| = |
( a* , -b )
|
The identity
( x y )* = y* x* is clearly true in the realm of real numbers
and it can be established for all hypercomplex numbers by induction:
|
[ ( a , b ) ( c , d ) ]*
| = |
( a c - d b* ,
a*d + c b )*
| | = |
( c* a* - b d* ,
- a*d - c b )
| |
( c* , -d )
( a* , -b )
| = |
( c* a* - b d* ,
- c b - a*d )
|
Hypercomplex Numbers: Normed Division Algebras
(multidimensional
numbers with real coordinates)
| Set | Dimension | Commutativity | Associativity |
| Octonions | 8 | No | Alternative |
| Quaternions | 4 | Yes |
| Complex Plane | 2 | Yes |
| Straight Line | 1 |
Arguably, the above process should stop with the octonions, as the
next step up forms something (the sedenions) that's
not a proper "division algebra", because two
nonzero elements may have a zero product.
Although other "numerical" objects (like decadic
integers) include such divisors of zero,
it seems abusive to call such things numbers
(among sedenions, the divisors of zero of unit norm are
homeomorphic
to the exceptional Lie group G2.)
By contrast, the noncommutativity of quaternions is acceptable
and interesting; the resulting algebraic structure
is called a skew field, and it repays study.
- Sir William Rowan
Hamilton
(1805-1865) invented the quaternions on October 16, 1843.
The
next day, he told John T. Graves about it...
- John T. Graves (1806-1870)
came up with octonions on December 26, 1843.
They were rediscovered by Arthur Cayley
in March 1845.
In 1886, Frobenius proved that, the reals, the complex numbers and the quaternions
form the only three types of real associative division algebras.
Multiplication of octonions isn't associative,
it's only alternative :
"x
"y
(xx)y = x(xy) and y(xx) = (yx)x
Interestingly, the term associativity was coined by
Hamilton
around the time (July 1844) when he found out that octonions
failed to have this property:
"x
"y
"z
( x y ) z = x ( y z )
Cayley-Dickson construction in
The Octonions
(PDF, 515 kB)
by John C. Baez (May 2001)
"On Quaternions and Octonions" by John H. Conway
and Derek A. Smith.
[Review]
(2005-07-19)
Von Neumann - Bernays - Gödel set theory
(NBG)
A set is a member of a class.
A proper class isn't a member of anything.
The theory originated with John von Neumann (1925).
It was then modified by Paul Bernays (1937) and simplified
by Kurt Gödel (1940).
|
|
|
