4
votes
Accepted
Showing permutation does not change output of commutative operation (recursion theorem)
First of all, I don't believe you have sufficient foundation in basic logic to tackle such problems. This is not your fault, naturally, because it is hard to find good teachers. For you to truly grasp ...
- 56k
3
votes
Why is the Cantor Set not a subset of $\mathbb{Q}$?
Let's start with what you know!
So, you know that there is a bijection between all ternary strings with only zeroes and twos and the cantor set. In the proof, what is used is the fact that the Cantor ...
- 121k
3
votes
Accepted
Is this an injection from $\mathbb{R}_+$ to $(0,1)$?
Your proposal is rather unclear, but per your comments it does not give a function with codomain $\mathbb{R}$ at all; this is because things like
[a sequence] of the form 0.0000000000…33333333… where ...
- 236k
2
votes
Accepted
Prove that $d(X,Y) = |X\setminus Y| + |Y\setminus X|$ is a distance
Hint: If $X^c$ denotes the complement of $X$ then:
$|X\setminus Z|=|X\cap Z^c|=|X\cap Z^c\cap Y|+|X\cap Z^c\cap Y^c|.$
And you can similarly decompose $|Z\setminus X|$. Can you find an upper bound for ...
- 36.5k
2
votes
Accepted
Is there reason for concern with this proof that "there is a bijective function from $\{1,...,m\}$ to $\{1,...,n\}$ only if $m = n$"?
In the context of proving a statement like this, you are correct that you should really never be using the notation "Card" as if it were a function. But the proof still works when you ...
- 323k
2
votes
Confused about the measure of the Cantor Set, and how to reconcile this with there being points not at the endpoints
so eventually we will get $\lim_{n\rightarrow \infty} (\frac 2 3)^n = 0$ left, such that nothing remains except the endpoints.
This sentence is where your intuition has led you astray, and led you to ...
- 3,607
1
vote
How can it be that the empty set is a subset of every set but not an element of every set?
Element:
An element x is said to be an element of a set A if x is
contained within the set A. This is denoted as: x ∈ A.
Subset:
A set A is considered a subset of another set B if every
element of ...
1
vote
Accepted
Prove that $C(X \times Y) = A \times C(Y) \cup C(X) \times B$
I think it is implicit that:
the complement of $X$ is meant to be with respect to $A$
the complement of $Y$ is meant to be with respect to $B$
the complement of $X \times Y$ is meant to be with ...
- 4,747
1
vote
Accepted
Confused about this proof of how set of finite binary strings is countable
Actually this is a good question.
Firstly, there is an error in the author's list of binary strings. It should be:
$$
\varepsilon, 0,1,00,01,10,11,000,001,010,011,100,101,110,111, \color{red}{0}000, \...
- 17.8k
1
vote
If $A, B$ and $C$ are sets, then $A - (B \cap C) = (A - B) \cup (A - C)$
You can prove it as shown below.
If $x∈(A−B∩C)$, then $$(x∈A) \wedge (x \notin B \ \text{ or }\ x \notin C)$$
If $x∈(A−B)\cup (A-C)$, then $$[ (x∈A)\wedge(x \notin B)] \quad or \quad [(x∈A)\...
- 11
1
vote
Accepted
Proving $f^{*}(\cup\mathscr{B})=\bigcup (f^*)_*(\mathscr{B})$
The image of $\mathscr{B}$ under the mapping $f^* \colon \mathscr{P}(Y) \to \mathscr{P}(X)$ is
$$
(f^*)_*(\mathscr{B}) = \{f^*(B) : B \in \mathscr{B}\}.
$$
So, another way to write the equality
$$
\...
- 20.1k
1
vote
Accepted
Proving (rigorously) that the number of $m$ element subsets of an $n$ element set is ${n \choose m}$
We are given a set $N$ and a set $M \subseteq N$, and we define $n = \operatorname{Num}(N)$ and $m = \operatorname{Num}(M)$. (With this setup, $m \leq n$.) We define $A_M = \{f \in B(\{1,\ldots,n\},N) ...
- 8,653
1
vote
Accepted
Cantor's diagonalization- why we must add $2 \pmod {10}$ to each digit rather than $1 \pmod {10}$?
In the case of the decimal expansions $0.9999\dots$ and $1.0000\dots$, the first digit after the decimal dot are $9$ and $0$, which are consecutive digits (modulo $10$). So, yes, $0$ is being treated ...
- 420k
1
vote
Accepted
What is the difference between $\in$, $\subseteq$, and $\subset$?
$A\in B$ means that $A$ is an element of $B$. For example $2 \in \{1,2,3\}$, $4\in \mathbb N$, but we can also do that with sets, for example, $\{1\}\in\{\{1\},\{1,2\},\{1,2,3\}\}$. In this case, $B$ ...
- 4,220
1
vote
Accepted
Does this prove $X \times Y$ is countable if $X$ and $Y$ are countably infinite sets?
I suspect your confusion arises from conflating the act of defining an injection $f:X×Y->N$, with the process of actually evaluating $f((x,y))$ at every point of the infinite set.
Your argument is ...
- 671
1
vote
Accepted
Does this prove the union of countably many countable sets is countable?
It seems fine to me. The usual argument is pretty much the same: we assign to each set in the union some $i\in \mathbb N,$ and to each element in each set we assign some $j\in \mathbb N,$ so each ...
- 55.4k
1
vote
Accepted
Associative definition of ordered pairs?
If such definition were posible you'll have the following:
By associativity:
$$((a,b),c)=(a,(b,c))$$
but then, by the defining property of the ordered pairs $$(a,b)=a$$
which is absurd since the LHS ...
- 16.3k
Only top scored, non community-wiki answers of a minimum length are eligible