Is My Proof on Finite Sets and One-to-One Correspondence Correct?

  • Context: Graduate 
  • Thread starter Thread starter AdrianZ
  • Start date Start date
  • Tags Tags
    Proof
Click For Summary

Discussion Overview

The discussion revolves around the proof concerning the relationship between finite sets and one-to-one correspondences, specifically addressing whether the proof provided by a participant is correct. The scope includes theoretical aspects of set theory and definitions of finite and infinite sets.

Discussion Character

  • Technical explanation
  • Conceptual clarification
  • Debate/contested

Main Points Raised

  • One participant claims that if there is a one-to-one correspondence between two sets X and Y, and if X is finite, then Y must also be finite, proposing a proof based on the properties of infinite sets.
  • Another participant agrees with the proof but notes that it may not be the shortest method available, suggesting that the use of infinite sets in the proof is surprising.
  • A further reply discusses the definitions from the participant's textbook, specifically Dedekind's definition of infinite sets and the definition of finite sets, indicating a preference for staying faithful to these definitions.
  • Some participants mention an alternative proof that could be shorter, which involves showing that a finite set is in one-to-one correspondence with the natural numbers.
  • There is a clarification about the distinction between Dedekind-finite and finite sets, with a note that the axiom of choice is necessary for this distinction.

Areas of Agreement / Disagreement

While there is agreement on the correctness of the proof, participants express differing views on the efficiency of the proof and the definitions being used. The discussion reflects multiple perspectives on the definitions of finite and infinite sets, and no consensus is reached on the best approach to the proof.

Contextual Notes

Participants reference specific definitions from their textbooks, which may influence their understanding and approach to the proof. There is also mention of the axiom of choice, indicating a complexity in the definitions being discussed.

AdrianZ
Messages
318
Reaction score
0
Suppose that f is a one-to-one correspondence between two sets X and Y. Prove that if X is finite, then Y is finite too.

my proof: I've already proved that if X is infinite, then Y is infinite too. since f is a one-to-one correspondence, f-1: Y->X exists and by applying the same theorem it can be shown that if f:X->Y and Y is infinite, then X is infinite as well.so, I can claim that if f is a one-to-one correspondence, then X is infinite if and only if Y is infinite. hence, It's possible to say that if f is a one-to-one correspondence between the two sets X and Y, then X is finite if and only if Y is finite.
Is my proof correct?
 
Physics news on Phys.org
Yes, your proof is correct (once you know that infinite = not-finite). Though, it might not be the shortest proof available. That is, that you proved it by making use of infinite sets is suprising.
 
micromass said:
Yes, your proof is correct (once you know that infinite = not-finite). Though, it might not be the shortest proof available. That is, that you proved it by making use of infinite sets is suprising.

Actually It's because the book I'm studying from uses Dedekind's definition of an infinite set that a set is infinite iff there is a one-to-one correspondence between the set and a subset of the set. and then it defines a finite set as a set that is not infinite.so, I tried to stay faithful to the definitions that my book suggests. surely there is a shorter way of proving this using the other definition that says a set A is finite iff it's in one-to-one correspondence with Nk. then I can say X~Nk and X~Y, hence Y~Nk. I guess you meant I could use the second approach and It would be shorter. Is that you what you mean?
 
AdrianZ said:
Actually It's because the book I'm studying from uses Dedekind's definition of an infinite set that a set is infinite iff there is a one-to-one correspondence between the set and a subset of the set. and then it defines a finite set as a set that is not infinite.so, I tried to stay faithful to the definitions that my book suggests. surely there is a shorter way of proving this using the other definition that says a set A is finite iff it's in one-to-one correspondence with Nk. then I can say X~Nk and X~Y, hence Y~Nk. I guess you meant I could use the second approach and It would be shorter. Is that you what you mean?

Aah, that explains things! Yes, when working with Dedekind-finite things then you need to do it the way you do it.
Also remark that Dedekind-finite is not the same as finite in the other definition. You need the axiom of choice for that. So it's best to stay close to the definitions!
 

Similar threads

Undergrad Contrapositive of theorem and issue with proof
  • · Replies 5 ·
Replies
5
Views
2K
High School Set Theory Question -- Which one is correct?
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Thinking about equality of infinite sets
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Countability of binary Strings
  • · Replies 18 ·
Replies
18
Views
4K
Undergrad Is an algorithm for a proof required to halt?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Error(?) in proof that the rational numbers are denumerable
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Does the definition of cardinality assume distinguishability?
  • · Replies 9 ·
Replies
9
Views
2K
Undergrad The answer is 15! What is the problem?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Is Every Statement Correct in Defining an Onto Function?
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Error bars in Excel (standard deviation, standard error, percentage)
  • · Replies 4 ·
Replies
4
Views
3K