**scientia** Thanks for your post, scientia. I am not as much familiar with the various kinds of mappings as you are. As you probably have observed, I do not use mappings in my proof, I simply use the fact that if A is a subset of B and B is a subset of A then A and B are identical.

I'll see if I can squeeze my brain into solving one of your exercises.

]]>Your problem is a consequence of two problems I set in my exercises thread about a mappings: http://www.mathisfunforum.com/viewtopic.php?id=18790:

Let

AandBbe finite sets withmandnelements respectively, and suppose :A→Bis a mapping. If is injective (one-to-one), thenm≤n. Let

AandBbe finite sets withmandnelements respectively, and suppose :A→Bis a mapping. If is surjective (onto), thenm≥n.

Normally to prove that a mapping is bijective, you have to show that it is both injective and surjective. However, if *A* and *B* are finite sets with the same number of elements (i.e. *m* = *n*) then the two statements above imply that will be bijective if we can show that it is EITHER injective OR surjective (so we don't have to waste them showing both).

In particular, if *A* = *B*, we have exactly the same problem as the theorem you are discussing here. This is because in this case is a mapping from *A* to itself and so (i) if is injective, *A* is a subset of *B* (ii) if is surjective, *B* is a subset of *A*.

PS: No-one has had a go at my exercises yet.

]]>Welcome to the forum.

]]>Theorem: If two finite sets have the same number of elements and one set is a subset of the other, the two sets are equal.

Proof: We name the sets A and B, and let A be the subset. We argue by contradiction: We assume that the theorem is false, meaning that A and B are not equal. Since A is a subset of B, there must be an element of B which is not in A because otherwise A and B would be equal. Since B contains A and an element that does not exist in A, the number of elements of B ≥ the number of elements of A + 1. However, this is against the requirement that the number of elements of B = number of elements of A. We have thus arrived at a contradiction and have proved the theorem.

This theorem has some practical benefit. Suppose, for example, that you are considering two lists of file names. They are sorted differently, and you suspect them to contain the same elements. To see that the lists have the same lengths is often easy. To compare them, if the lists have e.g. 3 elements, glancing back and forth between them a few times should be sufficient, but if the lists have 5-6 elements or more, this eye method becomes unreliable and a more systematic method, like one of the two methods indicated above, must be used. However, both of these methods have the weakness that to compare the two lists element by element is often a complicated, tedious, and time-consuming task. It is the amount of time spent comparing the lists that you can use the theorem to reduce.

]]>