MHB If S has the same number of elements as T, then T has the same number as S....

[VoNemo19]

Hi. The proof that I'm working is in the title. The Defition of "same number as" is given as follows: (1)Two sets S and T are said to have the same nuber of elements if each element of S can be paired with precisely one element ofT in such a way that every element ofT is paired with precisely one element of S.

Notation: If \pi is a pairing of the elements of Swith with those of Tand the element sof S is paired in \pi to the element tof T, we shall write s\overbrace{\leftrightarrow}^{\pi}{t} (I don't know how to put the \pi above the \leftrightarrow without the \overbrace).
I don't really understand the book's proof: Since S has the same number of elements as T, we can select a pairing between the elements of Sand T in accordance with (1).We define a pairing as follows: Ifs is paired with t by the selected pairing \pi, then pairt with s. That is if s\overbrace{\leftrightarrow}^{\pi}{t}, thent is paired with s to form the pairing of the elements T with those of S. If the original pairing satisfied (1),then so will the new pairing. Specifically, since\pihad each elementT paired with a unique element of S, then the second pairing also has this property. Therefore, T has the same number of elements asS.

Please help me to understand why this proposition is not trivial, and also the procedure of the proof.

 

[Evgeny.Makarov]

(I don't know how to put the \pi above the \leftrightarrow without the \overbrace).

\stackrel{\pi}{\leftrightarrow} or \overset{\pi}{\leftrightarrow} gives $\overset{\pi}{\leftrightarrow}$.

Please help me to understand why this proposition is not trivial

It is trivial to people because we have a great deal of intuition concerning the number of elements in a set and one-to-one correspondences between sets. Some of these intuitions probably come from visual images. If one has to construct a formal proof, for example, in order to convince a computer, which does not have these intuitions, then the task becomes more challenging.

For example, it is an obvious corollary of the pigeonhole principle that if f : {1, ..., m} -> {1, ..., n} and m > n, then there exist i1 and i2 such that 1 ≤ i1 < i2 ≤ m and f(i1) = f(i2). But if we have a formal proof of this fact, we can do more. We can mechanically extract a program that, given f, would compute such i1 and i2. Writing such program from scratch, though not hard, does not seem so trivial, especially if we are not allowed to use arrays. This implies to me that in considering the original fact obvious, we are cheating and coming up with some arguments that are different from a formal mathematical proof.

This problem is still simple enough, and it means that we are expected to provide a rather detailed proof.

Two sets S and T are said to have the same nuber of elements if each element of S can be paired with precisely one element ofT

This just means that there exists a function $\pi:S\to T$...

in such a way that every element ofT is paired with precisely one element of S.

Formally, this means

$\forall y\in T\,\exists! x\in S\,\pi(x)=y~(1)$

Here $\exists!x$ means that there exists a unique x. If, given y, we denote the x whose existence is guaranteed in (1) by $\pi'(y)$, then (1) expresses the following two facts.

$\forall y\in T\, \pi(\pi'(y))=y~(2)$
$\forall y\in T\,\forall x'\in S.\,\pi x'=y\to x'=\pi'(y)~(3)$

Now we need to show that $\pi'$ establishes a pairing that shows that T has the same number of elements as S. We already have that $\pi'$ is a function from T to S, so we need to check

$\forall x\in S\,\exists! y\in T\,\pi'(y)=x~(4)$

Of course, given x, we let $y = \pi(x)$. Now the unique existential quantifier results in the following two facts to prove.

$\forall x\in S\,\pi'(\pi(x))=x~(5)$
$\forall x\in S\,\forall y'\in T.\,\pi'(y')=x\to y'=\pi(x)~(6)$

Hmm, the first attempt to prove (5) would be to use (2), but it has functions in the wrong order. It does not seem so trivial now, does it? Hint: (5) is proved using (3) and (6) is proved using (2).