- #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.
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.
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: