Show that no injection exists for those infinite sets

In summary, there is no concept of an injection for infinite sets because it is impossible to map an infinite number of elements without leaving any unmatched. An injection is different from a bijection or a surjection, as it only maps each element to a unique element without necessarily covering all elements. However, an injection can exist for finite sets because there are a finite number of elements. Proving that no injection exists for infinite sets is significant in understanding cardinality and the concept of infinity. Finally, an infinite set cannot have the same cardinality as its power set, as the power set contains all possible subsets and is therefore always larger.
  • #1
andytoh
359
3
Let A,B,C be infinite sets. Suppose there is no injection from A to B and no injection from B to C. Prove there is no injection from A to C (without using cardinality and Schroeder-Bernstein).

My current solution:
Let f:A-> C. Assume f= s.r (. means composition), where r:A-> B and s:B-> C. If f is injective, then so is r (already proven), a contradiction. But what if we can't assume f= s.r?
 
Last edited:
Physics news on Phys.org
  • #2
So f=s.r must be true?
 
  • #3
So, I'll stick with my current proof.
 

1. Why does the concept of an injection not exist for infinite sets?

For infinite sets, there is no way to map each element of one set to a unique element of the other set without leaving any elements unmatched. This is because there are an infinite number of elements in each set, and thus, any potential injection would have to map an infinite number of elements.

2. How is an injection different from a bijection or a surjection?

An injection is a function that maps each element of one set to a unique element of another set, without leaving any elements unmatched. A bijection is a function that is both an injection and a surjection (meaning it maps every element of one set to a unique element of the other set, and vice versa). A surjection is a function that maps every element of one set to at least one element in the other set, but not necessarily all elements.

3. Can an injection exist for finite sets?

Yes, an injection can exist for finite sets because there are a finite number of elements to be mapped and thus, it is possible to map each element to a unique element without leaving any unmatched.

4. What is the significance of proving that no injection exists for infinite sets?

Proving that no injection exists for infinite sets helps to establish the concept of cardinality, which is the measure of the size of a set. It shows that not all infinite sets have the same size, as some sets may have a larger cardinality than others. This idea is important in understanding the concept of infinity and its different forms.

5. Can an infinite set have the same cardinality as its power set?

No, an infinite set cannot have the same cardinality as its power set. This is because the power set of a set contains all possible subsets of that set, including the set itself. Thus, the power set of an infinite set will always have a larger cardinality than the original set, as it contains all possible combinations of elements.

Similar threads

Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
504
##G## is Injective ##\iff ## ## f ## is onto ## Y ## (Lambda Notation)
    • Calculus and Beyond Homework Help
Replies
3
Views
750
Prove ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##.
    • Calculus and Beyond Homework Help
Replies
3
Views
549
Show injectivity, surjectivity and kernel of groups
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
Prove ##a + b = b + a## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
812
Does there exist a surjection from the natural numbers to the reals?
    • Precalculus Mathematics Homework Help
Replies
4
Views
2K
Prove ##(a+b)\cdot c=a\cdot c+b\cdot c## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
521
Theoretical Math: Proving an injection when it's countably infinite.
    • Calculus and Beyond Homework Help
Replies
1
Views
2K
Injective & Surjective Functions
    • Calculus and Beyond Homework Help
Replies
9
Views
2K
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
    • Calculus and Beyond Homework Help
Replies
1
Views
575

Hot Threads

Recent Insights

Back
Top