# Tag Info

## Hot answers tagged elementary-set-theory

5

The result is false as stated: if $I=\Bbb N$, $B_n=\Bbb N$ for each $n\in\Bbb N$, and $A_n=\{n\}$ for each $n\in\Bbb N$, then $\bigcap_{n\in\Bbb N}B_n=\Bbb N$, which is infinite, and $\bigcap_{n\in\Bbb N}A_n=\varnothing$, which is finite, but $$\bigcap_{n\in\Bbb N}(B_n\setminus A_n)=\bigcap_{n\in\Bbb N}(\Bbb N\setminus\{n\})=\varnothing$$ is finite.

4

If they're disjoint, take $f : [0,1) \to A$ and $g : [0,1) \to B$ bijections, then you can basically concatenate these two bijections as $h : [0,2) \to A \cup B,h(x)=\begin{cases} f(x) & x \in [0,1) \\ g(x-1) & x \in [1,2) \end{cases}$. If you don't like the use of $[0,2)$ for some reason then you can use $x \mapsto 2x$ to make the domain of $h$ be $[... 3 Welcome to MSE. The answer to your question is NO You can write it as $$S = \bigcup_{i = 1}^{n}S_i$$ where$S_i \cap S_m = \varnothing$for all$1 \leqslant m < i \leqslant n$. Note here:$i \not = m$. Hope this helps. Note: You can also write it as $$S = \bigcup_{S_i \cap S_m = \varnothing}^{}S_i$$ 3 It is not uncommon to use the symbols$\uplus$or$\sqcup$to denote disjoint unions, but there are two different interpretations of that: First,$A\uplus B$could mean the union of two sets that are isomorphic (in whichever way appropriate) to$A$and$B$but with their elements renamed to guarantee they will always be disjiont. Alternatively,$A\uplus B$... 3 Yes, you can. Simply map every (ordered) pair of subsets$(A, B)\in \mathcal P(\mathbb N)^2$to$(2A) \cup (2B+1)$. To find this idea, try to think of the cardinals. The cardinal of natural integer sets is$2^{\aleph_0}$and the cardinal of ordrered pairs of natural integer sets is$(2^{\aleph_0})^2=2^{2\aleph_0}=2^{\aleph_0}$. How do you fit$2\aleph_0$in$...

3

Hint: there are many ways. One way is to identify $c$ with the set $S$ of positive irrational numbers, which can be uniquely represented as infinite sequences of positive integers (using continued fractions). Now you have $S = A \cup B$ where $A$ comprises the sequences that start with an even number and $B$ comprises the sequences that start with an odd ...

3

Suppose $B \subseteq f(B)$. Take any $a \in A$. Then $f(a) \in B \subseteq f(B)$ so we can write $f(a)=f(b)$ for some $b \in B$. Since $f$ is injective this gives $a =b$ so $a \in B$. We have proved that $A \subseteq B$ which is a contradiction. [ It is given that $B \subseteq A$ but $B \neq A$].

2

Here is how the construction of that bijection mirrors the freeing of the first two rooms in Hilbert's Hotel. The function $h$ matches the rational numbers $$0, 1/1, 1/2, 1/3, 1/4, 1/5, \ldots$$ in order to the rational numbers $$1/2, 1/3, 1/4, 1/5, 1/6, 1/7, \ldots$$ That says the inverse function $h^{-1}$ creates "rooms" for the extra guests ...

2

You haven't quite shown that $h$ is one-to-one or onto, but you're very close! You have shown that two restrictions of $h$ are one-to-one, that no two elements map to $\frac12,$ and that infinitely-many elements of $(0,1)$ are in the range of $h,$ but that's not enough. You've hinted around the rest, but it should be made explicit. I would proceed in a ...

2

Saying that two sets $X, Y$ have the same cardinality says that there exists some function $f: X \longrightarrow Y$ which is one to one and onto. It says nothing about what other functions can exist. For instance, if $X = Y = \mathbb R$ we can consider $g: \mathbb R \longrightarrow \mathbb R$ such that $g(x) = 0$. Even though $\mathbb R$ and $\mathbb R$ ...

2

For the case of necklaces we have the cycle index $$Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}.$$ We get with $k$ colors $Q_j$ (this is PET) $$[Q_1^{n/k} \cdots Q_k^{n/k}] Z\left(C_n; \sum_{j=1}^k Q_j\right) = \frac{1}{n} \sum_{d|n} \varphi(d) [Q_1^{n/k} \cdots Q_k^{n/k}] \left(\sum_{j=1}^k Q_j^d\right)^{n/d}.$$ We see that $d$ must divide $n/k:$ $$... 2 STEP 1. Prove that there is a bijection f between \mathbb{R} and [0,1). STEP 2. Divide \mathbb{R} into countable pieces of copies of [0,1). 2 One easy way to get to an answer is to start by taking any set X, and simply looking at the simplest (but not trivial) collection of sets which guarantee that every finite subset of X will be a subset of some element in the collection: simply take all finite subsets of X. This is not linearly ordered set, and it's easy to see that if X is uncountable,... 2 No. A\setminus B\ne\emptyset\ne B\setminus A is sufficiently short and clear. 1 The definition of "antiset" given on the Wolfram MathWorld page you linked to (and also on Wiktionary!) is: A set which transforms via converse functions. This "definition" seems meaningless to me without more context. What is a "converse function"? What does it mean for a set to "transform via converse functions"? ... 1 Suppose that A \setminus B were countable (i.e. not uncountable). Then A = A\setminus B \cup B would be countable too as a (disjoint) union of two countable sets. But A is given to be uncountable. Contradiction. So A\setminus B is uncountable. 1 Hint: Consider the case where [w,x] = [0,1] and f\colon [0,1] \to [y,z] is defined by$$f(t) = tz + (1-t)y$$1 Yes, \forall X \subseteq A (X \notin \mathcal F \!\implies\! A \setminus X \in \mathcal F) is a property only for ultrafilters: Suppose that there exists a subset X of A such that X \notin \mathcal F and A \setminus X \notin \mathcal F. Then \mathcal F \cup \{X\} has the finite intersection property: if S_1,\dots,S_n \in \mathcal F then (S_1 \... 1 Yes, sets can contain arbitrary elements as long as they're distinguishable. 1 Yes, just because A=B, so both products are just A\times A = \{(1,1), (1,2), (2,1), (2,2)\}. 1 For example, let$$ C=\{\,\{x,A\}\mid x\in B\,\}.$$1 The only way this can be satisfied with the graphs having disjoint edge sets is if G_1 and G_2 are both empty graphs (and hence equal, since they have the same vertex set). This is because any edge of G_1 is an edge of G_1\cup(G_2\cap G_3), but not of G_2, contradicting the relationship. So G_1 has no edges, and G_1\cup(G_2\cap G_3)=G_2\cap G_3.... 1 Defining G_0 as the graph with the common vertex set but no edges, we can write$$G_2 = G_1\cup (G_2\cap G_3) = G_1\cup G_0 = G_1 Done! Note: We can go on to observe that the edge sets of $G_1$ and $G_2$ must also be empty, but this isn't required to establish the equality.

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