(2014-01-21) For over two millenia, the framework of logic was rigid and frozen.
Aristotle (384-322 BC) showed how to deducecategorical propositionsfrom each other. In a typical syllogism, a conclusion is derived from two premises. For example :
All men are mortal.
Socrates is a man.
Therefore, Socrates is mortal.
The pattern seems foolproof, and it is. Yet, difficulties may arise:
Rare things are not cheap.
A cheap horse is a rare thing.
Therefore, a cheap horse is not cheap.
As discussedbelow, the silly conclusion is not necessarilyinvalid (as it merely implies that there's no such thing as a cheap horse,which isn't so objectionable in this context). Nevertheless, clarifications are needed...
Such threats to logic from circularities in the premises bothered Gottlob Frege (1848-1925) as he seeked to put modern logicon solid foundations.
As he thought he had done so, Frege was proofreading his work, just beforegoing to press, when he received a letter from his youngercolleague Bertrand Russell (1872-1970) who pointed out to Frege what's now called Russell's paradox. To his credit, Frege saw immediately that his work could not be fixedand he did what he could to apologize to his readership.
Russell's objection was a fundamental one. The consequences for the very foundations of mathematics are still with us. Read on...
(2014-02-11) The basis for reasoning (violated in the realm ofquantum physics).
A system of axioms is consistent if, and only if, at least one statement is not provable in it.
Although natural language can be used for reasoning, it's notoriouslyunreliable in its rigor, or lack thereof (pay close attention to any debate involving a religious apologist to illustrate this point). As with the rest of mathematics, a formal language is neededfor logical statements. That language should be unforgiving enough to make mistakes detectable.
Definitions are equivalences involving newly named concepts.
The formal counterparts of Aristotelian categories are called sets. A set can be envisioned as the collection of all things that belong to it (something that belongs to a set is said to be a member of that set). Two sets that have the same members cannot be distinguished and arethus considered identical (that's the principle of extensionality).
Surely, you want to consider sets themselves as legitimate objects of studyand allow sets whose members are sets. However, the freedom to do so cannot be completely unrestricted,as Bertrand Russel first discovered. There's a need for a theory of sets which spells out what is required to avoid subtle or not-so-subtle contradictionsin our discourse.
(Ashlee of Braithwaite, LA.2000-05-03twice) 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 bea 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 existsjust does not make it appear out of thin air in spite of the logical contradictionshis very existence would imply. This is no more paradoxical than asilly 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 consideredeither nonsensical or vacuously true : Any such barberdoes shave himself. Any such barberdoes 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 (ex falso quodlibet).
Russell's Paradox:
More seriously, it is worth pointing out that a fundamental logicaldilemma 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 considerthe "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 instrumentalin 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 allsets 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 beinherentlymeaningless statements or descriptions in a languagethat's allowed to refer to itself. For example,"the integers that can be specified in twenty English words or less"cannot possibly describeany 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 anordinal is,you can tell that the above phrase must bemeaningless. 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.
(2018-10-28) How can a man who shaves almost every day have a long beard?
(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 thatwe can't solve problems by using the same kind of thinking we usedwhen we created them.Largenumbers 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 thatthe basic distinction between finite and infinite sets ought notto depend explicitely on the properties of somethingas complicated as the integers.
A more fundamental approach was first suggested byDedekind,who turned a perceived paradox about infinite setsinto a natural definition of infinity:
Only with a finite set are all injections from the set to itself surjective.
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 subsetnot equal to the entire set. The empty set is a proper subset of any set but itself.
Two sets are said to be equipollent when there's a one-to-one correspondence between the elements of one and theelements of the other. At the most fundamental level (which may not be the most intuitive one) the existence of infinite sets is built into theaxioms of modern set theory.
Consider the set N of natural integers {0,1,2,3,4,5,6,...}. One of itsproper subsets is the set ofall counting numbersN* = {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 betweenN and the even numbers,betweenN and the squares, etc. (This basic observation was made by Thabit ibn Qurra before 900 AD.) N is thus an example of an infinite set.
The same thingcannot be done withany finite set: {1,2,3,4,5,6,7} cannot be put in a one-to-onecorrespondence with any set of fewer than 7 elements.
Nowadays, a set equipollent to a proper subset is dubbed Dedekind-infinite.
Tarski's definition of infinity :
The problem with Dedekind's definition of infinity is thata proof of its equivalence with the previous definition (involving integers) requires theaxiom of choice (or, at least, the weaker Axiomof countable 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 the following definition, proposed in the doctoral dissertation (1924) of Alfred Tarski (1902-1983). It's based on the notion of a minimal element in a family of subsets. (A minimal element is a set not containing another set from that family. Seebelow.)
Tarski's Definition of Finite Sets (1924)
A set E is finite if, and only if, every nonempty family F of subsets has a minimal element. Formally:
F 2E , (F ) ( xF , yF , y x )
That clever definition is simply perfect from a theoretical standpoint (although it certainly doesn't qualify as an intuitive one).
The above goes to show how fundamental the concept of an extremal point (i.e.,minimal or maximal) really is. It applies to all partial ordering relations, whether or not elements exist which are (absolute) extrema (a minimum or a maximum). This cannot be overstated. Let's clarify the concept we just usedfor the fundamental inclusion ordering of set theory:
Minimal and maximal points in a partially ordered set (poset) F :
Considering a set F endowed with a partial ordering relation: An element is minimal when no other element of F is below it. An element is maximal when no other element of F is above it.
Infinity as a Limit of Large Numbers
If you allow mentally for the existence of such infinite sets (as you should)you realize that there's 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 possiblybe won by either player: Regardless of what number is named, it's always possible to say somethinglike "twice that" (or "this plus one") and not concede.
Mathematicians routinely study things whose infinite versions turn out to bemuch simpler than the finite ones. One example is the following sum (properly called a power series):
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 one of Zeno's paradoxes : Before an arrow reaches its target, it must first travelhalf 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!)
(2012-06-15) (1889) Defining the set of the natural integers.
The five Peano Axioms are:
Zero is a natural integer.
Every natural integer has a successor in the natural integers.
Zero is not the successor of any natural integer.
Two different natural integers have different successors.
A set which contains zero and the successor of every element in it,contains all natural integers.
Hermann Grassmann (1809-1877) was the first person who discussed in print how operations on natural integers could bedefined inductively using only the successor function (1861).
Formal systems of axioms for natural numbers were proposed by Charles S. Peirce (1839-1914) in 1881 and by Richard Dedekind (1831-1916) in 1888.
In 1889, Giuseppe Peano (1858-1932) published his own version of the axioms in a book he wrote in Latin (Arithmetices Principia). Presumably, he was thus stressing thetimeless nature of the work, at a time when Latin was rarely used in Science.
(2005-07-09) From integers to rational, real and surreal numbers.
The most rudimentary numbers are the counting numbers (1, 2, 3, 4 ...) but it'sbetter to letthe story begin with thenatural numbers (0, 1, 2, 3 ...) althoughzerois a sophisticated concept of relatively recent origin.
Negative integers originated after the fractions and constructible numbers which result from the applicationof classical rules (compass and straightedge)to Euclidean geometry. Algebraic numbers were also considered before negative numbers were accepted (along withcomplex numbers, during the Renaissance).
Real numbers were first formally defined (ascuts over the rationals) byRichard Dedekind (1858) to close all possible "gaps" in the number line. This is to say that whenever the real numbers are divided intotwo sets L and R such that no element of L exceedsany element of R, there'sone element at their common boundary. (This need not be the case with rational numbers. For example,there is no rational number at theboundary between the sets L and Rof rational numbers whose squares are respectively less than 2and more than 2.)
Archimedes attributes toEudoxuswhat's now called the Archimedean property of ordinary numbers: There's always an integral multiple of any given positive quantitythat exceeds any other prescribed quantity. Thesurreal numbers, mentionedabove,are not Archimedean, as they includeinfinitesimal positivequantities whose product byany integer can't exceed anumber like 1 (likewise, no integer exceeds aninfinite surreal quantity).
Totally-Ordered Number Classes (each one contains those below it)
ciderspider(Mark Barnes, UK.2000-10-11) How do you prove that there are more real numbers than rational ones?
Anyinfinite set which may be put in a one-to-one correspondence with theintegers is said to be countable (or to havecardinality). Infinite sets that are not countable are said to be uncountable. As shown below, real numbers arenot countable,whilerational numbers are.
The uncountability of real numbers :
The diagonal argument ofGeorg Cantor (1845-1918) is the remark that,with any infinite "list" of realnumbers 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 decimala digit that's different from the N-th decimal of the N-th number listed.
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.
Thus, any list of reals between 0 and 1 fails to contain allthe reals between 0 and 1. Therefore, the real numbers between 0 and 1 are uncountable.
This is one of the simplest and most beautiful proofs of all times ! Its elegance is often spoiled by presenting it as a proof by contradiction, starting with something like: "Suppose there was such a list..."
It's related to the superb proof ofCantor's theorem whichis even simpler and purer, albeit far more abstract.
The countability of rational numbers :
Now, to prove that there are more reals than rationals, it sufficesto show that rationals may be put in a list. There areneater ways to do so, but we'll describe only asimple-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 travelthis 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) Somevanishing 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 contextofLebesgue measure theory) holds for the set of rational numbers orany other countable set.
However, not all sets of numbers with zero probability (or, rather, zero measure in the sense ofLebesgue) are countable. It's easy to describe a set of numbers which has zero probability but yet containsjust as many elements as the whole set of real numbers (whichisn'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 thirdof any smaller segment that shows up in this (infinite) process.
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 containsas many elements as the whole number line (as sequences of zeroes and nines are in one-to-one correspondence withsequences of zeroes and ones, which areat least as numerous as the uncountableset of numbers between 0 and 1). The fractal dimension of that decimal version of the Cantor set is afamiliar number (smaller than the above dimension of the ternary set):
d = log 2 / log 10 = 0.3010299956639811952...
A self-similar countable set of realsmust have dimension 0. Example:
For { 1, 1/2, 1/4, 1/8, ... 1/2n ... } we have (1/2)d = 1 so, d = 0.
(2015-02-14) Symbols and idioms which can be used in the rest of mathematics.
The rest of this page may involved advanced topics of Set Theory (the biggest hurdle being the fundamental axioms) which can be skippedby most readers. However, the language introduced in this sectionwill be of interest to everybody. It allows many mathematicalstatements to be expressed quickly and accurately and its masterywill definitely help structure the thought process of aspiring mathematiciansat all levels of expertise. Some of it used to be taught systematically in primary and secondary education (to avoid highbrow fundamental queezes, what was taught was actuallymostly the "algebra of the parts of a given set E").
Membership : xA . x belongs to set A (it's an element ofA).
Inclusion :AB . Every element ofA belongs toB.
Equality :A =B . A andB are included in each other.
Union :AB is the set whose elements belong toAand/orB.
Intersection :AB (A interB). All elements in bothAandB.
Complement :A . All elements (of E ) not in A.
Powerset : 2A or P(A) . The set of all subsets of A.
The original symbol for inclusion was (so that AA may serve to express that A is a subset of itself). To express that A is a proper subset of B, the unambiguous notation is AB.
We introduced unions and intersections for two operands, but thoseare defined for several operands, possibly infinitely many of them...
Closely related to the above are the standard symbols of modern logic :
Universal quantifier : x Whatever follows is true for any x.
Existential quantifier : x Whatever follows is true for some x.
Defining quantifier : ! x Whatever follows is true for just one x.
Implication : If the LHS is true, so is the right-hand side.
Equivalence : Either both sides are true or both sides are false.
Disjunction : At least one side is true.
Conjunction : Both sides are true ("&" is also used for that).
Negation : Whatever follows is false.
Needless to say that we may also use comma separators, parentheses or various brackets wheneverthe precedence of the above operators needs to be clarified... Curly brackets are usually reserved to denote sets, in particular with thevery important set-builder notation.
The next order of business for a well-rounded basic vocabulary would be to considercartesian products,relations andfunctions, as introduced below.
(2002-06-04) Fraenkel's replacement schema (1922) was added to Zermelo's list.
AsRussell's paradox once showed,we cannot simply call aset 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 thatsome sets exists which may be put in one-to-one correspondence with a proper partof themselves.
Axioms of Set Theory
The empty set has no elements. ( A set with at least one element is called nonempty.)
( )( x )( x )
A set is characterized by its elements. ( In particular, there's only one empty set.)
( x )( xA xB ) A =B
Elements of A with property form asubsetB. ( This is to justify the set builder notation: B = { xA | (x) }. )
(B )( x )( xB ( xA & (x) ) )
Two elements form a set.
(A )( z )( zA (z = x) (z = y) )
C =
B
A
(C )( x )( xC (BA )( xB ) )
The power set C = 2A is the setof all subsets of A.
(C )(B )( BCBA )
Set membership is neither reflexive (AA ) nor circular. Every nonempty set has an element with which it has no common element.
, Fraenkel and/or Skolemadded this axiom in 1922. In 1923,von Neumann would showthat the assumption is also indispensable to prove that every well-ordered set is equipollent to anordinal. The axiom of replacement had first been proposed by Dmitri Mirimanov (1861-1945) from Switzerland, in 1917.
The above axioms constitute ZF theory whose major variant is ZFC (with the addition of the axiom of choice).
(2002-06-04) AC is a tricky addition to the Zermelo-Fraenkel (ZF) list of axioms.
More things are recognized as legitimate sets in ZFC than in ZF by itself.
The Axiom of Choice (AC) statedbelow postulates that sets neednot be explicitelyconstructiblein the various ways allowed by ZF but may instead be abstract collections of virtual choices.
It has been shown that, if Set Theory is consistentwithout theAxiom of Choice, then it's also consistentwith it.
AC is sometimes perceived as allowing more sets than strictly needed, which may falsify interesting theorems valid within a lesser realm of sets. To mitigate that, various alternate theories have been formulatedwhere AC 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 callednonconstructive,and is rejected byconstructivists. However, such a proof may serve to demonstrate [even toconstructivists]that thenegationof a nonconstructive theorem cannot possibly be shown to be true within the frameworkof the rest of Set Theory (since theAxiom of Choice must be consistent with it)...
A set may be formed which contains a single element from everynonempty set of a given family of pairwise disjoint sets.
(A 2E) (AA MN= )
(CE )(BA )( xE ) BC = {x}
More brutally stated:
(A, A, MN= ) (C,BA,x, BC = {x} )
Either of the above formulations of the axiom of choice is known as the Multiplicative Axiom (that name can be useful to distinguish that from several equivalent statements whichwill be discussed shortly). That original formulation of the Axiom of Choice was introduced in 1904 by Zermelo to establish that every set can be well-ordered (a statement which turns out to be equivalent to the axiom of choice).
In spite of its annoying consequences (seebelow) someformulations of the Axiom of Choice make it look trivial and unavoidable (e.g., "thecartesian 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 nice constraints on the definitions of key concepts. For example, ingeneral topology,the Axiom of Choice is found to be equivalent to Tychonoff's theorem (the product of compact topological spaces is always compact, when compactness and product topology are properly defined).
In that sense, paradoxically, the Axiom of Choice has abeneficial influence even in the "constructivist" axiomatic framework (called ZF or Zermelo-Fraenkel) where it is explicitely rejected. The full set of axioms stated above is usually referred to as ZFC (Zermelo-Fraenkel with Choice).
Note that ZF or ZFC assert only the existence of mathematical objects thatcan be defined as sets. Every mathematical object so defined, with the sole exception of the empty set,has some kind of sructure, in the sense that some simpler mathematical objects belong to it. This remains true even when convenient names are assigned to basicobjects whose set-theoretical definition is rarely used, if ever, starting withthenatural integers:
As part of ZF or ZFC, the additional assertion is often understood that allmathematical objects ultimately reduce to the empty set in that way. That's all there is to the mathematical universe we may talk about. This is what establishes the validity of the standard method of proof bystructural induction (also called mathematical induction ).
Nevertheless, it's also possible to postulate the existence of atoms (such fundamental elements orurelements are objects,different from the empty set, to which no other object "belongs"). In the simplest such model, called ZFA (Zermelo-Fraenkel with Atoms) all atoms are alike but distinct (e.g., there's only one setof two nonempty elements that are both atoms).
(2013-02-15) Ruling out infinite descending membership chains.
In 1917, Dmitri Mirimanov(1861-1945) discovered that certain models compatible with the axioms of ZF set theoryallow the existence of infinite descending membership chains: xn+1xn
John von Neumann found this repugnant and proposed his Axiom of Restriction to rule that out.
Philosophically, the axiom of restriction disallows sets beyond thosecreated in finitely many applications of the other axioms of ZF.
Interestingly, if theaxiom of dependent choiceis postulated instead of the full axiom of choice, then the axiom of restrictionimplies regularity (so regularity no longer needs to be postulated as an axiom).
(2012-09-22) Statements that may or may not require the full power of AC.
Statements Equivalent to the Axiom of Choice :
Here are some of the theorems which can be proved using the axiom of choiceand which, conversely, imply the full axiom of choice.
Axiom of choice (Zermelo, 1904): Thecartesian product of any family of nonempty sets is nonempty.
Skolem functions (choice functions) : For every set A of nonempty sets, there is a functionf such that xAf (x) x.
Zermelo's theorem (1904): Any set can be well-ordered (endowed with a total ordering where every subset has a least element).
Tarski's theorem(1924): Any set is equipollent to its cartesian square.
Zorn's lemma (1935): For any partial ordering of E, if anychain in Ehas an upperbound in E, then E has at least one maximal element.
Tukey's lemma : Any family of sets of finite character has at least one maximal element (with respect to set inclusion).
Tychonoff's theorem : The cartesian product of any family of compact spaces is compact.
??? There's an injection or a surjection from one given set to another.
Weaker alternatives to the axiom of choice :
Here are a few interesting statements that are undecidable within ZF andproven within ZFC, although their proofs does not require the full power ofthe unrestricted axiom of choice (the corresponding theoremmay be true even if the axiom of choice isn't). Statements equivalent to some of them have been proposed as weaker alternatives to the full axiom of choice to complement the rest of the ZF axioms.
König's lemma : In a infinite connectedgraph where every node has finitedegree, there is an infinite simple path. This can be proved using the above axiom of countable choice. Also, it's true in ZF for any graph with a well-ordered set of nodes (in particular, it's true for any countable graph).
Hahn-Banach theorem : A restricted linear form dominated by a sublinear form can be extended to the whole space.
Krein-Milman theorem : A compact convex nonempty set in a locally convex space has an extreme point.
The Hahn-Banach theorem and the Krein-Milman theorem taken together are equivalent to the full axiom of choice. Likewise, the Boolean prime ideal theorem and the Krein-Milman theorem taken together are equivalent to the full axiom of choice.
(2010-05-06) The Axiom of Choice guarantees it ! (Giuseppe Vitali, 1905)
The Lebesgue theory of integration is based on the notion of measurable sets of real numbers: The Lebesgue measure is a nonnegative real function defined on measurablesets, having the following properties:
It's translation-invariant: ({x}+A) = (A)
The measure of an interval is equal to its length : ( [x,y[ ) = y-x
It's countably additive : The measure of a countable union of pairwise disjoint setsis the (countable) sum of their measures.
Surprisingly enough, the Axiom of Choice then implies that there are setsof real numbers that are not measurable. Here's the proof:
Consider theequivalence relation among real numbers in the interval [0,1[ whereby two numbers are dubbed equivalent when theirdifference is a rational number (i.e., the quotient of two integers). By the Axiom of Choice, we may form a set W (called a Vitali set ) 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 theunion 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 makethe measure of [0,1[ vanish (as the union of countably many disjoint sets of measure zero).
Therefore, W cannot be Lebesgue-measurable.
(2010-05-06)
Robert M. Solovay (b. 1938) has argued in favor of dropping the Axiom of Choice from the standard axiomsof set theory to ensure that every set of real numbers is Lebesgue-measurable. This could make every linear map on a Banach space continuous (a so-called dream space ).
One possiblity, advocated by the late Belgian mathematician Henri Garnir (1921-1985) is to replace the Axiom of Choice (AC) by the weaker Axiom of Dependent Choice (DC) and to postulate that every set of reals has the Baire property (which is incompatible with the full axiom of choice).
In that system, every set of reals is Lebesgue-measurable.
(2014-12-04) Binary or multiple cartesian products and infinite ones.
The cartesian product of two sets A and B is the set, denoted AB , of all ordered pairs (a,b) whose first element (a) isin A and whose second element (b) is in B.
Multiple cartesian products :
This definition is readily extended to the cartesian product of a finite sequenceof n sets, which consists of all the n-tuples formedwith an element from every set, in the stated order. The cross symbol () used to denote cartesianproducts doesn't have a fixed arity. The lack of parentheses is meaningful (it's not like anassociativebinary operator, where parentheses can be omitted or not). For example:
(1,2,3) is an ordered triple belonging to = 3
(1,(2,3)) is an ordered pair belonging to ( ) = 2
Indexed and/or infinite cartesian products :
Far more generally, we may define the cartesian product of a family of setsindexed by a set I as afunction which sends every element i of I to some element of Ei . When I is finite, this is equivalent to our previous description. When at least one of the sets involved is empty, the cartesian product is trivially empty. However, the converse is only true if we postulate the Axiom of Choice which is equivalent to the following statement (which could seem obvious to the uninitiated):
The cartesian product of nonempty sets is not empty.
Formal definitions of cartesian products :
The intuitive notion of ordered pairs ought to bedefined first. This allows binary cartesian products to be definedas above. Building on that, relations and functions can be stated to be subsetsof binary cartesian products (as is done in thenext section). Only then, can the above definitions for multiple or infinite cartesian products be givenin terms of "functions".
Classically, an ordered pairs are awkwardly defined in termsof the fundamental concepts of set theory: The pair (x,y) is defined as the set {x,{x,y}}.
(2014-12-04) A binary relation between two sets is a subset of their cartesian product.
Technically, a [binary] relation between two sets X and Y is just asubset of their cartesian product X×Y. When (a,b) isin that subset, we say that "a is related to b" (it's not the same thing as "b is related to a" since we are talking about ordered pairs here).
Two elements a and b are said to be unrelated (with respect to R) when neither (a,b) nor (b,a) belong to R.
The converse relation (RC) or transpose (RT ) of a relation R is also called its opposite ordual (Ro ). Avoid calling it the inverse of R (R-1 ) unless there's no risk of confusion withubiquitousgroup inverses which are entirely differerent. Using the set-builder notation, wa have:
RC = RT = { (y,x) X×Y : (x.y) R }
A subrelation is a subset of a relation. For example, among positive integers, the relation "divides" ("is a divisor of") is a subrelation of "is less than or equal to". Likewise, "is a power of" is a subrelation of "divides".
For a relation R, the infix notation a Rb simply means (a,b) R.
A relation R from A to B is said to be entire (orserial) when any element of the domainA is related to some element ofthe rangeB:
aA , bB , a Rb
Composition of Binary Relations :
If R is a relation from set A to B and S is a relation from B to C, then the composition T = S R is the relation from A to C defined by:
a Tc {bB , a Rb , b Sc }
Readers who have been exposed to this notion for functions (which are just a special type of relations,as introducedbelow) may remarkthat the above reduces to the familiar composition of functions, when applicable.
If the relation R is a function, a Rb means the same as b = R (a )
The peculiar order of the operands in the above definitionis meant to accommodate functional definitions. Indeed,if R and S are functions, then the above definition translates into:
c = S R (a ) = S ( R (a ))
The composition of general binary relations (not necessarily functions) is especially useful to define uniform spaces,whose completeness can be determined even when distances are not defined.
Binary Relations within a Set :
A relation R from a set A to itself could verify the following properties.
Reflexivity : xA , x R x (thus, reflexive relations areentire).
Anti-reflexivity (orirreflexivity) : x, ( x R x )
Symmetry : x R y y R x
Antisymmetry : { x R y & y R x } x = y
Transitivity : { x R y & y R z } x R z
Totality (or connexity) : x, y, ( x R y ) ( y R x )
Those concepts are used to define several important types of relations:
A preorder relation (orquasiorder) is reflexive and transitive.
An equivalence relation is reflexive, symmetric and transitive.
An ordering relation is reflexive, antisymmetric and transitive.
A strict ordering is irreflexive, antisymmetric and transitive.
A total ordering relation is what the name implies, using theabove definitions (it's an ordering relation which is total). The locution partial ordering denotes an ordering relation which need not betotal (although it may well be, per the usual inclusive meaning of mathematical terms).
A poset (partially ordered set) is simply a set endowed with a partial ordering in the above sense. It's usually denoted as a couplelike (E, R) or (P, ≤). The notion is one of the most fundamental notions of mathematics. For example, the most fundamental way to distinguish between a finiteor infinite set (due to Tarski, 1924) is expressed as aproperty of the poset of the parts of that set with respect to the inclusion relation: (2E, ).
A directed set (more precisely, an upward-directed set) is a nonempty set endowed with a preorder relation (i.e., a reflexive and transitive relation, notrequired to be antisymmetric) which is such that two elements always have an upper-bound (i.e., an element which is greater than or equal to both). It's also called a directed preorder or a filtered set. This structure is more general than a upper-semilattice because the set of all the upper-bounds of two elements may not have a minimal element.
An ordering lattice (French: treillis) is a poset where any pair of elements has a unique join and a unique meet (maximal lower bound and minimal upper bound, respectively). One example of a lattice is the set of positive integers under the relation denotedby the symbol "|" (pronounced "divides") whereby x | y means that y is a multiple of x. The meet of two integers istheir greatest common divisor (GCD, wedge) while their join is their lowest common multiple (LCM, vee).
(x y) (x y) = x y
A similar relation holds in a lattice of subsets (under inclusion), where the meet and join are respectively the intersection () and union () of sets, if implicit multiplication is understoodto denote the symmetric difference (a.k.a,,disjunctive union).
Well-founded binary relations :
A relation iswell-founded in X when every subset of X has a so-called "minimal element" (to which no other element of that subset is related):
A X , (A ) mA , aA , (a R m ) (a = m )
A relation R whose converse is well-founded is said to be Noetherian :
A well-ordering is said to satisfy the descending chain condition (DCC). A Noetherian ordering satisfies the ascending chain condition (ACC).
(2014-12-04) It's the set formed by all the equivalent classes so defined.
When an equivalence relation R is defined on the set A,that set can be partitioned into disjoint equivalence classes such that two elements are related iff they belong to the same class. Any element of A belongs toone and only one such class. The empty set isn't an equivalence class.
The set of all those equivalence classes is denoted A/R and is calledthe quotient of A by R (also dubbed Amodulo R).
That's often used to cleverly define a new set from a more elementary one:
For example the set of signed integerscan be construed as the cartesian square of the natural integers ( 2 ) modulo the following relation R :
(a,b) R (c,d) a +d = b +c
The motivation is to make subtraction a well-defined operation verifying:
(a , 0) (c , 0) = (a ,c)
It is then a simple (albeit tedious) exercise to show that the set so constructed is given a ring structure using thefollowing operations which respect the equivalence R (i.e., the equivalence class of a result depends only on the equivalence classes of the operands).
(a,b) + (c,d) = (a +c , b +d) (a,b) (c,d) = (ac +bd , ad +bc)
The same approach can be used to form the rationals as the field of fractions of the ring formed by the above group endowed with the usual multiplication (defined by induction through repeated addition).
Likewise, the field of real numbers can be construed as the set of rational Cauchy sequences modulo Cauchy equivalence.
(2010-09-23) . Somefunctions from A to B can be injective, surjective, or both.
A function f from setA to setB is somethingthat associatesone and only one element f (x) ofB with every element x ofA. Formally, functions are special relations betweenthe elements of A and B, in the above sense (namely subsets of A×B). Thus, a function f is characterized by:
fAB ( xA ) ( ! yB ) ( (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 ofsome elementof A. (The idiom "onto" is synonymous with surjective.)
A function is said to be injective when no element of B is the image ofmore than one element of A. ("One-to-one" is synonymous with injective.)
A function that'sboth surjective and injective is said to bebijective, or "one-to-one onto". It's also said to be a "one-to-one correspondence".
Functions that are surjective, injective, or bijective are respectively calledsurjections,injections, orbijections. A bijection may also be called a transformation; (as in the common locution linear transformation).
Direct and reciprocal images of a set :
For a given function f from A to B, the following definitions and notations are commonly used:
Direct image (or simply image) of a subset A' of A : f (A' ) = { yB | xA' , y =f (x) }
Inverse image (also called preimage) of a subset B' of B : f -1(B' ) = { xA | yB' , y =f (x) }
It's useful to know that the [direct] image of an intersection is contained in the intersection of the [direct] images, but is not necessarily equal to it (unless the function is injective). In particular, the images of two disjoint sets aren't necessarily disjoint (unless the function is injective).
On the other hand, we do have equality for unions of direct images and forboth unions and intersections of inverse images. All told:
f (XY ) f (X ) f (Y ) f (XY ) = f (X ) f (Y )
f -1(XY ) = f -1(X ) f -1(Y ) f -1(XY ) = f -1(X ) f -1(Y )
The proofs are left as an enlightening exercise for the reader.
One application of those relations pertains to the characterizationof the continuity of a function in terms ofthe conservation of certain topological properties of sets for either their direct or their inverse images...
(2005-07-26) Nofunction from A to 2A can possibly besurjective (Cantor, 1891).
A beautiful proof :
Consider anyfunctionf from set A to its powerset 2A (bydefinition, 2A is the set of all the subsets of A). Let M be the subset of A consisting of all theelements 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. (: 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 withthe Axioms of Set Theory presented in theabove article,assuming familiarity with the concept of a function.
The above result is known as Cantor's theorem and it providesyet another argument (formerly known as the paradox ofBurali-Forti) against the existence of a set of all sets because the powerset of such a thing could not possiblybe of greater cardinality than itself. This argument was put forth byCesare Burali-Forti(1861-1931) in 1896 and it predates the formulation ofRussell's paradox(1901).
(2003-11-10) and the transfinite cardinals On the different sizes of infinite sets.
Two different approaches make sense of actualinfinite numbers which were both investigated byGeorg 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 correspondenceare said to be equipollent. This is a fundamental notion which does not require an ability to countthe elements in either set; the ability to pair them up suffices.
Loosely speaking, equipollence is an equivalence relation and we can give a name to each equivalenceclass. Such a name is called a cardinality. Two sets are equipollent if and only if theyhave the same cardinality.
Of course, finite sets, have the same cardinality if and onlyif 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'llcome up with the same number (0 if you have no fruit). One may thus consider natural integers (0,1,2,3,4 ...) to beindicative of the cardinality of either set (apples or oranges). In that capacity, thenatural integers arecalledcardinal numbers. The fancy vocabulary may be intimidating,but the whole thing is really the most basic kindofnumbers,only described in a philosophical way which can be extendedto infinite sets...
Caninfinite sets be "counted" too? Well, the finite integers are clearly not up to the task. But can't we just addone more "number"(using tentatively the "" symbol for it)and say that "" is the number of elementsinany infinite set?
Cantor showed that this won't do,because there are pairs of infinite sets whichcannotbe put into one-to-one correspondence with each other. To be consistent with the very concept ofcardinal numbers presentedabove, there has to be more than one "transfinite" cardinal number. The symbol (pronounced"aleph zero", "aleph null", or "aleph nought") was introduced by Cantor todenote the smallest of these; it's the number ofall the [finite] integers. An infinite set with this many elements is said to becountable. An uncountable set is an infinite set which is not countable.
Cantor'sdiagonal argumentshows that the continuum of the real numbersis uncountable. Its cardinality (called the power of the continuum) is the same as that of the powerset of the integers (the set of all setsof integers) as can be established directly by observing thatPierce expansions yield a one-to-onecorrespondence between sets of positive integers and the reals between 0 and 1.
ByCantor's theorem,the powerset of any set has a greater cardinalitythan that of the set itself. Therefore, there must be infinitely many different infinite cardinalities and infinitely many transfinite cardinals, including, at least, the followingsequence of so-called beth numbers :
0 = 0
; 1 = C =
; 2 =
... n+1 =
...
Georg Cantor used the notation C = 2 for the power of the continuum. andcalled 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 and C :
1 = C
The generalized continuum hypothesis (GCH) is the deep generalization:
Cantor could not prove or disprove the [restricted] continuum hypothesis,Neither could anyone else... because this can't be done,as discussednext.
(2009-04-11) Is every uncountable set of real numbers equipollent to the whole line?
Cantor thought that any uncountable subset of a continuumwas 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.
The reason why Cantor failed to prove or disprovethe Continuum Hypothesis is that it cannot be proved or disproved. It's undecidable... The axioms of set theory are equally consistentif 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 theFields medal for that work, in 1966.
Some preconditioned versions of CH are true :
In 1884, Cantor observed that an uncountable closed set of real numbers must have a subsetequipollent to theCantor set and, therefore,must be equipollent to the entire real line. So, the continuum hypothesis holds if restricted to closed sets.
More generally,Felix Hausdorff (1868-1942) proved, in 1916, that any uncountable Borel set of real numbers isequipollent to the real line.
(2020-05-04) Implied by CH, but consistent with the negation of CH.
(2003-11-10) and Cantor's transfinite ordinals (1897) Counting to infinity and beyond.
The second kind of transfinite numbers introduced by Cantorare called transfinite ordinals. They're more intricate than cardinals.
The key concept is that of order-type, which only applies to well-ordered sets (if we reject the Axiom of choice, not all sets can be well-ordered). Two well-ordered sets are said to have the same order-type if there's an order isomorphism between them, namely a monotonous bijectionwhose inverse is also monotonous. A function f is said to be monotonous if it respects the orders respectively defined on its domain and codomain:
x ≤ y f (x) ≤ f (y)
Although Bertrand Russell dubiously did so in Principia Mathematica, it wouldn't be acceptable to define an order-type as an equivalence-class, because an equivalence relation can only be properly defined within a set.
Instead, we define special sets dubbed ordinals canonicallyso that there is one and only one ordinal of each order-type. The modern way to do so was devised by John von Neumann in 1923and it's now universally accepted:
Following von Neumann, we may start with the following remark: A natural integer may be represented bytheset of all nonnegative integers before it,starting with the empty set ({} or )for 0 (zero) because there areno nonnegative integers before 0. Then, 1 corresponds to {0}, 2 is {0,1}, 3 is {0,1,2}, etc. That prompts the modern recursive definition of ordinals astransitive sets:
Every ordinal is the well-ordered set of all smaller ordinals.
Thus, any member of an ordinal is also an ordinal and a union of ordinals is an ordinal. So, any set of ordinals has a supremum which is just the ordinal obtained as union of all of them. This implies that there is no set of all ordinals (since such a set would be a memberof itself, which is ruled out byRegularity): The ordinals form a proper class.
The set of all finite ordinals {0,1,2,3...} is the first transfinite ordinal. For this, we use the symbol introduced by Cantor.
{0,1,2,3...} is the next transfinite ordinal, which is best called +1. {0,1,2,3...+1} is +2. {0,1,2,3...+1, +2} is +3, etc.
Addition of Ordinals :
You end up doing two different types of counting if you enumerate a finite set first and an infinite set second orthe other way around... The addition of ordinals is associative but not commutative:
1 + = + 1
Incidentally, the maximum number of different resultswhich 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, as indicated by dimmed headers.)
Number of different ways to add n ordinals (A005348)
n
0
1
2
3
4
k = -3
1
1
2
5
13
n
5
6
7
8
9
k = -2
33
81
193
449
1089
n
10
11
12
13
14
k = -1
2673
6561
15633
37249
88209
n
5k + 15
5k + 16
5k + 17
5k + 18
5k + 19
k ≥ 0
3381 k+2
81 k+3
19381 k+2
193 281 k+1
193 381 k
Infinite Numbers among Surreal Numbers :
The addition of infinite numbers such as may also be defined in other ways which retain commutativity. The best such approach was proposed byJohn H. Conway (1937-2020) who defined asabove, but in the context of his surreal numbers, a very satisfying generalization of the familar concept of number (including integers, rationals andreal numbers ).
Expressions like 1,2,2,,, etc. have consistent meanings in that superb construction of John Horton Conway, as presented below.
(2019-04-12) The Hartogs number of X is defined whether or not X is well-ordered.
If we assumed the Axiom of Choice, the Hartogs number of a set X would just be its ordinal.If we don't, X has no ordinal unless it's well-ordered.
We can still establish that a set is properly formed by all the ordinals such that an injection exists from to X.
A well-orderings of a subset of X is just a subset of X2.
All such well-orderings thus form a subset of the Powerset of X2.
The relevant ordinals are the order-types of the well-ordered sets in that set which correspond to injections into X.
As a defined subset of a set, those ordinals form a set.
The Hartogs number of X is, by definition, the supremum of that last set (or the cardinal thereof, accordiing to some authors).
(2003-11-10) (John H. Conway, 1972) What's the most general type of ordered numbers?
The most general type of number line (as opposed to unordered things likecomplex numbersorp-adic numbers) turns out to besimpler to define than the familiar real numbers. With the right approach,it's actually easier to include infinitesimals and transfinite ordinalsthan to rule them out...
The termsurreal numbers was coined byD.E. Knuthin 1973 to describe the beautiful construct ofJohn H. Conway,who gavesimultaneously recursive definitions of the numbersand the ordering among them...
Technical Presentation of Surreal Numbers :
Conway introduced the compact notation x = { L | R } for what he called a game. Namely, an ordered pair of two sets L and R, given either by name orby listing their elements, all of which being (simpler) games.
).
For a given game x, typical elements of L or R are respectively denoted xL or xR and are called left or rightoptions of x. Numbers are defined as special games whose options areother numbers,and which lay between their own left and right options, in the following sense, recursively defined:
If L = { xL } and R = { xR } are two sets ofknown surreal numbers, such that xR ≤ xL is never true, then one representation of another surreal number x is obtained as: x = { L | R } = { xL | xR }
x ≤ y means that we never have yR ≤ x or y ≤ xL
Those two mutual recursions allow the introduction of a fundamentalequivalence relation:
x = y is defined to mean that x ≤ y and y ≤ x.
The true statement x ≤ x (implying x = x) requires a nontrivial proof! So does the transitivity of the "≤" relation. From that follows the fact that the defined notion of equality is indeedan equivalence relation (technically, surreal numbers are thus equivalenceclasses of their representations modulo that relation). Finally, we should observe that the construction ensures the antisymmetryof "≤" which makes it a proper ordering relation.
The following definitions are merely introduced for convenience:
x ≥ y means that y ≤ x.
x < y means that x ≤ y is true and y ≤ x is false.
x > y means that y < x.
Here are the single-line definitions of the basic arithmetic operations:
Sum: x + y = { x L+ y , x + y L | x R+ y , x + y R }
Well, nobody said that this was easy to work with, but it sure isbeautiful... Conway himself said that it took him "several weeks of hard work" to findthe above genetic definition of multiplication (two years after defining addition c.1970) and another year to define division!
Constructing numbers using simpler numbers :
A representation of a surreal number is canonical when it's formed only with previously constructed simpler numbers. Let's now construct surreal numbers one generation at a time, using such canonical representations.
The simplest number is the game which has no left option and no right option (that game is indeed a number because no left option is to the right of a right option). For a reason which will soon be clear, we call it 0 (zero).
0 = { | }
We can show that this particular number must, indeed, be the neutral element for addition using structural induction on surreal numbers which have a canonical representation (we haven't yet proved thatall of them do). Indeed, if we apply the above definition of addition, we obtain:
x + 0
=
{ x L+ 0 , x + 0 L | x R+ 0 , x + 0 R }
=
{ x L+ 0 | x R+ 0 }
=
{ x L | x R } = x
Expressions with 0R and 0L are discarded because there's no such thing as an element of the empty set. The remaining expressions can be simplified using the induction hypothesis, which tells us that 0 is neutral for addition with the simpler numbers availablein either set of options of x.
0 ≤ 0 holds (since we can't have 0R ≤ 0 or 0 ≤ 0L) therefore 0 = 0. That goes to show that the game { 0 | 0 } is not a number. The next generation of surreal number includes only two numbers:
-1 = { | 0 } and 1 = { 0 | }
Indeed, those two are clearly opposite of each other andwe could prove, by structural induction, that the latter is the neutralelement of the multiplication defined above. (At first, Conway didn't have the luxury to do so!)
The 3 surreal numbers identified so far can form 8 sets which allow the construction of 4 new numbers, with multiple representations:
The seven simplest surreal numbers (the first three generations) :
Number
Canonical Representations (simplest one first)
Day
2
{ 1 | } { 0, 1 | } { -1, 1 | } { -1, 0, 1 | }
2
1
{ 0 | }
1
½
{ 0 | 1 } { -1 , 0 | 1 }
2
0
{ | }
0
- ½
{ -1 | 0 } { -1 | 0, 1 }
2
-1
{ | 0 }
1
-2
{ | -1 } { | -1, 0 } { | -1, 1 } { | -1, 0, 1 }
2
Any given number also has many noncanonical representationsinvolving at least one number of the same generation or greater. For example:
2n new numbers are born on Day n, including two extremities (identified with -n and n) and other new surreal numbers halfway between the 2n-1 numbers of the previous generations. In finitely many days we obtain surreal numbers corresponding to all fractions whosedenominators are powers of two, but only those.
Structural Recursion :
The great power of Conway's notations is that they make it easy to specify recursively new options for a number (or any other game) in terms of old options (i.e., previously born ones). For example, the following equation defines x = ={0,1,2,3,4...| } which is the simplest infinite surreal:
x = { 0, 1+xL | }
More precisely, that equation means to say that 0 is a left option of x and that whenever xL is a left option of x, so is 1+xL.
and - are the only infinite numbers born on Day . However, that Birthday is shared by all irrational numbers and all rational numbersnot born on a finite Day. That includes 1/3.
(2005-07-09) Real and complex numbers. Quaternions, octonions, sedenions, etc.
A division algebra over afield (here, we'll use only the field of reals) is an algebra in which every nonzero element has a multiplicative inverse (this doesn't rule out divisors of zero because no associativity is postulated).
The Cayley-Dickson construction doublesthe dimension of a previously established set of numbers, endowed with an involutiveconjugation (the conjugate of z is denoted z*) homomorphic for addition and anti-homomorphic for multiplication, which is to say:
x** = x (x+y)* = x* + y* (x y)* = y* x*
If multiplication is commutative, the trivial conjugation (z* z) is fine.
The construct endows the cartesian square of the base numbers (i.e., the set of all ordered pairs of the given numbers) by defining addition, multiplication and conjugation in the following way (defining conjugation allows the construct to be iterated):
(a ,b ) + (c ,d )
=
(a +c , b +d )
(a ,b ) (c ,d )
=
(acdb* , a*d + cb )
(a ,b )*
=
(a* , -b )
The base numbers are isomorphic to the pairs whose second component vanishand are thus considered immersed into the composite numbers.
The composite conjugation clearly remains involutive and additively homomorphic. It also remains a multiplicative anti-homomorphism:
[ (a ,b ) (c ,d ) ]*
=
(acdb* , a*d + cb )*
=
(c*a* bd* , a*dcb )
(c* , -d )(a* , -b )
=
(c*a* bd* , cba*d )
Assuming the base numbers are associative, let's see what it takes to preserve associativityamong the composite numbers:
(a ,b ) [ (c ,d ) (e ,f ) ]
= (aceafd*c*fb*edb* , a*c*f +a*ed +cebfd*b )
[ (a ,b ) (c ,d ) ] (e ,f )
= (acedb*efd*afb*c* , c*a*fbd*f +ea*d +ecb )
Those two expansions are easily checked to be identical if multiplication is commutative. Thus, base commutativity implies composite associativity. Otherwise associativity can't occur, sincetwo base numbers which don't commute (xy yx, say) yield a counterexample to associativity:
Thus, associativity is preserved iff the base numbers are commutative.
Likewise, commutativity is preserved iff the base conjugation is trivial. However, the composite conjugation doesn't remain trivial (except when base numbers have characteristic 2) and commutativity is therefore broken when the construction is performed again on the composite numbers.
By design, the construction allows the iteration of one quadratic form:
X X* = (x,y) (x*,-y)
= (x x* + y y* , 0) (x*x + y y* , 0)
= (x*,-y) (x,y) = X* X
Thus, the quadratic form X X* is standard because it's composed of two like formson the base numbers (while the form X* X, isn't).
Of particular interest is the above construction iterated on the field of real numbers, as tabulated below. They are called hypercomplex numbers. The product of any such number by its conjuguate is a non-negative real number (as is easily proved by induction on the dimensionality) whose square-root defines the canonical norm of the number.
Hypercomplex Numbers: Normed Division Algebras (multidimensionalnumbers with real coordinates)
Arguably, the above process should stop with theoctonions, as thenext step yields a strange realm (thesedenions) where twononzero elements may have a zero product. It seems abusive to call numbers things that include such zero-divisors, except for recreation (e.g.,decadicintegers).
The noncommutativity of the quaternions is rather benign. The resulting algebraic structureis called askew field, and it repays study.
Sir William RowanHamilton(1805-1865) invented thequaternionson October 16, 1843. Thenext 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 Cayleyin March 1845.
In July 1844,Hamiltonrealized that octonions failed to have the crucial propertyfor which he coined the word associativity, now universally used:
x y z ( x y ) z = x ( y z )
A nonassociative division algebra may containdivisors of zero. In an associative division algebra, a product of nonzero factors is never zero.
In 1886,Frobeniusproved that the reals, the complex numbers and the quaternionsare the only three associative division algebras over the reals.
Multiplication of octonions isn't associative,it's only alternative :
x y (xx)y = x(xy) and y(xx) = (yx)x
Alternativity is less demanding than associativity. Less demanding still is the power-associativity discussed below. The Cayley-Dickson construction transforms a power-associativealgebra into another power-associative algebra, so all the algebras discussed here arepower-associative. Likewise, they're allflexible.
(2013-07-08) Colorful names or systematic nomenclature.
There has been at least one colorful attempt to name some Cayley-Dickson algebras beyond the 16-dimensionalsedenions. Tony Smithreports the macaronic tongue-in-cheek nomenclature proposed by Robert de Marais :
Pathions (32 dimensions). Symbol: P. The32 paths of wisdomin the Kabbalistic tree of life.
Chingons (64 dimensions). Symbol: X (sinceis for dimension 2). The64 Hexagramsof the I Ching (Book of Changes).
With 0-plexions denoting real numbers, elements of the 2n-dimensional real algebracould be called n-plexions where the number n can be expressed withstandard numerical prefixes:
The reals are plexions (avoiding "noplexions" or "nilplexions").
The complex numbers are monoplexions (2 dimensions).
The quaternions are diplexions (4 dimensions).
The octonions are triplexions (8 dimensions).
The sedenions are tetraplexions (16 dimensions).
The list then continues naturally with pentaplexions (32 dimensions), hexaplexions (64 dimensions), heptaplexions (128 dimensions), octaplexions (256 dimensions), enneaplexions (512 dimensions), decaplexions (1024 dimensions), hendecaplexions (2048 dimensions) etc.
(2012-12-20) Any "multiplication" needs that forexponentiationto be well-defined. For an "addition", that property allows a consistent definition ofdivisors.
A multiplication is said to be power-associative when positive powers can be recursively well-defined as follows, for any element a :
a1 =a and m≥1 , n≥1 , an+m = anam
The innocent-looking requirement that the above be "well-defined" entailsan infinite sequence of independent conditions :
a3 is well-defined only if aa2 = a2 a
a4 is then well-defined only if a a3 = a2 a2 = a3 a
a5 is then well-defined only if a a4 = a2 a3 = a3 a2 = a4 a
Etc.
If a power-associative multiplication has a neutral element (1) the zeroth power of any element, invertible or not, is also well-defined:
a , a0 = 1
Invertible elements can also be raised to the power of a negative integer:
a-n = (a-1)n
For commutative nonassociative rings oralgebraswhose characteristic is either 0 or coprime with 30, A.A. Albert has shown (1947) that, if fourth powers are well-defined, then the multiplication is power-associative.
When the characteristic is 3 or 5, the same holds whenever fifth and sixthpowers are well-defined (Louis A. Sokotoris, 1952).
Examples of power-associative operators :
Alternative multiplications are power-associative,so is the multiplication in any set ofhypercomplexnumbers (even beyond the sedenions) or any commutative multiplication having the followingproperty, known as Jordan's identity (which is verified,in particular, by theJordan productused in quantum mechanics).
The following property is called either power-alternativity or third-power associativity (for short, I call it cube-associativity or cubic associativity):
x , x ( x x ) = ( x x ) x
This merely means that cubes are well-defined.
The ugly multiplication tabulated below for a set of 3 elements,has this property (since any square equals A and everythingcommutes with A). This makes all cubes well-defined: A3 = A, B3 = C, C3 = B. However, neither B nor C have well-defined fourth powers :
A
B
C
A
A
C
B
B
C
A
B
C
B
C
A
B B3 = B C = B B2B2 = A A = A B3B = C B = C
C C3 = C B = C C2C2 = A A = A C3C = B C = B
Therefore, this operation isn't power-associative.
(2005-07-19) Sets belong to classes. Aproper class isn't a member of anything. Any class is a subclass of the class of all sets.
Everything in NBG set theory is a class (a concept undefined in ZFC set theory) but only a class which is a member of another class is called a set. Any collection of sets can be considered collectively as a class but such classes cannot be considered collectively unless they are sets. Thus, quantified variables in NBG statements can't be proper classes.
In the 1990's, it was established that NBG is a conservativeextension of classical set theory (ZFC) in the sense that NBG introducesnew language but no new theorems expressible in the language of ZFC.
For example, within NBG, we may speak of the class of all sets,which is called the Absolute (always spelledwith a capital A). The Absolute is a proper class because of Russel's argument. That statement isn't a "new" theorem because it can't be expressed at all in the languageof ZFC. It may be more satisfying to say that "the class of all sets is proper" ratherthan "there's no such thing as the set of all sets" but both statements areequivalent in a deep sense...
Gödel marveled at the fact that somethingcan be known about the Absolute by pure reason, namely:
Anything which is true of the Absolute is also true of at least one set.
(2014-01-19) The nonconservative extension of ZFC used in the Mizar system.
Around 1973, Andrzej Trybulec chose TG set theory as the basis for his Mizarproof-checker (now, the most popular system of its kind).
TG set theory is essentially ZFC with the addition of Tarski's axiom (originally formulated byTarski in 1939). All objects are sets;the notion of class isn't part of the language of TG.
Tarski's axiom states (in modern language) that every set is a member of at least one Grothendieck universe, where a Grothendieck universe is, loosely speaking, a set within which all usual mathematical operations can be performed. More precisely, a set U is a Grothendieck universe if and only if the following fourconditions are met:
If x belongs to U and y belongs to x, then y belongs to U.
If x and y belong to U, then the set {x,y} belongs to U.
Reason's last step is the recognition that there are 
