Prove that if a non-empty set S is countable, then there exists an injection fro

Question

Prove that if a non-empty set S is countable, then there exists an injection from S to N (the natural numbers). Write neatly and be clear in your proof.

Explanation / Answer

a) A nonempty set S is countable if and only if there exists surjective function f:N->S (b) A nonempty set S is countable if and only if there exists a injective function g:S->N In either case (a) or (b) |S|S and injective function g:S->N to exist. Do I need to prove |S|N and show that the function is NOT bijective (mainly surjective since it needs to be injective) There are two way proves for both (a) and (b) (a-1) prove if a nonempty set S is countable, then there exists surjective function g:S->N; (a-2) also prove if there exists surjective function g:S->N, then a nonempty set S is countable (b-1) prove if a nonempty set S is countable, then there exists a injective function g:S->N; (b-2) also prove if there exists a injective function g:S->N, then a nonempty set S is countable

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.