Let A be a subset of X, and suppose we have an injection from X to A

  • Thread starter Artusartos
  • Start date
  • Tags
    Injection
In summary, the conversation discusses proving that the cardinalities of a set X and its subset A are equal, given that there is an injection from X to A. For finite sets, it can be proven by contradiction. For countably infinite sets, the injection can be used to show that the elements of X and A can be matched one-to-one, implying they have the same cardinality. However, the method for extending this to uncountable sets is still unclear. The definition of cardinality and same cardinality is also mentioned as a potential starting point for solving the problem.
  • #1
Artusartos
247
0

Homework Statement



Let X be a set and let A be a subset of X. Suppose there is an injection $f: X \rightarrow A$. Show that the cardinalities of A and X are equal.

Homework Equations





The Attempt at a Solution




I tried proving this for hours but couldn't really get anywhere. So I was wondering if anybody could give me a hint so that I could start from there. By the way, I'm not supposed to use the Cantor-Bernstein Theorem.

Thanks in advance
 
Physics news on Phys.org
  • #2
Suppose that X is finite. It's easy to prove by contradiction that they have the same cardinalities. A similar of proving the statement goes for the other cardinalities.
 
  • #3
kostas230 said:
Suppose that X is finite. It's easy to prove by contradiction that they have the same cardinalities. A similar of proving the statement goes for the other cardinalities.
For finite sets, let's suppose that ##|X|=n## and ##|A|=m## where ##m > n##.

Since ##A \subseteq X##, if ##a \in A## then ##a \in X##. So ##a_1 \in A \implies a_1 \in X##, ##a_2 \in A \implies a_2 \in X##, ... , [itex]a_m \in A \implies a_m \in X[/itex]. So we have a bijection h from X to the set {1, ... m}. But since ##|X|=n##, we also have a bijection k from X to {1, 2, ... ,n}. However, there exists no bijection between {1, 2, ... ,n} and {1, 2, ... , m} since m >n. A contradiction.

For countably infinite sets, we can use the injection ##f: X \rightarrow A##. Since X is countable, we can list the elements of ##X## as ##x_1, x_2, ... ##. We can also list the elements of A as ##a_1, a_2, ...##. Let us reorder the elements of A so that ##x_1## is sent to ##a_1##, ##x_2## is sent to ##a_2##, and so on. This function must be surjective. Suppose not. Then there exists ##a_k## for some k, such that ##f^{-1}(a_k) = \emptyset##. But this just means that we do not have ##x_k## in ##X##, which is a contradiction, since we assumed that X was countably infinite.

But I can't really see how I can extend this to uncountable sets...
 
Last edited:
  • #4
What is the definition of "cardinality"? Or, perhaps just the definition of "same cardinality".
 

1. What does it mean for there to be an injection from X to A?

An injection from X to A means that there exists a function that maps every element in X to a unique element in A. This function must also satisfy the property that if two elements in X map to the same element in A, then those two elements in X must be equal.

2. How is an injection different from a surjection?

An injection is a function that maps every element in its domain to a unique element in its codomain. A surjection, on the other hand, is a function that maps every element in its codomain to at least one element in its domain. In other words, an injection is a one-to-one mapping, while a surjection is an onto mapping.

3. Can there be more than one injection from X to A?

Yes, there can be more than one injection from X to A. As long as the function satisfies the properties of an injection, such as mapping every element in X to a unique element in A, it is considered an injection.

4. Does an injection always exist from X to A?

No, an injection does not always exist from X to A. For there to be an injection, X and A must have a certain relationship, such as A being a subset of X. If this relationship does not hold, then there may not be an injection from X to A.

5. What are some real-life applications of injections?

Injections are commonly used in computer science and mathematics, particularly in the study of functions and set theory. In real-life applications, injections can be used to model relationships between different sets, such as customer orders and products, or students and their grades. They are also used in cryptography to ensure the security of data transfers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
717
  • Calculus and Beyond Homework Help
Replies
13
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
460
  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
761
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
466
Back
Top