- #1

pc2-brazil

- 205

- 3

Good evening,

I was self-studying from a Discrete Mathematics book, and I ran across a question about infinite sets.

The exercise asked to show that a set S is infinite if and only if there is a proper subset A of S such that there is a one-to-one correspondence between A and S.

(Here, "one-to-one correspondence between A and S" refers to a function from A to S that is bijective, that is, both one-to-one (injective) and onto (surjective).)

After a little research, I thought of a way to do this proof, but I don't know if it is correct and consistent.

As it is an

The attempt is below:

I will try to show its contrapositive instead. I will try to show that: If a set S is

Suppose that a set S is finite and has

Suppose that S is an infinite set. Then, there is a proper subset A of S which is also infinite. As both A and S are infinite, A has no less elements than S does. It means that there will always be an element in A which can be mapped to a particular element in S (so that there is a one-to-one correspondence). This is different from the other situation (in which S and A are both finite), in which A had less elements than S.

Thank you in advance.

I was self-studying from a Discrete Mathematics book, and I ran across a question about infinite sets.

**Homework Statement**The exercise asked to show that a set S is infinite if and only if there is a proper subset A of S such that there is a one-to-one correspondence between A and S.

(Here, "one-to-one correspondence between A and S" refers to a function from A to S that is bijective, that is, both one-to-one (injective) and onto (surjective).)

**The attempt at a solution**After a little research, I thought of a way to do this proof, but I don't know if it is correct and consistent.

As it is an

**if and only if**proposition (*p*is true if and only if*q*is true), I have to proof both directions of the statement (that is, I have to show that*p*is true if*q*is true and that*q*is true if*p*is true). So, the solution has two parts.The attempt is below:

**Part 1**: A set S is infinite if there is a proper subset A of S such that there is a one-to-one correspondence between A and S.I will try to show its contrapositive instead. I will try to show that: If a set S is

**not**infinite (i.e., if S is finite), then there is**not**a proper subset A of S such that there is a one-to-one correspondence between A and S.Suppose that a set S is finite and has

*m*elements. A proper subset A of S, by definition, is a subset of S but is**not**equal to S. Then, it may not contain more than (*m*-1) elements (since the set S must contain at least 1 element that does not belong to its subset A). Therefore, there is not a one-to-one correspondence between A and S, because*m*-1 elements can't be mapped to*m*elements, as each element in a domain can't be mapped to more than one element in a codomain.**Part 2**: If a set S is infinite, then there is a proper subset A of S such that there is a one-to-one correspondence between A and S.Suppose that S is an infinite set. Then, there is a proper subset A of S which is also infinite. As both A and S are infinite, A has no less elements than S does. It means that there will always be an element in A which can be mapped to a particular element in S (so that there is a one-to-one correspondence). This is different from the other situation (in which S and A are both finite), in which A had less elements than S.

Thank you in advance.

Last edited: