25 Mar '07 15:188 edits

Sets A and B have the same cardinality if there is a

The cardinality of A is less than or equal to the cardinality of B if there is an

for instance, |{1,2,3}|=|{2,4,6}| using f(x)=2x. indeed, for finite sets cardinality is meerly the number of elements in a set. |{1,2,3}|=|{2,8,3}| using a rather artificial bijection.

for infinite sets this definition still holds, although it now becomes rather counter-intuitive. We can see that there exists a bijection between N, the natural numbers***, and 2N, the even numbers, which is meerly f(x)=2x. Therefore, |N|=|2N|.

* a function f is a bijection if there exists both an injection (see below) and a surjection between the sets x and f(x). a function f is said to be surjective if its values span its whole codomain (that is, for every y in the codomain, there is

** a function f is injective if f(a) = f(b) implies a = b (or a (does not equal) b implies f(a) (does not equal) f(b)), for any a, b in the domain.

***N=Natural numbers={0,1,2...} or {1,2,3...} depending on the definition. for our purposes here we can use either one arbitrarily.

****Z=the Integers={...-2,-1,0,1,2...}

*****Q=the Rational Numbers={a/b, a,b, contained in Z, b does not equal 0}

******R=the Rational Numbers=Q U {any number that cannot be written as a/b. for instance, Pi, e or sqrt(2)}

*bijection** f : A to B. In this case, write |A| = |B|.The cardinality of A is less than or equal to the cardinality of B if there is an

*injection*** f : A to B. (Write |A| (less than or equal to sign) |B|.)for instance, |{1,2,3}|=|{2,4,6}| using f(x)=2x. indeed, for finite sets cardinality is meerly the number of elements in a set. |{1,2,3}|=|{2,8,3}| using a rather artificial bijection.

for infinite sets this definition still holds, although it now becomes rather counter-intuitive. We can see that there exists a bijection between N, the natural numbers***, and 2N, the even numbers, which is meerly f(x)=2x. Therefore, |N|=|2N|.

**1:**easy warm-up question: does N have the same cardinality as Z, the set of integers****?**2:**hard question (hints can be given if needed): does N have the same cardinality as Q, the set of rational numbers*****?**3:**equally hard question: does N have the same cardinality as R, the set of real numbers******?**4:**Impossible To Answer question: If the answer to any of the above is no then does there exist a set A such that |N| (strictly less than) |A| (strictly less than) |S|, where S is the set where the answer was no...* a function f is a bijection if there exists both an injection (see below) and a surjection between the sets x and f(x). a function f is said to be surjective if its values span its whole codomain (that is, for every y in the codomain, there is

*at least*one x in the domain such that f(x) = y)** a function f is injective if f(a) = f(b) implies a = b (or a (does not equal) b implies f(a) (does not equal) f(b)), for any a, b in the domain.

***N=Natural numbers={0,1,2...} or {1,2,3...} depending on the definition. for our purposes here we can use either one arbitrarily.

****Z=the Integers={...-2,-1,0,1,2...}

*****Q=the Rational Numbers={a/b, a,b, contained in Z, b does not equal 0}

******R=the Rational Numbers=Q U {any number that cannot be written as a/b. for instance, Pi, e or sqrt(2)}