Hot answers tagged

12

Let me outline a proof. As previously stated in a comment, the only nontrivial part is to actually define what $\Bbb R$ is. In set theory, it is common to just let $\Bbb R := \mathcal P(\omega)$ and in this case, we immediately have that $\Bbb R \in U$. However, this definition is not very common amongst non-set theorists, and I shall therefore outline a ...


11

In fact, $\mathbf{P}=\mathbf{NP}$ is an arithmetical statement. What logicians mean by that is that it can be expressed (or, more precisely, a statement "fairly trivially" equivalent to it can be expressed) using only the language of first-order arithmetic, that is, as a formal statement built from {atoms of the form $s=t$ where $s$ and $t$ are expressions ...


5

Well, it depends on what are the real numbers for you. Set theory and logic are very implementation agnostic when it comes to "everyday mathematics". Nobody cares what is the set $1_\Bbb R$, just that we can find a construct in which this set exists and behave as expected. So for the sake of argument, let's take the usual construction: The natural numbers ...


5

No, in general the maps $f$ and $g$ need not be bijective. Simple counterexample: Let $A=\mathbb N$ and $B=\{2n:n\in\mathbb N\}$. Then you can take say $f(x)=4x$ and $g(x)=x/2$. Both are injective, but $f$ is not bijective.


4

No, the Schroder-Bernstein theorem only tells you that there exists a different map $h$ which is a bijection, not that $f$ and $g$ are bijections. For instance, suppose $A=[0,1]$ and $B=[0,2]$. You can take $f(x)=x$ and $g(x)=x/4$, and then $f:A\to B$ and $g:B\to A$ are both injections. Neither $f$ nor $g$ is a bijection however; Schroder-Bernstein just ...


4

$\mathbb{Z}$ is usually constructed is such a way that its elements form a partition of $\omega\times\omega$. So $\mathbb{Z}\subset\wp\left(\omega\times\omega\right)$ hence $\mathbb{Z}\in\wp\left(\wp\left(\omega\times\omega\right)\right)\in U$ and consequently $\mathbb{Z}\in U$. $\mathbb{Q}$ is usually constructed is such a way that its elements are ...


4

Note that $A\cap B\subseteq A,B\subseteq A\cup B$ so equality at the ends gives equality throughout.


4

If $Y$ is just an arbitrary set containing $X$, then you can equip $Y \setminus X$ with any metric you like (say, a discrete one) and join the spaces via some distinguished element. Let $d''$ be a metric on $Y \setminus X$ and let $x_0$ and $y_0$ be any elements of $X$ and $Y \setminus X$ respectively. Then $$ d'(\alpha,\beta) = \begin{cases} ...


3

Perhaps I will write something wrong? (This seems easy to me). First of all, I think you mean there can't exist an injective function $f:I_m\to I_n$, for if $n<m$ there actually exists an injective $I_n\to I_m$ (the inclusion). Suppose $n<m$ and $f:I_m\to I_n$ injective. Then $f:I_m\to f(I_m)$ is bijective, where $f(I_m)=\{f(1),...,f(m)\}$. Clearly ...


3

Suppose $A\not\subset B$, then there exists an $a\in A$ such that $a\notin B$. Hence $a\notin A\cap B$. Thus $A\cap B\neq A$. Conversely, if $A\cap B=A$ then $A\subset A\cap B$, so for each $a\in A$ we have that $a\in A\cap B$, which implies that $a\in B$. Thus $A\subset B$.


3

HINT: If $C_\alpha\cap \xi$ is unbounded (or even nonempty) in $\xi$, then some element of $\xi$ must be bigger than $\alpha$. What does that say about $\xi$ and $\alpha$? That is: think about what "$\kappa\setminus \alpha$" looks like in terms of the ordering on the ordinals.


3

This is a good example where intuition about a pattern breaks down; what is true of finite sets is not true of infinite sets in general. The natural numbers $\textit{cannot}$ be denoted by the set $A=\{1,2,...,\aleph_0\}$ as the set $\aleph_0$ is not a natural number. It is true that the cardinality of $A$ is $\aleph_0$ (a good exercise), but it contains ...


3

Your error is when you write "which clearly implies . . ." You seem to assume, there, that taking an intersection of a smaller collection of sets results in a smaller set. But the opposite is true in general: if $J\subseteq I$, we have $\bigcap_{k\in J}V_k$ is bigger (well, can be bigger - certainly is no smaller) than $\bigcap_{k\in I}V_k$! For example, ...


2

If by strictly ordered you mean linearly ordered (or totally ordered), then easily the answer is yes. $\Bbb R$ is a linearly ordered set with cardinality $2^{\aleph_0}>\aleph_0$. If by strictly ordered you mean well ordered, so every non-empty set has a minimum, the answer is also yes. Hartogs' theorem ensures that given any set $X$, there is a ...


2

Good question! You are free to include aleph null in your set, but it still contains an infinite set of natural numbers. So you can't count up to it. What you have is $$\{1,2,\ldots,\text{ an infinite list of numbers },\ldots , \aleph_0\}$$


2

For all finite sets with cardinality say $n$, the cardinality of its power set is given by $2^n$. Hence for B, the power set of B has $2^3=8$ elements. To find the number of elements in $\mathcal P(\mathcal P(B))$, we apply the formula one more time to get $2^8=256$.


2

If a pair $(x,y)$ belongs to the left-hand side set, then $(x,y)\in A_i\times B_i$ and $(x,y)\in C_j\times D_j$, for some $i$ and $j$. In particular $x\in A_i\cap C_j$ and $y\in B_i\cap D_j$, so the pair also belongs to the right-hand side set. Suppose $(x,y)$ belongs to the right-hand side set. Then, for some $i$ and $j$, $(x,y)\in (A_i\cap ...


2

Let $x \in A - (B \cap C)$. Hence, $x \in A$ and $x \notin B\cap C$. Suppose $x \notin B\cap C$. Hence $x \notin B $ or $x\notin C$. $x \in A$ and $x \notin B $ then $x \in (A - B)$. $x \in A$ and $x \notin C $ then $x \in (A - C)$. Hence $x \in (A - B) \cup (A - C)$ by definition.


2

The conversation seems almost equivalent to this hypothetical one: ME: Suppose there are positive integers $m$, $n$ such that $m^2=2n^2$. Then we can generate a list of all prime factors and read off the exponent of $2$. This exponent should be even (because it is in the unique factorization of $m^2$) but also odd (because it is in the unique factorization ...


2

First have a look at my comment on your question. In this answer I focus on special case $M=\varnothing$. Find the minimal number of subsets of $\left\{ 1,\dots,n\right\} $ with cardinality $r$ such that there intersection is empty. Thinking of their complements this can be rephrased as: Find the minimal number of subsets of $\left\{ 1,\dots,n\right\} $ ...


2

Answer on "how do I prove it?" If $a\in A$ is an upper bound of $A$ then any $c$ with $c<a$ is not an upper bound of $A$ since $a$ is an element of $A$ that does not satisfy $a\leq c$. We conclude that $a$ must be the least upper bound of $A$. $1\leq1+\frac{1}{n}$ for each $n$ so $1$ is a lower bound of $A$. If $c>1$ we can find an element ...


2

We can define the successor function on the class of all sets. In fact, we may define $S \colon V \to V, x \mapsto x \cup \{x\}$, where $V$ is the proper class of all sets. Note that this can be done within ZFC: While $S$ does not exists as an object in ZFC, we have that $S = \{ (x, x \cup \{x\}) \mid x \in V \}$ is a definable class and those can be ...


2

$C$ is a subset of $\mathbb{N}$ since $n+n \in \mathbb{N}$ for any $n \in \mathbb{N}$. $C$ is a proper subset of $\mathbb{N}$ since, for example, $1 \not \in C$. But $C$ and $\mathbb{N}$ have the same cardinality since $f$ is one-to-one and onto. Hence they are both infinite sets. I brushed over the details here. They are up to you to fill in.


1

No, that's not right. First of all $f$ is not a function. $(1,2)$ and $(1,4)$ are both elements of $f$, which means that $f$ is not a function. What you defined is essentially $\leq$ again. The goal is to define a function which takes an element and returns a set. So you need to ask yourself what sort of set you can associate each element that will tell ...


1

$\text{“}E_i$ and $F_i$ are disjoint$\text{''}$ could be construed to mean $E_i\cap F_i=\varnothing$, and that is not true. It is true that $E_1,E_2,E_3,\ldots$ are pairwise disjoint. Suppose $x\in\bigcup_i F_i$. Then there is some smallest index $i_0$ such that $x\in F_i$. For that smallest index $i_0$ we have $x\in E_{i_0}$; therefore $x\in\bigcup_i ...


1

This holds even without nested condition on $B_n$. \begin{align} \bigcup_{n=1}^{\infty}A_n&=\bigcup_{n=1}^{\infty}(B_1-B_n) \\ &=\bigcup_{n=1}^{\infty}(B_1\cap B_n^c) \\ &=B_1\cap\bigcup_{n=1}^{\infty}B_n^c \\ &=B_1\cap\left(\bigcap_{n=1}^{\infty}B_n\right)^c \\ &=B_1-\bigcap_{n=1}^{\infty}B_n \end{align}


1

You are correct. You could also say that $\emptyset \subseteq \Bbb{R}$ and every $\sigma$ algebra contains $\emptyset$. However, if $A\neq \Bbb{R}$ and $A\neq \emptyset$ then just consider the trivial $\sigma$ algebra $\{\Bbb{R},\emptyset\}$.


1

Besides the most basic "operational" topics, I don't think any standard for teaching set theory exists yet. As soon as you starts really "doing set theory" things become non-trivial and not very accessible for undergrads. For weak evidence about this, here is my experience: when I was finishing my third year in my undergrad program (after measure theory ...


1

Another counter-example: suppose $C\subset B$. Then $$A-(B-C)=(A-B)\cup(A\cap C)\quad\text{while}\quad (A-B)-C=A-B.$$ Actually, in the general case, $(A-B)-C=A-(B\cup C)$.


1

Assuming you are only talking about countably infinite sets, you can first say that there exists a bijection between $A$ and $ \mathbb N$: $f: A \to \mathbb N$ Since $ |A| = |B|$, we also have a bijection between $A$ and $B$, so write: $g : B \to A$ Use the fact that the composition of bijective maps is bijective too and you have: $ f\circ g : B \to ...



Only top voted, non community-wiki answers of a minimum length are eligible