# Homework Help: Showing the cardinality of A is less than B's

1. Mar 4, 2012

### k3k3

1. The problem statement, all variables and given/known data
If A and B are sets we say that |A|≤|B| if and only if there exists a one-to-one function f:A→B.

Prove that if A and B are sets such that A$\subseteq$B , then |A|≤|B|.

2. Relevant equations
Our text does not define this, so the definition comes from my class notes.

Definition: Suppose A and B are sets.
Then |A|≤|B| iff there exists a 1-1 function from A to B.
Note: Such an an f, if it exists, may or may not be onto. If f is also onto, then |A|=|B|

3. The attempt at a solution

Since A$\subseteq$B, then either A is B or all of A is in B.

Hence, there exists an injection f such that f:A→B defined by f(a)=a for all a in A.
Since f is not a onto B, then |A| < |B|

If f is a bijection, then, by definition, it follows that |A|=|B|.

Does this proof make sense?

2. Mar 4, 2012

### Dick

Just because f is not onto does not imply that |A|<|B|. That's only true for finite sets. Can you give me a counterexample?

3. Mar 4, 2012

### k3k3

|N| < |R| and there is not an onto mapping of N to R

4. Mar 4, 2012

### Dick

That's not a counterexample. I want an example where f is not onto but |A|=|B|.

5. Mar 4, 2012

### k3k3

I am unsure of an example of that. For infinite sets, all I know is either it will be the same as |N| else it will be what |R| is.

6. Mar 4, 2012

### Dick

How about A=even integers, B=all integers? Have you looked at cases like that?

7. Mar 4, 2012

### k3k3

If f is a function that takes all integers to even integers, f can be defined as f(n)=2n for all n in the integers. That is onto.

8. Mar 4, 2012

### Dick

That function would show |A|=|B|. But the function you are using in your proof is f(n)=n. That's is not onto. What I'm trying to point out the that f(n)=n not being onto does not show |A|<|B| which you are saying in your proof.

9. Mar 4, 2012

### k3k3

I see. Then if for all a in A there exists a b in B such that f(a)=b and if A is countable and B is not, f is not onto and |A| < |B|. If A is a countable subset of B, then |A| = |B|.

Is this correct thinking?

10. Mar 4, 2012

### Dick

Pretty much. But that's not something you need to include in your proof. You defined a 1-1 function from A to B by defining f(a)=a. By your definition that shows |A|≤|B|. That's about all you need to say.

11. Mar 4, 2012

### k3k3

I see. Thank you for the help!