# Thread: Proving one-to-one correspondence by Cardinality.

1. ## Proving one-to-one correspondence by Cardinality.

Hello everyone. At last I've reached the final question of my homework set, but I was kinda stuck as to how I can approach it. The question is as follows: Show that if a set S has cardinality m, where m is a positive integer, then there is a one-to-one correspondence between S and the set {1, 2, ..., m}.

For this one, I can see that the set {1, 2, ..., m} is just the set of all natural numbers, and thus has a cardinality of m. Since |S|=|{1, 2, ..., m}|, then they have to have
one-to-one correspondence. That's my reasoning for it. Does it look okay?

The second part of the question goes like this:Show that if S and T are two sets each with m elements, where m is a positive integer,then there is a one-to-one correspondence between S and T.

For this one, shouldn't I just have to let {1, 2, ..., m} be T? Not really sure as to how to approach the problem as I am new to Discrete Math. Anyways, thanks everyone for your help.

2. ## Re: Proving one-to-one correspondence by Cardinality.

Firstly the cardinal number is always positive so we need not specify it. secondly the question of correspondence to be one to one we need to know as to waht it is. it may be or may not be one to one. The cardinality of a set just indicates as to number of elements it has it mat not necessarily have natural numbers.

3. ## Re: Proving one-to-one correspondence by Cardinality.

Ya, I kinda figured that saying m is a positive integer contributes nothing to how the question develops, but I just copied it right out of the text because who knows, someone might be able to interpret it.

Anyways, as for the first question, do we really have to know what the specific elements S have? I was just wondering because it is said in the theorem that if two sets have the same cardinality, then it is absolutely necessary that there is a one-to-one correspondence between the sets. Since S has cardinality which is given as |S|= m, and we both know that the cardinality of the set of all the natural numbers is is equal to its last digit, which in this case is m. Then it should be true that |S|=|{1, 2, ..., m}|, and thus, from the theorem itself, it should be absolutely necessary that there is a one-to-one correspondence between S and the set {1, 2, ..., m}. Sorry if I have to restate my proof, I was just really convinced about it. But what do you think? Is there a better proof than this?

4. ## Re: Proving one-to-one correspondence by Cardinality.

Usually you need to specify a map.

The simplest map from S to the {1,..,m} set is a_i = b_i where a_i belongs to S, b_i belongs to {1,..,m} and i is an index. If you can show that an isomorphism exists then you've shown 1-1 ness between the sets.

So define a function taking a_i to b_i where f(a_i) = b_i and then show that an inverse exists where f^-1(b_i) = a_i for all appropriate i.

5. ## Re: Proving one-to-one correspondence by Cardinality.

Originally Posted by EliteAndoy
Show that if a set S has cardinality m, where m is a positive integer, then there is a one-to-one correspondence between S and the set {1, 2, ..., m}.
It is impossible to give an answer other than that this claim is obvious unless one knows how cardinality is defined in your course. It would also helpful to know the theorems that were proved, such as the "theorem that if two sets have the same cardinality, then it is absolutely necessary that there is a one-to-one correspondence between the sets".

You used three phrases:

(1) S has cardinality m
(2) |S| = m
(3) S has m elements.

Do they all mean the same by definition?

Originally Posted by ibdutt
Firstly the cardinal number is always positive
Really?

6. ## Re: Proving one-to-one correspondence by Cardinality.

Well, my professor didn't really gone over the class as to how the theorem is proved but he said that "if two sets have one-to-one correspondence between them, they should have the same cardinality" and he goes on to say that it it goes the other way around that "if two sets have the same cardinality then they must have a one-to-one correspondence." I just took his word for it as the basis of my proof. The thing that really throws me off is it is not really specified as to what composes set S. So here's how my phrases goes:

(1)|S|=m
(2) |{1, 2, ..., m}|=m
(3)|S|=|{1, 2, ..., m}|
(4) There is a one-to-one correspondence between them

But that proof is not valid at all it "if two sets have the same cardinality then they must have a one-to-one correspondence" is not true. Kinda hanging by a thread here, so how would you guys prove this question? Thanks by the way.

7. ## Re: Proving one-to-one correspondence by Cardinality.

EliteAndoy: Did you try showing that a simple map and its inverse exists between the two sets?

8. ## Re: Proving one-to-one correspondence by Cardinality.

Originally Posted by EliteAndoy
Well, my professor didn't really gone over the class as to how the theorem is proved but he said that "if two sets have one-to-one correspondence between them, they should have the same cardinality" and he goes on to say that it it goes the other way around that "if two sets have the same cardinality then they must have a one-to-one correspondence." I just took his word for it as the basis of my proof.
You still have not said how cardinality is defined in your course and whether the phrases "S has cardinality m", "|S| = m" and "S has m elements" all mean the same thing.

If you forget all technical stuff and could learn just one thing, which will be helpful in all areas of life, from this and other math courses, it's this: it does not make sense to prove something until you know exactly what you are proving. This means you have to know definitions of every term involved in the claim to be proved.

Originally Posted by EliteAndoy
Show that if a set S has cardinality m, where m is a positive integer, then there is a one-to-one correspondence between S and the set {1, 2, ..., m}.
I am saying this because the most reasonable (for me) definition for the phrase that occurs in the premise of your claim: "a set S has cardinality m", means by definition that there is a one-to-one correspondence between S and {1, 2, ..., m}. Then the claim is a tautology, like "empty set does not have any elements". If your definition is different, then there is no sense in attempting a proof until you find out that definition. For example, without the definition, how do you justify that "|{1, 2, ..., m}| = m"?

Originally Posted by EliteAndoy
Well, my professor didn't really gone over the class as to how the theorem is proved but he said that "if two sets have one-to-one correspondence between them, they should have the same cardinality" and he goes on to say that it it goes the other way around that "if two sets have the same cardinality then they must have a one-to-one correspondence."
Often this is given not as a theorem, but as a definition.

Originally Posted by EliteAndoy
But that proof is not valid at all it "if two sets have the same cardinality then they must have a one-to-one correspondence" is not true.
What makes you say it is not true, especially since you said above that you took your professor's word for it?

9. ## Re: Proving one-to-one correspondence by Cardinality.

Yeah I kinda of did what you told me earlier, and made a piece wise function f(x)=1 if f:x=a_1,f(x)=2x if f:x=a_2i+1, f(x)=2x+1 if f:x=a_2x. This basically says that 1 is mapped to a_1, the even numbers are mapped to the elements of S with odd numbered indexes, and the odd numbers are mapped to the elements of S with even numbered indexes. Thus, everything should be mapped and must have one-to-one correspondence. I'm still trying to show their inverses but eventually ill get there.

10. ## Re: Proving one-to-one correspondence by Cardinality.

First off, thanks everyone for the replies, I really appreciate it. Anyways, if you were asking if "S has cardinality m", "|S| = m" and "S has m elements" all mean the same thing in our course, then yes it does. As for the claim, It's kinda obvious that |S|=|{1, 2, ..., m}|, but I can't really just say that it's obvious in this homework, can I? Plus I'm asked to show their one-to-one correspondence and so I'm just using those terms as a tool to resort to the "definition" of cardinality. I'm not saying that the definition is not true, I'm just saying that if it is untrue then my whole argument is also untrue.

11. ## Re: Proving one-to-one correspondence by Cardinality.

Originally Posted by emakarov
You still have not said how cardinality is defined in your course and whether the phrases "S has cardinality m", "|S| = m" and "S has m elements" all mean the same thing.
Often this is given not as a theorem, but as a definition. What makes you say it is not true, especially since you said above that you took your professor's word for it?

Originally Posted by EliteAndoy
First off, thanks everyone for the replies, I really appreciate it. Anyways, if you were asking if "S has cardinality m", "|S| = m" and "S has m elements" all mean the same thing in our course, then yes it does. As for the claim, It's kinda obvious that |S|=|{1, 2, ..., m}|, but I can't really just say that it's obvious in this homework, can I? Plus I'm asked to show their one-to-one correspondence and so I'm just using those terms as a tool to resort to the "definition" of cardinality. I'm not saying that the definition is not true, I'm just saying that if it is untrue then my whole argument is also untrue.
@EliteAndoy, I actually feel sorry for the situation you find your self in. I realize that you are in a discrete mathematics class, and it is well known that that can mean many different things. It seems to me that you may have an instructor problem or you have not understood the material on sets and mappings.

Did you read carefully emakarov reply and request? You must have been given an exact definition for finite sets (that seems to be what you are posting about.) Usually there are two ways this is done. Both come down to this: If $k\in\mathbb{Z}^+$ define $\mathcal{N}_k=\{1,2,\cdots,k\}$.
Now define a finite set: The set $A$ is finite if $A=\emptyset\text{ or }A \sim \mathcal{N}_j$ for some $j\in\mathbb{Z}^+$. That is $A$ is finite if and only if it is empty in which case $|A|=0$ or there is a bijection $A \leftrightarrow {\mathcal{N}_j}$ in which case $|A|=j$.

So it seems to me that you have been asked to show what actually should have been the result of definitions.

I will give two quotes.
Paul Helmos writes
We know quite a bit about cardinal numbers by now, but we still do not what they are.
Speaking vaguely, we say that the cardinal number of a set is the property that a set has
in common with all sets equivalent to it.
Peter Zehna writes:
Cardinal Axiom: For each set $A$, there is a primitive notation called the cardinal number of $A$, denoted by $|A|$, with the property that:
$|A|=|B|\text{ if and only if }A\sim B~.$

12. ## Re: Proving one-to-one correspondence by Cardinality.

Thanks everyone for all the help, especially to Plato. That definition of finite set really helped me understand how to approach the problem. Anyways all I have to do was make a distinct mapping to show that it was one-to-one. My prof even said that saying a_i maps to b_i is good enough as an answer. I guess I was just over thinking things . Anyways, thanks again!

13. ## Re: Proving one-to-one correspondence by Cardinality.

If one has (and whether or not you CAN assume this, is to me, unknown):

$S = \{s_1,s_2,\dots,s_m\}$,

then the mapping $f:S \to \{1,2,\dots,m\}$ given by $f(s_i) = i$ is a bijection, since we have the inverse map $g:\{1,2,\dots,m\} \to S$ given by $g(i) = s_i$:

$f \circ g(i) = f(g(i)) = f(s_i) = i$ so that $f \circ g = \mathbf{1}_{\{1,2,\dots,m\}}$ and

$g \circ f(s_i) = g(f(s_i)) = g(i) = s_i$ so that $g \circ f = \mathbf{1}_S$

Alternatively, both sets are indexed by the same set, namely {1,2,...,m} (the second set is indexed by itself, a rather strange set of affairs, but as we see, quite possible).

The "sticking point" here, is what your course DEFINES a "finite set (of k elements)" to BE. If your definition is as Plato suggests, there is no need to prove anything, the bijection comes "built-in" with the definition.