Tag Info

New answers tagged

1

When Velleman writes $$I_n = \{i \in \mathbb Z^+ |\ i \le n\}$$ he is using set-builder notation to describe a certain set: The set of positive integers, ($i \in \mathbb Z^+$) that are less than or equal to n ($i \le n$). For example, $I_3 = \{1,2,3\}$ because 1, 2, and 3 are the positive numbers less than or equal to 3. Without using the notation, one ...


2

Suppose that $A$ is a set of physical objects in the room with you, and you have a bijection $f:I_{42}\to A$. You can point to $f(1)$, which is an element of $A$, and say "one" to yourself. You can then point to $f(2)$, which is a different element of $A$, and say "two" to yourself. Continuing, eventually you point to $f(42)$, say "forty-two", and you're ...


1

So $I_n=\{1,2,3,\dots,n\}$. For instance, $I_5=\{1,2,3,4,5\}$. Each of these $I_n$ sets give a standard-sized finite set. In order for a set to be finite it must be equinumerous with one of these standard finite sets (or it must be empty).


1

$D \notin (X-Y)$ if and only if $\neg (D \in X \wedge D \notin Y)$. Because of De Morgan's laws $$\neg (D \in X \wedge D \notin Y) \iff D \notin X \vee D \in Y$$ If we suppose that $D\in X$, than $D \in Y$ must be true.


1

Since you already answered that we are assuming $D \in X$, then suppose $D \not \in (X - Y)$. Note that $X - Y = X \cap Y^{c}$. So we have $D \not \in X - Y \implies D \not \in X \cap Y^{c}$. But $D \in X$, and $X = (X \cap Y) \cup (X \cap Y^{c})$, so if $D \in X$, then $D$ must be in one of the two sets $(X \cap Y)$ or $(X \cap Y^{c})$. Since we ...


1

If $D \in X$ and $D \not\in Y$, then by definition $D \in (X-Y)$. But since we know that $D \not\in (X-Y)$ we must have either $D \not\in X$ or $D \in Y$. Since you said you know that $D \in X$, then we are left with $D \in Y$. The statement $D \not\in (X-Y) \iff D \in Y$ is like saying "Since the cookie jar is not in any of the other rooms in the ...


6

$$d \notin (X-Y) \iff \lnot(d \in X \land d\notin Y) \iff (d\notin X \lor d\in Y)$$ Since we know that $d\in X$, we know that $$\lnot \lnot (d \in X) \iff \lnot(d\notin X)$$ which, together with the first premise, it follows that $d \in Y$.


3

This is not necessarily true, if $D\notin X$. Of course, in the context from which you take it, you already assume that $D\in X$, so it is necessarily the case that $D\in Y$.


2

First let's clear up the statement. Recall that: $X-(Y-Z)=(X-Y)\cup (X\cap Z)$. So we have that: $$\mathcal P(A-B)-(\mathcal P(A)-\mathcal P(B))=(\mathcal P(A-B)-\mathcal P(A))\cup\mathcal P((A-B)\cap B)$$ But of course that $\mathcal P(A-B)$ is a subset of $\mathcal P(A)$, so we are left with $\mathcal P((A-B)\cap B)=\mathcal ...


0

Something to get you started: $$ f^{-1}(\mathbb{N})=\cup_{n\in\mathbb{N}}f^{-1}(n) $$ Now, given $n\in\mathbb{N}$we want to find $$ f^{-1}(n)=\{(u,v)\in\mathbb{Q}_{+}\times\mathbb{Q}_{+}\mid f(u,v)=n\} $$ note that $$ \{(u,v)\mid f(u,v)=n\}=\cup_{v_{0}\in\mathbb{Q}_{+}}\{(u,v_{0})\in\mathbb{Q}_{+}\times\mathbb{Q}_{+}\mid f(u,v_{0})=n\} $$ see if given ...


1

Since you tagged boolean algebra, let's try the following. First let $x,x_i$ be elements of a boolean algebra, then $$\begin{aligned} \prod^n_{i=1}(x+x_i) &= x^n+(x_1+\cdots+x_n)x^{n-1}+(x_1x_2+\cdots)x^{n-2}+\cdots + (x_1\cdots x_n)\\ &=x(1+(x_1+\cdots x_n)+(x_1x_2+\cdots)+\cdots+(x_1\cdots x_n))+(1+x)\prod x_i\\ &=x\prod(1+x_i) +(1+x) \prod ...


1

There is no contradiction here. While it's certainly true that $\omega+1$ and $1+\omega$ have the same number of elements, and there's therefore a bijection between their elements, isomorphism of wellorders is more demanding. Let $(A,\leq_A)$ and $(B,\leq_B)$ be wellorders. They are isomorphic iff there's a bijection $f:A\to B$ between them such that ...


2

The term "isomorphism" means similar structure. But it doesn't specify the structure. The structure needs to be inferred from context, or stated explicitly in the text. If the context is just sets, then isomorphisms are not required to preserved any structure, in which case $\Bbb N$ and $\Bbb Q$ are isomorphic, since both are countably infinite. If the ...


0

$\omega+1$ and $1+\omega=\omega$ have the same cardinality and thus there's a bijection $f$ from $\omega+1$ onto $\omega$. $\in$ is the canonical well-ordering on $\omega+1$ and so via $f$ you'll get a well-ordering $<_f$ on $\omega$, namely $\alpha <_f \beta$ iff $f^{-1}(\alpha) \in f^{-1}(\beta)$ for $\alpha,\beta\in\omega$. However, this ...


0

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \text{"#2"} \\ \quad & } \newcommand{\endcalc}{\end{align}} $Just for fun, here is another way to check this, by using the definition $$ \tag{0} x \in X \triangle Y \;\equiv\; x \in X \not\equiv x \in Y $$ We can now try and see what the elements $\;x\;$ of ...


0

You asked this additional question in the last paragraph: Also just for clarity's sake: Would $A\cup B = A \cup C$ and $A \cap B = A \cap C$ be proven in a similar way to show whether or not the conditions imply $B = C$? A counterexample/ proof of this would be appreciated as well. $A\cup B=A\cup C$ $\Rightarrow$ $B=C$ is not true in general. ...


0

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \text{"#2"} \\ \quad & } \newcommand{\endcalc}{\end{align}} $As a first simplification, we can take out $\;C\;$ and rephrase your theorem as $$ \tag{0} A \Delta B = A \Delta D \;\Rightarrow\; B = D $$ The proof depends on your definition and the laws of logic ...


1

A well-ordering exists on both, but the ordinal orderings on $1+\omega$ and $\omega+1$ are different. The former has no maximal element, the latter has one.


0

Hint: Three of the four statements are true.


3

Set $\emptyset$ does not contain any elements so: 1) no element can be found in $\emptyset$ that is not an element of $\emptyset$ so indeed $\emptyset\subseteq\emptyset$ 2) no element can be found in $\emptyset$ that is not an element of $\{\emptyset\}$ so indeed $\emptyset\subseteq\{\emptyset\}$ 3) $x\notin\emptyset$ is true for any $x$ so also for ...


1

Using slightly different notation, you ask why, for any $\;k\;$, $$ \tag{0} \langle \cup i :: B_k \triangle B_i \rangle \;=\; \langle \cup i :: B_i \rangle - \langle \cap i :: B_i \rangle $$ Now I'm not sure what you mean by "proving using just basic set algebra", but in any case, I find this kind of equalities are easier proved on the element/logic level. ...


1

Taken literally, the question has an easy (but probably unsatisfying) answer: The subsets that the proof creates and forms the union of are, as you wrote, all the well-ordered sets $(B,\leq_B)$ such that each element $b$ of $B$ is the result of applying the choice function $f$ to the complement of the set of strict predecessors of $b$. One such $B$ is the ...


1

From $1$ to $k$ there are $k$ numbers. So from $1$ to $n$ there are $n$ numbers. Take away the numbers from $1$ to $m-1$ (there are $m-1$ of these), leaving the numbers from $m$ to $n$ inclusive. So the answer is $n-(m-1)=n-m+1$.


1

Try doing this: $n-m+1$: $m=0, n=2$: $\big|[0,1,2]\big| = 3$ $m = 5, n = 12$: $\big|[5,6,7,8,9,10,11,12]\big| = 8$


0

The problem of equality of two regular expression is EXPSACE-complete. So I guess building the automaton and working on the automaton would be the easier way to solve your problem.


3

This means that if you consider the collection of equivalence classes, and this order defined $\leq$, then it is a partial order. Namely, reflexive, antisymmetric and transitive. The problem is that usually, $|A|$ is not a set, and the collection of different equivalence classes is too big to be a set as well (even if we managed to choose a unique ...


3

There is no difference in meaning between "class" and "set" in this particular usage. He is correct on the right way to formalize these notations, but the shorthand is so much easier to read, and, as long as everybody knows what you mean, it is acceptable.


0

If you have already proved that inequality of ordinals is trichotomic, then the second part, which has the form of implication $$\gamma \alpha < \gamma \beta \qquad\Rightarrow\qquad \alpha<\beta$$ can be equivalently reformulated as $$\beta\le\alpha \qquad\Rightarrow\qquad \gamma\beta\le\gamma\alpha.$$ So now the two parts have very similar form: We ...


1

Let $x \in \bigcup_{i} B_i$. If $x$ is contained in all the $B_i$ than $x$ is not contained in $\bigcup_i B_k \triangle B_i$ and also not contained in $\bigcup_i B_i - \bigcap_i B_i$. Now suppose $x$ is contained in some, but not all, of the $B_i$. Then $x$ is contained in $\bigcup_i B_i - \bigcap_i B_i$. Furthermore, if $x \in B_k$ there is a $i \neq k$ ...


1

Your definition of $R$ is extremely cumbersome. You don't have to mention the set over which you apply separation if the definition is obviously bounded. Writing $R=\{(i,h)\mid h\in H(i)\}$ is far clearer. And if that is the relation that you were defining, then the proof is fine.


1

I use that $a \le b$ for order types iff there is a strict order-preserving function from a set with order type $a$ to one with order type $b$. As $a < b$ in particular $a \le b$, so there is a (strict) order preserving $f: a \rightarrow b$ (so for all $x,y \in a: a < b \rightarrow f(a) < f(b)$, where $<$ denotes the order on both $a$ and $b$. ...


0

The most straight-forward way to approach this is to show that $x \in F$ or $G$ if and only if it satisfies the conditions described, treating both directions of implication separately. For example, for $F$: suppose that $x$ appears in all but finitely many $E_j$. Then there is an $n$ such that $x \in E_j$ whenever $j\geq n$. It follows that $ x \in ...


1

If $x\in F$, then $x$ is element of one of the sets that are forming the union $F$, therefore $x\in \cap_{k = n}^\infty E_k$ for at least one $n\in\mathbb{N}$. Because $x$ is the element of the intersecion $\cap_{k = n}^\infty E_k$, $x$ is element of every $E_k$ where $k\geq n$. One can conclude that $x$ may be "missing" only in the first $n-1$ sets, which ...


0

As to a): $x \in F$ iff there exists some $n(x)$ such that for all $k \ge n(x)$, $x \in E_k$. So $x$ is in eventually all (except maybe the first $n(x)$ many) $E_k$... As to b): $x \in G$ iff for every $n$ there exists some $j \ge n$ such that $x \in E_j$, so we can always find "new" indices $j$ such that $E_j$ contains $x$.


2

A non principal ultrafilter on the set of natural numbers is a tail set but it is far from Borel. What you are missing is that you need to make use of the fact that your set is Borel (or Lebesgue measurable) so that you can apply something like Lebesgue density theorem.


1

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \text{"#2"} \\ \quad & } \newcommand{\endcalc}{\end{align}} $For comparison, here is a different (more "logical" :-) approach. Assuming that you're only allowed to use the definitions of $\;\subseteq\;$ and $\;\cap\;$, any proof $\;A \subseteq B \;\equiv\; A ...


0

Here is another answer. I assume from the discussion that "transfinite=infinite". Just remark that if $\alpha$ is finite then $\alpha+1$ is finite. So if $\beta$ is infinite then all finite ordinals are less than $\beta$. This means that $\omega \leq \beta$. $\omega$ being defined as the set of finite ordinals.


1

HINT: If an ordinal is infinite, then it has finite initial segments of every possible length.


2

Proceed as follows. All sets are well orders. 1) If $f: D\rightarrow D$ is order preserving, ($x<y \rightarrow f(x) <f(y)$) then $x\leq f(x)$ 2) If $f: D\rightarrow E$ is order preserving, then $ord(D) \leq ord(E)$. (Hint: use trichotomy and 1) to show you cannot order preservingly map a set into an initial segment of itself.) (I take your ...


2

The cartesian product of two sets : $X,Y$ is a set $Z$ defined as : $Z = \{ (x,y) \, | \, x \in X \, \text {and} \, y \in Y \}$ where $(x,y)$ is the ordered pair having $x$ as first component and $y$ as second component. Thus, the cartesian product $X \times Y$ is the set of all ordered pairs with first component in $X$ and second component in $Y$. A ...


2

There is a lot of inaccuracy in what you are saying. As Ittay notes, you are talking about the Lebesgue measure only, otherwise, for example, pick any singleton (say $\{0\}$) and say that $A\subseteq\Bbb R$ has measure $1$ if and only if $0\in A$. You can check that this is a measure and that it is $\sigma$-additive, and that every set is measurable. In ...


2

Actually, to prove that $f$ is injective, you have to show that $f(p_1,q_1)=f(p_2,q_2)$ implies $(p_1,q_1)=(p_2,q_2)$. But since $f(p,q)=(r,q)$, then this immediately implies $q_1=q_2$. The rest of the argument you gave shows that $p_1=p_2$, thus $(p_1,q_1)=(p_2,q_2)$. For the surjectivity, let $(r,q)\in H$. Let's find $p$ such that $(p,q)\in G$ and ...


0

I'm not sure why you have that $\operatorname{dom}(f)\subseteq\operatorname{ran}(f)$. Note that $x\in\operatorname{dom}(f)$ means that $x\in X\in A$, and $F(x)\in A$. Therefore $\operatorname{dom}(f)\subseteq\bigcup A$ and $\operatorname{ran}(f)\subseteq A$. So you can't quite use $\operatorname{ran}(f)$ to define $C$. Instead, consider $A'=\{\{X,x\}\mid ...


0

I had to define an n-tuple his way: I had to come up with a property $P(x, y)$ and state that an object $a$ is an n-tuple if it satisfies the property $P(a, n)$. Then I had to prove 1) and 2) parts as theorems. So parts 1) and 2) are not the way to define it, they have to follow from your definition. Look at the whole hint the author provides for this ...


3

The reason would depend on the particular argument you give but it all boils down to the fact that (with the axiom of choice) one can construct very bizarre sets of real numbers. You also have to be more precise. There are measures on the set of all subsets of $\mathbb R$, e.g., counting measure. What does not exist is a translation invariant extension of ...


1

Yes. $A\cap B\cap C\cap D=A\cap B\cap(C\cap D)$ is the intersection of the three sets $A$ and $B$ and $C\cap D$, so it is empty.


2

$A \cap B \cap C \cap D \subseteq A \cap B \cap C = \emptyset$. Thus $A \cap B \cap C \cap D = \emptyset$.


2

Yes, if $A$, $B$, $C$, and $D$ are sets such that the intersection of any three is empty, then because intersection is associative, we have that $A \cap B \cap C \cap D = (A \cap B \cap C) \cap D = \emptyset \cap D = \emptyset$. Just in case you aren't sure what associative means, it means that we can intersect in any order. So, in the case of three sets, ...


2

Yes. Let's suppose that $A \cap B \cap C = \emptyset$. Then $A \cap B \cap C \cap D = (A \cap B \cap C) \cap D = \emptyset \cap D = \emptyset$.


0

Let $S_{2n+1}$ denote the set of string of length exactly $2n+1$. Since this set is finite, there is a mapping $f_n:S_{2n+1} \to |S_{2n+1}|$ (where |S| denotes the cardinality of $S$)which lists all elements in $S_{2n+1}$. Now consider the function $f:\cup_{n \in \mathbb{N}}S_{2n+1} \to \mathbb{N}$ defined by ...



Top 50 recent answers are included