Tag Info

Hot answers tagged elementary-set-theory

16

If by $\{ \aleph_0, \aleph_1, \aleph_2, \dots \}$ you mean $\{ \aleph_n : n \in \mathbb{N} \}$, then this set is countable because it's indexed by the natural numbers. However, this set doesn't contain $\aleph_{\omega}$ or any larger alephs. If by $\{ \aleph_0, \aleph_1, \aleph_2, \dots \}$ you mean 'the set[sic] of all (well-orderable) cardinals', then it'...

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 Clive Newstead's answer is absolutely correct I would just like to add a short addendum with regards to the second phrasing of your question using power sets. As Clive already pointed out the "set" of \{\aleph_0,\aleph_1,\aleph_2,\cdots\} need not have almost anything to do with the "set" \{\omega,\mathscr{P}(\omega),\mathscr{P}(\mathscr{P}(\omega)),\... 5$$(xy)x=(yx)x=(xx)y=xyxy=(xy)(xy)=(y(xy))x=((xy)x)y=(xy)y=(yy)x=yx$$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, ... 4 In \sf ZF the two are equivalent: The axiom of choice. Every \beth number is an \aleph number. You can prove this by going through the following equivalent statement, The power set of an ordinal can be well-ordered. So if the axiom of choice fails, we know that there is some \alpha such that \beth_\alpha cannot be well-ordered. ... 4 Sets are collections of mathematical objects which are themselves mathematical objects. That means that in principle, a set can be a member of itself. We can therefore ask which sets are not members of themselves, and that is a valid question from a mathematical point of view. Russell's paradox shows us that the collection of sets which are not members of ... 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. 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 ... 3 It is not an equivalence relation because it fails to be reflexive as you noticed: (a, a) is not in R since a-a = 0 is even. Furthemore, it is not transitive since, for example (2, 1) \in R and (1,4) \in R but (2,4) \not\in R since 2-4 = -2. 3 You can use the following basic properties about sets:$$ \begin{array}{ll} (1) & X\setminus Y=X\cap Y^c\\ (2) & (X\cup Y)^c=X^c\cap Y^c\ \text{(De morgan rules)} \\ (3) & X\cap(Y\cup Z)=(X\cap Y)\cup(X\cap Z)\ \text{(distributive law)}\\ \end{array} $$Now$$ \begin{split} A\setminus(B\cap C) &=A\cap(B\cap C)^c\\ &=A\cap(B^c\cup C^c)\\ &...

3

You should start with $(x,y) \in R$ and $(y,z) \in R$ and from these two statements show that $(x,z) \in R$. This shows transitivity. Now, the two statements show that indeed $(x,z) \in R \circ R$ by definition (using $y$ as intermediate). We have the assumption that $R \circ R \subseteq R$, so we know that $(x,z) \in R$ as required, as $(x,z)$ is in the ...

3

Your formulation is incorrect. You're doing the right steps, but you're writing them down wrong, the logical meaning of what you write is different from what you mean. Here's proper formulation: Let $R$ be a relation on $A$ such that $R \circ R \subseteq R$. Let $x, y, z \in A$ such that $(x, y), (y, z) \in R$. By definition of $R \circ R$, it follows that ...

3

The intersection of $A$ and $B$ is simply $\lbrace 1 \rbrace$, which has only $\lbrace \rbrace$ and $\lbrace 1 \rbrace$ as subsets, and so the power set is $\lbrace\lbrace \rbrace, \lbrace 1\rbrace \rbrace$. The empty set is a subset of $A$ and $B$, but it is not a member of either set. Therefore, the empty set is not a member of $A \cap B$. Similarly, $\... 3 You're making this much too complicated. If such a$\psi$exists, to show that$f$is surjective, you just need to show that for every$b \in B$, there exists$a \in A$such that$f(a)=b.$You can define such an$a$explicitly using$\psi$and$b.$For the implication from left to right, note that you'll need to use the axiom of choice. In fact, that ... 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$... 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).) 3$M=U\cup\{4\}$and$N=U\cup \{6\}$. Neither are$U$and$M\cap N=U$. 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 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$) 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

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 ...

2

Here's a reasonably direct way that doesn't require developing arithmetic or limits in $\mathbb R$, or even arithmetic on $\mathbb Q$, if only we know that $\mathbb Q$ is densely ordered in the sense that for any $a<b$ there exists at least one $c$ with $a<c<b$. First, since we already know that $\mathbb Q$ is countable, fix a bijection $\psi:\... 2 The relation is transitive when for all$x,y,z\in A$, if$x\mathrel{R}y$and$y\mathrel{R}z$, then$x\mathrel{R}z$. Thus you have to start with$x,y,z\in A$, such that$x\mathrel{R}y$and$y\mathrel{R}z$, and prove that$x\mathrel{R}z$. Now,$x\mathrel{R}y$and$y\mathrel{R}z$implies$(x,z)\in R\circ R$; since$R\circ R\subseteq R$, we can deduce ... 2 If$\psi:B\to A$with$f\circ\psi=\text{id}_{B}$then for every$b\in B$we have$b=f\left(a\right)$if$a\in A$is defined by$a:=\psi\left(f\left(b\right)\right)$. This shows that$f$is surjective. If conversely$f:A\to B$is surjective then for every$b\in B$some$a_{b}\in A$exists with$f\left(a_{b}\right)=b$. Then function$\psi:B\to A$prescribed ... 2 You can tackle it simply by definition.$x \in (A \cup E) \cup E$means that$x$is in one of$A \cup E$or$E$. 'Expanding' further, we get$x$is in one of$A, E $or$E$. We can simplify this down to$x$is in$A$or$E$. i.e:$x \in A \cup E$. As noted by Brian M. Scott in the comment section, you can also use the associative law for unions to write ... 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$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.) 2 I finally got it. The question seems to be: How many pairs$(A,B)$of subsets of$\{1,2\dots n\}$exist so that$A\subseteq B$. For each element$x\in \{1,2\dots n\}$we have three choices:$x$is only in$Bx$is in$A$and$Bx$is not in$A$and not in$B$. Therefore there are$3^n$possible pairs. 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.

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