All Questions
Tagged with cardinals proof-writing
55
questions
1
vote
1
answer
64
views
How do I prove that my piecewise function is bijective
Question
Prove that the set $$\mathbb{N} \text{ and } S = {x\in \mathbb{R}|x^{2} \in \mathbb{N}}$$ have the same cardinality.
I drew an arrow diagram, and got this equation:
$$ f: \mathbb{N} \...
- 33
1
vote
1
answer
116
views
Showing cardinality inequalities involving equivalence relations without the Axiom of Choice
I am studying a course on ZF Set Theory and am currently looking at the cardinalities of infinite sets.
Consider any equivalence relation $\equiv$ on any set $X$. Show that $$2 ^{ |X/{\equiv}|} \leq ...
- 4,331
0
votes
0
answers
116
views
How to prove that Q \ Z is countable
The question is asking to prove that Q \ Z is countable. We are allowed to use the fact that Q and N have the same cardinality.
My current idea is to show that there is a bijection between the set Q \ ...
- 51
1
vote
0
answers
289
views
If $A$ is any infinite set, is $A × A$ equivalent/equinumerous to $A$? [duplicate]
I know the result is true for $\mathbb{N}$ and $\mathbb{R}$ and can even be generalized for $\mathbb{N^n}$ and $\mathbb{R^n}$ where $n \in \mathbb{N}$, but I'm not sure how I can prove this for an ...
- 61
1
vote
1
answer
102
views
Prove $[0,1)$ is of cardinality equal to $(0,1]$
Let $A=[0,1), B=(0,1], C=(0,1)$.
Prove $A$ is of cardinality equal to $B$ by using Glueing Lemma to 'glue together' the identity function id$_C$ and some appropriate bijective function.
I'd like to ...
- 133
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 ...
6
votes
1
answer
216
views
How to rigorously prove that $|A|\neq|A\cup B|$, when $B\not\subseteq A$ and $A$ is finite.
By definition of cardinality, $|X|=|Y|$ if there exists a bijective function $f:X\to Y$.
I would like to rigorously prove that if $A$ is a finite set, then $|A|\neq |A\cup B|$ when $B\not\subseteq A$. ...
- 4,472
-2
votes
1
answer
92
views
Difficulty of countable vs. uncountable sets proof? [closed]
I'm still having trouble understanding why showing there are strictly more uncountable sets than countable ones took as long as it did. It seems like there are no shortage of trivial ways to show this ...
- 6,014
2
votes
0
answers
53
views
Cardinals of $\mathbb{N}$ and $2^\mathbb{N}$ proof
Show that $\mathbb{N}^{\mathbb{N}}$ is equivalent to $2^\mathbb{N}$, where $2^\mathbb{N} = \{f:\mathbb{N} \rightarrow \{0, 1\}\}$.
My attempt:
It suffices to show that the two sets have the same ...
- 1,271
0
votes
1
answer
129
views
Cardinal Arithmetic Property Proof
The following proposition is "obvious" but I am having trouble obtaining a rigorous proof of it:
If the set $X$ is finite and $Y$ is a subset of $X$, then $Y$ is finite and #$(Y)\leq$#$(X)$. ...
- 445
0
votes
0
answers
106
views
Connected component in locally finite graph is countable
I have the following claim which I have been struggling to write a proof for:
Let $G=(V,E)$ be a graph such that $deg(v)<\infty$ for all $v\in V$. Then every connected component in the graph is ...
- 7,805
1
vote
1
answer
142
views
Cardinality of an infinite set of functions
There is a set A:
A = {a,b,c belongs to R | f(x) = ax^2 + bx + c, x belongs to R, a is not 0}
And set C is:
...
- 293
3
votes
2
answers
65
views
Show that $\{x\}^A \approx A$
I need to prove that $\{x\}^A \approx A$, that is, that the set of all functions from a set with a single element (namely, x) to another set A is equipotent to the set A.
Now the reasoning behind ...
- 89
0
votes
1
answer
198
views
Proving a set is uncountable by determining its cardinality
I was working on this problem for class
B is the set of all infinite binary strings. Show B is uncountable.
The given answer uses a diagonal argument similar to the Cantor proof, however that wasn'...
- 3,105
2
votes
1
answer
47
views
Bijection between $ \bigcup_{i \in [0, 1]} X_i \ \ \ \text{and} \ \ \ [0, 1] \times [0, 1] $
So I have got the following sets $$ \bigcup_{i \in [0, 1]} X_i \ \ \ \text{and} \ \ \ [0, 1] \times [0, 1] $$ where each $X_i$ has cardinality $c$ of the continuum and each pair of $X_i$ where $i \in [...
- 81