Bijections result when the function is surjective and injective

Click For Summary

Discussion Overview

The discussion centers on the concept of bijections, particularly in the context of finding a bijection between the set of natural numbers (N) and the set of all odd numbers. Participants explore the definitions and proofs required to establish a function as one-to-one (injective) and onto (surjective). There is also a comparison of bijections between power sets and sets of integers.

Discussion Character

  • Technical explanation
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant proposes the function f(x) = 2x + 1 as a potential bijection from N to the set of odd numbers and questions whether they need to prove it is one-to-one and onto.
  • Another participant confirms the need to prove that f is one-to-one by showing that if f(n) = f(m), then n must equal m.
  • A different participant emphasizes the necessity of proving surjectivity, suggesting that for any odd number m, there exists an integer n such that 2n + 1 = m.
  • Some participants express frustration over the variability in proving functions as one-to-one or onto, indicating that different problems may require different approaches to definitions.
  • A question is raised about the difference between finding a bijection between power sets P(N) and P(Z) versus between N and Z, with a suggestion that a bijection between N and Z implies a bijection between their power sets.

Areas of Agreement / Disagreement

Participants generally agree on the need to establish both injectivity and surjectivity for a function to be considered a bijection. However, there is no consensus on the specific methods for proving these properties, and the discussion includes varying perspectives on the relationships between different sets.

Contextual Notes

Participants mention the importance of definitions in establishing bijections, indicating that the proofs may depend on specific interpretations or approaches to these definitions. There is also an acknowledgment of the complexity involved in proving bijections across different types of sets.

laminatedevildoll
Messages
211
Reaction score
0
Bijections result when the function is surjective and injective.

How do I find a bijection in N and the set of all odd numbers?

f(x) = 2x+1

Do I have to prove that this is one-to-one and onto? Am I on the right track?
 
Physics news on Phys.org
laminatedevildoll said:
Bijections result when the function is surjective and injective.

How do I find a bijection in N and the set of all odd numbers?

f(x) = 2x+1

Do I have to prove that this is one-to-one and onto? Am I on the right track?
Yes. Can you prove that for all n and m in N, if f(n) = f(m), then n = m? (Just plug and play.)
 
You would also, of course, have to prove that it is a surjection: that is, that if m is an odd number then there exist an integer n such that 2n+ 1= m.
 
You can get the surjection from the definition of odd number.
 
Last edited:
Thank you for your help. I think that I need a lot of practice using the definition.
 
Which definition- bijection?
 
honestrosewater said:
Which definition- bijection?

Yeah. It's kind of frustrating to prove if a function is one-to-one or onto when one way of proving for one problem doesn't apply to the next. It's all about playing around with the definition and all.
 
What's the difference between finding a bijection between P(N) and P(Z) AND N and Z? P stands for power set (the curly P).
 
You mean a bijection between P(N) and P(Z) compared to a bijection between N and Z?

I've never done that kind of thing but I think if you have a bijection between N and Z then you automatically have a bijection between P(N) and P(Z) by replacing every element x of N in a given element y of P(N) with f(x) and mapping y to the resulting element z, which will be in P(Z). If you have a bijiection between P(N) and P(Z) then I don't think you necessarily can say you have a bijection between N and Z.
 

Similar threads

MHB Hilbert's hotel and busses : Injectivity - Surjectivity
  • · Replies 7 ·
Replies
7
Views
2K
Does there exist a surjection from the natural numbers to the reals?
  • · Replies 4 ·
Replies
4
Views
4K
MHB Compose Functions: True/False?
  • · Replies 1 ·
Replies
1
Views
2K
MHB How do you prove that a function is bijective?
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Is √9x a Bijection from N to R?
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad What is the Definition and Understanding of Surjective Functions?
  • · Replies 1 ·
Replies
1
Views
1K
Graduate Show a functions inverse is injective iff f is surjective
  • · Replies 10 ·
Replies
10
Views
4K
Undergrad On injectivity of two-sided Laplace transform
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Can the choice of codomain affect the surjectivity of a function?
  • · Replies 4 ·
Replies
4
Views
2K
MHB Inverting Injections and Surjections: A Discussion of the Axiom of Choice
  • · Replies 5 ·
Replies
5
Views
6K