Finite and Countable • Definition ○ Let J_n={1,2,3,…,n} and N={1,2,3,…} ○ For any set A, we say ○ A is finite if A~J_n for some n (∅~J_0 so ∅ is finite) ○ A is infinite if A≁J_n for all n ○ A is countable if A~N ○ A is uncountable if A is neither finite nor countable ○ A is at most coutable if A is finite or countable • Examples ○ N is clearly countable § N={1,2,3,…} ○ Z is countable § Z={0,1,−1,2,−2,3,−3,…} § Define f:N→Z by § f(n)≔{■8(n/2&n is even@(1−n)/2&n is odd)┤ § f is injective □ If f(n)=f(m) □ then n/2=m/2 or (1−n)/2=(1−m)/2 □ Either way, n=m § f is surjective □ Given k∈Z, □ If k0, k=f(2k) □ If k≤0, k=f(−2k+1) § Thus f is bijective ○ Q is countable § There are “less” rational numbers q=m/n (m,n∈Z,n≠0) than § there are ordered pairs of integers (m,n) □ 1/2=15/30 but (1,2)≠(15,30) □ We can also ignore negatives and zeros □ because integers are in 1-1 correspondence with N § Idea: Write ordered pairs of integers in a 2 dimension array § Putting this all together, we have § Q={0,±1,±2,±1/2,±1/3,±3,±4,±3/2,±2/3,±1/4,…} Sequence • Definition ○ A sequence is a function defined on N ○ Notationally, this is often written {x_n } ○ Meaning f(x)=x_n for all n∈N • Example ○ {1/n}={1, 1/2,1/3,…} Theorem 2.8 • Statement ○ Every infinite subset of a countable set is countable • Proof ○ Suppose E⊂A, A is countable and E is infinite ○ Since A is countable, its element will be a sequqnce ○ (order given by the bijective function f:N→A) ○ So, A={x_n } as a set ○ Let n_1 be the smallest n∈N such that x_(n_1 )∈E ○ Let n_2 be the next smallest n∈N such that 〖x_n〗_2∈E ○ So E={x_(n_k ) }={x_(n_1 ),x_(n_2 ),x_(n_3 ),…} (A sequence indexed by k∈N) ○ Now consider g:N→E given by g(k)=x_(n_k ) ○ g is clearly one-to-one and onto by construction ○ So E is countable • Example ○ If A={1, 1/2,1/3,…} and E={1, 1/4,1/9,1/16} ○ Then A={1/n}={1, 1/2,1/3,…} ○ and E={1/n_k }={1, 1/4,1/9,1/16} where n_k=k^2 for k∈N ○ f:A→E by f(k)=1/k^2
