PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q1(a)(i)

Theory of Computation · 2 marks

Open in the Padhaiko app

Topic: Sets, Functions & Relations

Question

Define countably infinite and uncountable set with example.

Solution

Countably Infinite Set Definition and Example: A set is countably infinite (or denumerable) if it has the same cardinality as the set of positive integers (). That is, there exists a bijective function (one-to-one and onto) .

Equivalently, the elements of a countably infinite set can be arranged in an infinite sequence without repetition or omission: .

Example: The set of all integers is countably infinite under the bijection:

Uncountable Set Definition and Example: A set is uncountable if it is infinite but cannot be put into a one-to-one correspondence with the set of natural numbers (). Any list of elements of an uncountable set necessarily omits elements of the set.

Example: The open interval of real numbers (and the set of all real numbers itself) is uncountable. Cantor's Diagonalization Argument proves that any enumerated list of real numbers in fails to include a newly constructed real number whose -th decimal digit differs from the -th digit of the -th number in the list.

Answer:

A countably infinite set has a bijection with (cardinality , e.g., or ). An uncountable set is infinite but cannot be put into one-to-one correspondence with (e.g., or ), as established by Cantor's diagonalization argument.

All past exam questions for Theory of Computation