6.042J/18.062J 5. Sets and Relations

1 lec 3M.1 Albert R Meyer, February 16, 2010 Mathematics for Computer Science MIT 6.042J/18.062J Cardinality (the size of sets) lec 3M.2 Albert R Meyer, February 16, 2010 ≥ 1 arrow in surjective & function A B ≤ 1 arrow out lec 3M.3 Albert R Meyer, February 16, 2010 Mapping Rule (surj) Surjective function from A to B implies |A| ≥ |B| for finite A, B Feb. 17, 2009 lec 3M.4 Albert R Meyer, February 16, 2010 Mapping Rule archery proof: function: A→B implies |A| ≥ #arrows. surjection implies #arrows ≥|B|. lec 3M.8 Albert R Meyer, February 16, 2010 A B bijection archery exactly 1 arrow out exactly 1 arrow in Feb. 17, 2009 Copyright © Albert R. Meyer, 2009. All rights reserved. lec 3M.9 Albert R Meyer, February 16, 2010 Mapping Rule (bij) A bijection from A to B implies |A| = |B| 2 lec 3M.10 Albert R Meyer, February 16, 2010 Same Size Infinite Sets? {1, 2, 3, 4, …} and {0, 1, 2, 3, …} ↑↑ ↑↑ a bijection lec 3M.11 Albert R Meyer, February 16, 2010 Same Size Infinite Sets? {1, 2, 3, 4, …} and {0, 1, 2, 3, …} ↑↑ ↑↑ the “same size”! lec 3M.12 Albert R Meyer, February 16, 2010 size of the power set # subsets of a finite set A? |pow(A)| ? for A = {a, b, c}, pow(A) = { ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} } lec 3M.13 Albert R Meyer, February 16, 2010 pow(A) bijection to bit-strings A : {a0, a1, a2, a3, a4, … , an-1} string: 1 0 1 1 0 … 1 subset: {a0, a2, a3, … , an-1} this defines a bijection, so # n-bit strings = |pow(A)| lec 3M.14 Albert R Meyer, February 16, 2010 pow(A) bijection to bin-strings every computer scientist knows #n-bit strings, so Corollary: |pow(A)| = 2|A| lec 3M.15 Albert R Meyer, February 16, 2010 pow(N) bijection to 1 bit-strings infinite set N = {0,1,2,…} string: 1 0 1 1 0 1 … } subset: {0, 2, 3, , 5 … } a bijection from pow(N) to infinite bit-strings, {0,1}ω 3 lec 3M.16 Albert R Meyer, February 16, 2010 Team Problems Problems 1—4 MIT OpenCourseWare http://ocw.mit.edu 6.042J /18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.