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
CHAPTER 13 Cardinality of Sets
intervals (0?) and (0
Math 215: Homework 14 Solutions May 7 2013 If A and B are sets
May 7 2013 So by transitivity of cardinality
Cardinality of sets
Nov 30 2020 Sets A and B have the same cardinality
Chapter VIII Cardinality
To prove that two sets have the same cardinality you are required problem we know that
MATH 242: Principles of Analysis Homework Assignment #3
The linear function L(x)=(b?a)x+a is a bijection between (01) and (a
Cardinality Lectures
Nov 22 2013 To prove the proposition we need to show that an onto function exists ... The interval (0
Chapter 7 Cardinality of sets
It is a good exercise to show that any open interval (a b) of real numbers has the same cardinality as (0
A Short Review of Cardinality
Jun 24 2017 that X is finite if X is either empty or there exists an integer n > 0 such that X has the same cardinality as the set {1
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
cardinality - Millersville University of Pennsylvania
Example Prove that (01) has the same cardinality as R+ = (0?) De?ne f : (01) ? (1?) by f(x) = 1 x Note that if 0 < x < 1 then 1 x > 1 Therefore f does map (01) to (1?) 0 1 f(x) = 1/x swaps these intervals I claim that f?1(x) = 1 x If x > 1 then 0 < 1 x < 1 so f?1 maps (1?) to (01) Moreover f f?1(x) = f 1 x
CHAPTER 13 CardinalityofSets - Virginia Commonwealth University
Proposition 7 1 1 then implies thatany two open intervals of realnumbers have the same cardinality It will turn out that NandRdo not have the same cardinality (Risbigger"; in fact so is (0;1)) It will take the development of some theorybefore this statement can be made meaningful 7 4 Countable sets
CHAPTER 13 CardinalityofSets - Virginia Commonwealth University
R and(01) 2 R and(p 21) 3 R and(01) 4 Thesetofevenintegersand The sets N and Z have the same cardinality but R
NOTES ON CARDINALITY - Northwestern University
0;1; 1;2; 2;3; 3;4; 4;::: We can de nite a bijection from N to Z by sending 1 to 0 2 to 1 3 to 1 and so on sending the remaining natural numbers to the remaining integers in the list above consecutively Thus even though N is a proper subset of Z both of these sets have the same cardinalities!
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 r have the same cardinality filetype:pdf
procedure establishes a bijective correspondence between the sets (01)?B and A ? C Now note that both B and C are countable (make sure you can prove this!) Then by Problem 3 above (01) = A (b) Prove that R× R = R Solution: By part (a) there exists a bijective function f : R? A where A is the set of sequences of 0s and 1s
How do you prove that two sets have the same cardinality?
- The proof of this fact, thoughnot particularly di?cult, is not entirely trivial, either. The fact that f and guarantee that such anhexists is called thethe Cantor-Bernstein-Schröeder theorem. This theorem is very useful for proving two setsAandBhave the same cardinality: it says that instead of ?nding a bijection
What is the cardinality of a set of real numbers?
- The cardinality of the set of real numbers is usually denoted by c. This result tells us that even though both R and N are infnite, the set of real numbers is in some sense 4 NOTES ON CARDINALITY larger" than the set of natural numbers; we denote this by writing @ 0< c.
Do All Nite sets have the same cardinalities?
- Thus even though N is a proper subset of Z, both of these sets have the same cardinalities! This is where we start to see interesting facts about cardinalities that we do not see for fnite sets. In fact, any countably infnite set is equinumerous with any of its infnite subsets. Next we consider the rational numbers Q.
Why does B have the same cardinality?
- B have the same cardinality because there is a bijective functionf : A!Bgiven by the rule f(n)Æ ¡n. Several comments are in order. First, ifjAj Æ jBj, there can belotsofbijective functions fromAtoB.
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), say1;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- 12CHAPTER 7. CARDINALITY OF SETS
spondence betweenBandC, thengfis a 1-1 correspondence betweenAandC.
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 a1-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,AandBcan 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 a1-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= 01 + 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) andR. 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 allappear 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 ofNN8CHAPTER 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 order0;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
[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] provided that logic
[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] provided that logic
