Tag Info

New answers tagged

1

$r$ is an example of a relation, which is a simply a subset $R \subseteq X \times Y$ of the Cartesian product of two given sets $X, Y$. (For $r$, $X$, $Y$ are not specified but we could certainly take $$X = [-1, 1], \quad Y = [0, 1].)$$ We say that a relation $R \subseteq X \times Y$ is a function $R: X \to Y$ iff for all $x \in X$ there is exactly one $y ...


6

Consider the statement $x \in \bigcap_{m=1}^\infty \bigcup_{n=m}^\infty A_n$. This means exactly that $x \in \bigcup_{n=m}^\infty A_n$ for every $m$. (Here I have expanded the definition of the intersection.) This means exactly that for every $m$, $x \in A_n$ for some $n \geq m$. (Here I have expanded the definition of the union.) This means exactly that $x$ ...


0

Let $b$ be an arbitrary element in $B$. If $A$ and $B$ are uncountable and $A\times B$ is countable, then $A\times\{b\}$ is also countable, because $A\times\{b\}\subset A\times B$. But $A$ is uncountable iff $A\times\{b\}$ does. This contradicts.


0

Here's an easy proof (if you already know every subset of $\Bbb N$ is countable) -- please only look at this after you've already attempted the problem yourself given the other hints: Suppose $R$ and $Y$ are uncountable sets. Suppose by contradiction $R \times Y$ is countable. Let $\phi : R \times Y \to \Bbb N$ be the bijection you can find. Then fix ...


1

HINT: This is done in two steps: If $A$ and $B$ are not empty, then there is an injective function from $A$ into $A\times B$. If $A$ is uncountable there is an injective function from $A$ into $D$, then $D$ is uncountable.


1

You can use the Cantor diagonalization argument to show that $$A \text{ and } B \text{ countable } \implies A\times B \text{ countable.}$$ So: $$A \times B \text{ uncountable} \implies A \text{ or } B \text{ is uncountable}.$$ Alternatively, you can fix $b \in B$. Then $A \times \{b\}$ has the same quantity of elements that $A$, which is uncountable, and $A ...


1

Yes. Do it by contradiction. Assume there is a bijection between $\mathbb{N}$ and the cartesian product and show this would imply there is a bijection with at least one of the original sets.


0

If either $A$ or $B$ are empty, then $A\times B=\varnothing$. In that case there is only one relation between the two sets. The empty relation. And there are certainly no proper subsets to $A\times B$.


1

Recall that the definition of a relation $R$ between two sets $A$ and $B$ is a subset $R \subseteq A \times B$ so relations are not always a proper subset of $A \times B$. For example, given $A = \{a,b,c\}$ and $B = \{d,e,f\}$, we have $R = \{(a,d),(a,e),(a,f),(b,d),(b,e),(b,f),(c,d),(c,e),(c,f)\}$ which covers the entire set $A \times B$.


4

It is entirely valid to have a relation that relates every element of $A$ to every element of $B$. It can even have fancy properties -- for example if $B$ is a singleton set, the relation $A\times B$ will be a function!


0

Let's first assume that (2) holds. Let $g: X \to X$ be a function, which is surjective, but not not injective. From this we can deduce, that the set $X$ contains infintely many elements, since for a finite $X$ every injective function is also surjective. We now choose a $x_1 \in X$. Suppose that $x_1, \ldots, x_n \in X$ have been chosen. Then we choose a ...


0

Here is an alternative solution, which additionally establishes that the order type of $R$ is $\alpha^\beta$, by constructing an explicit order isomorphism from the set $A=\{f:\beta\to\alpha:f\mbox{ has finite support}\}$ to the ordinal $\alpha^\beta$ (defined recursively via $\alpha^{\beta+1}=\alpha^\beta\alpha$, ...


0

$\bf (1) \Rightarrow (2)$ Define $g$ as: $$ g(x) = \begin{cases} f(f^{-1}(x)+1) & \text{if $x$ is in the image of $f$} \\ x & \text{otherwise} \end{cases} $$ Then $g$ is injective, but no element maps to $f(1)$. $\bf (2) \Rightarrow (1)$ Assume that $(1)$ is not true. Then $X$ must be finite. If $X$ has $n$ elements, then an injective function ...


8

The first, and perhaps deepest problem is on the first line. $X/{\sim}$ is not the union of the equivalence classes. It is the set of equivalence classes. More specifically, $\bigcup_{x\in X}[x]=X$, whereas $X/{\sim}=\{[x]\mid x\in X\}$. It is a set whose elements are subsets of $X$. So a function from $X$ to $X/{\sim}$ is a function mapping points of $X$ ...


2

First responding to your claim "science and specially mathematics are based on the set theory": I agree with Zev. Today we could pick an entirely different foundation for mathematics and I'm rather certain that physicists, biologists, and chemists won't change their attitude with how they apply mathematics to their work. You don't need to think of simple ...


10

Yes. This is a trivial consequence of a theorem by Steinhaus: Suppose that $X$ has a positive measure, then $X-X=\{x-y\mid x,y\in X\}$ contains an interval around $0$. It is not hard to prove that if $X$ is infinite, then $X$ and $X-X$ are equipotent (there is a surjection from $X^2$ onto $X-X$, and there is an obvious injection from $X$ into $X-X$). ...


1

You want to show that $A\cup \phi = A$. Then you have to show $A\subseteq A\cup \phi $ $A\cup \phi \subseteq A$ If $x\in A$ then $x\in A\cup \phi $ obviously. If $x\in A\cup \phi $ then either $x\in A$ or $x\in \phi$ but the latter case is impossible since $\phi $ is the set with no members. So $x$ miust be in $A$. The proof for intersections is ...


2

Two sets $A$ and $B$ are equal, if and only if for all $x$ we have $x\in A \Leftrightarrow x\in B$. Alternatively you can show $A\subseteq B$ and $B\subseteq A$. We have: $$x\in A \cup \emptyset \Leftrightarrow x\in A \vee x\in \emptyset \Leftrightarrow x\in A$$ so $A\cup \emptyset = A$. (Note, that $x\in A\Rightarrow x\in A\vee \phi$ is true for any ...


4

Notice that $\Bbb R \times \{0\} \subset \Bbb R \times \Bbb R$ has the same quantity of elements that $\Bbb R$¹. So if you prove that $\Bbb R$ is uncountable, you're done. ¹ Actually $|\Bbb R| = |\Bbb R^n|$ for every $n$.


0

Real numbers are uncountable, hence the Cartesian product of real numbers is uncountable.


1

The points on the curve $t\mapsto (1,t,t^2,t^3,\ldots,t^{n-1})$ satisfy this. The determinant of any matrix whose rows consist of $n$ distinct points on this curve is nonzero, as it is the Vandermonde matrix of the elements.


2

It can, but it usually isn't. We always have $\varnothing\in2^A$ and also $\varnothing\subset2^A$. So there exists an element of the power set $2^A$ which is also a subset of the power set $2^A$. On the other hand, in your example, $\{7\}\in2^A$, but $\{7\}\not\subset2^A$.


0

Here is an explicit formula for a bijection with $\mathbf N$, using the ordering first by ‘total degree’, then by first coordinate (known as grlex order on $\mathbf N\times\mathbf N$): $$f(n_1,n_2)=\frac{(n_1+n_2)(n_1+n_2+1)}2+n_1+1.$$


2

Another easy way :take a pair, write down the numbers in any numeration basis. For example (decimal) 1234 and 987. Add extra zeros where needed so they are the same length, and shuffle them 1 2 3 4 0 9 8 7 -------- 10293847 Reverse operation : take digits with even (resp. odd) positions. EDIT: and of course there are explicit formulas, here given as 3 ...


3

To a question in title No, $2^A \not\subseteq A$ because a power set of any $A$ has a cardinality strictly greater than $A$ itself. To a question in text No, $f(a)\subseteq 2^A$ does not hold in general, as $f(a)$ is by definition an element of $2^A$, and an element of a set is not (in general) a subset of the same set. Althoug in some special cases it ...


1

Yes, here is a bijection example, where $p_k$ is the $kth$ prime number: $f(x,y)=p_x^{p_y}$ $g(x)=(x,x)$


3

Depends on which topology you are talking about. If it is the topology on the real number system $\mathbb{R}$, then $\mathbb{R}$ is the closure of itself. If it is the topology on the extended real number system $\bar{\mathbb{R}}$, then $\bar{\mathbb{R}}$ is the closure of $\mathbb{R}$.


3

First, list the pairs in which the sum is $0$: $$(0,0)$$ Then those in which the sum is $1$: $$(1,0),(0,1)$$ Then those in which the sum is $2$: $$(2,0),(1,1),(0,2)$$ Then those in which the sum is $3$: $$(3,0),(2,1),(1,2),(0,3)$$ And so on.


10

Consider the function $f: \mathbb{N} \times \mathbb{N} \longrightarrow \mathbb{N}$ defined by $f(a,b)=2^a \, 3^b$. Then this function is one-one. Consequently cardinality of $\mathbb{N} \times \mathbb{N}$ is "no more than" (if I may use this phrase) that of $\mathbb{N}$, hence countable.


2

Yes, you do the diagonalization like with rational numbers which is basically the same thing.


1

It matters with respected to which sense of convergence you are speaking of. If a point is in the space because it is the limit of a cauchy sequence, then yes R is it's own closure.


2

I am admittedly no expert in set theory, but what I believe to be true is this: In answer to your questions- 1) The answer to this is unknown. A famous result (known as Godel's Theorem) says that set theory is not "powerful" enough to prove its own (logical) consistency. This does not preclude proving set theory is consistent using some more "inclusive" ...


1

Here is an alternative argument which is almost as simple as yours but more general; e.g., it also shows that the set of transcendental numbers is not closed under multiplication. Theorem. If $X$ is a subset of $\mathbb R$ such that (a) the complement $\mathbb R\setminus X$ is countable, and (b) there is a nonzero number $c\in\mathbb R\setminus X$, then $X$ ...


0

If a positive integer is not a perfect squae then its square root is irrational: So take a perfect square, say $100$ and factorize it into two numbers which are not perfect squares, say $100=5\times20$. Now take square roots on both sides of the equation. We get $10=\sqrt{100}=\sqrt{5}\times\sqrt{20}$, the last two are irrationals with an integer as their ...


1

Now the challenge is that not all numbers under a root is irrational. For example, $$\sqrt{4} = 2, \sqrt{9} = 3, \sqrt{16} = 4, ..... $$ are all rational numbers However, all the numbers under the square root between these numbers are irrational. For example, $$\sqrt{5}, \sqrt{6}, \sqrt{7},\sqrt{8}$$ are all irrational numbers and of course the most popular ...


3

Usually, the set of irrational numbers is written simply as $\mathbb R\setminus \mathbb Q$. As for the symbolic proof, my advice is "Avoid symbolic proofs." A good proof in mathematics is not one that is fully written with symbols alone. A good proof is written in words, but is still mathematically rigorous, such that there is no doubt that any ...


4

You denote (not notate!) the set of rational numbers by $\mathbb Q$ and that of the real numbers by $\mathbb R$ ; therefore the set of irrational numbers can be written as $\mathbb R \backslash \mathbb Q$ or $\mathbb R - \mathbb Q$, depending on your taste. Your proof could simply go as follows : since $\sqrt 2 \in \mathbb R \backslash \mathbb Q$ but $(\sqrt ...


0

Proof of closure of multiplication of positive rational numbers: Let $q_1,q_2\in\mathbb{Q}^+$. Then $q_1 = \frac{a}{b}$ and $q_2=\frac{c}{d}$ where $(a,b,c,d)\in(\mathbb{N}\setminus\{0\})^4$. You have then that $q_1\cdot q_2 = \frac{a}{b}\cdot \frac{c}{d}$ which by definition of multiplication of rational numbers becomes $\frac{a\cdot b}{c\cdot d}$. Note ...


1

"Russel's paradox" is not a theorem or axiom per se, rather it's a motivation for restrictions of axioms. This paradox made us realize that we need something like ZFC. It doesn't make sense to say "such and such theorem is equivalent to Russel's Paradox." In order to prove those statements, the key thing needed is the "Axiom of Regularity": ...


1

Where are we proving things? This matters a lot, because different choices of axioms for set theory will give different answers. According to the standard set of axioms - ZFC - both statements are true; however, in (say) NF, another set of axioms, they are false! So to show (in some system) that these aren't sets, we need to use some specific axioms in ...


1

I think you are confused in thinking that the union of $\{A,A\cup f[A]\}$ is the closure. In general that is not a closure of $A$ under $f$. Think of $A=\{1\}\subseteq \mathbb{Z}$ and $f(x)=2x$. Then you need to iterate the $h$ function infinitely many times and take the union of all the ranges of $h$ to get the correct closure which is $2\mathbb{N}^+$. If ...


3

This might depend on the form of logic you are using. It is certainly true if you use "standard" logic. And as has already been pointed out it just follows from basic logical axioms. Surprisingly though there are (fairly often) used logical systems where the statement $P\vee \neg P$ (called the law of excluded middle) is not provable. An example of this ...


16

Yes, though this has nothing to do with set theory really and is much more about propositional logic. If we replace "$A \in B$" with the propositional variable $\textrm{P}$, then your statement is simply an instance of $$\textrm{P} \lor \lnot \textrm{P}$$ which is of course always true.


1

Notice that $$(A\subset B)\vee (A\not\subset B)\iff (A\subset B)\vee(A\cap B^c\neq\emptyset)$$ which is always true.


0

Two very standard texts on set theory are Introduction to Set Theory by Hrbacek & Jech. This book approaches the subject informally(not much formal logic) and has a good range of topics. Also there is Elements of Set Theory by Enderton. This book requires some familiarity with formal logic and so it a bit more rigorous than Hrbacek & Jech. It ...


4

Whenever you have $$ x\in f^{-1}(A) $$ you can say $f(x)\in A$ and conversely. Thus $$ x\in f^{-1}(A)\implies f(x)\in A\implies f(x)\in B\implies x\in f^{-1}(B) $$


4

Take an arbitrary $x \in f^{-1}(A)$. By definition, $f(x) \in A$. As $A \subset B$, $f(x) \in B$. As $f(x) \in B$, it must also lie in ....


0

(a): Suppose $x\in A\cup B$. Then $x\in A$ or $x\in B$. If $x\in A$, then $x\in A\cup B\cup C$. If, however, $x\in B$, then $x\in A\cup B\cup C$. Either way, $x\in A\cup B\cup C$ when $x\in A\cup B$. Thus, $A\cup B\subseteq A\cup B\cup C$. (b): Suppose $x\in A\cap B\cap C$. Then $x\in A$ and $x\in B$ and $x\in C$. Hence, we have that $x\in A$ and $x\in B$; ...


0

Am I the only one who sees a mistake here? Quote: "By the Cantor–Bernstein–Schroeder theorem, if $X\precsim Y$ and $Y\succsim X$, then $X\cong Y$, so we can define a relation $\leq$ on cardinalities as follows:" That's not the Cantor-Bernstein-Schroeder theorem. This is the CBS theorem: If $X\precsim Y$ and $Y\precsim X$, then $X\cong Y$ where the original ...



Top 50 recent answers are included