[PDF] [PDF] Chapter VIII Cardinality - BYU Math Department

[PDF] Cardinality

22 avr 2020 · Show that the open interval (0, 1) and the closed interval [0, 1] have the same cardinality The open interval 0

[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 · When the set is infinite, comparing if two sets have the “same size” is a The interval (0,1) has the same cardinality as the interval (0,7) Proof

[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] 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,1) → (−1,1) given by f(x) = 2x − 1 We note that if x 

[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

If f is a 1-1 correspondence between A and B then it has an inverse, (prove it) Hence these sets have the same cardinality • The function f : (0,1) → (−1,1) 

[PDF] CARDINALITY, COUNTABLE AND UNCOUNTABLE SETS PART

two finite sets have the same number of elements: we just need to verify Ex 1 Z ∼ N We “count” the elements of Z as follows: Z = {0,1,−1,2,−2,3,−3,4,−4,

[PDF] Cardinality

When can we say one set is no larger than another? ○ Unequal Cardinalities ○ How do we prove two sets don't have the same size?

[PDF] Math 8 Homework 7 1 Cardinality and Countability 2 - UCSB Math

(ii) The sets R and (0, 1) have the same cardinality (iii) The sets cardinality (b) Prove there is not a largest set; that is, for any set S there is a set T with S < T

[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

[PDF] proverbe créole martiniquais traduction

Cardinality Lectures

Enrique Trevi~no

November 22, 2013

1 Denition of cardinality

The cardinality of a set is a measure of the size of a set. When a setAis nite, its cardinality is the number of elements of the set, usually denoted by jAj. When the set is innite, comparing if two sets have the \same size" is a little dierent. Georg Cantor in the late 1800s came out with the following idea to compare innite sets: Denition 1.LetAandBbe sets. We sayjAj=jBjif and only if there exists a bijective functionf:A!B. Note that the denition also works for nite sets, because ifAandBare nite sets andf:A!Bis a bijection, thenjAj=jBj. Here are two other denitions that work for nite and innite sets: Denition 2.LetAandBbe sets. We sayjAj jBjif and only if there exists an onto functionf:A!B(orBis empty). Denition 3.LetAandBbe sets. We sayjAj jBjif there exists a one-to-one functionf:A!B(or ifAis empty). These denitions extend naturally to the following: jAj>jBjifjAj jBjandjAj 6=jBj, i.e., there exists an onto function fromAtoB, but no bijection exists fromAtoB. jAj2 Innite sets versus nite sets Let's check if our denitions pass the \eyeball-test" by checking if an innite set is indeed \larger" than a nite set: Proposition 1.LetAbe an innite set andBbe a nite set. ThenjAj>jBj. Proof.To prove the proposition we need to show that an onto function exists fromAtoB, yet there is no bijection fromAtoB. Let's start by building an onto function. SinceBis nite,jBj=nfor somen2N, therefore B=fb1;b2;:::;bngfor someb1;b2;:::bn. SinceAis innite, it has at leastn elements, label thesenelementsa1;a2;:::an.

Letf:A!Bbe dened as

f(a) =8 :b iifa=aifori= 1;2;:::;n b

1otherwise:

Clearlyfis a function and its image isB, sofis onto. This proves that jAj jBj. Now, let's prove thatjAj 6=jBj. For the sake of contradiction, suppose jAj=jBj, i.e., suppose that there exists a bijectiong:A!B. SinceAis innite, then it has at leastn+ 1 elements, label thesea1;a2;:::;an;an+1. Sincegis one-to-one, theng(a1);g(a2);:::g(an+1) are all dierent, so the size ofBmust be at leastn+ 1. But the size ofBisn. This contradicts our assumption thatjAj=jBj. Since cardinality tries to measure size, it would be nice to show that a sub- set of another set has smaller cardinality. That's what the next proposition says: Proposition 2.IfAandBare sets andAB, thenjAj jBj. Proof.Letf:A!Bbe the functionf(a) =afora2A.fis one-to-one becausef(a) =f(b) =)a=b. Sincefis one-to-one by denitionjAj jBj. 2

3 Examples of bijections between innite sets

Proposition 3.The interval(0;1)has the same cardinality as the interval (0;7). Proof.Letf: (0;1)!(0;7) be dened byf(x) = 7x. Let's provefis a bijection. To prove thatfis a bijection we must show (a) thatfis one-to-one, and (b) thatfis onto. Let's show thatfis one-to-one: Letf(a) =f(b), then 7a= 7b, soa=b.

Thereforefis one-to-one.

Let's show thatfis onto: Supposeb2(0;7). Leta=b=7, thenf(a) =

7(b=7) =banda2(0;1), sobis in the image off. Sincebis arbitrary, then

fis onto. Sincefis one-to-one andfis onto,fis a bijection. Sincefis a bijection, the intervals (0;1) and (0;7) have the same cardinality.

Proposition 4.The interval

2 ;2 has the same cardinality asR. Proof.To prove that the sets have the same cardinality we must nd a bijec- tion between them. I claim thatf(x) =tanxis a bijection from 2 ;2 toR. Let's start by showing it is one-to-one. Supposef(a) =f(b). Then tana= tanbwhereaandbare in the interval 2 ;2 . Thereforeaandb are angles between=2 and=2. Since tana= tanband they are angles with that restriction, thena=b. No let's showfis onto. Letxbe a real number. We need to show there exists ana2 2 ;2 such thatf(a) =x, i.e., such that tana=x. Let a= arctanx. Then tana=x. We need only verify thatais between=2 and=2. But the arctan function has range 2 ;2 , soamust be between =2 and=2.

This concludes the proof.

A more illustrative proof is the graph off(x) = tanx(Figure 1). 3

Figure 1: Note that in the graph, any horizontal line intersects the graph at most once, which means the

function is one-to-one. Also note that every horizontal line intersects the graph, so everyyvalue has at least

onexvalue. This means the function is onto. Proposition 5.The set of even integers has the same cardinality as the set of integers. Proof.Let 2Zbe the set of even integers. Letf:Z!2Zbe the function f(n) = 2n. fis one-to-one because iff(m) =f(n), then 2m= 2nand hencem=n. fis onto because ifnis an even integer, thenn= 2mfor some integerm (by the denition of even integer) and hencef(m) =n. So all even integers are in the image off, sofis onto. 4

4 Cardinality is an equivalence relation

In this section we will prove that the cardinality relation is an equivalence relation. We say two setsAandBare related by cardinality ifjAj=jBj. First note that any setAsatisesjAj=jAj, becausef:A!Adened byf(a) =ais a bijection. Therefore the cardinality relation is re exive. That cardinality is symmetric is not obvious, but it's not hard to prove. SupposejAj=jBj, therefore there exists a bijectionf:A!B. Sincef is one-to-one thenf1:Im(f)!Ais a bijection (it's one-to-one and onto by denition off1). Sincefis onto, thenIm(f) =B, thereforef1is a bijection fromBtoA. ThereforejBj=jAj. Transitivity is a bit harder to prove. Proving transitivity boils down to showing that given a bijection fromAtoBand another bijection fromB toC, there exists a bijection fromAtoC. We prove that in the following proposition (where we go even further and prove that the composition of two bijections is a bijection):

Proposition 6.Letf:A!Bandg:B!Cbe bijections, then

gf:A!Cis a bijection. Proof.Let's start by proving thatgfis one-to-one. Supposegf(a) =g f(b). Theng(f(a)) =g(f(b)). Sincegis one-to-one, this impliesf(a) =f(b). Sincefis one-to-one,a=b. Thereforegfis one-to-one. Let's now prove thatgfis onto. Supposec2C. Sincec2Candgis onto, there existsb2Bsuch thatg(b) =c. Sinceb2Bandfis onto, there exists ana2Asuch thatf(a) =b. Thereforeg(f(a) =c, i.e.,gf(a) =c.

Sincegfis one-to-one and onto, it is a bijection.

Since cardinality is re

exive, symmetric and transitive, then it is an equiv- alence relation. Exercise 1.Say that the setAis related to the setBifjAj jBj(where jAjis the cardinality of the setA). Prove that this relation is re exive, antisymmetric and transitive. 5quotesdbs_dbs17.pdfusesText_23