# Tag Info

## Hot answers tagged elementary-set-theory

10

We write $A^B$ as the set of all functions $f\colon B\to A$. Namely $f$ is a function whose domain is $B$ and takes values in $A$. In this case $A=\{0,1\}$ and $B=\Bbb N$. So this is the set of all functions from $\Bbb N$ into $\{0,1\}$. If we think about those as indicator functions then we have a natural way of thinking about $2^\Bbb N$ as the power set ...

7

The set $A$ is the union of the two disjoint sets $A\cap B$ and $A-B$, so $|A|=|A\cap B|+|A-B|$. Now, if only we could show that $|B|=|A\cap B|+|B-A|$ . . .

6

Another possible method: How many subsets of $\{1,2,3,4,5,6,7,8,9,10\}$ are there in total? Call this number $n$. How many subsets contain both 2 and 7? This is the same as the number of subsets of $\{1,3,4,5,6,8,9,10\}$. Call this number $m$. Then your solution is $n - m$.

5

Yes, we can always partition an infinite set to countable subsets. But the partition itself is not going to be finite, and certainly not countable. Namely, if $T$ is uncountable, and $T=\bigcup_{i\in I}A_i$ where each $A_i$ is countable, then $I$ is necessarily uncountable. In fact we can prove that $|I|=|T|$. Similarly, you can partition every set into ...

5

A power set $\mathcal P(S)$ of a set $S$ is sometimes denoted $2^S$. If $S$ is a finite set with $|S| = n$ elements, then the number of subsets of $S$ is $|\mathcal P(S)|=2^n$. This is the motivation for the notation $2^S$.

4

It's easy to get bogged down with the details here. But the simplest way would be to find a bijection between $A$ and $B$. We are given that $|A-B|=|B-A|$, therefore there is a function $f\colon (A-B)\to (B-A)$ which is a bijection. Can you think of a way to extend $f$ to be a bijection between $A$ and $B$?

4

The relation cannot be reflexive. $(X, X)\in R$ if and only if both the following statements are true: $$X\subseteq X\tag{1}$$ $$X \neq X\tag{2}$$ $(1)$ is true for all $X \in \mathcal P(A)$. $(2)$ is false for all $X \in \mathcal P(A)$. Hence, for all $X \in \mathcal P(A)$, $(X, X) \notin R$.

4

Yes, indeed, you are correct. The relation is not symmetric, and for the reason you post. $$(X\subseteq Y\; \text{ AND }\;Y\subseteq X) \iff X=Y$$ Hence, since $(X, Y)\in R \implies (X\subseteq Y$ and $X\neq Y$), it cannot be the case that $Y \subseteq X$.

4

The axiom of choice is absolutely not needed here. We only need to choose one element from $b$, since it's not empty we can do it. And the axiom of choice is not needed. Then simply map everything not in $B$ to $b$, while keeping the rest in place. This is similar to the problem of inversing functions. The axiom of choice is needed in order to construct an ...

4

Hint: How many subsets are there containing neither $2$ nor $7$? How many subsets are there containing $2$ and not $7$? How many subsets are there containing $7$ and not $2$? For the second one, any subset must be a union of $\{2\}$ and any subset of $\{1,3,4,5,6,8,9,10\}$. Can you say something similar for the other two?

3

There's something I don't find intuitive about using set operations like 'union' and 'intersection' on functions. The short answer to this is that there isn't really an intuitive way to understand union applied to functions. To use set theoretic operations on functions absolutely requires a detour through the definition of a function as a set of ordered ...

3

Let's say $0$ instead of $\emptyset$ and $1$ instead of $\{\emptyset\}$. We know that $0 \neq 1$. If $(a,b)=(c,d)$ (using normal parentheses because they're easier to type) that means $\{\{0,a\},\{1,b\}\} =\{\{0,c\},\{1,d\}\}$ by definition. If $a \neq 1$, then there's only one set on the left side containing the element $1$, so there can only be one on ...

3

Your question has two parts which are really unrelated. Every set of sets has a union, that is the axiom of union. From this follows that every set of ordinals has a supremum, its union. Then you ask on something which is very much not a set of ordinals $\{V_\alpha\mid\alpha\in\rm Ord\}$. Standard arguments show that $V$ is not a set, therefore this ...

3

By the definition of $|K_0|=|K_1|$ there is a bijection between the two sets. You can use this two construct a bijection between between $K_0!$ and $K_1!$ (by conjugating permutations of $K_1$ by a fixed bijection between $K_0$ and $K_1$).

3

No. It's not possible. Simply note that if $\{A_i\mid i\in I\}$ is a family of pairwise disjoint and non-empty sets, then $A_i\mapsto\min A_i$ is an injection into $\Bbb N$.

3

It should be clear that $\operatorname{cf}(\alpha)\leq \alpha$ for all $\alpha$, so specifically $\operatorname{cf}(\operatorname{cf}(\alpha))\leq \operatorname{cf}(\alpha)$. Let's assume $\gamma = \operatorname{cf}(\operatorname{cf}(\alpha)) < \operatorname{cf}(\alpha) = \beta$. Then what you have above shows that you can construct a cofinal sequence ...

3

HINT: If $S$ is an infinite set and $R$ is a well-ordering on $S$, then $R$ has an initial segment isomorphic to $\omega$. If $S$ is infinite, note that $R$ has an initial segment of order type $\omega$, therefore this is an infinite decreasing sequence in $R^{-1}$, so it is not a well-order. Incidentally, the axiom of choice is equivalent to the ...

2

I'll flesh out the details for you. Write $\beta = \mathrm{cf}(\alpha)$ and $\gamma = \mathrm{cf}(\beta)$. Certainly $\gamma \le \beta$ since $\langle \zeta : \zeta < \beta \rangle$ is a cofinal sequence in $\beta$ of length $\beta$, so it suffices to prove $\gamma \ge \beta$. Let $\langle \alpha_{\xi} : \xi < \beta \rangle$ be a cofinal sequence in ...

2

$F$ is non-empty. Then there is a set $A_1 \in F$. Now as per the conditions there is a propoer subset $A_2 \subset A_1$ such that $A_2 \in F$. You can continue to induct that there is a sequence $A_1, A_2, ...A_n, ..$ such that each of them are elements of $F$. Or proceed by contradiction. Suppose there are but a finite number of elements in $F$. Say, $F ... 2 Order$F$by inclusion. Then it has no minimal element. That makes it possible to construct a infinite chain. So$F$must be infinite. Start with some$A_1\in F$. Then find$A_2\in F$as a proper subset of$A_1$. Repeat this. 2 Note that we can remove the negation because this is an if and only if. Therefore this is the same as saying$a\mathrel{R}b\iff b\mathrel{R}a$. This property is called symmetry, and such$R$is called a symmetric relation. 2 Axiom of choice implies König's theorem which estimates cardinality of the product from below, namely$|\prod_{i\in I}A_i|\geq|\sum_{i\in I}A_i|$, the sum stands for the disjoint union. In particular, the product has at least as many elements as any of the factors, which is stronger than just non-empty. However, if$I=\mathbb{N}$and$A_i=A$"every ... 2 First of all,$A$might not be countable.$A$is just an arbitrary set. So it isn't necessarily enumerated by the integers; in fact Cantor's theorem holds without even appealing to the axiom of choice, so it should hold for sets which cannot be enumerated by any ordinal anyway. Secondly,$B$as given is a subset of$A$. And$f$is a function taking$x\in A$... 2 First, state the principle of transfinite induction in the case that$X = \mathbb{N}$. If$\mathbb{N}$is a well-ordered set,$S \subset \mathbb{N}$, and$s(x) \subset S \implies x \in S$(where$s(x)$is the set of natural numbers less than$x$), then$S = \mathbb{N}$. To show this is equivalent to standard induction, you need to show the conditions ... 2 Let$A$be the set of infinte subsets of$\mathbb R$. We have an injective map$\mathcal P(\mathbb R)\to A$given by$X\mapsto \{\,e^x\mid x\in X\,\}\cup [-1,0]$, hence$|A|\ge |\mathcal P(\mathbb R)|>|\mathbb R|$by Cantor. 2$f$is continuous and $$\bullet\lim_{x\to-\infty }f(x)=-\infty$$ $$\bullet \lim_{x\to\infty }f(x)=+\infty.$$ By the intermediate value theorem,$f(\mathbb R)=\mathbb R$, then$f$is surjective. An other way to show the injectivity, is to remark that $$f'(x)=5x^4>0$$ for all$x\in\mathbb R\backslash \{0\}$, then the function is strickly increasing on ... 2 Recall that a function is just a set of ordered pairs with a particular property. So the union and intersection of functions are also sets of ordered pairs. Whether or not these are functions require us to verify the functional property. So we ask ourselves: Suppose that$(x,y)$and$(x,z)$are both in$f\cap g$. Can we necessarily conclude that$y=z$? ... 2 Let $$\mathcal{D} := \{A \in \sigma(\mathcal{C}); \mu(A)=\lambda(A)\}.$$$\emptyset \in \mathcal{D}$: This follows obviously from the fact that$\mu(\emptyset) = \lambda(\emptyset)=0$. Let$A \in \mathcal{D}$. By assumption, we can choose a sequence of sets$(G_n)_n \subseteq \mathcal{D}$such that$G_n \uparrow \Omega$,$\mu(G_n)=\lambda(G_n)<\infty$... 2 Hint: Let$S' = \lbrace 1,3,4,5,6,8,9,10\rbrace$. How many subsets does$S'$have? Call$n$that amount. To any of those subsets, you can add$\lbrace 2\rbrace$or$\lbrace 7\rbrace$or neither to have any of the desired subsets. So you have$3n$subsets of$S$that don't contain$2$or$7\$.

2

I'm guessing you are a beginner and hence are expecting a rudimentary explanation. At this level I don't know if you've realised the need to define what natural numbers actually are. I mean it is easy enough to accept them as counting numbers initially. But in formal set theory and laying the foundations for Analysis we do try to develop the natural numbers ...

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