GATE CSE 1994 | Question: 3.9

Question

Every subset of a countable set is countable.

State whether the above statement is true or false with reason.

Comments

Every subset of a countable set is countable. It is TRUE.

Set $S$ is countable iff there exists an injective mapping from $S$ to some countable set.

We need to prove that: If set $A$ is countable then every subset of $A$ is countable. 

Proof:

Given: Set $A$ is countable. 

Let $S$ be a subset of $A.$ We can create an injective function $f$ from $S$ to $A$ by the rule $f(x) = x.$

So, since there exists an injective mapping from $S$ to countable set $A$, So, $S$ is countable. 

Video Explanation of this proof is HERE( https://www.youtube.com/watch?v=fl8Z3oM2EJk&t=3492s) 

Answer 1

True
Reference: https://proofwiki.org/wiki/Subset_of_Countable_Set_is_Countable

Comments

http://dspace.bracu.ac.bd/xmlui/bitstream/handle/10361/523/Vol%201%20No%202.14.pdf?sequence=1&isAllowed=y

---

Let $S$ be the given countable set, then there is a bijection $f: S\rightarrow N$ (Since $S$ is coutable $S$ there is a on-to-one correspondence between $S$ and $N$). But then $f(S') = N'$, where $S' \subset S$ and $N' \subset N$ and $f$ is a bijection between $S′$ and $N′$.

Source: https://www.math.brown.edu/~res/MFS/handout8.pdf

 

Answer 2

Theorem . Every subset of a countable set is countable.

Proof.  Suppose a1,a2,a3,....... is an enumeration of the countable set A and B is any nonempty subset of A. If, for some n∈ N, the element 'an' (a subscript n) belongs to B, then we assign the natural number n to it. For each n∈ N let k(n) denote the number of elements among a1,a2,a3,a4,...an, which belong to the subset B. Then ,0≤ k(n) ≤n . Therefore, B is countable by the Countability Lemma.

Every subset of a countable set is countable.  TRUE

Answer 3

In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers. A countable set is either a finite set or a countably infinite set.

R = {1,2,3,4............................} 

R1= {1,2}--------(Countable))------------ cardinality =2

R2={2,3}-------(Countable))------------ cardinality =2

R3={3,4}-------(Countable))------------ cardinality =2

so Every subset of a countable set is countable (true)

Answer 4

Every subset of a countable set is countable. It is TRUE.

Set $S$ is countable iff there exists an injective mapping from $S$ to some countable set.

We need to prove that: If set $A$ is countable then every subset of $A$ is countable. 

Proof:

Given: Set $A$ is countable. 

Let $S$ be a subset of $A.$ We can create an injective function $f$ from $S$ to $A$ by the rule $f(x) = x.$

So, since there exists an injective mapping from $S$ to countable set $A$, So, $S$ is countable. 

Video Explanation of this proof is HERE( https://www.youtube.com/watch?v=fl8Z3oM2EJk&t=3492s) 

---

Countability Complete Course, with Proofs, Variations & All type of questions covered: https://youtube.com/playlist?list=PLIPZ2_p3RNHgXosiQv-gL1PvJkcHokW1p&feature=shared