Tag Info

Hot answers tagged

10

Let $f: A\to A$ be any function. For each $a\in A$, let $N(a)$ be the number of elements in $A$ that are mapped to $a$. Then $\sum_a N(a) = n = |A|$ because every element of $A$ is mapped to some element of $A$. (This is the statement that the fibers of $f$ partition $A$.) If $f$ is surjective, then $N(a)\ge 1$ for all $a$. If $f$ is not injective, then ...


9

To understand the $\aleph$ numbers properly you need to understand the ordinal numbers first, at least a little bit. The idea of an ordinal is to model the notion of a length of a queue to the bathroom in a party. There is an empty queue, then there is one person waiting, then another, and so on. But here we can talk about infinite queues as well. At some ...


6

This is an issue about which mathematicians who haven't studied set theory beyond what they actually use are often confused. $\aleph_1$ is the cardinality of the set of all countable ordinal numbers. $\aleph_2$ is the cardinality of the set of all ordinal numbers of cardinality $\le\aleph_1$. $\aleph_3$ is the cardinality of the set of all ordinal numbers ...


6

The proof isn’t really a proof by contradiction, even though it’s often presented in that language. It’s really a demonstration that there is an algorithm that takes as input any infinite sequence of real numbers in $[0,1]$ and constructs as output a specific real number that is not in that sequence. This shows that no sequence can list all of the real ...


5

Consider the sets $A_r = \{x \in \mathbb{Q}: x < r\}$ for each real $r$.


5

We use mathematical induction to show that $\frac{1}{4}$ and $\frac{3}{4}$ are in $C_n$ for every $n\in \mathbb{N}\cup \{0\}$. Clearly, $\frac{1}{4}$ and $\frac{3}{4}$ are in $[0,1]=C_0$. Suppose $\frac{1}{4}$ and $\frac{3}{4}$ are in $C_n$. We observe the structure of $[0,\frac{1}{3}]$ after $n+1$ cuts is similar to $[0,1]$ after $n$ cuts. Hence if $x \in ...


4

Choose $g_1(n)$, $g_2(n)$ and $g_3(n)$ simultaneously in order of increasing $n$. In a typical step you first choose $g_1(n)$ as the simplest rational not yet hit by $g_1$. Then chose $g_2(n)$ as the simplest rational such that it is not yet hit by $g_2$, and $f(n)-g_1(n)-g_2(n)$ is not yet hit by $g_3$ (this is always possible because only finitely many ...


4

Yes. If $A\in \mathscr P(Y)$ (so $A \subset Y$), then for each $a\in A$ there exists some $x_a\in X$ with $f(x_a)=a$ (because $a\in Y$ and $f$ is surjective). Put $S = \bigcup_{a\in A}\{x_a\}$. Then $S\in\mathscr P(X)$ (because $S\subset X$) and $f(S) = A$. We could also just note that $f(f^{-1}(A))=A$, so the set $f^{-1}(A)$ does the trick. In fact, a map ...


3

Let $f(1) = 1$ and $f(n) = n-1$ for all $n \geq 2$. The function is not injective since $f(1) = f(2)$, but $1\neq 2$. If $n \in \mathbb N$, then $f(n+1) = n+1-1 = n$ so that $f$ is surjective.


3

This is an important point. Formulas, in particular those that appear in the separation axiom schema, are part of the meta-theory. This meta-theory could be some set theory, where the formulas are encoded as sets, or it could be something as weak as some fragment of Peano arithmetic where the formulas are encoded as natural numbers. But in either case, the ...


3

Let's assume the actual question is to find the power set of $S=\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}$. Using Von Neumann's definition of the natural numbers, this is equivalent to finding the power set of $S=\{0,1,2\}$, where $0=\emptyset$, $1=\{0\}$, and $2=\{0,1\}$. The power set is then ...


3

Each of the sets $A$ and $B$ has a single element. For a moment call those elements simply $a$ and $b$ to avoid being distracted by the specific nature of the elements; then it should be clear that the only member of $A\times B$ is the ordered pair $\langle a,b\rangle$. Now let’s go back and recall what $a$ and $b$ actually are: $a=\{5\}$, and ...


3

There are three things to prove: $0$ is in every interval, hence in the intersection of all of them. If $x>0$, then there is at least one interval that does not contain $x$, so $x$ is not in the mutual intersection. (choose $n$ so that $2/n<x$). If $x<0$, then there is at least one interval that does not contain $x$, so $x$ is not in the mutual ...


3

Why should $B$ not be well founded (or rather: properly defined)? The comprehension used to define $B$, i.e. to select elements from a given set by a specific property, is the main method to describe a set. Here, $B$ is the subset of $A$ that consists of precisely those elements o$x$ of $A$ for which the deus-ex-machina property $x\notin x$ holds. (Btw. ...


3

No, it is not possible. In particular, suppose we had sets $S_i$ such that your set was $S_1\times S_2 \times S_3 \ldots$ - that is, it could be written as $$S=\{(x_i)_{i\in\mathbb{Z}^+}\,|\,\forall i\in \mathbb{Z}^+[x_i\in S_i]\}$$ To show that this is impossible, notice that if $x_i$ and $y_i$ were sequences in $S$, any sequence $z_i$ such that, for all ...


3

Think of the Cartesian product of 3 sets. It's the set of ordered triples, $(x_1,x_2,x_3)$, where $x_i\in X_i$ for $i=1,2,3$. That means you can also describe it as the set of functions from $\{1,2,3\}\to \bigcup X_i$, with the restriction that $f(1)\in X_1$, $f(2)\in X_2$ and $f(3)\in X_3$. Just think of the ordered triple $(a,b,c)$ as the function given by ...


2

The example you give actually is a $\sigma$-finite Borel measure. Equip $[0,1]$ with the cofinite topology (in which a set is open iff it is either empty or its complement is finite). Then your $\Sigma$ is the Borel $\sigma$-algebra of the cofinite topology (it is a nice exercise to verify this). However, there is the following result: Proposition. Let ...


2

You are going in the right direction. $\mathcal{P}(A) = \{x | x \subseteq A \}$, so just by replacing the symbols we see $\mathcal{P}(A \cap B) = \{x | x \subseteq A \cap B\}$. So you are being asked to relate $$\{x | x \subseteq A \cap B\}$$ To $\mathcal{P}(A) \cap \mathcal{P}(B)$ which is $$\{x | x \in \mathcal{P}(A) \text{ and } x \in \mathcal{P}(B)\}$$ ...


2

hint: to get from $$ \{x|x⊆A∩B\} $$ to $$ \{x|x∈P(A) \text{ and }x∈P(B)\} $$ The property $$ X\subset Y \iff X\cup Y = Y $$can be useful. solution: $$\begin{align} \{x|x∈P(A) \text{ and }x∈P(B)\} &= \{x|x\subset A \text{ and }x\subset B\}\\ &= \{x|x\cup A = A \text{ and }x\cup B = B\}\\ &= \{x|x\cup A \cup B = A\cup B\}\\ &= ...


2

No, that is the only way to do it. (Your remark on order is true.)


2

HINT: If you just want "uncountably many", then it's easy to observe that each countable ordinal can be expressed as a linear order of $\Bbb N$. However if you want $2^{\aleph_0}$ (which is the maximal number of orders), then given $A\subseteq\Bbb N$, it is possible to use $A$ to define a unique linear order which looks like copies of the rational numbers ...


2

HINTS: For (a) it’s easy to verify that $A_x\subseteq\Bbb R^+$ for each $x\in\Bbb R^+$. For the opposite inclusion remember that $1\in\Bbb Q$, so $x\in\ldots\;$? You’ve the right general idea for (b). As a preliminary step, though, I’d show that if $x\in A_y$, then $A_x\subseteq A_y$. Then go on and suppose that $z\in A_x\cap A_y$. That tells you that ...


2

Here is an answer that works for ordinal numbers, and not just natural numbers or integers. Every member of your set equals $n+n+1$ for some (natural number / ordinal number) $n$.


2

Every number in your set is a positive odd integer, and the $\ldots$ on the right indicate that the set contains every positive, odd integer. We usually represent odd numbers by $2n+1$ where $n \in \mathbb N_0.\;$ $\;(\mathbb N_0$ is being used to mean the set of natural numbers (including $0))$. So we can describe the set using set-builder notation: ...


2

You can certainly define a family of sets indexed by $\{1,\ldots,n\}\times\{1,\ldots,m\}$, and you can write them in a rectangular structure if you have a need to. Nothing at all wrong with this. (And you might well use LaTeX's matrix environments to typeset it). But it probably wouldn't do much mathematical good to call this family a "matrix", unless you ...


2

Yes, the cardinality of the power set $\mathcal P(S)$ of a set $S$ is given by $2^n$, and so in your case, by $2^{15}$. Note: There is a difference between a set, and its cardinality. The power set $\mathcal P(S)$ itself is the set of all subsets of $S$, whereas $2^n$ is the number of these sets (which are the elements) in $\mathcal P(S).$


2

Hint: consider the following 2 facts: the family of functions $\{y=ax: a\in \mathbb{R}\}$ already has the cardinality of the continuum, the cardinality of family of continuous functions is at most the cardinality of $\mathbb{R}$ (since the value at rational points uniquely identify a function)...


2

In the power set of $A$ you get every subset. Note that there are 4 elements in $P(A)$, this implies that $A$ has two elements, since $2^2 = 4$. The only subset of $P(A)$ is $\{x,y\}$ which must be $A$. In fact, if $A$ is finite, the largest element in $P(A)$ (if we look at the cardinality of that element) is $A$ itself


2

Modern set theory conceives of a set as an abstraction of a property. Two properties might seem different, but be essentially the same because they are true of the same objects. For example, the property $\mathcal O_1$ of being a natural number of the form $2n+1$, and the property $\mathcal O_2$ of being a natural number that is the difference of two ...


2

First point: your answer has an "if" but no "then". It therefore is ungrammatical, makes no sense, and cannot possibly be the right answer. Second point: you can do this by symbolic logic if you want, but why? IMHO it merely adds extra work. (That's in this case: in a more complicated question it might be a good idea.) The negation of "if $P$ then $Q$" ...



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