# Tag Info

## New answers tagged elementary-set-theory

2

You can do it by induction on $|Y|$; however a key word is missing in the statement, that is, $Y$ must be non empty. If $|Y|=1$, the result is obvious. Suppose $|Y|=n+1$ and that you're able to find a surjection $X\to Z$ when $|Z|=n$. Let $a\in X$ and $b\in Y$; then $Y'=Y\setminus\{b\}$ has $|Y'|=n$ and $X'=X\setminus\{a\}$ is infinite. By the induction ...

2

Assume $Y$ is non empty (otherwise, statement is not true). Since $|Y|$ is finite, let $|Y|=n$ for some $n \in \{1,2,...\}$. Thus, $Y=\{a_1,a_2,...,a_n\}$ Then select $n$ distinct elements from $X$ (you can do that since $X$ is infinite). Call these elements $b_1, b_2,...,b_n$. Then set $f: X \rightarrow Y$ to be $$f(b_1)=a_1$$ $$f(b_2)=a_2$$ $$...$$ $$f(b_n)... 0 In set theory, X^Y is the set of functions from the set Y to the set X. Now, as you already noted, in the standard construction of the natural numbers, 2=\{0,1\}, and thus 2^S is the set of functions from S to the set \{0,1\}. Each such function can be interpreted as the indicator function 1_M of a subset M of S (1_M(x) is 1 for x\in ... 4 In set theory, given two sets A,B, the notation A^B is often used to denote the set of all functions f : B \to A. So, as you say, if we take 2 = \{0,1\} then 2^S is the set of functions f : S \to \{0,1\}. The connection with subsets is that there is a bijection between subsets A \subset S and functions f : S \to \{0,1\}, where A ... 2 The number 2 is used because there are 2^n subsets of a set of n elements. An often-used alternative notation for the power set of a set G is \mathcal{P}(G). 1 As David Ullrich notes, the empty set does not contain itself--it does not contain anything. I suspect, perhaps, that you are confusing \in with \subseteq (you may find this helpful if that is, indeed, the case). Then, note that A\subseteq A for all sets A, even when A=\varnothing. On a different note, you may enjoy the following exercise that ... 2 In ZF or ZFC there is no such thing as the set of all sets. There is a class of all sets, but it is a "proper" class, which simply means that it isn't a set. It also means that it is not an element of itself. Within ZF or ZFC you might additionally ask whether any set (not just the universal set) is an element of itself. In ZF or ZFC there is a separate ... 3 In most modern set theories the collection of all sets is not a set itself. Namely, if X is a set, then there is a set Y such that Y\notin X. Set theories like Zermelo-Fraenkel prove this by showing that if X is a set, then \{x\in X\mid x\notin x\} is a subset of X which cannot be an element of X. However, they also prove this using the axiom ... 0 Recall that Comprehension essentially said that if \varphi(x) is a property, then there exists a set X such that x\in X if and only if \varphi(x) holds. This is useful, because mostly we want collections of mathematical objects to be yet again a mathematical object. But this is also problematic, as shown by the many paradoxes of naive set theory. ... 3 If A = \varnothing is empty, then A \times B = \varnothing is empty too; it is not equal to B. So there is only one possible function f : A \times B = \varnothing \to C, namely the empty function. If you want you can do something else and say "If A is non-empty we define f : A \times B \to C by [...], if A is empty we define a function f : B \... 3 If \Phi has other free variables... then \{ x \mid \Phi \} is still the unique term with the property that t \in \{ x \mid \Phi \} if and only if \Phi[t/x]. (assuming x does not appear in the term t) 2 What we actually need to show is that a,b \in F. Let's start with a. Assume towards contradiction that a\notin F. F is closed and thus there's an interval I = (a-\epsilon ,a+\epsilon) for some \epsilon > 0 such that I\cap F = \emptyset (because in that case F^c is open), therefore we get that F is contained in S' = [a+\epsilon , b] ... 1 Note that each one of the three balls is relatively open AND CLOSED in K, being the intersection of a closed ball of \mathbb{C} with K. For instance, B_1 = \overline{B_1} \cap K, where the closure is meant in \mathbb{C}. So you have found a subset of K (namely, B_1) which is relatively closed and open in K, hence K is disconnected. Your ... -3 This appears to be common doubt expressed in the following places: What are the cases of not using (countable) induction? Why induction cannot be used for infinite sets? Why doesn't induction extend to infinity? (re: Fourier series) Induction essentially shows if something is true for 1 and n, it is true for n+1 - and is thus true for countably ... 0 First take one obligatory b and one B, and forget about them. They'll always be there. Then you're looking for multisets of size k-2 that contain at least one b or B. We can get those by counting all multisets of size k-2 and then subtract the k-1 ones that consist only of A and a. By stars-and-bars there are \binom{k-2+3}{3} multisets with or ... 0 First, substitute x_2 \mapsto x_2' + 1, x_3 \mapsto x_3' + 1. Then this formulation is equivalent to$$x_0 + x_1 + x_2' + x_3' = k-2$$with the variables \geq 0. The total number of solutions is then {k+1 \choose 3} by standard methods. The one case which doesn't work are those where x_2' = x_3' = 0. Can you take it from here? 0 You are right. Induction only gives you that for every finite case, the finite union of countable sets is countable. However, we can prove directly the following. Suppose that for every n we are given S_n and an injection f_n\colon S_n\to\omega. Then \bigcup S_n is countable. Now, using the axiom of countable choice, given a sequence of ... 1 A function must map a domain (input) set to a range set. Often the domain is not explicit stated but even so it must exist. In these examples you are stating that sets A and B exist but you are assuming, without explicitly stating the \psi:A \rightarrow B. This is fine but exploited ambiguities makes the second example unclear. Here are the ... 2 It seems to me that option (3) is correct. \boxed{(p, m) \text{ is not minimal for }m \geq 3}: Since m \geq 3, we know that m - 1 \geq 2, so (p, m - 1) \in M \times M - \{(p, m)\}. Since p \mid p and m - 1 \leq m, we have that (p, m - 1) \leq (p, m). \boxed{\text{There is no maximal element}}: Given any candidate maximal element (p, q) \in ... 1 Probably a bit aside of the point, but if each A_i is countable, this means that there is a surjective map \phi_i: {\mathbb N} \rightarrow A_i. Now choose your favorite surjective map:  n\in {\mathbb N} \mapsto (a(n),b(n)) \in {\mathbb N} \times {\mathbb N}. Then n\in {\mathbb N} \mapsto \phi_{a(n)} (b(n)) \in \cup_i A_i is surjective. Why use ... 2 The formal statement of the principle of mathematical induction is to start with a statement P(n) that depends on a natural number variable n. If: P(1) is true P(k+1) is true whenever P(k) is true. Then P(n) is true for all n. Let A_1, A_2, \dots, A_n, \dots be an infinite sequence of countable sets. To use induction, you would need to ... 2 Induction can be used to prove that the union any fixed, arbitrarily large, but finite, number of countable sets is countable. This statement is emphatically not the same as saying that the union of countably infinitely many countable sets is countable. Somewhat more formally, suppose that A_i is a countable set for each i\in\mathbb N. You can use ... 3 Any proper subset S of \mathbb{N} such that the complement of S has cardinality greater than or equal to 2 can be written in the form you want. Suppose that \mathbb{N} \backslash S \supseteq \{a,b\} then$$ S = (S \cup \{a\}) \cap (S \cup \{b\}). $$It's easy to see that any set whose compliment contains fewer than 2 elements can not be written ... 3 M=U\cup\{4\} and N=U\cup \{6\}. Neither are U and M\cap N=U. 1 You are on the right track, you have already proved the function F is injective. Let's take any element a from A, by definition there exists a positive integer N such that N=\dfrac1a, thus a=\dfrac1N=F(N), we can conclude the function F is onto. 2 By definition, a function \psi:A \to B must assign a value to every element of the domain. In your case, this means that either \psi(a_3) = b_1 or \psi(a_3) = b_2 must hold. In both cases, the resulting map \psi isn't injective. (And, more generally, you cannot have an injection from a finite set to a smaller finite set.) 0 Not quite right. See if you can follow this argument and how it differs from yours: Assume that f\circ h is onto and that t\in T. Then there exists r\in R such that (f\circ h)(r)=t. But then f(h(r))=t with h(r)\in S. Hence, f is onto. \blacksquare 0 Think of S,R, T as set of cities in three countries of name SS, RR, TT. Imagine f as a specification of direct flights, with just one flight from each city of SS to cities of TT etc. Surjectivity of f means our selection of cities have covered all the cities of TT. Now given data means f\circ h is surjective. That is flight from RR to TT with one ... 0 If you’ve already proved that symmetric difference is associative, you can prove the desired result without having to chase elements. Since A\mathrel{\triangle}C=B\mathrel{\triangle}C, we have$$A\mathrel{\triangle}(C\mathrel{\triangle}C)=(A\mathrel{\triangle}C)\mathrel{\triangle}C=(B\mathrel{\triangle}C)\mathrel{\triangle}C=B\mathrel{\triangle}(C\mathrel{...

3

Part (b) follows immediately from part (a): $|\{0, 1\}^n| = |\{0, 1\}|^n = 2^n$. (If you want an explicit bijection--- which is probably not the best way of doing this problem--- then consider an element of $\{0, 1\}^n$ as a binary string and unravel the bijection in part (a).)

0

The characteristic function of the symmetric difference $A \Delta B$ if $f_A + f_B \pmod 2$. Here, we have $f_A + f_B = f_A + f_C \pmod 2$ and adding $f_A$ to both sides, we get $f_B = f_C$ and thus $B=C$.

1

Since $A\Delta C=B\Delta C$, intersecting with $C^c$ yields $A\cap C^c=B\cap C^c$. Prove that $(X\Delta Y)^c=(X\cap Y)\cup (X^c\cap Y^c)$. Apply this to both sides of the identity $(A\Delta C)^c=(B\Delta C)^c$, then intersect with $C$. This yields $A\cap C=B\cap C$.

3

Suppose $x \in A$. Then $x \in A \setminus C$ or $x \in A \cap C$. Case 1. $x \in A \setminus C$. Then, since $A \Delta C = B \Delta C = (B\setminus C) \cup (C \setminus B)$, $x \in B \setminus C$ as $x \not\in C$. In particular, $x \in B$. Case 2. $x \in A \cap C$. Again, since $A \Delta C = B \Delta C$, $x \not\in B \Delta C$. That is, $x \in B \cap C$ ...

0

I understand you didn't finish proving surjectivity of $h$, let me complete it. You want to prove that, that for any $b \in B$ such that $b \in (A_k - B_k)$ for some positive integer $k>1$, there exists some $\alpha \in A \; |\,h(\alpha)=b$. Due to $A_k=f(A_{k-1})$, $B_k = f(B_{k-1})$ and $f$ is an injective function,$A_k - B_k = f(A_{k-1}) - f(B_{k-1}) ... 1 Your grasp of these 'proof techniques' is roughly correct, though there are indeed clearer ways of understanding the difference between them. 'Indirect proofs' included not only 'proof by cases' but also 'proof by contradiction' and 'proof by contrapositive'. But I'll focus on the distinction between 'proof by cases' and 'proof without cases'. A 'proof by ... 0 Let$A_0, A_1,\ldots $refer to the sequence of ans values, starting with$A_0 = \varnothing$, and with$A_{n+1} = (B_n\cup A_n) \cap C$. The claim is that for any$n$,$A_{n+1} = C\cap \bigcup_{i=0}^n B_i$. The proof is by induction. In the base case that$n=0$, we have$A_1 = (B_0 \cup A_0) \cap C = (B_0 \cup \varnothing)\cap C = B_0 \cap C$, so the ... 4 In most cases the data set will be a true set if you view it as a set of observations. In the example of temperatures, there are only a few different temperatures, but each one corresponds to a different day. Your data set consists of ordered pairs (day, temperature on that day) and no pair is repeated. The only way you get repetition is if you observe ... 9 Arthur is right; the term "data set" usually means multiset. For example, a bivariate data set just means a multiset of elements of$\mathbb{R}^2$. Intuitively, a multiset in$X$is like a finite subset of$X$, except that repetitions are allowed. (Order still doesn't matter.) For example, the following are multisets in$\mathbb{N}$: $$\{1,2,2\} \quad \{2,1,... 5 A "data set" in statistics does indeed allow repetitions and in that sense is different from a "set" in set theory. It wouldn't make much sense otherwise: for instance, if you take the average daily temperature of each day for a year, there are only going to be a couple of dozen values (or a few dozen, in Fahrenheit), and the concept of average or mean, ... 5$$(xy)x=(yx)x=(xx)y=xyxy=(xy)(xy)=(y(xy))x=((xy)x)y=(xy)y=(yy)x=yx$$1 Note that axiomatic set theory is usually formalized in a logical language where there are no set-valued expressions other than variables. Whenever something that looks like a set-valued expression seems to appear in a formula, it is actually to be understood as an abbreviation of a more complex logical formula that intuitively claim that some variable x ... 0 Why not$$F(x) = \{y \mid \{\{x\},\{x,y\}\} \in F\}\;?$$This y is guaranteed to exists and be unique by the definition of F being a function. 1 Recall that a σ-algebra for X is a collection of subsets \Sigma of X such that: The empty set and the whole set X belong to \Sigma. \Sigma is closed under all countable unions. \Sigma is closed under all countable intersections. \Sigma is closed under complementation. Recall that a monotone class for X is a collection of subsets \... 2 No. For n\in\Bbb N let T_n=\{k\in\Bbb N:k\ge n\}. Then$$T_0\supsetneqq T_1\supsetneqq T_2\supsetneqq T_3\ldots$$is an infinite descending chain in$\langle\wp(\Bbb N),\subseteq\rangle$and would necessarily remain so in any extension of$\subseteq$. This will happen with any infinite set. 2 Consider the infinite descending chain of intervals$(-1/n,1+1/n)$of real numbers. If$A\subseteq B\implies A\le B$, as in the comment, then this is an infinite descending chain in the supposed well-ordering, but has no smallest element. (If we wish, we can restrict to the rationals in the given intervals.) 1$A \subseteq B$is defined so that if$a \in A$, then this implies that that$a \in B$. Note that is$A= \emptyset$, this statement is true, vacuously. Therefore, to show that$A \subseteq C$, we need only consider the case where$A$is nonempty. So, let$a \in A$. Then, by definition,$a \in B$... Can you see how to finish this kind of proof? It is ... 0 Since we have$A\subseteq B$we have$x\in A \implies x\in B$Since$B\subseteq C$we have$x\in B \implies x\in C$We know use the tautology$((p\implies q)\wedge(q\implies r))\implies (p\implies r)$. We conclude$x\in A \implies x\in C$. And so$A\subseteq C$2 Let$a\in A$, because$A\subset B$,$a\in B$and because$B\subset C$,$a\in C$. Then, for all$a\in A$we proved that$a\in C$, ie$A\subset C$4 Suppose$R\not \in R$. Then$R$is a set that does not have itself as an element. Since$R$satisfies this condition, we conclude$R\in R$.... woops. 1 Yes, this is correct, and yes, only the cardinality of$U$matters. You could slightly simplify the proof by noting that there are$2^{n-k}$subsets of$U\setminus x\$, so you don't have to sum over binomial coefficients. I find the combinatorial proof in Carry on Smiling's answer simpler and more elegant.

Top 50 recent answers are included