MACM 101 Lecture 17: Lecture 17 Part 1_ Cardinality

• School: Simon Fraser University
• Department: Math & Comp Sci
• Course: MACM 101
• Professor: Andrei Bulatov

Document Summary

A function f is said to be one-to-one, or injective, if and only if f(a) = f(b) implies a = b. A function f from a to b is called onto, or surjective, if and only if for every element b . B there is an element a a with f(a) = b. A function is called a surjection if it is onto. A function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. Easy for finite sets, just count the elements. Sets a and b (finite or infinite) have the same cardinality if and only if there is a bijection from a to b. The function f: n 2n, where f(x) = 2x, is a bijection. We say that | a | | b | if there is an injective function from a to b. The function f(x) = x is an injective function from 2n to n. therefore |2n| |n|