UGC NET CSE | December 2015 | Part 2 | Question: 3

Question

Which of the following is/are not true ?

1. The set of negative integers is countable.
2. The set of integers that are multiples of 7 is countable.
3. The set of even integers is countable.
4. The set of real numbers between 0 and 1⁄2 is countable.
   • A. i and iii
   • B. ii and iv
   • C. ii only
   • D. iv only

Comments

Detailed Video Solution: https://www.youtube.com/watch?v=fl8Z3oM2EJk&t=7638s 

Proof of Statement D using Cantor’s Diagonalization Argument: https://youtu.be/WDHRu5LkpWc?feature=shared&t=587 

---

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

Answer 1

ans is 4 d)only

a set is countable if it each element can be associated with a natural number e.g set of whole numbers like 0,1,2,3,....c

now such mapping is not possible to set of all real numbers between 0 to 1/2 hence it is not countable

for rest options such mapping is possible

Answer 2

A set is countable if there is a bijective function f: N→A so that every element in set occur exactly once

Countable:

• Set of all negative integers
• Set of all strings over Σ
• Set of all Recursively enumerable languages are countable. (In short, all regular, CFG, R, RE languages are countable)
• Set of all languages over Σ accepted by Turing machines

Not countable:

• Set of real numbers between 0 and 1
• Set of all languages over Σ

Answer must be d as it is impossible to map all real numbers in a range to N

Answer 3

Answer: D

We must understand if a set is finite it must be countable for e.g. number of states in India. but in set theory it is also possible that even if a set is infinite still it can be countable.

A set is countable if it each element can be associated with a natural number, because we consider that natural numbers are infinite but yet they are countable. So, for a set to be countable there is a one-to-one mapping between the elements of the set and natural numbers. e.g. set of stars, set of integers.

Such mapping is not possible to set of all real numbers because between any two real numbers there will be infinite real numbers and in that any two real numbers again infinite real numbers and so on, so set of real numbers between 0 to 1/2 is not countable.

So according to this logic integers are countable and if integers are countable then their subset will also be countable.