Introduction to Countability (Countable and Uncountable Sets) | TOC | Automata Theory

Описание: #countability, #toc, #automata, #thegatehub
Contact Datils (You can follow me at)
Instagram:   / ahmadshoebkhan  
LinkedIn:   / ahmad-shoeb-957b6364  
Facebook:   / ahmadshoebkhan  

Watch Complete Playlists:
Data Structures:    • Introduction to Data Structures || Basics ...  

Theory of Computation:    • Introduction to Theory of Computation || G...  

Compiler Design:    • Ambiguous Grammar || Introduction to Ambig...  

Countable Set is a set having cardinality same as that of some subset of N the set of natural numbers . A countable set is the one which is listable.
Uncountable Sets:
A set such that its elements cannot be listed, or to put intuitively, there exists no sequence which can list every element of the set at least once.
Examples:
set of real numbers is uncountable.
set of all binary sequences of infinite length.

History
In 1874, in his first set theory article, Cantor proved that the set of real numbers is uncountable, thus showing that not all infinite sets are countable.
In 1878, he used one-to-one correspondences to define and compare cardinalities.
In 1883, he extended the natural numbers with his infinite ordinals, and used sets of ordinals to produce an infinity of sets having different infinite cardinalities.

A set is countably infinite if the same size as N. It is countable if finite or countably infinite. This
means there is a numbered list of all elements.

Cantor and Infinity
The idea of diagonalization was introduced by Cantor in probing infinity. Both his result and
his proof technique are useful to us.

Diagonalization
Given a list of words, one can construct a word not on the list:
Start with the diagonal as a word, and then replace each letter by the next letter in the
alphabet.

Diagonalization Always Gives New Word
The new word cannot be on the list: it is different from first word in first letter, different from
second word in second letter, etc.
Cantor’s insight was that same idea works with infinite lists. . .

Summary
A set is countable if it can be placed in 1–1 correspondence with the positive integers. Cantor
showed by diagonalization that the set of subsets of the integers is not countable, as is the
set of infinite binary sequences. Every TM has an encoding as a finite binary string. An infinite
language corresponds to an infinite binary sequence; hence almost all languages are not r.e.

theory of computation in hindi
theory of computation lectures in hindi
theory of computation lectures
toc gate lectures
theory of computation in hindi
theory of computation gate lectures
theory of computation
theory of computation tutorial
theory of computation basics
countable and uncountable sets in hindi
countability and uncountability
countably infinite, uncountably infinite
countable and uncountable sets
countability and uncountability in real analysis
countability and uncountability in discrete mathematics
countability and uncountability in mathematics
countability and real numbers
countability and uncountability in csir net