Showing the cardinality of A is less than B's

[k3k3]

Homework Statement

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\subseteqB , then |A|≤|B|.

Homework 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|

The Attempt at a Solution

Since A\subseteqB, 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?

 

[Dick]

Homework Statement

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\subseteqB , then |A|≤|B|.

Homework 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|

The Attempt at a Solution

Since A\subseteqB, 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?

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?

 

[k3k3]

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

 

[Dick]

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

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

 

[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.

 

[Dick]

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.

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

 

[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.

 

[Dick]

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.

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.

 

[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?

 

[Dick]

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?

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.

 

[k3k3]

I see. Thank you for the help!