Articles

1.4: Countable and Uncountable Sets - Mathematics


Definition 1.18

A set (S) is countable if there is a bijection (f : mathbb{N} ightarrow S). An infinite set for which there is no such bijection is called uncountable.

Proposition 1.19

Every infinite set (S) contains a countable subset.

Proposition 1.19

Every infinite set (S) contains a countable subset.

Proof

Choose an element (s_{1}) from (S). Now (S-{s_{1}}) is not empty because (S) is not finite. So, choose (s_{2}) from (S-{s_{1}}). Then (S-{s_{1}, s_{2}}) is not empty because (S) is not finite. In this way, we can remove (s_{n+1}) from (S-{s_{1}, s_{2}, cdots, s_{n}}) for all (n). Then set ({s_{1}, s_{2}, cdots}) is countable and is contained in (S).

So countable sets are the smallest infinite sets in the sense that there are no infinite sets that contain no countable set. But there certainly are larger sets, as we will see next.

Theorem 1.20

The set (mathbb{R}) is uncountable.

Proof

The proof is one of mathematics’ most famous arguments: Cantor’s diagonal argument [8]. The argument is developed in two steps .

Let (T) be the set of semi-infinite sequences formed by the digits 0 and 2. An element (t in T) has the form (t = t_{1}t_{2}t_{3} dots) where (t_{i} in {0, 2}). The first step of the proof is to prove that (T) is uncountable. So suppose it is countable. Then a bijection (t) between (mathbb{N}) and (T) allows us to uniquely define the sequence (t(n)), the unique sequence associated to (n). Furthermore, they form an exhaustive list of the elements of (T). For example,

[t(1) = extbf{0},0,0,0,0,0,0,0,0,0,0, dots onumber]

[t(2) = 2, extbf{0},2,0,2,0,2,0,2,2,2, dots onumber]

[t(3) = 0,0, extbf{0},2,2,2,2,2,2,2,2, dots onumber]

[t(4) = 2,2,2, extbf{2},2,2,0,0,0,0,0, dots onumber]

[t(5) = 0,0,0,2, extbf{2},0,2,0,0,2,0, dots onumber]

[t(6) = 2,0,0,0,0, extbf{2},0,0,0,2,2, dots onumber]

[vdots onumber]

Construct (t^{*}) as follows: for every (n), its nth digit differs from the nth digit of (t(n)). In the above example, (t^{*} = extbf{2}, extbf{2}, extbf{2}, extbf{0}, extbf{2}, extbf{0}, dots). But now we have a contradiction, because the element (t^{*}) cannot occur in the list. In other words, there is no surjection from (mathbb{N}) to (T). Hence there is no bijection between (mathbb{N}) and (T).

The second step is to show that there is a subset (K) of (mathbb{R}) such that there is no surjection (and thus no bijection) from (mathbb{N}) to (K). Let (t) be a sequence with digits (t_{i}). Define (f : T ightarrow mathbb{R}) as follows

[f(t) = sum_{i=1}^{infty}t_{i}3^{-i} onumber]

If (s) and (t) are two distinct sequences in (T), then for some (k) they share the first (k-1) digits but (t_{k} = 2) and (s_{k} = 0). So

[f(t)-f(s) = 2 cdot 3^{-k}+sum_{i=k+1}^{infty} (t_{i}-s_{i}) 3^{-i} ge 2 cdot 3^{-k}-2 sum_{i=k+1}^{infty} 3^{-i} = 3^{-k} onumber]

Thus (f) is injective. Therefore (f) is a bijection between (T) and the subset (K = f(T)) of (mathbb{R}). If there is a surjection (g) from (mathbb{N}) to (K = f(T)), then,

[mathbb{N} xrightarrow{ ext{g}} K xleftarrow{ ext{f}} T onumber]

And so (f^{-1} g) is a surjection from (mathbb{N}) to (T). By the first step, this is impossible. Therefore, there is no surjection (g) from (mathbb{N}) to (K), much less from (mathbb{N}) to (mathbb{R}).

Corollary 1.21

(i) The set of infinite sequences in ({1,2,cdots, b-1}^{mathbb{N}}) is uncountable.

(ii) The set of finite sequences (but without bound) in ({1, 2, cdots, b-1}^{mathbb{N}}) is countable.

Proof

The proof of (i) is the same as the proof that (T) is uncountable in the proof of Theorem 1.20. The proof of (ii) consists of writing first all (b) words of length 1, then all (b^{2}) words of length 2, and so forth. Every finite string will occur in the list.

Theorem 1.22

(i) The set (mathbb{Z}^2) is countable.

(ii) (mathbb{Q}) is countable.

Proof

(i) The proof relies on Figure 2. In it, a directed path (gamma) is traced out that passes through all points of (mathbb{Z}^2). Imagine that you start at ((0, 0)) and travel along (gamma) with unit speed. Keep a counter (c in mathbb{N}) that marks the point ((0, 0)) with a “1”. Up the value of the counter by 1 whenever you hit a point of (mathbb{Z}^2). This establishes a bijection between (mathbb{N}) and (mathbb{Z}^2).

Figure 2. A directed path (gamma) passing through all points of (mathbb{Z}^2).

(ii) Again travel along (gamma) with unit speed. Keep a counter (c in mathbb{N}) that marks the point ((0, 1)) with a “1”. Up the value of the counter by 1. Continue to travel along the path until you hit the next point ((p, q)) that is not a multiple of any previous and such (q) is not zero. Mark that point with the value of the counter. (mathbb{Q}) contains (mathbb{N}) and so is infinite. Identifying each marked point ((p, q)) with the rational number (frac{p}{q}) establishes the countability of (mathbb{Q}).

Notice that this argument really tells us that the product of a countable set and another countable set is still countable. The same holds for any finite product of countable set. Since an uncountable set is strictly larger than a countable, intuitively this means that an uncountable set must be a lot largerthan a countable set. In fact, an extension of the above argument shows that the set of algebraic numbers numbers is countable. And thus, in a sense, it forms small subset of all reals. All the more remarkable, that almost all reals that we know anything about are algebraic numbers, a situation we referred to at the end of Section 1.4.

It is useful and important to have a more general definition of when two sets “have the same number of elements”.

Definition 1.23

Two sets A and B are said to have the same cardinality if there is a bijection (f : A ightarrow B). It is written as (|A| = |B|). If there is an injection (f : A ightarrow B), then (|A| le |B|).

Definition 1.24

An equivalence relation on a set (A) is a (sub)set (mathbb{R}) of ordered pairs in (A imes A) that satisfy three requirements.

  • ((a, a) in mathbb{R}) (reflexivity).
  • If ((a, b) in mathbb{R}), then ((b, a) in mathbb{R}) (symmetry).
  • If ((a, b) in mathbb{R}) and ((b, c) in mathbb{R}), then If ((a, c) in mathbb{R}) (transitivity).

Usually ((a, b) in mathbb{R}) is abbreviated to (a sim b). The mathematical symbol “(=)” is an equivalence.

It is easy to show that having the same cardinality is an equivalence relation on sets (exercise 1.23). Note that the cardinality of a finite set is just the number of elements it contains. An excellent introduction to the cardinality of infinite sets in the context of naive set theory can be found in [15].


Ask Math: Uncountable set

I'm trying to understand what characterizes an uncountable set, but Wikipedia (http://en.wikipedia.org/wiki/Uncountable_set) says: "In mathematics, an uncountable set is an infinite set that contains too many elements to be countable." This doesn't help too much, does exist infinite sets that contains elements which can be countable and then exists another infinite set which is uncountable ? Thanks =)

WALL OF TEXT WARNING

Just going to put another phrasing of CorneliusJack's post out there.

Definition A set S is called countable if there exists a 1-1 and onto mapping between S and some subset of N (the set of natural numbers, which we'll take here to start at 0).

Let's examine what this means. If S is a finite set (containing some m elements), then it is necessarily countable, as you can come up with a bijective (1-1 and onto) mapping between S and <1,2,3. m> (just come up with some ordering of S). However, there are countable sets that are not finite, which are aptly named countably infinite sets.

It is clear from the definitions above that there is a bijective mapping between countably infinite sets and some infinite subset of the naturals (it turns out, as we will see in due time, that there is also a bijective mapping between any such set and the set of all naturals). As this is both a sufficient and necessary condition, it is clear that the set of all even numbers, all prime numbers, and all natural numbers (recall that I never said proper subset) are countable. However, it turns out that there are many more (I'm going to be lynched for saying that) countable sets than those described above.

For example, as CorneliusJack pointed out, the set

is countable because there is a bijective mapping between S and N (described by the 1-1 and onto function

for any x in S). Further, and this is probably slightly more surprising, the set of all integers, Z, is countable, as described by the function

where POS(x) is 1 if x is positive, zero otherwise.

Although these examples here aren't terribly difficult, there are many sets that require much more complicated mappings than the ones I put above. Thus, we note a cute property of countable sets (which is, in fact, where they got their name)

Property A set S is countable iff there is some method of iterating through its elements in some order.

For the two sets I proposed above, possible simple orderings include

(0, 0.5, 1.0, 1.5, . ) and (0, -1, 1, -2, 2, -3, 3, . )

however, even crazier orderings like the following are fine:

(0, 1, 2, .5, 1.5, 3, 4, 2.5, 3.5, 5, 6, 4.5, 5.5, . x, x + 1, x-.5, x+.5, . )
and
(0,1,2,3,4,5,-1,6,7,8,9,10,-2. )

since each ordering visits each element of the set exactly once (if you end up taking an analysis class at some point in the future, you'll re-investigate these orderings when going over the Riemann series theorem).

Note, however, that these are not valid orderings (for the purpose of directly determining countability, at least):

(0, 1, 2, 3, 4, . (to infinity), 0.5, 1.5, 2.5, 3.5. )
and
(0, 1, 2, 3, 4, . (to infinity), -1, -2, -3, . )

as you'll have to iterate through an infinite number of steps before reaching some of the elements (note that in the orderings given before these two, each element had a finite position in the list (!)).

Ok, great. But how do we iterate over the rationals? This is at first very unintuitive because it seems like there are a heck of a lot more rationals than integers (as there are an infinite number of rationals between any two integers!). However, there is a very nice way of iterating, which CorneliusJack already provided.

If that chart doesn't make sense, perhaps you'll find this algorithm more intuitive:

The resulting sequence looks something like

(0, 1, -1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3, 3/1, -3/1, 1/4, -1/4, 2/3, -2/3, 3/2, -3/2 4/1, -4/1, . )

which visits each rational number at some finite point.

Note that we could have saved ourselves a bit of trouble here by instead showing that the set of positive rationals is countable, then noting that the set of nonnegative rationals must also be countable (take some ordering and just tack a 0 on at the beginning), and then show that the set of all rationals is countable (using the same technique as we did for showing that |Z| = |N|).

Okay, great. So we just showed that the rationals are countable. Does this mean that every set is countable? It turns out (as you already know, having posted this question) that no, there exist some sets that are not countable. While perhaps the most classic example is the set of reals, R, the easiest proof lies in the set of infinite binary sequences.

Statement: the set of infinite binary (0,1) sequences is uncountable.

And here's where the fact that caused years of controversy comes in.

Proof (by diagonalization, not historically the first known proof)

Assume that the set of binary sequences is countable. Since it is assumed to be countable, there must be some ordering (as discussed before) which allows one to iterate through this sequence. Let's come up with a sample start to the ordering to see what it might look like

So far so good. Now here's where the trick comes in. Lets consider the diagonal entries (the sequence consisting of the kth digit of row k). Using what we have above, this would start with

Okay, good. Now let's consider the "complement" of this sequence (that is, the sequence where all of these bits are flipped). We instead get

which we will call S (can you guess my favorite letter by this point?). It turns out, as we will see shortly, that S is not in the ordering above (neither in the first 10 slots, nor in any slot after it). Why's that? Well, pretend that it's equal to the sequence at row k. S, by its infinitude, must have some kth digit. However, by the construction of S, its kth digit must not equal the kth digit of row k. Thus, S cannot be exactly equal to the sequence in row k (!). Therefore, we know that S can't appear in row k for any integer k, so it is not in the ordering.

This fact, that S cannot appear anywhere in the ordering, means that there is absolutely no way to iterate through the set of infinite binary sequences. Any ordering you come up with will necessarily leave at least one sequence behind (in fact, it leaves out a lot of sequences). Since it turns out that you can come up with a bijective mapping between the set of infinite binary sequences and real numbers (it's not complicated, but we will not do that here), this also implies that the set of real numbers is uncountable.

Now what is this aleph-0, aleph-1 garbage people have been talking about? For convenience, mathematicians decided to name the "sizes" of infinite sets. Inconveniently, they decided to do so using characters from a right-to-left language (Hebrew), so it's a pain in the neck to use them in text boxes. Anyway, the size of the naturals, |N|, is called aleph-naught (or aleph-zero), as it is the smallest infinite size that there is. The next smallest cardinality (size) is called aleph-1, the next is called aleph-2, and so on (I'm implicitly assuming a certain mildly "debated" axiom here in stating that this ordering exists, but we'll leave that aside for now).

What's an example of a set of size aleph-1? Contrary to what you've been told in the other replies, it is not taken as fact that the reals are of size aleph-1. In fact, it has been shown that using Zermelo-Fraenkel set theory (the most common collection of axioms used) does not allow you to either prove or disprove that the reals are of size aleph-1 (it is "independent" of ZF set theory). That is, there are models in which the cardinality of the reals really is the second smallest "infinite number", and there are models where it is not. If you wish to state that the reals are of size aleph-1, you're assuming what is called "the continuum hypothesis", which is not generally taken as true (or as false, it is generally left undetermined).

If you want to be accurate in your labeling of the cardinality of the reals, you can say that it is of the size 2 aleph-naught, as it can be shown that the cardinality of the reals is exactly equal to the cardinality of the power set (set of all subsets) of the natural numbers (2 S is used as the notation for the power set, since for some finite set of cardinality n, its power set contains 2 n elements). Thus, an alternate phrasing of the continuum hypothesis is that 2 aleph-0 = aleph-1. The generalized continuum hypothesis (which is also independent of ZF) in turn states that 2 aleph- k = aleph-(k+1) for any k.

I hope this came out formatted correctly, and moreso hope it helped you out :).


1.2. Countable Sets 可数集

A set that is either finite or has the same cardinality as the set of positive integers called countable可数的

A set that is not countable is called uncountable不可数的

When an infinite set S is countable, we denote the cardinality of S by (aleph null“阿里夫零”))

If , the set A is countably infinite可数无限

Below we will list some examples of countably infinite sets

1.2.1. Hilbert’s Grand Hotel 希尔伯特大酒店

1.2.2. Show that a set is countable 可数性证明

Key: Find a bijection!

Method 1. Linear Mapping 简单的线性映射

E.g.1 The set E of even positive integers 偶数集

Let f(x) = 2x. Then, f is a bijection from to

x 1 2 3 4 ……
f(x) 2 4 6 8 ……

The numbers of positive even integers is the same as positive integers

E is a proper subset of , but

E.g.2 The set of integers Z 整数集

Method 2. Cantor Table 利�ntor表构造映射

E.g.3 The set of positive rational numbers $Q^+$ 有理数集
Step 1 Prove $|Q^+|leq|S|$
Step 2 Prove $|S|=|Z^+|$

1 2 3 p
1 (1,1) (2,1) (3,1) (p,1)
2 (1,2) (2,2) (3,2) (p,2)
3 (1,3) (2,3) (3,3) (p,3)
q (1,q) (2,q) (3,q) (p,q)

this mapping is invertable, which means we found a bijection

An infinite set is countable iff it is possible to list all the elements of the set in a sequence

Step 3 Prove $|Z^+|leq|Q^+|$

Note:

The set of all rational numbers Q, positive and negative, is also countable infinite.

E.g.4 Show that the set of the real numbers with decimal representations consisting of all 1s is countable

We can arrange the numbers in a 2-dimensional table as follows:

1 2 3 4 5
1
2
3
4
5

Then number these numbers as before, like 1 to , 2 to , 3 to , 4 to , 5 to ……

Thus, we found a bijection!

Method 3. Define an order for strings 字符串的“运算符重载”

E.g.5 Show that the set of finite strings S over a finite alphabet A is countably infinite

Assume an alphabetical ordering of symbols in A. Show that the strings can be listed in a sequence. First list

  1. All the strings of length 0 in alphabetical order.
  2. Then all the strings of length 1 in lexicographic (as in a dictionary) order.
  3. Then all the strings of length 2 in lexicographic order.
  4. And so on.

This implies a bijection from N to S and hence it is a countably infinite set.

E.g.6 Show that the set of all Java programs is countable

A computer program written in a programming language can be thought of as a string of symbols from a finite alphabet

Hence, using the conclusion form the last example, we know this statement is true.

1.2.3. The properties of the countable sets 可数集性质

No infinite set has a smaller cardinality than a countable set

The union of two countable sets is countable

  • Case 1: A and B are finite. (Obviously…)
  • Case 2: A is infinite and B is finite. (Obviously…)
  • Case 3: A and B are both countably infinite. (We can list their elements as and respectively. By alternating terms of these two sequences, we can list the elements of A𢊫 in the infinite sequence , hence A𢊫 is countably infinite)

The union of finite number of countable sets is countable

The union of a countable number of countable sets is countable


1.4 Countable Sets (A diversion)

A set is said to be countable, if you can make a list of its members. By a list we mean that you can find a first member, a second one, and so on, and eventually assign to each member an integer of its own, perhaps going on forever.

The natural numbers are themselves countable- you can assign each integer to itself. The set (Z) of integers is countable- make the odd entries of your list the positive integers, and the even entries the rest, with the even and odd entries ordered from smallest magnitude up. Here is how this particular sequence of numbers begins:

(If a set is countable you can list it in lots of ways.)

The positive rational numbers, are also countable , and here is why. Take first all those whose numerator and denominator sum to (1), then (2) then (3), and so on. When several do so, order them by size. Here is how this list begins. (frac<0><1>, frac<1><1>, frac<1><2>, frac<2><1>, frac<1><3>, frac<2><2>, frac<3><1>, frac<1><4>, frac<2><3>, frac<3><2>, frac<4><1>), and so on. Every positive rational number appears on this list somewhere, and actually appears often on it. (This happens because (frac<1><2>) appears as (frac<1><2>) and also as (frac<2><4>) and (frac<3><6>) and so on. ) But all fractions eventually appear, and appear over and over again.

The number of positive and negative rational numbers are also countable, and we can list all together by taking alternatively from lists of each separately as done above for integers.

Rational numbers are described by pairs of integers, and the arguments above generalize to imply that any collection of pairs of members of a countable set are countable. And this can be generalized to the statement that a countable set of countable sets is countable.

It follows then that algebraic numbers , which are all solutions to polynomial equations of finite degree with integer coefficients are countable. There are a countable number of finite degrees, and a countable number of sets of coefficients for each degree and a countable number of solutions for each equation, and so the algebraic numbers of countable sets of countable sets of countable sets, which is still countable.

On the other hand, the set of all decimal expansions is not countable.

Well, if we had a list of all decimal expansions, we could easily construct a number that cannot be on it. Just make its entry (j) places beyond the decimal point differ by (2) from the entry in that place of the number that is (j^) on your list . Then the number we create differs from every number on your list and therefore cannot be on it. All of this means that we cannot list all the real numbers or decimal expansions!

Neither you nor I could actually do the infinite number of acts necessary to construct such a number, but we can imagine it done.

To visualize this imagine the first three numbers on your list were

A number not on the list by the construction given would start by (.335) since this sequence differs from the first number by (2) in the first place, differs from the second number by (2) in the second place and from the third member by 2 in the third place. The number we ultimately get will definitely differ from the three numbers above. With the rest of its digits similarly determined in reference to the next numbers in sequence on the list, we can deduce that this number cannot be on the list anywhere, so long as the number of its digits is the same as the length of the list.

This means that the set of all decimal expansions cannot possibly be listed. The decimal expansions are uncountable.

Are decimal expansions the same as real numbers?

Actually every real number between 0 and 1 has a decimal expansion, but some, namely those rational numbers that end with all (0)’s, appear twice as decimal expansions. The reason is that (0.99999. ) is really the same as (1.00000). Since these are a subset of the rational numbers, this difference is of no particular importance.

Exercise: Subtract (.9*) from (1.0*). What do you get ? If the (9)'s stopped somewhere, you could subtract and get a (1) in the next place and (0)'s everywhere else. But what happens when the (9)'s never stop?


1.4: Countable and Uncountable Sets - Mathematics

Question from Mac, a student:

Hi, i tried to read few webpages related to the countably infinite and uncountable sets.
Even i read few questions from this forum.

But i am not convinced with this explanation. If you have any good book that
explains this in layman term, please redirect me to that.

1) Can you please explain what is the difference between these too ?
2) How could you say set of Natural number and set of even numbers are countably infinite ?
N= <1,2,3. >and Even= <2,4,6. >
When an element in the even set is some 2n, we will map it to 'n'.So now we have a bigger number(2n) right ?
Sorry, i didn't understand that.
3) So whatever the set , do we try to map it with the Natural Number (N) ?
4) In some places, it says map it to the nature number and in some places it says, subset of natural number, can you please explain more on that ?
5) I didn't understand the explanation over here in this link,
http://www.cs.xu.edu/csci250/06s/Theorems/powerSetuncountable.pdf
Initially we are assuming 2^N is countably infinite and we are taking the subset of N (Is it all subsets..ie power set ?). Then we are defining a set A that has members other than any A(i). When we take the set of N, this set A
also should be part of that right ?

confusing subject !! spent hours today but still i didn't understand the concept.

Can you please help me out to understand that ?

The concepts of countable and uncountable can be confusing and counterintuitive. The concept most mathematicians use to distinguish the size of infinite sets comes from Georg Cantor. I want to start with an example:

Suppose you are organizing a meeting in some hall and you have put out chairs for the people sit on. Quite a few people have arrived and you wonder if you need to get more chairs. One way to determine this without counting the chairs and people is to ask everyone to sit down. If everyone sits down and there are chairs left then there are more chairs then people. If all the chairs are occupied and some people are left standing there are more people then chairs. If everyone is seated and there are no unoccupied chairs then there are the same number of chairs as people.

The idea here is that you match chairs with people. Mathematicians call this a one to one correspondence and it is used to compare the size of sets. The word we use for size is cardinality.

Definition:

Let A and B be sets. If there is a one to one correspondence from A into B we say the cardinality of A is less than or equal to the cardinality of B. If there is a one to one correspondence from A onto B we say that the cardinality of A is equal to the cardinality of B.

Before getting to your questions I want to state the Cantor&ndashBernstein&ndashSchroeder theorem

If the cardinality of A is less than or equal to the cardinality of B and the cardinality of B is less than or equal to the cardinality of A then the cardinality of A is equal to the cardinality of B.

Definitions:

A set A is finite if it is empty or its cardinality is the cardinality of <1, 2, ···, n>for some natural number n.

A set A is countably infinite if its cardinality is equal to the cardinality of the natural numbers N.

A set is uncountable if it is infinite and not countably infinite.

N = <1, 2, ···, >and Even = <2, 4, ···, 6>have the same cardinality because there is one to one correspondence from N onto Even. The correspondence, as you stated is n &rArr2n.

Two other useful results involving cardinality are:

If A and B have the same cardinality and B and C have the same cardinality then A and C have the same cardinality.

If A is a subset of B then the cardinality of A is less than or equal to the cardinality of B.


There are many equivalent characterizations of uncountability. A set X is uncountable if and only if any of the following conditions hold:

  • There is no injective function (hence no bijection) from X to the set of natural numbers.
  • X is nonempty and for every ω-sequence of elements of X, there exist at least one element of X not included in it. That is, X is nonempty and there is no surjective function from the natural numbers to X.
  • The cardinality of X is neither finite nor equal to ℵ 0 > (aleph-null, the cardinality of the natural numbers).
  • The set X has cardinality strictly greater than ℵ 0 > .

The first three of these characterizations can be proven equivalent in Zermelo–Fraenkel set theory without the axiom of choice, but the equivalence of the third and fourth cannot be proved without additional choice principles.

The best known example of an uncountable set is the set R of all real numbers Cantor's diagonal argument shows that this set is uncountable. The diagonalization proof technique can also be used to show that several other sets are uncountable, such as the set of all infinite sequences of natural numbers and the set of all subsets of the set of natural numbers. The cardinality of R is often called the cardinality of the continuum, and denoted by c >> , [2] or 2 ℵ 0 >> , or ℶ 1 > (beth-one).

The Cantor set is an uncountable subset of R. The Cantor set is a fractal and has Hausdorff dimension greater than zero but less than one (R has dimension one). This is an example of the following fact: any subset of R of Hausdorff dimension strictly greater than zero must be uncountable.

Another example of an uncountable set is the set of all functions from R to R. This set is even "more uncountable" than R in the sense that the cardinality of this set is ℶ 2 > (beth-two), which is larger than ℶ 1 > .

Without the axiom of choice, there might exist cardinalities incomparable to ℵ 0 > (namely, the cardinalities of Dedekind-finite infinite sets). Sets of these cardinalities satisfy the first three characterizations above, but not the fourth characterization. Since these sets are not larger than the natural numbers in the sense of cardinality, some may not want to call them uncountable.

If the axiom of choice holds, the following conditions on a cardinal κ are equivalent:

However, these may all be different if the axiom of choice fails. So it is not obvious which one is the appropriate generalization of "uncountability" when the axiom fails. It may be best to avoid using the word in this case and specify which of these one means.


Countable and Uncountable Sets

On the Finite Sets page we defined what it meant for a set $S$ to be finite and infinite.

We will now look at another important definition for the number of elements in a set.

Definition: A set $S$ is said to be Countably Infinite or Denumerable if there exists a bijection $f: mathbb o S$ .
Definition: A set $S$ is said to be Countable if it is either a finite set or a countably infinite set. A set $S$ is said to be Uncountable otherwise.

Let's first look at an example of a countably infinite set. Consider the set of even natural numbers $mathbb_> := < 2n : n in mathbb> = < 2, 4, 6, . >$ We can find a bijection $f : mathbb o S$ with the formula $f(n) = 2n$ , so we can say that $S_>$ is countably infinite and thus also countable. Similarly, the set of odd natural numbers is also countably infinite.

Of course, there are sets that are not countable, for example, the set of real numbers $mathbb$ , that is, there does not exist a bijection that maps $mathbb$ onto $mathbb$ . We will prove this later on.


Uncountable

The most common way that uncountable sets are introduced is in considering the interval (0, 1) of real numbers. From this fact, and the one-to-one function f( x ) = bx + a. it is a straightforward corollary to show that any interval (a, b) of real numbers is uncountably infinite.

The entire set of real numbers is also uncountable. One way to show this is to use the one-to-one tangent function f ( x ) = tan x. The domain of this function is the interval (-π/2, π/2), an uncountable set, and the range is the set of all real numbers.


1.4: Countable and Uncountable Sets - Mathematics

Subject: countable and uncountable sets
Name: piyush
Who are you: Student

we se that union of countably infinite no of sets having countably infinite number of elements is a countable set
we can express p(n) (i.e power set of natural number) as a union of countable infinite number of sets i.e p(n)=s1Us2Us3.
where s1=null
s2=<1,2,3,4,5. >
s3=<<1,1>,<1,2>,<1,3>. <2,1>,<2,2>. >
using the same statement can we prove that power set of natural number is a infinite countable set

Hi, we have two responses for you

The set you describe as p(n) = s1 U s2 U s3 U . is indeed countable by the argument you have given. This set however is not the power set of the natural numbers. The power set of the natural numbers is the set of all subsets of the natural numbers. In your construction every element of sk is finite, every element of sn has k-1 elements, and hence every member of p(n) is finite. The power set of the natural numbers contains all subsets of the natural numbers, including the infinite subsets such as

What you can prove in this way is that the set of FINITE subsets of natural numbers is countable. But to get the whole power set, you also need to count the infinite subsets, like <2, 4, 6, 8, . > <1, 4, 9, 16, . >and even strange ones like <1, 1093, 1094, 2222, . >. Actually, there is an uncountable number of these.


Product measure on two uncountable well-ordered sets

Let $(X,leq)$ be an uncountable well-ordered set such that for any $yin X,$ is countable. For any $Asubset X$ , let $mu(A)=0$ if $A$ is countable and $mu(A)=1$ if $Xsetminus A$ is countable. Then $mu$ is a measure defined on a $sigma$ -algebra. Define $T$ , the "ordinal triangle", by $T:=<(x,y)in X imes X:y<x>$ . Then egin iint1_T(x,y)dmu(y)dmu(x)=0 eq1=iint1_T(x,y)dmu(x)dmu(y). end

This contradicts the following theorem.

Product Measure Existence Theorem Let $(X,mathcal,mu)$ and $(Y,mathcal, u)$ be two $sigma$ -finite measure spaces. In $X imes Y$ let $mathcal$ be the collection of all "rectangles" $B imes C$ with $Binmathcal$ and $Cinmathcal$ . For such sets let $ ho(B imes C):=mu(B) u(C)$ , where (in this case) we set cdotinfty:=inftycdot0:=0$ . Let $mathcalotimesmathcal$ be the $sigma$ -algebra generated by $mathcal$ . Then $ ho$ extends uniquely to a measure on $mathcalotimesmathcal$ such that for all $Einmathcalotimesmathcal$ , egin ho(E)=iint1_E(x,y)dmu(x)d u(y)=iint1_E(x,y)d u(y)dmu(x). end


Watch the video: Countable and Uncountable Sets (December 2021).