[PDF] [PDF] Cardinality Lectures - Lake Forest College

[PDF] Cardinality

22 avr 2020 · Therefore, the interval (0, 1) must be uncountably infinite Since the interval (0, 1) has the same cardinality as R, it follows that R is uncountably infinite as well Notice that Z (which is countably infinite) is a subset of R

[PDF] CHAPTER 13 Cardinality of Sets

A bijection f : (0,∞) → (0,1) Page 5 Sets with Equal Cardinalities 221 Example 13 3 Show that (0,∞)=(0,1) To accomplish this, we need to show that there is a  

[PDF] Cardinality Lectures - Lake Forest College

22 nov 2013 · A When the set is infinite, comparing if two sets have the “same size” The interval (0,1) has the same cardinality as the interval (0,7) Proof

[PDF] Math 215: Homework 14 Solutions May 7, 2013 If A and B are sets

7 mai 2013 · Proposition HW14 2: The set (0,1) has the same cardinality as (−1,1) Proof Consider f : (0 

[PDF] Chapter VIII Cardinality - BYU Math Department

We will prove that the open interval A = (0, 1) and the open interval B = (1, 4) have the same cardinality We thus want to construct a bijection between these two 

[PDF] A Short Review of Cardinality

24 jui 2017 · We will give a short review of the definition of cardinality and prove some We say that two sets A and B have the same cardinality if there exists a 0 ≤ x ≤ 2 is a bijection, so the intervals [0, 2] and [0, 1] have the same 1 

[PDF] Chapter 7 Cardinality of sets

A 1-1 correspondence between sets A and B is another name for a function ( prove it) Hence these sets have the same cardinality • The function f : (0,1) 

[PDF] Cardinality Part 1 - Mathtorontoedu

S T have the same cardinality if there exists f: S → T 1: 1 onto (i e a "pairing" ) or one – to one Proof: We'll show no list can contain all numbers in [0,1] a ij 

[PDF] Cardinality

How do we prove two sets don't have the same size? Page 3 Injections and Surjections ○ An injective function associates at

[PDF] Lecture 29: Sections 101-103

If two sets A and B are both empty, A and B have the same cardinality • Two finite sets have Ex : R, the set of real numbers from 0 to 1 (i e, [0,1]) R − Q (the set of Prove that the set of odd (positive) numbers is countable 3 Prove that the 

[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

[PDF] proverbe créole martiniquais traduction

[PDF] proverbe sur apprendre de ses erreurs

Chapter 7

Cardinality of sets

7.1 1-1 Correspondences

A1-1 correspondencebetween setsAandBis another name for a function f:A!Bthat is 1-1 and onto. Iffis a 1-1 correspondence betweenAandB, thenfassociates every element ofBwith a unique element ofA(at most one element ofAbecause it is 1-1, and at least one element ofAbecause it is onto). That is, for each elementb2Bthere is exactly onea2Aso that the ordered pair (a;b)2f. Sincefis a function, for everya2Athere is exactly oneb2B such that (a;b)2f. Thus,f\pairs up" the elements ofAand the elements ofB. When such a functionfexists, we sayAandBcan be put into 1-1 correspondence. When we count the number of objects in a collection (that is, set), say

1;2;3;:::; n, we are forming a 1-1 correspondence between the objects in

the collection and the numbers inf1;2;:::;ng. The same is true when we arrange the objects in a collection in a line or sequence. The rst object in the sequence corresponds to 1, the second to 2, and so on. Because they will arise in what follows, we reiterate two facts. Iffis a 1-1 correspondence betweenAandBthen it has an inverse, andf1isa 1-1 correspondence betweenBandA. Iffis a 1-1 correspondence betweenAandB, andgis a 1-1 corre- 1

2CHAPTER 7. CARDINALITY OF SETS

spondence betweenBandC, thengfis a 1-1 correspondence between

AandC.

The following proposition will also be useful. It says that the relation \can be put into 1-1 correspondence" is transitive: two sets that can be put into 1-1 correspondence with the same set can be put into 1-1 correspondence with each other. Proposition 7.1.1LetA;BandCbe sets. IfAandCcan be put into 1-1 correspondence, andBandCcan be put into 1-1 correspondence, thenA andBcan be put into 1-1 correspondence. Proof. Supposef:A!Candg:B!Care both 1-1 correspondences. Sincegis 1-1 and onto,g1exists and is a 1-1 correspondence fromCtoB. Since the composition of 1-1, onto functions is 1-1 and onto,g1f:A!B is a 1-1 correspondence.

7.2 Cardinality of nite sets

A set is calledniteif either

it is empty, or it can be put into 1-1 correspondence withf1;2;:::;ngfor some natural numbern. The size of a nite set (also known as its cardinality) is measured by the number of elements it contains. Remember that counting the number of elements in a set amounts to forming a 1-1 correspondence between its elements and the numbers inf1;2;:::;ng. Thecardinality(size) of a nite setXis the numberjXjdened by j;j = 0, and j Xj=nifXcan be put into 1-1 correspondence withf1;2;:::;ng.

7.3. CARDINALITY OF INFINITE SETS3

As an aside, the vertical bars,j j, are used throughout mathematics to denote some measure of size. For example, the absolute value of a real number measures its size in terms of how far it is from zero on the number line. According to the denition, set has cardinalitynwhen there is a sequence ofnterms in which element of the set appears exactly once. The following corollary of Theorem 7.1.1 seems more than just a bit obvious. But, it is important because it will lead to the way we talk about the cardinality of innite sets (sets that are not nite). Corollary 7.2.1IfAandBare nite sets, thenjAj=jBj=n0if and only ifAandBcan be put into 1-1 correspondence. Proof. ()) First, supposejAj=jBj= 0. ThenA=B=;, sof=;is a

1-1, onto function fromAtoB. (The criteria for being 1-1, and onto, are

met vaccuuously.) Now supposejAj=jBj=n1. Then there are 1-1, onto functions f:A! f1;2;:::;ngandg:B! f1;2;:::;ng. By Proposition 7.1.1,Aand

Bcan be put into 1-1 correspondence.

(() Supposef:A!Bis a 1-1 correspondence. IfA=;thenB must also be empty, otherwisefis not onto. In this case,jAj=jBj= 0. Now supposeA6=;. Sincefis a function,B6=;. By hypothesis, there is a 1-1 correspondenceg:B! f1;2;:::;ng, for some natural numbern. Since the composition of 1-1, onto functions is 1-1 and onto, we have that gf:A! f1;2;:::;ngis a 1-1 correspondence betweenAandf1;2;:::;ng.

ThereforejAj=jBj=n.

7.3 Cardinality of innite sets

A set isinniteif it is not nite.

The denition of \innite" is worth a closer look. It says that a set is innite if it is not empty and can not be put into 1-1 correspondence with f1;2;:::;ngfor anyn2N. That means it has more thannelements for any natural numbern.

4CHAPTER 7. CARDINALITY OF SETS

Corollary 7.2.1 suggests a way that we can start to measure the \size" of innite sets. We will say thatanysetsAandBhave the same cardinality, and writejAj=jBj, ifAandBcan be put into 1-1 correspondence. IfA can be put into 1-1 correspondence with a subset ofB(that is, there is a 1-1 function fromAtoB), we writejAj jBj. Strange and wonderful things happen when this denition is applied to innite sets. For example: The functionf:N! f12;22;32;:::gdened byf(n) =n2is a 1-1 correspondence betweenNand the set of squares of natural numbers.

Hence these sets have the same cardinality.

The functionf:Z! f:::;2;0;;2;4gdened byf(n) = 2nis a

1-1 correspondence between the set of integers and the set 2Zof even

integers. Hence these sets have the same cardinality. (The notation 2Zis used because its elements are obtained by multi- plying each element ofZby 2. For an integerk1, the setkZis the set whose elements are obtained by multiplying each element ofZby k.) The functionf:N!Zdened byf(n) = (1)nbn=2cis a 1-1 corre- spondence between the set of natural numbers and the set of integers (prove it!). Hence these sets have the same cardinality. The functionf: (0;1)!(1;1) dened byf(x) = 2x1 is a 1-1 correspondence between the open interval (0;1) and the open interval (1;1). Hence these sets have the same cardinality.

The functiong: (1;1)!Rdened by

g(x) =8 :0 ifx= 0

1 + 1=xifx >0

1 + 1=xifx <0

is a 1-1 correspondence between the open interval (1;1) andR. Hence these sets have the same cardinality. Forfandgas in the previous two bullet points, the functiongf: (0;1)!Ris a 1-1 correspondence between the open interval (0;1) and

R. Hence these sets have the same cardinality.

7.4. COUNTABLE SETS5

In each case above, one of the sets properly contains the other and, in fact, contains innitely many elements that are not in the other. It can run con- trary to the intuition that these sets have the same cardinality. But that is what the denition implies. If there is a 1-1 correspondence between two sets, then it \pairs up" their elements. We have taken that to mean that the two sets have the same \size". It is a good exercise to show that any open interval (a;b) of real numbers has the same cardinality as (0;1). A good way to proceed is to rst nd a 1-1 correspondence from (0;1) to (0;ba), and then another one from (0;ba) to (a;b). Thus any open interval or real numbers has the same cardinality as (0;1). Proposition 7.1.1 then implies thatany two open intervals of real numbers have the same cardinality. It will turn out thatNandRdo not have the same cardinality (Ris \bigger"; in fact, so is (0;1)). It will take the development of some theory before this statement can be made meaningful.

7.4 Countable sets

A setXiscountably inniteif there is a 1-1 correspondence betweenNand X. A setXiscountableif it is nite, or countably innite. According to the examples in the previous section, the set of squares of natural numbers is a countably innite set, and so areZand 2Z. It will turn out that any innite subset of the integers is countably innite, and there are lots of other countably innite sets. Surprisingly, perhaps, the set of rational numbers is also countably innite. The argument used to prove that rests on the principles that follow. We mentioned before that if a set is nite then its elements can be ar- ranged in a sequence. When this happens we're actually forming a 1-1 cor- respondence withf1;2;:::;ng. Something similar with countably innite sets. If there is a 1-1 correspondencef:N!X, then there is a sequence of ele- ments ofXthat contains every element ofXexactly once:f(1);f(2);f(3);:::. The converse is also true. A sequencex1;x2;:::that contains every element ofXexactly once is the same as a 1-1 correspondencef:N!X: dene f(n) =xn, then-th element of the sequence.

6CHAPTER 7. CARDINALITY OF SETS

We can drop the condition that every element ofXbe contained in the sequence exactly once and, instead, require only that every element ofXbe guaranteed to appear somewhere in the sequence. Why? If such a sequence exists, then we can get a sequence that contains every element ofXexactly once by deleting elements that have appeared earlier in the sequence (that is, there is a subsequence in which every element ofXappears exactly once). This gives our main tool for proving that sets are countable. Theorem 7.4.1A setXis countable if and only if there is a sequence in which every element ofXappears (at least once).

Proof.

()) The implication is easy to see ifXis a nite set. IfXis countably innite, then there is a 1-1 correspondencef:N!X, and the sequence f(1);f(2);f(3);:::contains every element ofX. (() Suppose there is a sequencex1;x2;:::that contains every element ofX(at least once). Denef(1) =x1, and forn2 letf(n) be the rst element of the sequence that does not belong toff(1);f(2);:::g \X. Then fis 1-1 by its construction. To see thatfis onto, take anyy2X. Then yappears somewhere in the sequence. Supposexiis the rst element of the sequence that equalsy. Then, by the description off,y=f(n) for n= 1 +jfx1;x2;:::;xi1gj. Hencefis onto. Sincefis also 1-1, it is a 1-1 correspondence. Theorem 7.4.1 suggests a really good way to think about countable sets. A countable set is a set whose elements can be systematically listed so that every element eventually apears.Since every element of the set appears in the list, if we go far enough along the list we will eventually nd any element we're looking for. We will now explore some amazing consequences of Theorem 7.4.1. Notice that the sequence in the statement can contain elements that are not inX.

Corollary 7.4.2Any subset ofZis countable.

Proof. LetXbe a subset ofZ. The sequence 0;1;1;2;2;:::contains every integer exactly once. The result follows from Theorem 7.4.1. Almost exactly the same argument that proves Corollary 7.4.2 also proves the following.

7.4. COUNTABLE SETS7

Corollary 7.4.3Any subset of a countable set is countable. It can come as quite a shock that the set of rational numbers is countable. We have all of the tools to prove it, but rst will illustrate the argument by showing thatNNis countable. For reasons that will become evident, the method of proof is called \diagonal sweeping".

Proposition 7.4.4The setNNis countable.

Proof. It suces to describe a sequence in which every element ofNN is guaranteed to appear. The elements ofNNare the coordinates of the lattice points (points with integer coordinates) in the rst quadrant of the Cartesian plane. The sequence is illustrated by the arrows in Figure 7.1. It is clear that every element ofNNeventually appears: the components in the ordered pairs on subsequent diagonals sum to 2;3;:::. Therefore the ordered pair (a;b) appears on diagonala+b, and the elements on this diagonal all

appear in the list when it is \swept out".(1;1)(2;1)(2;2)(1;2)(1;3)(2;3)(3;3)(3;2)(3;1)(4;1)(3;4)(2;4).

..(1;4). ..Figure 7.1: Using diagonal sweeping to list the elements ofNN

8CHAPTER 7. CARDINALITY OF SETS

Theorem 7.4.5The set,Q, of rational numbers is countable. Proof. List the rationals as shown in Figure 7.2. The rst row consists of the rational numbers with denominator 1, the second row consists of those with denominator 2, and so on. In each row, the numerators appear in the order

0;1;1;2;2;:::. Every rational number appears because its sign (+ or)

can be associated with its numerator. A sequence in which every rational number appears (many times) is obtained by \sweeping out" the gure as ..0=4. ..Figure 7.2: Using diagonal sweeping to list the rational numbers Notice that, on the diagonals in the gure, the sum of the absolute value of the numerator and the absolute value of the denominator is constant. The sum of these numbers on thei-th diagonal isi. Hence, a rational number a=bappears in the list when the elements on diagonaljaj+jbjare listed. Almost exactly the same argument { make an array and systematically sweep it out { proves the following, more general, theorem. Theorem 7.4.6The union of any countable number of countable sets is countable.

7.5. UNCOUNTABLE SETS9

To summarize, we have the following methods of demonstrating that a set is countable. Show that: it is nite; or it is a subset of a countable set; or there is a sequence in which each of its elements is guaranteed to appear at least once (the list may be made by \diagonal sweeping"); or it can be put into 1-1 correspondence with a set that's known to be countable; or it is the union of countably many countable sets. The cardinality ofNis often denoted by@0(pronounced aleph-naught or aleph-zero; aleph is a letter in the Hebrew alphabet). Thus the cardinality of any countably innite set is@0.

7.5 Uncountable sets

A set isuncountableif it is not countable.

What does it mean for a set to be uncountable? According to the deni- tions, it means the set is innite, and can not be put into 1-1 correspondence withN. That means that there is no sequence that contains all of its ele- ments. To show that a set like (0;1) is uncountable (which it is), proceed by con- tradiction. Assume that it is countable. That means there is a list (sequence) that contains each of its elements exactly once. Then, use the description ofquotesdbs_dbs17.pdfusesText_23