Tag Info

Hot answers tagged

9

The reason your intuition deceives you is because we often like to forget strategies which depend on the numbering of the coins, and instead think about it in terms of abstract coins, so at each step the devil takes back one coin, and puts in two new ones instead. The problem is that this description of the problem has different possible outcomes, which ...


8

Take your claim But since $\forall x \in A: x \in B$ and $\forall x \in B: x \in C$ by the statement above, every $x \in A$ must also be in C. That's already a proof of your result! So packaging that proof inside a longer argument which starts off by assuming the opposite of what you want to establish, and then aims for a contradiction, is just ...


8

Effectively there are only $50$ students to worry about. There are $50-12=38$ students who take math, and therefore $19$ who take biology. Thus $19-12$, that is, $7$ take both. That leaves $38-7$ students who take math but not biology. Remark: A picture (Venn diagram) may be useful in keeping track of things.


7

You don't need the axiom of choice to show that $|\Bbb R|=2^{\aleph_0}$. If you observe carefully neither the injection from $\Bbb R$ into $\mathcal P(\omega)$ defined by enumerating the rationals and using Dedekind cuts, nor the injection from $\mathcal P(\omega)$ into $\Bbb R$ defined by creating the Cantor set use the axiom of choice. Since the proof of ...


7

The definition of $\varnothing$ refers to its lack of elements, it says nothing about its subsets, so although it is clearly absurd that a nonempty set should be a subset of $\varnothing$, it's not enough to say "it is clearly absurd"... at least, not for a proof of such a low-level statement. Something along the following lines would be better: suppose $A ...


7

This is actually a well known problem called the Ross–Littlewood paradox. The paradox typically, however, does not say anything about the numbering of the coins or which coins are added/removed. In this case it is impossible to say how many coins are left due to what Asaf Karagila said. In your version, however, it is true that there will be no coins left. ...


6

Yes, There are arbitrarily large fields. This follows from a result in logic, namely the Upward Löwenheim–Skolem theorem (see http://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem). To be more concrete, consider the countable algebriacly closed field, $\bar{\mathbb{Q}}$. Every elements of this field is algebraic (meaning it is a root of a ...


6

@dwalke: This means all integers except for 0. Edit: I'm all the more convinced now that you said it's a "vestibular"-type question. This notation is taught in the standard high-school curriculum in Brazil. See http://www.infoescola.com/matematica/numeros-inteiros/ for example.


5

Yes. You can change th codomain, and as long as it includes the range of $f$, the function is the same. For example, $\sin\colon\Bbb R\to\Bbb R$ and $\sin\colon\Bbb R\to[-1,1]$ are the same function. Or $f(1)=1$ is the same whether or not $f\colon\{1\}\to\Bbb N$ to $f\colon\{1\}\to\{0,1\}$. As the other answers indicate, in some contexts a function is a ...


5

Let the number of students who take strictly Biology be $b$, the number who take strictly maths be $m$, the number who take both be $d$, and the number who take neither be $n$. Then $$ b + m + d + n = 65 $$ We are also given that $$ m + d = 2(b + d) $$ and that $b = 12$ and $n = 15$. Then $$ m + d = 38 $$ and $$ m - d = 2b = 24 $$ So $$ 2m = 24 + 38 = ...


5

Define $$R = \{(m, n)\mid m, n\in \mathbb N \;\text{ and }\;m, n \text{ are both even}\}$$ Then, for every odd integer $t\in \mathbb N$, $(t, t)\notin R$, hence reflexivity fails. Recall that for reflexivity to hold, it must be the case that for every $n\in \mathbb N$, $(n, n) \in \mathbb N$. No exceptions. However, it is easy to verify that $R$ is both ...


4

$\varnothing$. It's transitive and symmetric by vacuous arguments. But it is not reflexive since $(n,n)\notin\varnothing$ for all $n\in\Bbb N$!


4

Given any set $X$, you can come up with an integral domain $\mathbb Q[X]$, of polynomials with each $x\in X$ an indeterminate. This ring is an integral domain, so it has a field of fractions, and that field of fractions has at least $X$ elements. If $X$ is infinite, I believe the field of fractions will have the same cardinality as $X$, but don't quote me. ...


4

You can "put" all integers $x$ from $0$ to $\infty$ into the reals in $[0,1]$ by assigning $x$ to $1/x$. You eventually see later, that the other way round it is completely impossible.


4

Take any arbitrary element $a\in A$, and take any one-element set $\{x\}$ and let $f_x(a) = (a, x)$. So $f_x(A) = \{(a, x)\mid a\in A, x\in \{x\}$. Note, this $x\in \{x\}$ must be the same $x$ in all ordered pairs $(a,x)\in A\times \{x\}$, else $f$ is not a function. You can show that $f_x$ is bijective by proving it has an inverse $f_x^{-1}(a, x) = a$.


3

The key question here is what do we mean by "size". How do you count an infinite set? Aren't they both infinite? When we count a finite number of things, one way of thinking about it is that we designate each thing with a counting number - so to count the number of people in a room, I designate each person a consecutive number and the number of people in ...


3

Intuitively the answer is ∞ because I added one coin for infinite times. This intuition attempts to apply a rule of procedure: After step $k$ there are $k$ coins therefore after infinitely many steps there are infinitely many coins. the correct answer seems to be 0 because every coin numbered k has been removed This answer responds to the above ...


3

Let us formalize: The Analytic approach Let $C_m$ be the number of coins at time $\frac1m$ (after the exchange). Then $$C_m = \sum_{n=1}^m 2_{\text{added}} - 1_{\text{removed}} = \sum_{n=1}^m 1 = m$$ The number of coins in the basket at time $t\in [-\frac1n, -\frac1{n+1})$ is simply $n$. $$\mathrm{COINS}(t) = \left\lceil \frac1{-t} \right\rceil, \qquad ...


3

How about: $$ \bigcup_{S \subset \mathbb{N}, |S| \geq m} \left( \bigcap_{i \in S} A_i \right) $$ Actually, we can do this instead: $$ \bigcup_{S \subset \mathbb{N}, |S| =m} \left( \bigcap_{i \in S} A_i \right) $$ This works because if $x \in A_1 \cap \dots A_m \cap A_{m+1} \cap \dots A_k$ for some $k$ then it's certainly in $x \in A_1 \cap \dots A_m$, and ...


3

I like the one that snake around, $0, -1, 1, -2, 2, -3, 3,\ldots$ So it goes $$\begin{cases}f: \Bbb N\to \Bbb Z \\ f(2n)=n-1 \\ f(2n-1)=-n\end{cases}$$ If you want it to go the other way, you just reverse the idea and compute the inverse of $f$.


3

We have $\varnothing \subset A$ for any set $A$, including $ A = \{\varnothing \}$. Suppose there is a set $A$ such that $\varnothing \not\subset A$. Then exists $x \in \varnothing$ such that $x \not\in A$. But this is a contradiction, because there is no element in $\varnothing$.


3

You find it hard to talk about the cardinality of an ordered pair, because you don't think of an ordered pair as a set. You think about it as an ordered pair. Similarly you will have a hard time talking about the cardinality of a real number. What is the cardinality of $\pi$? Well, of course it depends on how you construct the real numbers, and what exactly ...


3

First off, if you have a solution to one of the halves, you also have one for the other -- just replace $X$ and $A$ with their complements, which preserves decidability and makes $A\subseteq X$ into $\overline X\subseteq \overline A$. Second, there's an important subtlety here. The problem is about whether we can find some $X$ such that there is/isn't a ...


3

Since we are describing $C$ as the union of two sets, why not simply refer to $A$ as the first set in this union of two sets. But, honestly, I'd simply refer to these sets by name. If you state that $C = A\cup B$, why not go on to assert: "Set $A$ ensures...., while $B$ guarantees..."


2

Hint: the restriction of an injective function to a subset of the domain is still an injective function. Also the inverse of a bijection is still a bijection. Also, Cantor-Berstein.


2

You pretty much finished. Just remember that $X$ is denumerable if and only if $|X|=|\Bbb N|$, and that equicardinality is an equivalence relation. Another option is to show there is an injection from $A$ into $B$. Then use the Cantor-Bernstein theorem.


2

You don't need to assume anything is true. You can easily show this is true. Let $x \in \emptyset$. Since there is no such $x$, all statements about $x$ are perforce true, including $x \in \{\emptyset\}$. So $\emptyset \subset \{\emptyset\}$.


2

Your list has absolutely no pattern, because you're doing it "wrong", in the sense that you are not writing it in a way that a pattern emerges. Of course there is no order preserving function, so writing both sets with their natural order will promise you that there is no reasonable pattern. Instead write the natural numbers, and then try to write the ...


2

That is indeed right. Git Gud's objection doesn't really apply if the definition you learned for $\subseteq$ is the one you wrote, because it seems that's how your teacher writes down such things.


2

By the stars and bars method, there is a bijection between $A_{k,M}$ and the set of $k-1$-subsets of $\{1,2,\dots,M+k-1\}$. Essentially, $n_1,n_2,\dots,n_k$ goes to $\{n_1+1,n_1+n_2+2,\dots,n_1+\dots+n_{k-1}+k-1\}$. The set of $m$-subsets of $\{1,2,\dots,N\}$ can be given indices in $\{0,1,\dots,\binom{N}m-1\}$ via the squashed ordering, where $1\leq ...



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