Questions tagged [uncountability]
The uncountability tag has no usage guidance.
45 questions
6
votes
2
answers
2k
views
How to determine if a set is countable or uncountable?
When I am presented with a problem of finding whether or not the given set is countable, I cannot figure out how to determine it or prove it. The general approach is to compare it with $\mathbb{N}$, ...
- 141
6
votes
1
answer
293
views
Are any "standard" complexity classes uncountably infinite?
(This is a somewhat fuzzy question.)
I believe that most of the "standard" complexity classes that one comes across in complexity theory are countably infinite, because they are defined in ...
- 1,146
4
votes
1
answer
192
views
Is the set of all DFAs countable?
Let $\Sigma$ be a finite nonempty alphabet. Is the set of all DFAs over $\Sigma$ countable?
I know the set of all regular languages is countable, however, it is impossible to build an injection from ...
- 155
-2
votes
2
answers
83
views
Is the set of all strings over $\Sigma$ countably infinite or not?
Let $\Sigma$ be an alphabet. Is the set of all strings over $\Sigma$ (i.e. $\Sigma^*$) countably infinite or uncountably infinite?
- 1
0
votes
2
answers
49
views
What are the definitions of countable and measurable colourings of a graph?
In this paper, the author discusses colourings of the plane, or in other words, of the underlying graph. I suppose a finite colouring is a colouring using at most $k$ colours for some natural number $...
- 817
-1
votes
1
answer
159
views
Turing machine to find maximum of an infinite set
Given a set that is infinite but still countable, does a TM exist that goes over every element in the set and finds the maximum?
Is this a computable function?
- 53
1
vote
1
answer
1k
views
Is $\Sigma^*$ countable or uncountable?
Consider $\Sigma = \{a,b\}$. Now $\Sigma^*$ represents the collection of all possible strings over alphabet $\Sigma = \{a,b\}$.
As there exists an enumeration procedure for $\Sigma^*$, it is countably ...
1
vote
2
answers
328
views
Hilbert's Hotel for guests with infinite string name
I was watching this video How An Infinite Hotel Ran Out Of Room, by Veritasium.
The video says that it is not possible to fit names made of infinite strings of $\{A,B\}$.
We know we can fit infinite ...
- 13
0
votes
2
answers
2k
views
How come the set of all binary strings is uncountable?
Sorry for bumping this very old problem which already has answers on multiple SE sites, but I just cannot understand any of the answers.
Let $\Sigma_{bool} = \{0, 1\}$.
Then, $(\Sigma_{bool})^*$ is ...
- 127
3
votes
1
answer
424
views
Prove that not all languages over unary alphabet are regular
Let the alphabet be $\{0\}$. I have to prove that not all languages over this alphabet are regular, using some countability argument.
My Ideas:
The set of all languages over $\{0\}$ is uncountable. ...
- 53
0
votes
1
answer
139
views
What's wrong with this "proof" that $\mathbb{R}$ is enumerable?
The fake proof:
We know that $\mathbb{R}$ is uncountable, hence we cannot enumerate over it.
But what we do know is that $\mathbb{Q}$, the set of rationals, is countable, and even denumerable.
We ...
- 157
2
votes
4
answers
1k
views
Does infinite length strings lead to uncountable languages?
This answer says:
We can have uncountable languages only if we allow words of infinite length.
So does that means any (finite / infinite) language or any (finite / infinite) set of languages over ...
- 235
0
votes
2
answers
237
views
How is the set of functions from ${\{a,b\}}$ to $N$ countable?
Assume a set of functions from ${\{a,b\}}$ to $N$
Where $N$ is the set of Natural numbers.
Let us assume that the size of $N$ is $n$.
i.e $|N|=n$
The first element $a$ have $n$ choices for mapping....
- 281
2
votes
1
answer
4k
views
Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable
I came across following facts:
Set of finite languages over a finite alphabet is countable.
Set of languages over finite alphabet is uncountable.
I believe proof of this will be similar to ...
- 1,727
0
votes
1
answer
113
views
Doubt regarding Cantor's diagonalization argument [closed]
So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider.
I understand the overall argument but have a problem regarding one caveat mentioned in my ...
- 111
10
votes
3
answers
4k
views
Show that there are infinitely more problems than we will ever be able to compute
I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ...
- 1,073
0
votes
1
answer
676
views
Question about non recursively enumerable language [duplicate]
Is every language (including languages over alphabet having infinite symbols) which is not recursively enumerable, uncountable?
In other words, let $R$ be the set of languages (including languages ...
1
vote
1
answer
2k
views
Is L={<M>|M is a TM and L(M) is uncountable} decidable?
Is $L=\{\langle M\rangle\mid \text{$M$ is a Turing machine and $L(M)$ is uncountable}\}$ decidable?
My intuition is that it is not, but I'm not sure if Rice's Theorem applies in this case. If it is ...
user87413
3
votes
1
answer
1k
views
What is the relation between countability and recursive enumeration? [duplicate]
Does recursive enumeration implies countability?
Does countability implies recursive enumeration?
I believe the first implication holds but not sure about the second. A good example would suffice.
- 717
4
votes
2
answers
6k
views
Are all finite strings over some infinite alphabet countable?
Over some infinite alphabet $\Sigma$, can we state that the set of all possible finite strings is countable?
- 279
0
votes
3
answers
2k
views
Are the sets of all finite automata and pushdown automata countable?
So considering that set of all turing machines is countably infinite, can we also say that set of all FA machines(DFA/NFA) or set of all PDA machines(DPDA/NPDA) are countably infinite, Considering ...
- 307
1
vote
1
answer
143
views
Is this language countable : $L= \{ w : w \in (1 + 0)^{*} \}$
This is my take :
Epsilon ---> 1
0 --> 2
01 ---> 3
10 ---> 4
11 ---> 5
001 ---> 6
010 ---> 7
.
.
.
So therefore we can count them.
But based on this video : https://www.youtube.com/watch?v=...
- 307
4
votes
1
answer
91
views
Is repetition the origin of countability?
The original question was "Do all non-regular languages have an uncountable number of strings?".
How can someone prove that..? I am squeezing my head but I can't figure it out.
And the other side ...
- 43
2
votes
1
answer
2k
views
Is there any undecidable language that is countable?
All we know is that if a language is countable than it must be recognizable. However, a recognizable language may or may not be decidable.
- 21
3
votes
2
answers
3k
views
Decidability of Unary Languages / One-to-One Mapping
I'm trying to prove that there exists an undecidable subset of {1}* by showing a one-to-one correspondence between it and {0, 1}* (which would imply a one-to-one correspondence between their power ...
- 33
-2
votes
1
answer
514
views
Is every countably infinite language recursive?
We'll say the alphabet for the languages is finite, say {0,1}.
- 43
2
votes
2
answers
1k
views
Can a regular language have uncountably many strings?
Obviously it can have a countably infinite number of strings. (Take the language descibed by the regular expression 0* as an example.) But can a RL have uncountably many strings? I'm leaning toward no,...
3
votes
2
answers
1k
views
Is there a non-recursive and uncountable language L?
Does there exist a non-recursive language, L, such that the cardinality of L is uncountable?
I would really like an explanation as to why this question is true or false because at the moment, I have ...
- 31
5
votes
4
answers
939
views
Showing that the number of primitive-recursion programs for each function is countably-infinite
Problem Statement
Prove that if a function $f$ is primitive recursive, then there are countably infinite number of primitive recursive definitions of $f$
Yes, this is a homework question.
My ...
- 1,208
0
votes
2
answers
1k
views
Countability of a binary tree
Problem:
We'll define a binary tree as a tree where the degree of every internal node is exactly 3. Show that the set of all binary trees is countable.
My attempt:
A set is countable if it is ...
- 483
2
votes
2
answers
3k
views
Number of finite strings over a countably infinite alphabet
If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite?
3
votes
1
answer
2k
views
Can a recursive language be uncountable?
Does there exist a recursive language $L$ whose cardinality is uncountable?
I would like to have an explanation whether Turing Machine can encode uncountable languages and whether we can use this to ...
1
vote
1
answer
145
views
Is the union of finite and infinite sequences over alphabet of length 1 countable?
Is the union of finite and countably infinite sequence over alphabet $\Sigma=\{1\}$, countably infinite as well?
I understand this is similar a question to the one of finite and countably infinite ...
1
vote
1
answer
216
views
Countability union of all finite and countably infinite sequences over finite alphabet
Is the set of all finite and countably infinite sequences over $\{0,1\}$ countable?
From my analysis, I think it is countable. I think of this as the set of all strings from a finite alphabet $\Sigma=...
0
votes
1
answer
3k
views
Deciding Countability of Languages
Suppose we have given $\Sigma=\{a,b\}$, Which one of the following set is not countable
(a) Set of all languages over $\Sigma$
(b) Set of all regular languages over $\Sigma$
(c) Set of ...
- 749
2
votes
1
answer
1k
views
Are all languages generate by Turing machines countable?
Are all languages generate by Turing machines countable? I know that the set of all TMs are countable, but what about the languages that they generate?
- 21
0
votes
1
answer
820
views
Prove that the set of all total functions is countable [closed]
I'm stuck on a theory/set proof question:
$S$ is the set of all total functions $f : \{0, 1\} \to \mathbb{N}$ (natural numbers), prove that S is countable.
I have found a sample solution already ...
user15860
1
vote
2
answers
401
views
Why are pushdown automata countable? [closed]
I began a chapter in a textbook on computational theory where they begin to talk about decidable languages.
The problems in this section are pretty confusing and I honestly don't know how to begin ...
3
votes
1
answer
971
views
Undecidability and Countability
This question is prompted by Undecidable unary languages (also known as Tally languages)
How does the countability of a language imply (un)decidability?
- 213
2
votes
2
answers
3k
views
Is the set of all valid C programs countable?
Is the set of all syntactically valid C programs countable or uncountable?
- 498
6
votes
1
answer
1k
views
Where am I wrong?: "countability" and "recursive enumerability"
I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong ...
- 203
2
votes
1
answer
448
views
How to prove "The power set of a countable set must be uncountable"?
I'm not sure if this statement is correct, but my friend said so.
The problem arose from this T/F question:
Let $F=\{f: f$ be a primitive recursive function from $\mathbb{N}$ to $\mathbb{N}\}$, then $...
- 265
-2
votes
3
answers
848
views
If set of TM's is not countable?
I was reading about counting principle related to TOC. I understand that the set of TMs are countable infinity. I couldn't understand the significance of it. What is its not countable?
- 2,221
3
votes
2
answers
2k
views
Cantor's diagonal method in simple terms?
Could anyone please explain Cantor's diagonalization principle in simple terms?
- 2,221
8
votes
2
answers
2k
views
Does there exist any work on creating a Real Number/Probability Theory Framework in COQ?
COQ is an interactive theorem prover that uses the calculus of inductive constructions, i.e. it relies heavily on inductive types. Using those, discrete structures like natural numbers, rational ...
- 868