MHB What is the meaning of one-to-one correspondence between subsets of S?

  • Thread starter Thread starter yakin
  • Start date Start date
  • Tags Tags
    Subsets
Click For Summary
One-to-one correspondence refers to a function that establishes a unique mapping between elements of two sets, ensuring that each element in the domain corresponds to a unique element in the range. A function is considered one-to-one if it passes both the vertical and horizontal line tests, meaning no vertical or horizontal line intersects the function at more than one point. The term "one-to-one correspondence" is often used interchangeably with "bijective function," which is both one-to-one and onto, indicating that every element in the codomain is covered. This concept is crucial for demonstrating that two infinite sets have the same cardinality. Understanding these definitions clarifies the relationship between functions and their mappings.
yakin
Messages
42
Reaction score
0
What is the meaning of one-to-one correspondence between subsets of S?
 
Physics news on Phys.org
So, a function you can think of as a subset of points in the $xy$ plane that satisfy a vertical line test: no vertical line you draw can touch the function in more than one place. If, in addition, the function passes a horizontal line test (no horizontal line you could draw touches the function in more than one place), then we say the function is one-to-one. When you say "one-to-one correspondence", you typically mean a one-to-one function.

More formally: a one-to-one function is a function that maps unique points in the domain to unique points in the range. (And of course, if it's a function, then unique points in the range had to come from unique points in the domain.)
 
Ackbach said:
When you say "one-to-one correspondence", you typically mean a one-to-one function.
Wikipedia says that one-to-one correspondence is a bijective function, i.e., a function that is both one-to-one and onto. I've seen this interpretation before as well. And yes, it is confusing.
 
Evgeny.Makarov said:
Wikipedia says that one-to-one correspondence is a bijective function, i.e., a function that is both one-to-one and onto. I've seen this interpretation before as well. And yes, it is confusing.

Sure, although in this context, it likely means a function between two infinite sets that allows you to conclude that they have the same cardinality. Is "onto" a necessary property to show this?
 
Of course: the fact that two sets have the same cardinality is evidenced by a bijection, and by definition it is both one-to-one and onto.

In any case, this is the terminology that I've seen so far.
  • One-to-one function: a function that maps different inputs to different outputs.
  • One-to-one correspondence: a function that is one-to-one and onto, i.e., covers the whole codomain.
 

Thread 'A variant of the Monty Hall problem'

There is a nice little variation of the problem. The host says, after you have chosen the door, that you can change your guess, but to sweeten the deal, he says you can choose the two other doors, if you wish. This proposition is a no brainer, however before you are quick enough to accept it, the host opens one of the two doors and it is empty. In this version you really want to change your pick, but at the same time ask yourself is the host impartial and does that change anything. The host...
View full post »

Similar threads

MHB A Subset of a Graph with No Perfect Matching
  • · Replies 1 ·
Replies
1
Views
2K
MHB Proper Subsets and Relations of Sets
  • · Replies 1 ·
Replies
1
Views
2K
MHB Proving that a subset of a countable set is countable
  • · Replies 1 ·
Replies
1
Views
3K
I Sets, Subsets, Possible Relations
  • · Replies 1 ·
Replies
1
Views
1K
I Billard balls on table
  • · Replies 10 ·
Replies
10
Views
2K
A Probability of finding a k-subset in a d-dimensional random
  • · Replies 2 ·
Replies
2
Views
1K
MHB One to One Correspondence vs One to One function
  • · Replies 1 ·
Replies
1
Views
3K
I When does ## { n \choose k } ## represent set of lists?
  • · Replies 20 ·
Replies
20
Views
2K
I Measure with respect to complete measure is also complete
  • · Replies 3 ·
Replies
3
Views
2K
MHB Understanding Proper Subsets of Ordinals in Searcoid's Theorem 1.4.4 - Peter
  • · Replies 2 ·
Replies
2
Views
1K