Showing infinite sets are countable using a proper subset

[k3k3]

Homework Statement

Show if a set is infinite, then it can be put in a 1-1 correspondence with one of its proper subsets.

Homework Equations

This was included with the problem, but I am sure most already know this.

A is a proper subset of B if A is a subset of B and A≠B

The Attempt at a Solution

Did I do this correctly? Here is my work:


Showing the forward implication first:

Show if a set is infinite, then it can be put in a 1-1 correspondence with one of its proper subsets.


Let A be an infinite set.
Let B be an infinite set that is a proper subset of A.

Since A is infinite, there exists a bijective mapping f:X→A, where X is either the set of natural numbers or real numbers depending if the sets are countable or not, be defined by f(x_n)=a_n where x_n is in X and a_n is in A.

Similarly for B, there exists a bijective mapping g:X→B be defined by g(x_n)=b_n where x_n is in X and b_n is in B.

Since g is a bijection, its inverse exists and is a bijection.

Let h=f($g^{-1}$)

Since $g^{-1}$(b_n)=x_n, then f($g^{-1}$)=a_n

Therefore if a set is infinite, it can be put into a 1-1 correspondence with one of its proper subsets.

Reverse implication:

If a set can be put into a 1-1 correspondence with one of its proper subsets, then it is infinite.

Suppose a finite set can be put into a 1-1 correspondence with one of its proper subsets.

Let A={a,b,c,d}
Let B={c,d}

Let f:B→A
Where f(c)=a and f(d)=b

It is a 1-1 function, but not onto.

Therefore, if a a set can be put into a 1-1 correspondence with one of its proper subsets, it must be infinite.

 

[SteveL27]

Homework Statement

Show if a set is infinite, then it can be put in a 1-1 correspondence with one of its proper subsets.

What's your definition of an infinite set? Reason I ask is that the property you're trying to prove is very often taken as the definition of an infinite set. So if you're using some other definition, it will be helpful to state it.

 

[k3k3]

What's your definition of an infinite set? Reason I ask is that the property you're trying to prove is very often taken as the definition of an infinite set. So if you're using some other definition, it will be helpful to state it.

The book defines an infinite set as:

Let A be an arbitrary set.
The set A is finite if it is empty or if its elements can be put in a 1-1 correspondence with the natural numbers.

The set A is infinite if it is not finite.

I included the finite definition too since the infinite definition is not very descriptive.

 

[SteveL27]

The book defines an infinite set as:

Let A be an arbitrary set.
The set A is finite if it is empty or if its elements can be put in a 1-1 correspondence with the natural numbers.

How can a finite set be put into 1-1 correspondence with the natural numbers? Are you sure you wrote that down correctly?

 

[k3k3]

How can a finite set be put into 1-1 correspondence with the natural numbers? Are you sure you wrote that down correctly?

Sorry, with a finite subset of natural nunbers I meant to write. That was not typed properly.

 

[SteveL27]

Sorry, with a finite subset of natural nunbers I meant to write. That was not typed properly.

Well, what's a finite subset? Isn't that the word we're trying to define?

Don't mean to be picking at you with details ... but the overall steps here are going to involve

1) Nailing down the definition of "infinite set."

2) USING that definition to prove what's required.

So we're stuck on step 1 here.

 

[k3k3]

Well, what's a finite subset? Isn't that the word we're trying to define?

Don't mean to be picking at you with details ... but the overall steps here are going to involve

1) Nailing down the definition of "infinite set."

2) USING that definition to prove what's required.

So we're stuck on step 1 here.

If it is finite, it can be put into a 1-1 correspondence with the set {1,2,3,...,n} for some positive integer n

 

[SteveL27]

If it is finite, it can be put into a 1-1 correspondence with the set {1,2,3,...,n} for some positive integer n

Ok!

Now, can you redo your proof, using that definition?

 

[k3k3]

Ok!

Now, can you redo your proof, using that definition?

Is this supposed to be a contradiction proof? If I am showing that a set is infinite if one of its proper subsets are infinite, then there cannot be a 1-1 correspondence from either of the sets to any set {1,2,3,...n} for some positive integer n.

 

[SteveL27]

Is this supposed to be a contradiction proof? If I am showing that a set is infinite if one of its proper subsets are infinite, then there cannot be a 1-1 correspondence from either of the sets to any set {1,2,3,...n} for some positive integer n.

Helpful to go directly back to what's required by the problem. You started out " If I am showing that a set is infinite if one of its proper subsets are infinite ..." which is a little confusing.

By the way, what class is this for? The fact that these two definitions are equivalent is non-trivial and involves some set-theoretical subtleties. However you're only being asked here to prove one direction, so perhaps that's more straightforward.

 

[k3k3]

Helpful to go directly back to what's required by the problem. You started out " If I am showing that a set is infinite if one of its proper subsets are infinite ..." which is a little confusing.

By the way, what class is this for? The fact that these two definitions are equivalent is non-trivial and involves some set-theoretical subtleties. However you're only being asked here to prove one direction, so perhaps that's more straightforward.

It's for a real analysis class. It is a if and only if problem, but I found the forward implication to be difficult. I should have paid attention to what I was typing instead of just transcribing everything I wrote on my paper and not include the reverse.

Here is the question verbatim from the book: Prove that a set is infinite if and only if it can be put into a 1-1 correspondence with one of its proper subsets. (A set A is a proper subset of B if A$\subseteq$B and A≠B)

 

[SteveL27]

It's for a real analysis class. It is a if and only if problem, but I found the forward implication to be difficult. I should have paid attention to what I was typing instead of just transcribing everything I wrote on my paper and not include the reverse.

Here is the question verbatim from the book: Prove that a set is infinite if and only if it can be put into a 1-1 correspondence with one of its proper subsets. (A set A is a proper subset of B if A$\subseteq$B and A≠B)

I don't have time to work this out at the moment ... but here's a link showing why this is a harder problem than it looks. The link doesn't have a proof or even a hint, just some interesting context for the question.

http://en.wikipedia.org/wiki/Dedekind-infinite_set

Try posting what you've got so far and perhaps others can jump in.