Cardinal number

From Citizendium
Revision as of 07:11, 28 October 2008 by imported>Jitse Niesen (copy-edit (mostly adding links))
Jump to navigation Jump to search
This article is developing and not approved.
 Main Article
 Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
https://en.citizendium.org/wiki/index.php?title=Cardinal_number&printable=yes
This editable Main Article is under development and subject to a disclaimer.

In set theory, cardinality is a property of sets that generalises the notion of the size of a finite set. Because of this, it is often thought of as the “size” of a (possibly infinite) set. While this is useful for thinking about the concept, it can lead to misconceptions. Some of the intuitive notions associated with size do not carry over to cardinality, and some do in certain set theories but not in others.

Motivation

In comparing two finite sets, say {1, 2, 3} and {a, b, c, d, e}, the elements may be counted to give a unique natural number for each set, here 3 and 5 respectively, called the size of the set. 5 is a greater number than 3, and so the second set is said to be greater than the first. Various properties of size are intuitively familiar, such as the fact that adding elements to a set yields a set of greater size, while removing elements yields a set of smaller size. But when considering two infinite sets, say the set of natural numbers {1, 2, 3, 4,... } and the set of natural numbers greater than 19, {20, 21, 22,... }, the second is obtained by removing elements from the first, but there is no obvious way of assigning a “number” to each of the sets which would indicate that the second is “smaller” than the first.

Therefore, instead of attempting to generalise the process of counting, mathematicians generalise another relation between finite sets that is equivalent to their being the same size. Two finite sets X and Y are the same size precisely if the elements of X can be mapped to the elements of Y in such a way that every element in Y is mapped to by exactly one element in X; in this case X and Y are said to be equinumerous or equipotent. Finiteness is not necessary to ask whether two sets are equinumerous so we can immediately generalise it to arbitrary pairs of sets.

Definition

The cardinality of a set X then, will be an object associated with X, which we denote |X|, that should satisfy the property:

|X| = |Y| if and only if X and Y are equinumerous.

There may be many such objects, any of which could be used as a definition of cardinality. The objects chosen to be used as the cardinality of sets are called cardinals or cardinal numbers. Which possible definitions are available for use will depend on the set theory one is working with. The collection of sets equinumerous with X is the same as the collection equinumerous with Y precisely when X and Y are themselves equinumerous. If therefore there is a set whose elements are precisely the sets equinumerous with X, this is usually taken as the definition of |X|. However the existence of such sets is not consistent with Zermelo–Fraenkel set theory and its extentions, which are the most commonly used set theories. However, there are workarounds. If the axiom of foundation holds, the set of all sets of minimal rank equinumerous with X can be used. If the axiom of choice is available, X can always be well ordered, and |X| can be defined as the least ordinal that is the order type of some well ordering of X; this is the definition of cardinal numbers most familiar to mathematicians.

Conventionally, arbitrary cardinals are represented by lower-case gothic letters.

Ordering and arithmetic with cardinals

Order

The above does not settle the question of how to talk about some infinite sets being larger than others. For this mathematicians again generalise a concept in terms of mappings of finite sets that is equivalent to greater size. For finite sets X and Y, the set X has size at least as great as Y if and only if the elements of Y can be mapped to the elements of X in such a way that every element of X is mapped to by at most one element of Y (such a map is called an injection). This is a definition in terms of X and Y, but it is straightforward to show that it depends only on the cardinalities of X and Y. The relation ≥ is therefore defined by:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{a} \ge \mathfrak{b}} if and only if there exist X and Y such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{a} = |X|} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{b} = |Y|} and there is an injection from Y into X.

The fact that this does indeed define an order relation on cardinals is known as the Schroeder–Bernstein theorem.

Another relation between sets that is equivalent to larger size in finite sets is the existence of a surjection from X to Y (i.e. a map from X to Y such that every element of Y is mapped to by at least one element of X). However, without the axiom of choice, this relation is not necessarily an order relation at all. It may be that there is a surjection from X to Y and another from Y to X without X and Y being equinumerous. With the axiom of choice however, the two relations are the same, and are a well ordering of the cardinals.

Arithmetic

A number of arithmetic operations are defined on cardinals in relation to sets analogously to how arithmetic operations on natural numbers can be defined in relation to finite sets.

For finite cardinals, addition can be defined in terms of disjoint unions. 2 + 3 is the size of a set obtained by combining a set of size 2 with a set of size 3, so long as the two sets do not share any elements. So we define addition in general by:

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A| = \mathfrak{a}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |B| = \mathfrak{b}} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{a} + \mathfrak{b} = |A\sqcup B|}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\sqcup B} is the disjoint union of A and B.

Similarly 5 × 4 is the size of the Cartesian product of a set of size 5 with one of size 4. We define in general:

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A| = \mathfrak{a}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |B| = \mathfrak{b}} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{a} \cdot \mathfrak{b} = |A\times B|.}

And 34 is the size of the set of functions from a set of size 4 into a set of size 3, so we define

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A| = \mathfrak{a}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |B| = \mathfrak{b}} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{a}^\mathfrak{b} = |\{ f : f \text{ is a function from } B \text{ to } A \}|.}

All of these operations can easily be proved to be independent of the choice of sets A and B.

As with ordering, addition and multiplication are very simple in the presence of the axiom of choice, and very little can be said without it. With the axiom one can prove

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{a} + \mathfrak{b} = \mathfrak{a \cdot b} = \max (\mathfrak{a},\mathfrak{b})} for all cardinals Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{a}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{b}} .

Without the axiom, such relations cannot in general be proved. In fact the simple statement that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{a}^2 = \mathfrak{a}} for all cardinals Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{a}} is itself equivalent to the axiom of choice.

Cantor's theorem

Much less can be proved about cardinal exponentiation in general than about addition and multiplication, even with the axiom of choice. One well known result is Cantor's theorem, which states

for any set X, there is no surjection from X to P(X)

which implies

for any cardinal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{a}} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{a} < 2^\mathfrak{a}} .

Cantor's theorem relies essentially on the axiom of separation, and may be false in set theories without that axiom. In particular if there is a universal set V, then

|V| ≥ |P(V)|

and if the set theories allows urelements, this may even be a strict inequality.

Particular cardinal numbers

Finite cardinal numbers correspond to natural numbers. In fact natural numbers are usually defined to be the finite cardinal numbers in set theory. In addition there are two major classes of infinite cardinals, each indexed by the ordinal numbers and defined recursively in terms of |N|, the cardinality of the natural numbers. The first class is denoted by the Hebrew letter aleph and defined by

  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_0 = \left|\mathbb{N}\right|,}
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_\alpha} is the least well ordered cardinal strictly greater than all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_\beta} for which β < α.

The second class is denoted by the letter beth and defined by

  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beth_0 = \left|\mathbb{N}\right|} ,
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beth_{\alpha + 1} = 2^{\beth_\alpha}} ,
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beth_{\alpha}=\sup\{\beth_{\beta}:\beta<\alpha\}} if α is a limit ordinal.

Every cardinal that is the cardinality of an infinite well orderable set is equal to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_\alpha} for some ordinal α. Such cardinals are called aleph numbers. Similarly, cardinals that are equal to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beth_\alpha} for some ordinal α are called beth numbers.

The continuum hypothesis

By definition, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_0 = \beth_0} . The statement that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_1 = \beth_1} is known as the continuum hypothesis. The more general statement that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_\alpha = \beth_\alpha} for every ordinal α is known as the generalised continuum hypothesis. Both the continuum hypothesis and its generalisation are undecidable in ZFC, and little is known about what conditions are necessary or sufficient for their decidability.

The Löwenheim–Skolem theorem

The Löwenheim–Skolem theorem is an important fact in model theory underlining the limitations of first-order logic. The statement of the theorem is:

Let L be a first order language whose alphabet has cardinality Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{n}} , and let T be a theory over L with at least one infinite model. Then for any infinite cardinal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{m}} satisfying Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{m} \ge \mathfrak{n}} , there is a model for T of cardinality Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak{m}} .

This means that there is no way in first-order logic to design axioms that ensure the models of a theory are a certain cardinality. No matter what the theory is (so long as it has infinite models), it will have arbitrarily large models.

Cantor's theorem can be proved in ZF set theory. In particular one can prove the existence of uncountable sets. But the alphabet of ZF is finite, so the Löwenheim–Skolem theorem means (assuming ZF is consistent) that it has a countable model. How can a countable model contain uncountable sets? This is known as Skolem's Paradox. It arises because there may be sets X such that we can define a one-to-one relation between N and X, but this relation is not realisable as a set in ZF, so the theory "thinks" it is uncountable.

Retrieved from "https://citizendium.org/wiki/index.php?title=Cardinal_number&oldid=531300"