Countable and Uncountable InfinitiesDate: 08/13/2009 at 03:33:36 From: Emir Subject: Countable and Uncountable Infinities Could you please elaborate the terms 'countable' and 'uncountable' infinity? Are uncountable infinities greater than countable? How does the relation 'be greater of' work with such 'numbers'? As an example of uncountable infinities, we could take the cardinality of the continuum, but could you give me an example of a countable infinity? Is the number of different positive integers, aleph-null a countable inf.? Also, e.g. in calculus, when we write infinity as the answer to, let's say, [ lim(1/x) ; when x->0 ], what kind of infinity are we taking into consideration? Is that a countable or uncountable one? What's the 'name' of such infinity? I'm looking for some theoretical concepts to explain my questions. Date: 08/13/2009 at 05:06:46 From: Doctor Jacques Subject: Re: Countable and Uncountable Infinities Hi Emir, The word "infinity" corresponds to a concept that can have different meanings depending on the context. It is best to speak of countable and uncountable (infinite) sets. These concepts are related to the concepts of cardinality and cardinal numbers. The idea is to extend to infinite sets the notion of "having the same size". For finite sets, we say that two sets have the same size if they contain the same number of elements. This is obviously an equivalence relation on the class of all finite sets: the equivalence classes are: the empty set the sets of 1 element (singletons) the sets of 2 elements .... We could also put all the infinite sets in another class. However, as Cantor discovered, we can do a little more. If we want to know if there are the same number of chairs and students in a lecture room, we could count the students and chairs separately, but we could also tell everybody to sit down: if there are no empty chairs and nobody is left standing, we know that the two sets have the same number of elements, without needing to count these elements separately. The advantage of that method is that we can extend it to infinite sets. If A and B are two sets (finite or infinite), we say that A and B are equipotent (or equipollent) if there is a bijection (a one-to-one and onto function) between the two sets. In that case, we also say that the sets have the same cardinality, and we write: card (A) = card (B) or, more concisely, #A = #B Now, the identity function is a bijection, the inverse of a bijection is a bijection, and the composition of two bijections is a bijection: this shows that equipotence is an equivalence relation on the class of all sets. The equivalence classes are called cardinal numbers: they consist of classes of sets equipotent to each other. In particular, for finite sets, we get the equivalence classes mentioned above, corresponding to the natural numbers. For that reason, the natural numbers are sometimes called "finite cardinal numbers". For example, we can think of "2" as meaning "the class of all sets of 2 elements", or, more correctly, "the class of all sets S such that there exists a bijection for {a,b} to S". The sets in the equivalence class of N (the natural numbers) are called countable. (Some authors also call the finite sets countable, and use "countably infinite" or "denumerable" for the equivalence class of N). By definition, an infinite set S is countable if there is a bijection between N and S. This means that you can list all the elements of S in sequential fashion: if you write f(n) for the nth element of the list, f is the desired bijection from N to S. Countable sets include: N (the natural numbers) (by definition) Z (the integers) Q (the rational numbers) The algebraic numbers The set of finite words over a finite alphabet. That last class is of particular interest, because it often gives a practical way to prove that a set is countable. If you can represent all the elements of a set by finite strings over a finite alphabet, you can arrange those strings as follows: the empty string the strings of 1 letter the strings of 2 letters .... and, within each class, you can arrange the strings in dictionary order; note that some classes may be empty, we do not require that every finite string correspond to an element of the set. For example, using that technique, you can easily prove that Q is countable, because each rational number is a fraction with integer terms, like -123456/789, and this can be written as a finite string over the 12-letter alphabet {0,1,...,9,'-','/'). The cardinal number of N (the class of countable sets) is denoted by aleph_0. As the classical "diagonal" argument of Cantor shows, not every infinite set is countable; in particular, the set R of real numbers is not countable, or "uncountable". Up to now, we have defined an equivalence relation between sets, but this leaves open the question of comparing sets that are not equipotent; as you put it, can we define a relation "greater than" on cardinal numbers? It turns out that this is indeed possible. We say that the set A is "smaller than or equal to" the set B if A is equipotent to a subset of B; this agrees with intuition. In that case, we write: #A <= #B This also means that there is an injective (one-to-one) function from A to B. This new relation is compatible with the previous equivalence: if #A <= #B and #B = #C, then #A <= #C. Beware that this is not "obvious", because we give a particular meaning to the symbols '<=' and '='. This should be proved from the definition of these relations. In this case, we have, by hypothesis, two functions: f : A -> B g : B -> C where g is a bijection and f is injective. f is a bijection from A to a subset B' of B, and (g o f) (the composite of f and g) is a bijection between A and g(B'), a subset of C. By definition, this means that #A <= #C. It would be nice if the relation "<=" was an order relation. It is easy to see that it is reflexive and transitive, and, in fact, it is also antisymmetric, although this is far less obvious. What we claim here is that, if: #A <= #B #B <= #A then #A = #B This is know as the Schroeder-Bernstein Theorem: Schröder-Bernstein Theorem from MathWorld--A Wolfram Web Resource http://mathworld.wolfram.com/Schroeder-BernsteinTheorem.html As I said, this is far from obvious. What the theorem states is that, if there are injective functions: f : A -> B g : B -> A then there is a bijective function: h : A -> B (write back if you would like a proof). For example, this can be used to show that the closed interval A = [0,1] is equipotent to the half-open interval [0,1), although a bijection h : A -> B is not obvious (well, it is not very hard to find...). Another question is whether this relation "<=" is a total order. Given two sets A and B, is it always true that at least one of the relations #A <= #B or #B <= #A holds, i.e., are any two sets "comparable"? It turns out that the answer to this question requires a special axiom of set theory, namely the axiom of choice: Wikipedia: Axiom of Choice http://en.wikipedia.org/wiki/Axiom_of_choice This axiom is independent of the other axioms of set theory. It is possible to develop a (rather dull) set theory without the axiom of choice. In such a theory, you could not assume that any two sets are comparable. Regarding the use of "infinity" in the context of limits, this is a completely different concept. It is not related to the sizes of sets, but rather to the natural order of the integer, rational, or real numbers. In fact, you could (although it would probably not be very useful) define a similar concept with any infinite set on which you can define a total order. If S is an infinite set with an order relation '<=' such that any two elements of S are comparable with respect to '<=' (such a relation is called a total order), you can say that a sequence of elements u[n] of S tends to infinity if, for every element m of S, there is a natural number N (depending on m), such that: n >= N implies u[n] >= m As I pointed out, this does not depend on whether S is countable or not: you can have sequence tending to infinity in the natural numbers (a countable set) or in the real numbers (an uncountable set) : this only depends on S being infinite and totally ordered. Please feel free to write back if you want to discuss this further. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/