# Tag Info

8

The key is that it's different by construction, which means that you're choosing the digits of $s$ specifically so that it will be different from every other item in the list. Compare $s$ to $s_1$: you see right away that they are different because the first digit is different. Now compare $s$ to $s_2$: they are different at the second digit. The same holds ...

5

Basically, the diagonalizing method is to take every possible number one at a time and say "I can make a number that is different than this and different than any number so far". !!*!IF!!!* the resulting number did exist in the list then you would have come across it and you would have said "I can make a number different than this" and you would have, so ...

5

The problem is not in choosing one particular $\overline x$. To "choose" means to prove it exists, and equivalence classes are non-empty, so such an $\overline x$ definitely exists. The problem is in choosing one for every equivalence class simultaneously, that is, to define a function $f:E/\mathcal{R}\rightarrow E$ such that $f([x])=\overline x \Rightarrow ... 5 This theorem, in fact, is provable in ZF. To see this, let$\alpha_i,i\in I$be a set of ordinals. If we take union$\bigcup_{i\in I}(\alpha_i+1)$, we will get an ordinal$\beta$greater than all of$\alpha_i$. But now$\{\alpha_i\}_{i\in I}$is a subset of$\beta$, and$\beta$is by definition well-ordered. Finally, every subset of a well-ordered set is ... 5 What happens if$X=Z=\{1\},Y=\{1,2\}$and$f:X\to Y$is defined by$f(1)=1$and$g:Y\to Z$is defined by$g(1)=g(2)=1$? 4 For each irrational number$\alpha$, consider the function$f:\mathbb{Q}\to\mathbb{R}$given by$f(x)=0$if$x<\alpha$and$f(x)=1$if$x>\alpha$. This is an element of$A$, and gives an injection from the set of irrational numbers into$A$. Since there are uncountably many irrationals, this means$A$is uncountable. (This answer assumes$f^2=f$... 4 This is definitely not true. The easiest example is a constant function.$f(x,y)=c$for all$(x,y)\in\Bbb R^2$. For a less trivial example, consider$f(x,y)=x^2+y^2$. Here$f(\Bbb R^2)=[0,\infty)$. 4 That is false in general; consider the map$f: (x,y) \mapsto \sin x: \Bbb{R}^{2} \to \Bbb{R}. 4 No. There are an infinite number of finite sets. Consider \begin{align} \{&1\}, \\ \{&1,2\},\\ \{&1,2,3\}, \\ \;\;&\vdots\\ \{&1,2,3,\dotsc,n\}, \\ \;\;&\vdots\\ \end{align} In this list there is exactly one finite set for every integer. Since there are an infinite number of integers, this is an infinite list of finite sets. 4 As mentioned above, countably infinite formally means a bijection (one to one and onto mapping) to the naturals exists, but I wanted to offer a personal response to "Why distinguish between countably infinite and uncountably infinite?" Well, we don't always distinguish between the two. For example if you were answering a question in elementary linear ... 3 I think one surprising consequence is that we tend to think of transcendental numbers like\pi$and$e$as being incredibly rare. (After all, how many can you name?) However, all but countably-many real numbers are transcendental. It is the algebraic numbers that are rare. In fact, the algebraic numbers account for precisely$0\%$of the real numbers. You ... 3 idea: You should start with$(x,y) \in A \times (B/C)$. By definition this means$x \in A$and$y\in B/C$. This implies$(x,y) \in A \times B$And$(x,y) \not\in A \times C$. Consequently $$(x,y) \in (A \times B)/(A \times C)$$ Now try the other set containment. 3 You are correct that the statement is not true. This is also evident from the following Venn diagram: 3$\forall A(A\notin\mathcal{G}\lor x\notin A)$is exactly equivalent to$\forall A\in\mathcal{G}(x\notin A)$. Note that$A\notin\mathcal{G}\lor x\notin A$is logically equivalent to$A\in\mathcal{G}\to x\notin A$, and both $$\forall A(A\in\mathcal{G}\to x\notin A)$$ and $$\forall A\in\mathcal{G}(x\notin A)$$ simply say (a) that no member of$\mathcal{G}$... 3 Let us forget temporarily about the "proper" subset restriction on$B$. So we want to divide$X$into$4$pairwise disjoint parts,$A_1,A_2,A_3,A_4$, and then let$A=A_1$,$B=A_1\cup A_2$, and$C=A_1\cup A_2\cup A_3$. Given such a partition of$X$, there is an associated function$f:X\to\{1,2,3,4\}$given by$f(x)=i$if and only if$x\in A_1$. And given ... 3 Two sets$A, B$have the same cardinality (the same 'size') if there is a bijection$A \to B$. That is, a one-to-one correspondence between the elements of$A$and the elements of$B$. The famous 'diagonalization' argument you are giving in the question provides a map from the integers$\mathbb Z$to the rationals$\mathbb Q$. The trouble is it is not a ... 3 Here's a straight application of simple induction (not strong induction), twice: We want to prove$P(m,n)$by induction over$n$. Thus we need to prove$P(m,0)$and$P(m,n)\to P(m,n+1)$. But in order to prove$P(m,0)$we use induction over$m$, so we need to prove$P(0,0)$and$P(m,0)\to P(m+1,0)$. In symbols, this amounts to the following assertion: ... 3 The terms of the ordered pairs must be separated by a comma. The right answer is$\{(2,a),(3,a),(4,a),(2,b),(3,b),(4,b)\}$. 2 Yes, this is true (though in (3) you should really say$\subset$well-orders$\lambda$, or that$\subseteq$nonstrictly well-orders$\lambda$). First, note that (2) implies (3) even without assuming (1). For suppose$\lambda$satisfies (2) and$x,y\in \lambda$. Then since$\in$is a transitive relation on$\lambda$,$x\in y$implies$x\subseteq y$, but in ... 2 Definition .$N$is the set of non-negative integers.....Take a strictly decreasing sequence$(x_n)_{n\in N}$with$x_0=5$and$\lim_{n\to \infty}x_n=3. $Take a strictly decreasing sequence$(y_n)_{n\in N}$with$y_0=2 $and$\lim_{n\to \infty}y_n=1 . $Let$f:[x_{n+1},x_n)\to (y_{n+1},y_n] $be bijective for each$n\in N . $And let$f(3)=1.$(Note that ... 2 It is not hard to show directly from the definitions: If$(A,<)$is a well-ordered set, then for every$B\subseteq A$,$(B,<\restriction_B)$is also well-ordered. Every set of ordinals is a subset of an ordinal. So without using the axiom of choice we have that every set of ordinals is well-ordered. 2 This is not true, suppose$f,g:\mathbb{R}\rightarrow \mathbb{R}$, such that$f(x)=e^x$and$g(x)=x^2$. So$g(f(x))=e^{2x}$and therefore is$1-1$, but g is not$1-1$. 2 We can modify the function in @EliRose's comment to get a solution. First note that$f(x) = \frac{x}{x+1}$maps from$(0,\infty)$to$(0,1)$. We'll make a new function$g(x)$with the desired property. Start with$g(x) = f(x)$for all$x$. We need to send a point to$0$; let's choose$g(1) = 0$. But now no point gets mapped to$f(1) = \frac12$. We can fix ... 2 The other answers address the issue of showing that the set is countable; let me try to tackle the other end, your intuition that the set should be uncountable. You write: "It still looks susceptible to the diagonal argument." OK, let's see if it actually is. The diagonal argument is quite non-intuitive at first; if you think it applies, it's always ... 2 You seem to have the right idea. Let me address a few issues of execution. Assume$\mathbb{N}\sim B$by a function$f$. 1)$A \subseteq B$means that$\forall a \in A, a \in B$If we use the same function$f$that defines$\mathbb{N}\sim B$and apply it to$N_A = \{ n : f(n) \in A \}$, then$\exists a_1, a_2 \in A : a_1 \ne a_2 \Rightarrow ...

2

The colon : inside set brackets means "such that". Here, $(x,y)\in$$R iff (x,y)\in$$A$$\times$$A$ and $(f(x),f(y))\in$$S$.

2

A basis for a vector space is a collection of vectors such that any $v \in V$ can be expressed as a finite sum of elements of it. Your proof is kind of a classic argument, prove that $|2^{\mathbb{N}}| = |\mathbb{R}|$. Using that, given any subset of $\mathbb{N}$ how could that define a map...?

2

Yes, you have proven, by way of counterexample, that the implication does not hold in general.

2

If $x \in C \setminus B$, then $x \in C$ and $x \notin B$ by definition, implying that $x \in C$ and $x \notin A$ by the assumption that $A \subset B$; this proves the first statement. If $x \in A$, then $x \in B$ and $x \in C$ by the assumption that $A \subset B$ and $A \subset C$; but this implies by definition that $x \in B \cap C$. We have proved the ...

2

The notation $|A|$ is just a shorthand for "the cardinality of $A$".

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