- #1

- 78

- 0

## 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([itex]g^{-1}[/itex])

Since [itex]g^{-1}[/itex](b_n)=x_n, then f([itex]g^{-1}[/itex])=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.