# cardinals of finite sets

• Dec 7th 2013, 08:08 AM
nerazzurri10
cardinals of finite sets
Hello,

I have the following question:
Prove that a set A has the same cardinality of a subset of a Set B, if and only if exists an injective function A to B.

I find it hard to prove it because I can easily find a set A which is:

A={1,2}
B={1,2,3,4}
C={1,2,3}

C is a subset of B. C's cardinality is bigger than A's.

There is an injective function from A to B, of course.

where am I wrong?

Thank you!
• Dec 7th 2013, 08:32 AM
Hartlw
Re: cardinals of finite sets
A and B have the same cardinality if there is a 1-1 mapping of A onto B (bijective).

If there is a 1-1 mapping of A onto a subset of B (the same cardinality), there exists a 1-1 mapping into B (injective).
If there is an injective mapping into a subset of B, The mapping is onto that subset from A, and A and that subset have the same cardinaity.
• Dec 7th 2013, 08:56 AM
emakarov
Re: cardinals of finite sets
Quote:

Originally Posted by nerazzurri10
Prove that a set A has the same cardinality of a subset of a Set B, if and only if exists an injective function A to B.

I find it hard to prove it because I can easily find a set A which is:

A={1,2}
B={1,2,3,4}
C={1,2,3}

C is a subset of B. C's cardinality is bigger than A's.

There is an injective function from A to B, of course.

where am I wrong?

If there is an injective function from A to B, it means that A has the same cardinality as some subset of B, not every subset of B. So, C may have a greater cardinality than A's, but there is another subset of B that has the same cardinality as A's.
• Dec 7th 2013, 08:57 AM
Plato
Re: cardinals of finite sets
Quote:

Originally Posted by nerazzurri10
I have the following question:
Prove that a set A has the same cardinality of a subset of a Set B, if and only if exists an injective function A to B.

Let's first agree on notation and definitions. By $\displaystyle \|A\|$ I mean the cardinality of the set $\displaystyle A.$ .
Then $\displaystyle \|A\|=\|B\|\text{ if and only if }A\overset{f} \leftrightarrow B$, i.e. $\displaystyle f$ is a bijection.

To start suppose that there is an injection $\displaystyle \phi : A\to B$ then clearly $\displaystyle \phi(A)\subseteq B.$
Prove that $\displaystyle A\overset{\phi} \leftrightarrow \phi(A)$.

For the converse, assume that $\displaystyle (\exists C\subseteq B)[A\overset{\rho} \leftrightarrow C]$ where $\displaystyle \rho$ is a bijection.