Tell me more ×

I'm confused. Two finite sets (call them A = [a, b] and C = [c, d]) are equivalent if there exists a 1-1 bijection from A to C. But the bijection exists iff A has the same number of elements as C.

So am I correct in saying that two finite sets can't be equivalent unless they have the same number of elements?

I've been asked this: Let a < b and c < d. Show [a, b] is equivalent to [c, d].

share|improve this question
You have probably bean asked to prove that real intervals $[a,b]$ and $[c,d]$ are equivalent. The set consisting of two elements $a$ and $b$ is denoted $\{a, b\}$ not $[a,b]$ – Levon Haykazyan Sep 27 '11 at 20:36
Yes, for finite sets, equivalence is essentially "how many elements does it have?" But for infinite sets, it's a bit more interesting. Here, $[a,b]$ is the set of all real numbers $x$ such that $a\leq x\leq b$; and $[c,d]$ is the set of all real numbers $y$ with $c\leq y\leq d$. You want to establish that these two have the same number elements. As a hint, consider this previous question – Arturo Magidin Sep 27 '11 at 20:38
Ah okay, thanks! – user16794 Sep 27 '11 at 20:38
@chrislegend: No, $[0,10]$, as it happens, has "the same number" of elements as $[0,100]$; where "same number" means "there is a bijection between them". Infinity can be counterintuitive at first (one tends to develop a bit of intuition for it with practice)! That's the point of this exercise. – Arturo Magidin Sep 27 '11 at 20:46

1 Answer

up vote 2 down vote accepted

We will construct the desired bijection geometrically, in steps.

(i) The function $f$ defined by $f(x)=x-a$ is a bijection from $[a,b]$ to $[0,b-a]$. This function $f$ is called a translation. (It translates, meaning shifts, everything over by an amount $-a$.)

(ii) We now map the interval $[0,b-a]$ bijectively to $[0, d-c]$. This can be done by scaling by the factor $\frac{d-c}{b-a}$ , that is, by applying the function $g$, where $g(x)=\frac{d-c}{b-a}x$.

(iii) After we have applied the transformation (i) and then (ii), the interval $[a,b]$ is mapped to the interval $[0,d-c]$. Now let $h(x)=x+c$. The translation $h$ maps $[0,d-c]$ bijectvely to $[c,d]$.

Finally, let $W(x)= h(g(f(x)))$. Then $W$ maps $[a,b]$ bijectively to $[c,d]$.

share|improve this answer
For discovery purposes, I like to do this by mapping $[a,b]$ to $[0,1]$, followed by mapping $[0,1]$ to $[c,d]$. That is, form the composition of the following maps: $[a,b] \rightarrow [0,b-a]$ (subtract $a$), $[0,b-a] \rightarrow [0,1]$ (divide by $b-a$), $[0,1] \rightarrow [0,d-c]$ (multiply by $d-c$), $[0,d-c] \rightarrow [c,d]$ (add $c$). – Dave L. Renfro Sep 27 '11 at 21:34
@Dave L. Renfro: Your view is an improvement, doing an intermediate mapping to a standard interval is pedagogically better. I wanted to draw the picture that goes with my answer, for the case the intervals are of different length say. That would have made a good complete answer. – André Nicolas Sep 27 '11 at 21:52
Last night looked at some notes I wrote in the early 1980s, where I came up with the idea of using $[0,1]$ as a "navigation hub" (and I'm sure many hundreds of others have also come up with this idea), and the actual idea was slightly better than what I gave here: Map $[a,b]$ to $[0,1],$ change letters to get a mapping from $[c,d]$ to $[0,1],$ and then travel forwards along the first map followed by backwards along the second map. (It was in a real analysis class and I had to show that the normed Lebesgue spaces $L[a,b]$ and $L[c,d]$ were linearly isometric.) – Dave L. Renfro Sep 28 '11 at 18:43
It is a clear and useful way to see things, a mixture of geometric and kinematic/kinesthetic. Beside pictures in the head, sometimes mathematics involves feeling things slotting into place, more muscular action than pattern. – André Nicolas Sep 28 '11 at 19:38

Your Answer

