[PDF] CHAPTER 13 Cardinality of Sets





Previous PDF Next PDF



cardinality.pdf

By the lemma g · f : S → U is a bijection





MAT246H1S Lec0101 Burbulla

Mar 10 2016 4: if a < b then [a





Chapter 7 Cardinality of sets

1 then implies that any two open intervals of real numbers have the same cardinality. following proposition which can also be proved by noting that R and (0



MATH 242: Principles of Analysis Homework Assignment #3

We conclude that the open intervals (01) and (a



CHAPTER 13 Cardinality of Sets

The next example shows that the intervals (0∞) and (0





Math 215: Homework 14 Solutions May 7 2013 If A and B are sets

May 7 2013 Proposition HW14.2: The set (0



CPY Document

injective then there exists a bijection h: A-B. Use the Schröder-Bernstein Theorem to prove that the open interval (0







= 2 since {0

we need to show that there ...



Cardinality Cardinality

Oct 17 2014 How do we prove two sets don't have the same size? Page 3. Injections ... Set all nonzero values to 0 and all 0s to 1. 0. 0 0 1 0 0 … Page 53 ...



Sets and Functions

Corollary 1.48. The set Σ of binary sequences has the same cardinality as P(N) and is uncountable. Proof. By Example 1.30 



cardinality.pdf

Apr 22 2020 I can tell that two sets have the same number of elements by trying to ... Prove that the interval (0



Math 215: Homework 14 Solutions May 7 2013 If A and B are sets

May 7 2013 Proposition HW14.2: The set (0





Chapter 7 Cardinality of sets

We will say that any sets A and B have the same cardinality Proof. Let X be a subset of Z. The sequence 0



MATH 301

(b) Show that an unbounded interval like (a?) = {x : x>a} has the same cardinality as R as well. (c) Show that [0



Countable and Uncountable Sets In this section we extend the idea

Example (infinite sets having the same cardinality). Let f : (01) ? (1





Cardinality

cardinality k must have the same number of elements



6 Cosets & Factor Groups

We have already proved the special case for subgroups of cyclic groups:1 into several subsets each with the same cardinality as H. We call these ...



Sets and Functions

Corollary 1.48. The set ? of binary sequences has the same cardinality as P(N) and is uncountable. Proof. By Example 1.30 



cardinality - Millersville University of Pennsylvania

In other words having the same cardinality is an equivalence relation Proof (a) By the lemma the identity function id : S?Sis a bijection soS =S (b) If S =T then there is a bijectionf: S?T By the lemmaf?1: T?Sis a bijection Therefore T =S (c) If S =T andT =U then there are bijectionsf : S T andg : T ?U



discrete mathematics - Proving the interval $ (0 1)$ and $ (1 3

De nition 1 Two sets A and B are said to have the same cardinality (written jAj= jBj) if there exists a bijective function f : A !B Otherwise they are said to have di erent cardinalities (written jAj6= jBj) De nition 2 Let n 2Z If a set A has the same cardinality as f1;2;3;:::;ng then we say it has cardinality n and write jAj= n Theorem



Chapter 7 Cardinality of sets - University of Victoria

It is a good exercise to show that any open interval (a; b) of real numbershas the same cardinality as (0;1) A good way to proceed is to rst nd a 1-1correspondence from (0;1) to (0; b a) and then another one from (0; b a)to (a; b) Thus any open interval or real numbers has the same cardinalityas (0;1)



3 Cardinality - University of Pennsylvania

De?nition 9 (Final attempt) Two sets A and B have the same cardinality if there is a one-to-one matching between their elements; if such a matching exists we write A = B The two sets A = {123} and B = {abc} thus have the cardinality since we can match up the elements of the two sets in such a way that each element



Chapter VIII Cardinality

We will prove that the open intervalA= (0;1) and the open interval = (1;4) have the same cardinality We thus want to construct a bijection betweenthese two sets The most obvious option would be to stretch by a factor of 3 andthen shift right by 1 So we de neg: (0;1)!(1;4) by the rule g(x) = 1 + 3x:



Searches related to prove that 0 1 and a b have the same cardinality filetype:pdf

A to B then we say that the cardinality of A is less than or equal to the cardinality of B In this case we write card(A) card(B) Theorem 8 7 Let A B and C be sets Then we have the following: (a) If A B then card(A) card(B) (b) If card(A) card(B) and card(B) card(C) then card(A) card(C)

How to prove that the intervals have the same cardinality?

    Proving the interval ( 0, 1) and ( 1, 3) have the same cardinality. Prop: Show that the intervals ( 0, 1) and ( 1, 3) have the same cardinality. What I have tried: I showed that the intervals [ 2, 4] and [ 0, 5] have equal cardinality by creating a function F ( x) = 5 2 x ? 5.

What is the cardinality of set a and B?

    This is called the cardinality of the set. The number of elements in a set is the cardinality of that set. Let A = {1, 2, 3, 4, 5, 6} and B = {2, 4, 6, 8}. What is the cardinality of B?

Is equal cardinality enough?

    Also, because this is an open interval aren't we not supposed to include 0, 1, or 3 in the set. Yes, it is enough, because by definition equal cardinality implies bijective relation between the two sets. Both are open intervals, so you can ignore the border numbers. For each number inside , there is a unique number inside

Do s and t have the same cardinality?

    S and T have the same cardinality if there is a bijection f from S to T. Notation: means that S and T have the same cardinality. (b) A set S is finite if it is empty, or if there is a bijection for some integer . A set which is not finite is infinite .

CHAPTER 13

Cardinality of Sets

T his chapteris all about cardinality of sets. At first this looks like a very simple concept. To find the cardinality of a set, just count its elements. IfAAE©a,b,c,dª, thenjAj AE4; ifBAE

©n2Z:¡5·n·5ª, then

jBjAE11. In this casejAjÇjBj. What could be simpler than that? Actually, the idea of cardinality becomes quite subtle when the sets are infinite. The main point of this chapter is to explain how there are numerous different kinds of infinity, and some infinities are bigger than others. Two setsA andBcan both have infinite cardinality, yetjAjÇjBj. 13.1 Se tswit hEq ualCardinalities We begin with a discussion of what it means for two sets to have the same cardinality. Up until this point we"ve saidjAjAEjBjifAandBhave the same number of elements: Count the elements ofA, then count the

elements ofB. If you get the same number, thenjAjAEjBj.Although this is a fine strategy if the sets are finite (and not too big!),

it doesn"t apply to infinite sets because we"d never be done counting their elements. We need a new approach that applies to both finite and infinite sets. Here it is:

Definition 13.1

Two setsAandBhave thesame cardinality, written

j AjAEjBj, if there exists a bijective functionf:A!B. If no such bijective function exists, then the sets haveunequal cardinalities, that is,jAj6AEjBj.edcba 432
10AB fThe above picture illustrates our definition. There is a bijective function f:A!B, sojAjAEjBj. The functionfmatches upAwithB. Think offas describing how to overlayAontoBso that they fit together perfectly.

218Cardinality of SetsOn the other hand, ifAandBare as indicated in either of the following

figures, then there can be no bijectionf:A!B. (The best we can do is a function that is either injective or surjective, but not both). Therefore the definition saysjAj6AEjBjin these cases.dcba

43210ABf

dcba e3210ABf

Example 13.1

The setsAAE©n2Z: 0·n·5ªandBAE©n2Z:¡5·n·0ª have the same cardinality because there is a bijective functionf:A!B given by the rulef(n)AE¡n. Several comments are in order. First, ifjAjAEjBj, there can belotsof bijective functions fromAtoB. We only need to find one of them in order to concludejAjAEjBj. Second, as bijective functions play such a big role here, we use the wordbijectionto meanbijective function. Thus the function f(n)AE¡nfrom Example 13.1 is a bijection. Also, an injective function is called aninjectionand a surjective function is called asurjection. We emphasize and reiterate that Definition 13.1 applies to finite as well as infinite sets. IfAandBare infinite, thenjAjAEjBjprovided there exists a bijectionf:A!B. If no such bijection exists, thenjAj6AEjBj.

Example 13.2

This example shows thatjNjAEjZj. To see why this is true, notice that the following table describes a bijectionf:N!Z. n1 2 3 4 5 6 7 8 9 10 11 12 13 14 15...f(n)0 1¡1 2¡2 3¡3 4¡4 5¡5 6¡6 7¡7... Notice thatfis described in such a way that it is both injective and surjective. Every integer appears exactly once on the infinitely long second row. Thus, according to the table, given anyb2Zthere is some natural numbernwithf(n)AEb, sofis surjective. It is injective because the way the table is constructed forcesf(m)6AEf(n)wheneverm6AEn. Because of this bijectionf:N!Z, we must conclude from Definition 13.1 thatjNjAEjZj. Example 13.2 may seem slightly unsettling. On one hand it makes sense thatjNjAEjZjbecauseNandZare both infinite, so their cardinalities are both "infinity." On the other hand,Zmay seem twice as large as

Sets with Equal Cardinalities219

NbecauseZhas all the negative integers as well as the positive ones. Definition 13.1 settles the issue. Because the bijectionf:N!Zmatches upNwithZ, it follows thatjNjAEjZj. We summarize this with a theorem. Theorem 13.1There exists a bijectionf:N!Z. ThereforejNjAEjZj. The fact thatNandZhave the same cardinality might prompt us compare the cardinalities of other infinite sets. How, for example, doN andRcompare? Let"s turn our attention to this. In fact,jNj6AEjRj. This was first recognized by Georg Cantor (1845-1918), who devised an ingenious argument to show that there are no surjective functionsf:N!R. (This in turn implies that there can be no bijections f:N!R, sojNj6AEjRjby Definition 13.1.) We now describe Cantor"s argument for why there are no surjections f:N!R. We will reason informally, rather than writing out an exact proof. Take any arbitrary functionf:N!R. Here"s whyfcan"t be surjective: Imagine making a table forf, where values ofninNare in the left- hand column and the corresponding valuesf(n)are on the right. The first few entries might look something as follows. In this table, the real numbersf(n)are written with all their decimal places trailing off to the right. Thus, even thoughf(1)happens to be the real number0.4, we write it as0.40000000...., etc.nf(n)10 . 4 0 0 0 0 0 0 0 0 0 0 0 0 0...

28 . 5 0 0 6 0 7 0 8 6 6 6 9 0 0...

37 . 5 0 5 0 0 9 4 0 0 4 4 1 0 1...

45 . 5 0 7 0 4 0 0 8 0 4 8 0 5 0...

56 . 9 0 0 2 6 0 0 0 0 0 0 5 0 6...

66 . 8 2 8 0 9 5 8 2 0 5 0 0 2 0...

76 . 5 0 5 0 5 5 5 0 6 5 5 8 0 8...

88 . 7 2 0 8 0 6 4 0 0 0 0 4 4 8...

90 . 5 5 0 0 0 0 8 8 8 8 0 0 7 7...

100 . 5 0 0 2 0 7 2 2 0 7 8 0 5 1...

112 . 9 0 0 0 0 8 8 0 0 0 0 9 0 0...

126 . 5 0 2 8 0 0 0 8 0 0 9 6 7 1...

138 . 8 9 0 0 8 0 2 4 0 0 8 0 5 0...

148 . 5 0 0 0 8 7 4 2 0 8 0 2 2 6...

220Cardinality of SetsThere is a diagonal shaded band in the table. For eachn2N, this band

covers thenthdecimal place off(n): The 1st decimal place off(1)is the 1st entry on the diagonal. The 2nd decimal place off(2)is the 2nd entry on the diagonal. The 3rd decimal place off(3)is the 3rd entry on the diagonal. The 4th decimal place off(4)is the 4th entry on the diagonal, etc. The diagonal helps us construct a numberb2Rthat is unequal to anyf(n). Just let thenth decimal place ofbdiffer from thenth entry of the diagonal. Then thenth decimal place ofbdiffers from thenth decimal place off(n). In order to be definite, definebto be the positive number less than1whose nth decimal place is0if thenth decimal place off(n)is not0, and whose nth decimal place is1if thenth decimal place off(n)equals0.Thus, for the functionfillustrated in the above table, we have bAE0.01010001001000... andbhas been defined so that, for anyn2N, itsnth decimal place is unequal to thenth decimal place off(n). Thereforef(n)6AEbfor every natural numbern, meaningfis not surjective. Since this argument applies toanyfunctionf:N!R(not just the one in the above example) we conclude that there exist no bijectionsf:N!R, sojNj6AEjRjby Definition 13.1. We summarize this as a theorem. Theorem 13.2There exists no bijectionf:N!R. ThereforejNj6AEjRj. This is our first indication of how there are different kinds of infinities. BothNandRare infinite sets, yetjNj 6AE jRj. We will continue to develop this theme throughout this chapter. The next example shows that the intervals(0,1)and(0,1)onRhave the same cardinality.11 8 >>:1 xP

0¡1f(x)Figure 13.1.A bijectionf:(0,1)!(0,1)

Sets with Equal Cardinalities221

Example 13.3Show thatj(0,1)jAEj(0,1)j.To accomplish this, we need to show that there is a bijectionf:(0,1)!(0,1).

We describe this function geometrically. Consider the interval(0,1)as the positivex-axis ofR2. Let the interval(0,1)be on they-axis as illustrated in Figure 13.1, so that(0,1)and(0,1)are perpendicular to each other. The figure also shows a pointPAE(¡1,1). Definef(x)to be the point on (0,1)where the line fromPtox2(0,1)intersects they-axis. By similar triangles, we have

1xÅ1AEf(x)x

and therefore f(x)AExxÅ1. If it is not clear from the figure thatf:(0,1)!(0,1)is bijective, then you can verify it using the techniques from Section 12.2. (Exercise 16, below.) It is important to note that equality of cardinalities is an equivalence relation on sets: it is reflexive, symmetric and transitive. Let us confirm this. Given a setA, the identity functionA!Ais a bijection, sojAjAEjAj. (This is the reflexive property.) For the symmetric property, ifjAj AE jBj, then there is a bijectionf:A!B, and its inverse is a bijectionf¡1:B!A, sojBj AE jAj. For transitivity, supposejAj AE jBjandjBj AE jCj. Then there are bijectionsf:A!Bandg:B!C. The compositiong±f:A!Cis a bijection (Theorem 12.2), sojAjAEjCj. The transitive property can be useful. If, in trying to show two setsA andChave the same cardinality, we can produce a third setBfor which jAj AE jBjandjBj AE jCj, then transitivity assures us that indeedjAj AE jCj.

The next example uses this idea.

Example 13.4Show thatjRjAEj(0,1)j.

Because of the bijectiong:R!(0,1)whereg(x)AE2x, we havejRjAEj(0,1)j. Also, Example 13.3 shows thatj(0,1)jAEj(0,1)j. ThereforejRjAEj(0,1)j. So far in this chapter we have declared that two sets have "the same cardinality" if there is a bijection between them. They have "different cardinalities" if there exists no bijection between them. Using this idea, we showed thatjZj AE jNj 6AE jRj AE j(0,1)j AE j(0,1)j. So, we have a means of determining when two sets have the same or different cardinalities. But we have neatly avoided saying exactly what cardinalityis. For example, we can say thatjZjAEjNj, but what exactlyisjZj, orjNj? What exactlyare these things that are equal? Certainly not numbers, for they are too big.

222Cardinality of SetsAnd saying they are "infinity" is not accurate, because we now know that

there are different types of infinity. So just what kind of mathematical entity isjZj? In general, given a setX, exactly whatisits cardinalityjXj? This is a lot like asking what a number is. A number, say 5, is an abstraction, not a physical thing. Early in life we instinctively grouped together certain sets of things (five apples, five oranges, etc.) and conceived of 5 as the thing common to all such sets. In a very real sense, the number

5 is an abstraction of the fact that any two of these sets can be matched

up via a bijection. That is, it can be identified with a certain equivalence class of sets under the "has the same cardinality as" relation. (Recall that this is an equivalence relation.) This is easy to grasp because our sense of numeric quantity is so innate. But in exactly the same way we can say that the cardinality of a setXis what is common to all sets that can be matched toXvia a bijection. This may be harder to grasp, but it is really no different from the idea of the magnitude of a (finite) number. In fact, we could be concrete and definejXjto be the equivalence class of all sets whose cardinality is the same as that ofX. This has the advantage of giving an explicit meaning tojXj. But there is no harm in taking the intuitive approach and just interpreting the cardinalityjXjof a setXto be a measure the "size" ofX. The point of this section is that we have a means of deciding whether two sets have the same size or different sizes.Exercises for Section 13.1 A. Show that the two given sets have equal cardinality by describing a bijection from one to the other. Describe your bijection with a formula (not as a table).

1.Rand(0,1)

2.Rand(p2,1)

3.Rand(0,1)

4.The set of even integers and

the set of odd integers n :n2Nª

7.ZandSAE©...,18

,14 ,12 ,1,2,4,8,16,...ª

8.ZandSAE©x2R:sinxAE1ª

9.

©0,1ª£NandN

10.©0,1ª£NandZ

11.[0,1]and(0,1)

12.NandZ(Suggestion: use Exercise 18 of Section 12.2.)

13.P(N)andP(Z)(Suggestion: use Exercise 12, above.)

14.N£Nand©(n,m)2N£N:n·mª

B.Answer the following questions concerning bijections from this section.quotesdbs_dbs17.pdfusesText_23
[PDF] prove that (0 1) and 0 1 have the same cardinality

[PDF] prove that (0 1) and r have the same cardinality

[PDF] prove that a connected graph with n vertices has at least n 1 edges

[PDF] prove that any finite language is recursive decidable

[PDF] prove that any two open intervals (a

[PDF] prove that if both l1 and l2 are regular languages then so is l1 l2

[PDF] prove that if f is a continuous function on an interval

[PDF] prove that if f is bijective then f inverse is bijective

[PDF] prove that if lim sn and lim tn exist

[PDF] prove that if t ? l(v satisfies t 2 t then v = null t ? range t)

[PDF] prove that lr is context free for every context free language l

[PDF] prove that range(t + s) ? range(t) + range(s).

[PDF] prove that the class of non regular languages is not closed under concatenation.

[PDF] prove that the interval (0

[PDF] prove the inverse of a bijective function is bijective