Tag Info

Hot answers tagged

5

Hint: For a function $f : A \to 2$ and an element $a \in A$, either $f(a) = 0$ or $f(a) = 1$. For a subset $B \subseteq X$ and an element $a \in A$, either $a \in B$ or $a \not \in B$. How might you match up functions $A \to 2$ with subsets of $A$? Bigger hint: (hover mouse over grey box to see)


5

Note that $\Bbb N^k$ is countable, for every finite $k$. Therefore the limit is $\aleph_0$, because the sequence is essentially constant. On the other hand, $\Bbb{N^N}$ is uncountable. Cardinal exponentiation is not continuous. (Note by the way, that $\infty$ from calculus is not quite compatible with infinite products in cardinal arithmetic.)


4

In ZFC set theory, everything is a set, and in order to speak about numbers you need to chose some set to represent each number. The most commonly used representation of the natural numbers is to choose to represent the number $n$ by the set $\{0,1,\ldots,n-1\}$. Under this representaion (the Von Neumann ordinals), the number $0$ is represented by the ...


4

It is always the case that $f[A\cap B]\subseteq f[A]\cap f[B]$. If $y\in f[A\cap B]$ then there is an $x\in A\cap B$ such that $f(x)=y$. It follows that $f(x)\in f[A]$ and $f(x)\in f[B]$. However, it is not always the case that $f[A\cap B]\supseteq f[A]\cap f[B]$. If we look at your purported proof, the error is in the first inference (working from the ...


4

A poset is not to be confused with the Cartesian product of two sets $A, B$. It is set under an ordering relation, and it is this relation that is a subset of $A\times B$ (if and only if $A = B$) which must satisfy the three properties (reflexivity, antisymmetry, and transitivity) to be deemed an ordering relation. Note, e.g., that $(3, 3) \notin A\times ...


4

A set is just a collection of mathematical objects, it doesn't matter if they aren't well ordered. Imagine you have a bag full of oranges, of different sizes, is it necessary to arrange those oranges by size in order for it to be called a collection of oranges? And so, you can simply write: ...


3

Let $$f:x\mapsto x^2$$ and $$A=(0,\infty)\quad;\quad B=(-\infty,0)$$ then we have $$f(A\cap B)=\emptyset\subset f(A)\cap f(B)=(0,\infty)$$ Edit In your proof you have two mistakes: The first by writing $$f(x)\in f(A\cap B)\Rightarrow x\in A\cap B$$ but in my counterexample we have $f(-1)=1\in f(A)$ and $-1\not\in A=(0,\infty)$. The second by writing ...


3

If you don't care about a constructive bijection: There is a clear injection from $\mathbb{N} \to \mathbb{Q}_+$. If we can show that there is a surjection $\mathbb{N} \to \mathbb{Q}_+$, then this shows (Cantor-Bernstein) that they have the same cardinality. To construct our surjection, we note that there is a surjection $\mathbb{N} \times \mathbb{N} \to ...


3

In $\sf ZFC$, as said, every object in the universe is a set. Including the objects we use to represent the natural numbers with. Note, by the way, that this is not a very peculiar idea. We use Dedekind cuts to represent real numbers. In that case $\{1_\Bbb R,2_\Bbb R,3_\Bbb R\}$ is a set of subsets of the rational numbers, and their union is actually ...


3

There are enumerations with and without this property. The first claim is easy (just let $q_n=\frac1{n^2}$ for odd $n$ and enumerate the rest among the even indices somehow). To enumerate $\mathbb Q\setminus\{0\}$ such that $|q_n|>\frac 1n$ for all indices $n$, start with any enumeration $p_n$ of $\mathbb Q\setminus\{0\}$ and recursively define $q_n$ as ...


3

$$\bigcup_{i\in I}(\bigcap_{j\in J}[A_i-B_j])=\bigcup_{i\in I}(\bigcap_{j\in J}[A_i \cap B_j^c])=\bigcup_{i\in I}A_i \cap(\bigcap_{j\in J} B_j^c)=\bigcup_{i\in I}\left[A_i -(\bigcup_{j\in J}B_j)\right]$$ $$=\bigcup_{i\in I}A_i -(\bigcup_{j\in J}B_j)$$ Edit (proof second to third equality): $$\bigcap_{j\in J}[A_i \cap B_j^c]=A_i \cap(\bigcap_{j\in J} ...


2

As usually, when these problems my advice is to use placeholders for the actual sets, and analyze this step by step. Let's set $a=\{\varnothing\}$ and $b=\{\{\varnothing\}\}$ and $c=\bigcup b$. We are asked, if so, to find out $\mathcal P(c)$. What is this set? It's the set $\{x\mid x\subseteq c\}$. So first order of business is to understand what is $c$. ...


2

The function is called the empty function. The empty function $f:\emptyset \to A$ doesn't map $\emptyset$ to anything, since $\emptyset\notin \emptyset$. There is nothing in $\emptyset$, so $f$ doesn't map anything anywhere. Why is it unqiue? Well, suppose we have a function $g:\emptyset\to A$. Then trivially $g(x)=f(x)$ for all $x\in \emptyset$ (since ...


2

When we write $\{u\mid\varphi(u)\}$ then $u$ is a free variable in $\varphi$. If you are given $y$, then $y$ is no longer a free variable, range over all possible values. So it should be written as $\{(x,y)\mid x\in A\}$, and just make sure that the reader understands that $y$ is given and fixed. What you wrote, $\{(x,y)\mid x\in A\land y=z\land z\in A\}$ ...


2

Cosider the constant function $f\colon \mathbb N\to\mathbb N$ given by $f(n)=42$. Let $S=\{1,2,3\}$ and $s=4$. Then $f(s)=42$, $f(S)=\{42\}$, i.e. $f(s)\in f(S)$, but $s\notin S$. For the other direction, if $s \in S$, then by definition $f(s)\in\{\,f(s):s\in S\,\}$ - this is precisely what the notation implies!


2

See Axiom of union : Given any set $A$, there is a set $B$ such that, for any element $c$, $c$ is a member of $B$ if and only if there is a set $D$ such that $c$ is a member of $D$ and $D$ is a member of $A$. In symbols : $\forall A \exists B \forall c(c \in B \leftrightarrow \exists D(c \in D \land D \in A)$. In your example : $A= \{ ...


2

Your friend's argument relies on changing the $a_i$, $a_{ij}$, $a_{ijk}$, etc. for each irrational number. Even if these are chosen from some fixed countable collection (such as the rationals), there are uncountably many different ways to choose these infinitely many terms, so this has no bearing on the number of terms. Your reasoning is correct. For each ...


2

In axiomatic set theory we don't "define elements". Everything1 is an element, and everything is a set. There is no issue with sets being elements of other sets, if you consider the power set of $A$, it's a set and all its elements are sets themselves. Axiomatic set theory says what are the properties of the $\in$ relation, and what sets we can prove to ...


2

There is not much to apply. But we have to be careful and see that we apply theorems only to objects which we proved to satisfy the conditions required for the theorem. We want to prove that $S$ is denumerable. We already know the following things. $\Bbb{N\times N}$ is denumerable. An infinite subset of a denumerable set is denumerable. So in order to ...


2

Your proof has some problems. You haven't defined $A$. I suppose it should denote some subset of $[0,1]$. If $A$ is a subset of $[0,1]$ then it's not the case that $[0,1]\in A$. Perhaps you meant $[0,1]\setminus A$? The idea is that $A$ can be "easily described" as a sequence $a_n$ for $n\in\Bbb N$, preferably such that $a_0=0$ and $a_1=1$. Then you can ...


2

I'll just point out that when you write $2^{\mathbb N^{\mathbb{N}}}$ , there is a certain ambiguity to it. To make sure that it is clear what you have in mind, you should write $(2^{\mathbb N})^{\mathbb{N}}$. (This is what you have used here.) The other possible meaning is $2^{(\mathbb N^{\mathbb{N}})}$. In fact, when someone writes $a^{b^c}$, they ...


2

Assuming you have experience with cardinal arithmetic, the following show that its size is the cardinality of the continuum: First, $\mathbb{C}\cong \mathbb{R}\times \mathbb{R}$. Thus, $$|\mathbb{C}|=|\mathbb{R}\times \mathbb{R}|=|\mathbb{R}|\cdot |\mathbb{R}|=\max\{|\mathbb{R}|,|\mathbb{R}|\}=|\mathbb{R}|$$ Next, we know that $|\mathbb{R}|=2^{\aleph_0}$ ...


1

If you use $\mathbb{Z}$ only in context of size, i.e. $|\mathbb{Z}|$ then yes, you can swap it with $\mathbb{N}$, because $$|\mathbb{Z}| = \aleph_0 = |\mathbb{N}|.$$ However, generally, you cannot swap it. If the simple example $(2-3) \in \mathbb{Z}$ does not convince you, consider the set of strictly decreasing sequences: \begin{align} A_\mathbb{Z} &= ...


1

There are $\binom{n}{2}$ ways to choose $2$ (distinct) numbers $a$ and $b$ in $S$. (Note that this is the number of "hands" of $2$, and not a set of ordered pairs.) For any such distinct numbers $a$ and $b$ we can say Yes if $(a,b)$ and therefore $(b,a)$ will be in our set, and No if $(a,b)$, and therefore $(b,a)$, will not be in our set. So we have ...


1

This is not a real answer but more an alternative proof. If it is useless in this context then please let me know. In that case I will delete the answer. If $g\circ f=id$ then $g$ is surjective since $g\left(f\left(a\right)\right)=a$ for each $a\in A$. So if $g$ is injective as well then it is bijective (i.e. isomorphic in the category of sets) and, as its ...


1

This is one of those cases where the proof strategy is just to write down your conclusion and your premise, and at every step just write down the first thing you can do with the tools you are given. Always start by writing down the premise: Suppose that $g \circ f = id$ and $f$ is onto. We would like to show that $g$ is one-to-one, which means ...


1

$1$. Show that $S = (S \cap T) \cup (S-T)$ and $T = (S \cap T) \cup (T-S)$. $2$. Show that $(S \cap T)$, $(S-T)$ and $(T-S)$ are disjoint. $3$. Hence, $\left \vert S \right \vert = \left \vert S \cap T \right \vert + \left \vert S-T \right \vert$ and $\left \vert T \right \vert = \left \vert S \cap T \right \vert + \left \vert T-S \right \vert$ $4$. Now ...


1

From the same article on Wikipedia: A collection F of subsets of a given set S is called a family of subsets of S Here, $A_1, A_2, ..., A_4$ are each an arbitrary subset of S. F is a collection of subsets of S. This does not mean F should have the same number of members. The term "collection" is used here because, in some contexts, a family of ...


1

I think you're getting a little too bogged down in the details. The basic idea is that the sets $$A_0=\{a_0,a_1,a_2\ldots,a_n,\ldots\}\text{ and }A_1=\{a_1,a_2,a_3\ldots,a_n,\ldots\}$$ have the same cardinality, where $\{a_0,a_1,a_2\ldots\}$ is any sequence of distinct numbers. So $$B\cup A_0\text{ and }B\cup A_1$$ have the same cardinality, where $B$ is any ...


1

Order the algebraically independent subsets of $\mathbb{C}$ by inclusion. The union of a chain of algebraically independent subsets of $\mathbb{C}$ is algebraically independent. Thus by Zorn's Lemma there is a maximal algebraically independent subset $I$ of $\mathbb{C}$. The set $I$ cannot be countable, since the algebraic closure of a countable subset of ...



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