Proof concerning infinite sets

[pc2-brazil]

Good evening,

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.

 

[Dick]

That's a good try. Part 1 looks ok. But saying "As both A and S are infinite, A has no less elements than S does." is a very naive statement when you are talking about infinite sets. Do you know the Cantor diagonal argument? Do you know the set of all subsets of the integers has more elements than the integers even though both are infinite? I'd look that up and then rethink Part 2. You need to be more specific about the subset you are thinking of. You might also want to look up the DEFINITION of 'infinite'.

 

[pc2-brazil]

That's a good try. Part 1 looks ok. But saying "As both A and S are infinite, A has no less elements than S does." is a very naive statement when you are talking about infinite sets. Do you know the Cantor diagonal argument? Do you know the set of all subsets of the integers has more elements than the integers even though both are infinite? I'd look that up and then rethink Part 2. You need to be more specific about the subset you are thinking of. You might also want to look up the DEFINITION of 'infinite'.

Thank you for your response.
The following section of the book I'm using talks about Cantor's diagonal argument. I will get to it soon, and, when I do, I will try to rethink Part 2.

 

[HallsofIvy]

What, exactly, is your definition of "infinite" set?

 

[pc2-brazil]

What, exactly, is your definition of "infinite" set?

I haven't read much yet about infinite sets, so I can't give any formal definition. But I'm inclined to think that an infinite set is a set where one can never end enumerating different elements; for example, the set of integers and the set of real numbers. I also think that the difference between the set of integers and the set of real numbers is that the set of real numbers is uncountable, so that an interval from an integer to another in the set of integers (for example, 0 and 2) is a finite set ({0, 1, 2}), but an interval between two different real numbers is an infinite set (for example, (0,2)).

 

[Dick]

I haven't read much yet about infinite sets, so I can't give any formal definition. But I'm inclined to think that an infinite set is a set where one can never end enumerating different elements; for example, the set of integers and the set of real numbers. I also think that the difference between the set of integers and the set of real numbers is that the set of real numbers is uncountable, so that an interval from an integer to another in the set of integers (for example, 0 and 2) is a finite set ({0, 1, 2}), but an interval between two different real numbers is an infinite set (for example, (0,2)).

One common definition is that an infinite set is a set that has a proper subset that is in one-to-one correspondence with the set. That makes your proof easy. Another is to define a finite set and then say an infinite set is one that is not finite. That makes it a little trickier. You'll have a hard time proving this without knowing the formal definition of 'infinite set'.