SP18:Lecture 8 Cardinality

From CS2800 wiki
Revision as of 15:17, 15 September 2018 by {{GENDER:Mdg39|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)


We proved some of the claims about inverses from the last lecture, and defined set cardinality relationships in terms of 'jectivity.


Inverses and 'jectivity

At the end of the last lecture, we made several claims about the relationship between inverses and 'jectivity:

In this lecture we prove one direction of these claims; the other directions are left for homework.

Function equality

Recall that the definition of left inverse states that two functions are equal:

Left inverse definition

Therefore, in order to prove that functions are left inverses of each other, we must have a definition of function equality:


Two functions [math]f [/math] and [math]g : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math] are equal (written [math]f = g [/math]) if they agree on every input. In other words, [math]f = g [/math] if, for all [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], [math]f(x) = g(x) [/math].

Proof outlines

We now proof that injections have left inverses and surjections have right inverses. The idea behind these proofs is that we do the best we can to construct an inverse.

Injections have left inverses

If [math]A \href{/cs2800/wiki/index.php/Equality_(sets)}{\neq} \href{/cs2800/wiki/index.php?title=%5Cemptyset&action=edit&redlink=1}{\emptyset} [/math] and [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math] is injective, then [math]f [/math] has a left inverse.
Proof: injections have left inverses
To demonstrate the technique of the proof, we start with an example.

Let [math]f := [/math] Fun-12-abc-1a2b.svg

We want to construct an inverse [math]g:\href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b,c\}} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} [/math] for [math]f [/math]; obviously such a function must map [math]a [/math] to 1 and [math]b [/math] to 2. We must also define [math]g(c) [/math] (so that [math]g [/math] is a function, i.e. total). So we'll just arbitrarily choose a value to map it to (say, 2).

So we have [math]g := [/math] Fun-abc-12-a1b2c2.svg

Then we plug [math]g [/math] into the definition of left inverse and we see that [math](g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f)(1) = 1 [/math] and [math](g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f)(2) = 2 [/math], so that [math]g [/math] is indeed a left inverse.

Note that this wouldn't work if [math]f [/math] was not injective. For example,

if [math]f := [/math] Fun-abc-12-a1b2c2.svg

then the [math]g [/math] we constructed would need to map [math]2 [/math] to both [math]b [/math] and [math]c [/math]; if we did both then [math]g [/math] would be ambiguous and thus not a function. If we chose one of the two (say [math]b [/math]), then [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f [/math] would give the wrong answer on the other ([math](g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f)(c) [/math] would be [math]b [/math], not [math]c [/math]).

Here is the general proof:

Choose an arbitrary [math]A \neq \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math], [math]B [/math], and an injection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]. We want to show that there exists a left inverse [math]g [/math] of [math]f [/math].

Let [math]x_0 [/math] be an element of [math]A [/math] (we know that such an element exists because [math]A \href{/cs2800/wiki/index.php/Equality_(sets)}{\neq} \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math]).

Let [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math] be given by

[math]g(y) := \left\{\begin{array}{ll} x & \text{if } \href{/cs2800/wiki/index.php/%E2%88%83}{∃x}\href{/cs2800/wiki/index.php/%E2%88%88}{∈}A \text{ such that } f(x) = y \\ x_0 & \text{otherwise} \\ \end{array}\right. [/math]

[math]g [/math] is well defined, because if [math]f(x_1) = y [/math] and [math]f(x_2) = y [/math] then [math]x_1 = x_2 [/math] (since [math]f [/math] is injective). Thus the output of [math]g [/math] is unambiguous.

To see that [math]g [/math] is a left inverse of [math]f [/math], choose an arbitrary [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math]; we have

[math]\begin{aligned} (g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f)(x) &= g(f(x)) && \text{by definition of }\circ \\ &= x && \text{by definition of }g \\ &= id(x) && \text{by definition of }id \\ \end{aligned} [/math]

so [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f \href{/cs2800/wiki/index.php/Equality_(functions)}{=} \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math], which is the

definition of a left inverse.

Surjections have right inverses

If [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math] is surjective, then [math]f [/math] has a right inverse.

To demonstrate the proof, we start with an example.

Let [math]f := [/math] Fun-abc-12-a1b2c2.svg

We want to construct an inverse [math]g:\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b,c\}} [/math] for [math]f [/math]; obviously such a function must map [math]1 [/math] to a, but we have a choice of where to map [math]2 [/math]. We can't map it to both [math]b [/math] and [math]c [/math] (because then [math]f [/math] would be ambiguous), but we can just pick one of them (say [math]b [/math]).

So we have [math]g := [/math] Fun-12-abc-1a2b.svg

Then we plug [math]g [/math] into the definition of right inverse and we see that [math](f \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g)(1) = 1 [/math] and [math](f \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g)(2) = 2 [/math], so that [math]g [/math] is indeed a right inverse.

Note that this wouldn't work if [math]f [/math] was not surjective, (for example, if [math]2 [/math] had no pre-image) we wouldn't have any output for [math]g(2) [/math] (so that [math]g [/math] wouldn't be total).

Here is the general proof:

Proof: surjections have right inverses
Choose an arbitrary [math]A \neq \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math], [math]B [/math], and a surjection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]. We want to show that there exists a right inverse [math]g [/math] of [math]f [/math].

Define [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math] on input [math]y [/math] as follows: we know that there exists at least one [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] with [math]f(x) = y [/math], since [math]f [/math] is surjective. Choose one of them and call it [math]g(y) [/math].

Note: it is not clear that there is an unambiguous way to do this; the assumption that it is possible is called the axiom of choice.

Now, we must check that [math]g [/math] is a right inverse of [math]f [/math], i.e. that [math]f \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g \href{/cs2800/wiki/index.php/Equality_(functions)}{=} \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math].

Choose an arbitrary [math]y \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math]. We have [math](f \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g)(y) = y [/math] by definition of [math]g [/math]. Therefore [math]f \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g \href{/cs2800/wiki/index.php/Equality_(functions)}{=} \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math]

as required.

Cardinality definitions

You may have noticed that in our examples of injections [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math], there are always at least as many elements in [math]B [/math] as there are in [math]A [/math]. Similarly, surjections always map to smaller sets, and bijections map to sets of the same size.

This insight lets us use functions to compare the sizes of sets in a way that applies to infinite sets as well as finite sets. We give some definitions here.

The cardinality of a set [math]A [/math] (written [math]|A| [/math]) is the size of the set. However, for the time being, we will not use this definition by itself. Doing so will encourage you to write proofs about cardinality that don't apply to infinite sets.

Instead, we will only define relationships between the cardinalities of sets; these definitions come from the intuitive relationship between sizes and 'jectivity described above.

Definition:
If [math]A [/math] and [math]B [/math] are sets, then [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |B| [/math] means that there exists an injection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]
Definition:
If [math]A [/math] and [math]B [/math] are sets, then [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A5}{≥} |B| [/math] means that there exists a surjection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]
If [math]A [/math] and [math]B [/math] are sets, then [math]|A| \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} |B| [/math] means that there exists a bijection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]

Cardinality properties

Note that it is dangerous to redefine symbols like ≤ and ≥! People expect that these relations work the same way they do for numbers, but it is not a-priori obvious that they do. For example, you might expect that



Luckily, these are all true (most will be proved on the homework), but it's important to note that they need to be proved!

The last of these claims is called the Cantor-Schroeder-Bernstein theorem; the proof is much more difficult than the others.