Set-Theoretic Operations • Set theoretic union ○ ⋃24_(n=1)^∞▒A_n =A_1∪A_2∪A_3∪⋯ • Set theoretic intersection ○ ⋂24_(n=1)^∞▒A_n =A_1∩A_2∩A_3∩⋯ • Indexing set ○ ⋃8_(α∈A)▒E_α , where ○ A is an indexing set ○ E_α is a specific set that depends on A • Example ○ Let A={x∈R0x≤1} ○ Let E_α={x∈R0xa} ○ Then⋃8_(α∈A)▒E_α =(0,1) and ⋂8_(α∈A)▒E_α =∅ Theorem 2.12 • Statement ○ Let {E_n }_(n∈N be a sequence of countable sets, then ○ S=⋃24_(n=1)^∞▒E_n is also countable • Proof ○ Just like the proof that Q is countable ○ E_n={〖x_n〗_k }={〖x_n〗_1,〖x_n〗_2,〖x_n〗_3,…} ○ ■(x_11&x_12&x_13&x_14&…&@x_21&x_22&x_23&⋱&&@x_31&x_32&⋱&&&@x_41&⋱&&&&@⋮&&&&&) ○ Go along the diagonal, we have ○ S={x_11,x_21,x_12,x_31,x_22,x_13…} • Corollary ○ Suppose A is at most countable ○ If for α∈A, B_α is at most countable, then ○ T=⋃8_(α∈A)▒B_α is also at most countable Theorem 2.13 • Statement ○ Let A be a countable set ○ Let B_n be the set of all n-tuples (a_1,a_2,…a_n ) where a_k∈A for 1≤k≤n ○ And a_k may not be distinct, then B_n is countable • Proof ○ We proof by induction on n ○ Base case: n=2 § ■((a_1,a_1 )&(a_1,a_2 )&(a_1,a_3 )&(a_1,a_4 )&…&@(a_2,a_1 )&(a_2,a_2 )&(a_2,a_3 )&⋱&&@(a_3,a_1 )&(a_3,a_2 )&⋱&&&@(a_4,a_1 )&⋱&&&&@⋮&&&&&) § Here a_i are all the elements of A with possible repetition ○ Now assume for n=m (m≥2) § The set of m-tuples (a_1,a_2,…a_m ) are countable § Now we treat the (m+1)\tuples as ordered pairs § (a_1,a_2,…a_(m+1) )=((a_1,a_2,…a_m ),a_(m+1) ) § By n=2 case, the set of (m+1)\tuples is still countable Theorem 2.14 • Statement ○ Let A be the set of all sequqnecse whose digits are 0 and 1 ○ Then A is uncountable • Proof: Cantor
