|
|
| Line 1: |
Line 1: |
| − | ==Infinite Sets and Cardinality== | + | == Licensing == |
| − | '''The Size of a Finite Set'''
| + | Content obtained and/or adapted from: |
| − | | + | * [https://en.wikipedia.org/wiki/Cardinality Cardinality, Wikipedia] under a CC BY-SA license |
| − | When deciding how large finite sets are, we generally count the number of elements in the set, and say two sets are the same size if they have the same number of elements. This approach doesn't work too well if the sets are infinite, however, because we can't count the number of elements in an infinite set.
| |
| − | | |
| − | However, there is another way to define when two sets have the same size that works equally well for finite and infinite sets. We say that two sets <math>A</math> and <math>B</math> have the same size if we can define a function <math>f: A\to B</math> which satisfies the following properties:
| |
| − | | |
| − | *<math>f(a)</math> is defined for every <math>a\in A</math>.
| |
| − | *<math>\forall b\in B</math>, <math>\exists a\in A</math> such that <math> f(a)=b</math>. We say that f is ''onto'' or ''surjective''.
| |
| − | *<math>\forall a_1, a_2\in A</math>, <math>f(a_1)=f(a_2) \implies a_1=a_2</math>. We say that f is ''one-to-one'' or ''injective''.
| |
| − | | |
| − | Functions which satisfy these properties are called ''bijections''.
| |
| − | | |
| − | '''Examples'''
| |
| − | | |
| − | The sets <math>\{1,2,3\}</math> and <math>\{4,5,6\}</math> both have three elements. We can define a bijection between them like this: <math>f(1)=6, f(2)=4, f(3)=5</math>.
| |
| − | | |
| − | The set of all positive integers, <math>\{1,2,3,...\}</math> is the same size as the set of nonnegative integers, <math>\{0,1,2,...\}</math>. Let <math>f(1)=0, f(2)=1</math>, and more generally <math>f(n)=n-1</math>.
| |
| − | | |
| − | '''Exercise'''
| |
| − | | |
| − | Prove that the above function is a bijection.
| |
| − | | |
| − | Often it is difficult to construct an explicit bijection between two sets of the same cardinality, so the following theorem can come in handy:
| |
| − | | |
| − | '''Cantor-Schroeder-Bernstein Theorem'''
| |
| − | | |
| − | If <math>A</math> and <math>B</math> are two sets and there exist injective functions <math>f:A\to B</math> and <math>g:B\to A</math>, then there exists a bijection between <math>A</math> and <math>B</math>.
| |
| − | | |
| − | ==Resources==
| |
| − | * [https://mathstats.uncg.edu/sites/pauli/112/HTML/section-39.html Definition of Cardinality], Ancient and Contemporary Mathematics (Sebastian Pauli) | |
