Tag Info

New answers tagged

0

The "sensible" statement to consider is: Conjecture. For all sets $X$, the power set of $X$ satisfies the following identity. $$A∩(B∪C)=(A∩B)∪C$$ This is false. E.g. take $A=\emptyset_X$ and $C=X$. Then $A \cap (B \cup C) = \emptyset_X$, while $(A \cap B) \cup C = X$. However, it can be salvaged by adjoining the condition that $C \subseteq A,$ ...


0

Hints: $A \cap(B\cup C^*)=(A\cap B)\cup (A\cap C^*)$ So if $A \cap C=\emptyset$, then $A \subset C^*$ and the equality is holds.


1

The set : $(X \times Y) \backslash (A \times B)$ is obtained from the set $\{ (x,y) | (x∈X ∧ y∈Y) \}$, "deleting" all couples from the set $\{ (x,y) | (x∈A ∧ y∈B) \}$. Thus, a couple $(x,b)$, with $x \in X$ and $b \in B$ will be in it, while the same couple will not belong to $(X \backslash A) \times (Y \backslash B)$. Let : $A = \{ 1, 2 \} ...


1

$X=Y=\mathbb{R},A=B=[0,1]$, $(X \times Y) \setminus (A \times B) =\Big((-\infty,0)\cup (1,\infty)\times\mathbb{R}\Big)\cup \Big(\mathbb{R}\times(-\infty,0)\cup (1,\infty)\Big)$ $(X \setminus A) \times (Y \setminus B)=(-\infty,0)\cup (1,\infty)\times (-\infty,0)\cup (1,\infty)$ In particular, $(-\frac{1}{2},\frac{1}{2})$ is in the first not the second. ...


1

A point is in the left hand side if it is in $X \times Y$, so of the form $(x,y)$ with $x \in X, y \in Y$, but not in $A \times B$, so it is not of the form $(a,b)$ with $a \in A, b \in B$. But this can happen in two diferent ways: $x \notin A$ or $y \notin B$. In the right hand side both are the case, while either one suffices not to be in $A \times B$.


0

Usually, a truth set is the set of "values" of $x$ such that $\varphi(x)$ holds, where $\varphi(x)$ is a formula with a free variable $x$. Thus we have to consider the formula : $(x \subseteq A)$ and its truth set will be $\mathcal P(A)$, because the formula $(x \subseteq A)$ holds exactly for those $x$ such that $x \in \mathcal P(A)$. Note that ...


1

Just for fun, here is another way of proving this: expand the definitions, then use the laws of logic to simplify. $ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \text{"#2"} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Tag}[1]{\text{(#1)}} \newcommand{\true}{\text{true}} ...


0

I have already given this answer elsewhere. Let me repeat this here. To prove the countability of $\bigcup _{n=1}^\infty A^n$, it suffices give an injective function $\phi$ from this union to $A$. Without loss of generalty take $A$ to be the set of positive integers and for the sake of this proof regard them as written out in base 10, which makes use of ...


0

Here is the idea: Suppose $Q=\{q_n\}$ is a countable collection of distinct elements, and $R=\{r_1,...,r_k\}$ is a finite set of other (distinct) elements. Define $\phi(r_i) = q_i$ and $\phi(q_i) = q_{i+k}$. Then $\phi: Q \cup R \to Q$ is a bijection. That is, if we have a countable collection, we can 'absorb' a finite number of elements (in fact, we can ...


0

The elements of a set are separated by commas. In (C), you see that "$2$" is the first element, and "$\{2\}$" is the second element. However, the elements of (D) are "$\{2\}$" and "$\{\{2\}\}$" (which are sets), neither of which is simply the number $2$.


-1

Let $|A|= a,\quad |B|= b,\quad |C|= c \quad$ then $0 \le |A \cap B|=n_1 \le a$ or $b$ $\quad $ And $\quad $ $a$ or $b \le |A \cup B|=u_1 \le a+b $ $\implies n_1 \le u_1$ $0 \le |B \cap C|=n_2 \le b$ or $c$ $\quad $ And $\quad $ $b$ or $c \le |B \cup C|=u_2 \le b+c$ $\implies n_2 \le u_2$ $0 \le |A \cap C|=n_3 \le a$ or $c$ $\quad $ And $\quad $ $a$ or ...


0

The term on the right hand side can be written as $$A\cap(B\cup C)=(A\cap B)\cup(A \cap C)$$ Thus, the given relation becomes $$(A\cap B)\cup C=(A\cap B)\cup(A \cap C)$$ Now, for the first direction (of the iff statement) assume that $C\subseteq A$. Then $$A\cap C=C$$ and it is immediate that the above equality holds. For the other direction (of the iff ...


0

Counterexample: Let $f: \omega \rightarrow \omega$ be defined by $f(0) = f(1) = 0$ and $f(n) = 1$ if $n \geq 2$. For $n \geq 0$, let $C_n = \{0, 1\} \bigcup \{n+2, n+3, \dots\}$. Then $C_n$'s are decreasing and $f[C_n] = \{0, 1\} \subseteq C_n$ for each $n$. Let $C = \bigcap_{n \geq 0} C_n = \{0, 1\}$. Then $\bigcap_{n \geq 0} f[C_n] = \{0, 1\} \neq f[C] = ...


0

$(A \cap B) \cup C = A \cap (B \cup C) \Longleftrightarrow C \subseteq A$ $(\Rightarrow)$ $x \in C \Rightarrow x\in (A \cap B) \cup C \Rightarrow x \in A \cap (B \cup C) \Rightarrow x \in A$ $\therefore C \subset A$ $(\Leftarrow)$ $ x \in A \cap (B \cup C) \Leftrightarrow x \in (A \cap B)\cup(A \cap C) \Leftrightarrow x \in (A \cap B) \cup C$ This last ...


0

You are right - but, as it turns out, the two notions are equivalent. There are lots of ways to define a metric on $\Bbb R^k$. The "natural" Euclidean metric is $d(x,y) = \|x-y\|_2$, where $\|z\|_2 = \sqrt{z_1^2+\cdots+z_k^2}$. Another way is to set $d'(x,y) = \|x-y\|_\infty$, where $\|z\|_\infty = \max\{|z_1|,\dots,|z_k|\}$. (And there are many others ...


3

Why should $B$ not be well founded (or rather: properly defined)? The comprehension used to define $B$, i.e. to select elements from a given set by a specific property, is the main method to describe a set. Here, $B$ is the subset of $A$ that consists of precisely those elements o$x$ of $A$ for which the deus-ex-machina property $x\notin x$ holds. (Btw. ...


1

The inclusion-exclusion principle states that for sets $A, B, C$ and universal set $U$: $|A\cup B\cup C| = |A| + |B| + |C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$ In our example and letting $A$ be the set of students studying Japanese, $B$ being the set of those studying Polish, and $C$ being the set of those studying Arabic, plugging in what ...


1

HINT: Let $n\in\Bbb N$ be arbitrary, and fix $x\in A_n$. If $y\in\Omega\setminus A_n$, there is an $S_y\in\Sigma$ such that $A_n\subseteq S_y\subseteq\Omega\setminus\{y\}$. Since $\Omega$ is countable, ...


1

See the Principle of Inclusion-Exclusion for more information and a faster (but slightly less intuitive) way to solve the problem. Basically, you have $100$ on the left hand side of your equation, and on the right hand side: $(65-12-25-x)$ - Japanese only $(42-25-7-x)$ - Polish only $(45-12-7-x)$ - Arabic only $25$ - Japanese and Arabic only $12$ - ...


1

You just need to prove that $A_j \in \Sigma$. Suppose $A_j = \{x_1, x_2, \cdots\}$, then $\exists B_1 \in \Sigma$ such that $A_j \subset B_1$. Suppose $\{y_1, y_2, \cdots \}$ are elements in $B_1 $ that are not in $A_j$, then for each $y_n$ we can either find $C_n \in \Sigma$ such that $y_n \in C_n$ but all $x_n$'s are not in it, or find $D_n \in \Sigma$ ...


1

Let $f\colon A\to A$ be a surjective map. Let $$ \mathcal A=\{\,X\subseteq A\mid f|_X\colon X\to A\text{ is injective}\,\}.$$ Then $\mathcal A$ is not empty because $f|_\emptyset$ is injective. Let $B\in\mathcal A$ be maximal (how?). Then $f|_B$ is onto as otherwise we'd find $b\in A$ with $f(b)\notin f(B)$ and then $B\cup\{b\}$ would conflict with $B$'s ...


10

Let $f: A\to A$ be any function. For each $a\in A$, let $N(a)$ be the number of elements in $A$ that are mapped to $a$. Then $\sum_a N(a) = n = |A|$ because every element of $A$ is mapped to some element of $A$. (This is the statement that the fibers of $f$ partition $A$.) If $f$ is surjective, then $N(a)\ge 1$ for all $a$. If $f$ is not injective, then ...


2

The trick, when you do this by induction, is that you replace $f$ by a function $g$ which maps the $n+1$-th element to itself. Without loss of generality, we can assume $A=\{0,\ldots,n\}$. And $f\colon A\to A$ is surjective. First we can assume that $f(n)\neq n$, for if it were then by simply taking $k$ to be some element such that $f(k)=0$ and redefining ...


0

Countable Finite: $A=\mathbb{R}^+$ $B=\mathbb{R}^-$ Countable Infinite: $A=\mathbb{R}^+\cup\mathbb{N}$ $B=\mathbb{R}^-\cup\mathbb{N}$ Uncountable Infinite: $A=\mathbb{R}$ $B=\mathbb{R}$


1

You could go for $R\times\{0\}$ and $\{0\}\times R$ for the first. For b) roughly $ R\times N$ and $N\times R$ . For c)$ R\times R$ and $R\times R$


0

a) $A = \{x: x \in \mathbb{Q^c} \text{and} x \geq \sqrt{2}\}$, and $B = \{x: x \in \mathbb{Q^c} \text{and} x \leq \sqrt{2}\} \to A \cap B = \{\sqrt{2}\}$ - a finite set. b) $A = \left([0,1]\cap \mathbb{Q^c}\right)\cup \{\frac{1}{n}: n \in \mathbb{N}\}$, and $B = \left([-2,-1] \cap \mathbb{Q^c}\right)\cup \{\frac{1}{n}: n \in \mathbb{N}\}$, then $A \cap B = ...


0

Some detailed hints: Both examples can be constructed using subsets of the real numbers. For (a), I would look at certain intervals of the real line. Can you find two real intervals which intersect in a finite set? For (b), I would consider two sets $C \cup E$ and $D \cup E$, where $C$ and $D$ are disjoint uncountable subsets of real numbers and $E$ is a ...


8

To understand the $\aleph$ numbers properly you need to understand the ordinal numbers first, at least a little bit. The idea of an ordinal is to model the notion of a length of a queue to the bathroom in a party. There is an empty queue, then there is one person waiting, then another, and so on. But here we can talk about infinite queues as well. At some ...


6

This is an issue about which mathematicians who haven't studied set theory beyond what they actually use are often confused. $\aleph_1$ is the cardinality of the set of all countable ordinal numbers. $\aleph_2$ is the cardinality of the set of all ordinal numbers of cardinality $\le\aleph_1$. $\aleph_3$ is the cardinality of the set of all ordinal numbers ...


1

$(a,b) \, R \, (c,d) \iff a+b=c+d$ Every relation in a set $X$ defined by $x \sim y \iff f(x) = f(y)$, where $f:X \to Z$, is an equivalence relation because equality is an equivalence relation. There is nothing really left to prove after you make this observation. In your case, $Z= \mathbb Z$ and $f(a,b)=a+b$.


2

First point: your answer has an "if" but no "then". It therefore is ungrammatical, makes no sense, and cannot possibly be the right answer. Second point: you can do this by symbolic logic if you want, but why? IMHO it merely adds extra work. (That's in this case: in a more complicated question it might be a good idea.) The negation of "if $P$ then $Q$" ...


0

Hint: Try proving that any element $x$ of the left hand side must be an element of the right hand side, and vice versa. You can't use associativity; you're being asked to prove this associativity property.


1

Choose any $(x,y,z) \in A \times B \times (A \cap C)$ so that $x \in A$ and $y \in B$ and $z \in A \cap C$. Then $z \in A$ and $z \in C$, so $(x,y,z) \in A \times B \times A$ and $(x,y,z) \in A \times B \times C$. But then $(x,y,z) \in (A \times B \times A) \cap (A \times B \times C)$, as desired.


1

Any time you’re asked to prove a statement of the form $X\subseteq Y$, you should think first of the element-chasing approach: let $x$ be an arbitrary element of $X$, and show somehow that this forces $x$ to be an element of $Y$. If you can do that, you’ve proved that $X\subseteq Y$. In your case that means starting out like this: Let $x\in A\times ...


1

HINT: For convenience let $D_n=A_n\setminus A_{n+1}$ for $n\in\Bbb N$, and let $C=\bigcap_{n\in\Bbb N}A_n$. Use the hypotheses to show that $\mathscr{P}=\{C\}\cup\{D_n:n\in\Bbb N\}$ is a family of pairwise disjoint sets whose union is $U$. (In other words, they form a partition of $U$ except that some may be empty.) A generalization of the desired result can ...


2

hint: to get from $$ \{x|x⊆A∩B\} $$ to $$ \{x|x∈P(A) \text{ and }x∈P(B)\} $$ The property $$ X\subset Y \iff X\cup Y = Y $$can be useful. solution: $$\begin{align} \{x|x∈P(A) \text{ and }x∈P(B)\} &= \{x|x\subset A \text{ and }x\subset B\}\\ &= \{x|x\cup A = A \text{ and }x\cup B = B\}\\ &= \{x|x\cup A \cup B = A\cup B\}\\ &= ...


2

You are going in the right direction. $\mathcal{P}(A) = \{x | x \subseteq A \}$, so just by replacing the symbols we see $\mathcal{P}(A \cap B) = \{x | x \subseteq A \cap B\}$. So you are being asked to relate $$\{x | x \subseteq A \cap B\}$$ To $\mathcal{P}(A) \cap \mathcal{P}(B)$ which is $$\{x | x \in \mathcal{P}(A) \text{ and } x \in \mathcal{P}(B)\}$$ ...


0

I think you only need to prove $A_i \backslash A_{i+1}$ and $A_j \backslash A_{j+1}$ are disjoint for $i<j$. This follows from for $i+1\leq j$, we have $A_{j}\subset A_{i+1}$. Then the statement holds by intersects $\Big(\bigcup_{n=0}^\infty (A_{2n} \backslash A_{2n+1})\Big)^c$ on both sides of your assumption 2.


0

No, in general this is wrong! Consider the Borel algebra generated by the cofinite topology: $$\Sigma:=\{E\subseteq[0,1]:\#E\leq\aleph_0\lor\#E^c\leq\aleph_0\}=\sigma(\mathcal{T}_{cofinite})$$ and the finite Borel measure: $$\lambda(\#E\leq\aleph_0):=0$$ $$\lambda(\#E^c\leq\aleph_0):=1$$ Then the atoms are all the uncountables but no singleton is a point ...


2

The example you give actually is a $\sigma$-finite Borel measure. Equip $[0,1]$ with the cofinite topology (in which a set is open iff it is either empty or its complement is finite). Then your $\Sigma$ is the Borel $\sigma$-algebra of the cofinite topology (it is a nice exercise to verify this). However, there is the following result: Proposition. Let ...


1

To show that $X \cap Y = Y$, it suffices to show that $Y \subseteq X$. So all we need to do is prove that $\overline C - A \subseteq \overline A \cup B$. Indeed: $$ \overline C - A = \overline C \cap \overline A \subseteq \overline A \subseteq \overline A \cup B $$


1

Hints: $f$ must one-to-one for the inverse function to exist. Consider what happens if it is onto $S_2$ or not. (See Bijection, injection, surjection)


2

Modern set theory conceives of a set as an abstraction of a property. Two properties might seem different, but be essentially the same because they are true of the same objects. For example, the property $\mathcal O_1$ of being a natural number of the form $2n+1$, and the property $\mathcal O_2$ of being a natural number that is the difference of two ...


1

In the case of two empty sets, $\emptyset_1, \emptyset_2$, we have that $\forall x(x\in\emptyset_1\Leftrightarrow x\in \emptyset_2)$ is vacuously true.


1

As $$\forall x(x\not\in\emptyset_i)$$ is obvious that $$x\in\emptyset_1\iff x\in\emptyset_2$$ because both conditions are false.


3

$\mathbb{N}$ has a minimal element; $\mathbb{Z}$ doesn't. An order isomorphism preserves minimality of an individual element. Can you show this?


2

You can't prove that there is no bijection between $\Bbb N$ and $\Bbb Z$, because there is one. On the other hand, you can certainly prove that their natural orders are not isomorphic. Simply ask yourself, if $f$ is an order preserving injection from $\Bbb N$ to $\Bbb Z$, and $k=f(0)$, what could $f^{-1}(k-1)$ be?


1

If $R$ is anti-symmetric then any subset of $R$ is anti-symmetric, also $R\cap S$. I think the normal way of doing such things is: If $(a,b),(b,a)\in R\cap S\implies (a,b),(b,a)\in R\implies a=b$.


0

If your new equivalence relation $\underset{S}{\sim}$ is a constriction from the whole set $E$, then the answer is yes. Equivalence relation have to satisfy 3 axioms: Reflexivity. $a \underset{S}{\sim} a$. It is true for new relation because of the fact that we can look at the element $a$ like an element of the whole $E$ and use fact that $a ...


1

Yes. But you should give your reasoning if this is an exercise. Try arguing that X have a subset of every order and so assuming it have a finite cardinality contradict this fact (how many subsets can a set of cardinality n have?)



Top 50 recent answers are included