All Questions
Tagged with cardinals discrete-mathematics
113
questions
4
votes
1
answer
105
views
Among 101 dalmatian dogs, each dog has a unique number of black spots, Addition property
Among 101 dalmatian dogs, each dog has a unique number of black spots from the set {1, 2, 3, . . . , 101}. We choose any 52 of the 101 dogs. We want to prove that any set of 52 dogs satisfies the ...
- 343
2
votes
1
answer
92
views
How the comparison of the cardinalities of sets affects the cardinalities of their powersets [duplicate]
In my question, I denote by $|\cdot|$ the cardinality of any set. Moreover, if $f: X \to Y$, we denote by $\mathcal{P}f$ its direct image, i.e. $\mathcal{P}f(A)=\{f(a) : a \in A\}$. Let $X,Y$ be two ...
- 5,192
1
vote
1
answer
109
views
Questions about the Infinite Monkey Theorem
(Context: the Infinite Monkey Theorem stipulates that given infinite time, a monkey can type out the complete works of Shakespeare, or any other text of finite length, just by randomly pressing keys.)
...
- 467
-1
votes
1
answer
61
views
Given |A\B| = |B\A|, prove |A|=|B| and provide 2 sets (A and B) such that |A| = |B| but |A\B| is not the same as |B\A|
Part A : Given |A\B| = |B\A|, prove |A|=|B|
Part B : Provide 2 sets (A and B) such that |A| = |B| but |A\B| is not the same as |B\A|
Part A:
Let A,B be sets. Given that |A\B| = |B\A| then |A|=|B|
Hint ...
- 147
1
vote
2
answers
48
views
Find cardinality of a set {$f \in \mathbb{N}^{\mathbb{N}}|f\le h$} where $h(n)=n+1$
On a set $\mathbb{N}$ is defined a partial order relation $f \le g \iff \forall{n\in\mathbb{N}}
f(n) \le g(n) $.
Also let $h: \mathbb{N}\to\mathbb{N}$ given by a formula $h(n)=n+1$.
Find cardinality ...
- 33
2
votes
0
answers
75
views
Is there a set $\mathbb{X}$ such that $\mathcal{P}(\mathbb{X})$ has a cardinality of $\aleph_0$? [duplicate]
Is there a set $\mathbb{X}$ such that $\mathcal{P}(\mathbb{X})$ has a cardinality of $\aleph_0$ ? Give a proof.
As for me, i think no, because $\aleph_0$ is a cardinality of a set of natural numbers, ...
- 33
1
vote
1
answer
40
views
How to prove that function that maps elements from Z to N is injection
I have a function that maps Z to N.
Intuitively I know that it is an injection, but I don't know how to prove it's injection.
I know how to prove that some function is injection, but if the function ...
- 33
0
votes
1
answer
22
views
Size of the set of functions from [n] to X.
I have trouble understanding this statement in my lecture notes on Cardinality.
For all sets $X$ and all $n \in \mathbb{N}$, $Maps([n+1], X) \approx Maps([n], X) \times X$.
$[n]$ is defined to be the ...
0
votes
0
answers
47
views
What is the cardianlity of Z[x], the set of all polynomials with integer coefficients? [duplicate]
Apparently it's aleph null, but I really don't understand why or how to form a bijection between the two sets, Z[x] and Z.
- 1
3
votes
2
answers
165
views
Prove that the set of all ternary sequences is uncountable
I have the following question in Discrete Math 2 in one of my assignments.
A ternary sequence is defined as a function $t\colon\mathbb{N}_0\longrightarrow\mathbb{N}_0$ such that $t(3n+1) = t(3n)+1$ ...
- 65
0
votes
1
answer
38
views
Prove that the cardinality of $\mathbb{N}^{\mathbb{N}_2}$ countable.
Since $\mathbb{N}_2 = \{1,2\}$ and the cardinality of $\{1,2\}$ is $2$. I assume you can re-express this as $|\mathbb{N}|^{2}$. The part where I'm stuck on is understanding what $|\mathbb{N}|^{2}$ ...
- 3
2
votes
3
answers
338
views
How can we prove that $\mathbb{N^2}$ has the same cardinality as $2\mathbb{N} + 1$
How can we prove that $\mathbb{N^2}$ has the same cardinality as $2 \mathbb{N} + 1$?
I've thought about using Cantor's theorem and mapping every element in a coordinative system, am I going to the ...
- 37
-1
votes
1
answer
75
views
Cardinality Proving Question
[Hi everyone, I am not sure of how to apply question 2, and Proposition 9.2.4(2) [which means Any subset A of a countable set B is countable] shown in 1 of the pictures above to solve questions 3(a) ...
- 1
0
votes
0
answers
50
views
How to prove and define amount of countably infinite set in the naturals numbers
I have the following question
Picture of the question
What is the cardinality of $D=\{A \subseteq \Bbb N \mid \vert A \vert = \aleph_0 \land \vert \Bbb N \setminus A \vert = \aleph_0 \}$?
I do ...
- 11
3
votes
2
answers
299
views
Tips for forming countability proofs?
I'm new to writing proofs, and I'm having a really hard time enumerating sets. I'm struggling to construct functions which convert positive integers into the desired set and which is bijective. For ...
