Tag Info

Hot answers tagged

35

The Zermelo-Fraenkel Axioms for set theory were developed in response. The key axiom which obviates Russell's Paradox is the Axiom of Specification, which, roughly, allows new sets to be built based on a predicate (condition), but only quantified over some set. That is, for some predicate $p(x)$ and a set $A$ the set $\{x \in A : p(x)\}$ exists by the ...


9

I'm aware of two principal approaches to solving Russell's paradox: One is to reject $x \not\in x$ as a formula. This is what Russell himself did with his theory of types: inhabitants on the universe are indexed with natural numers (types), and $x \in y$ is only a valid formula if the type of $y$ is one greater than the type of $x$. Basically, this slices ...


8

It lead to the development of a number of solutions in logic and set theory, as well as other insights. You can find a nice introduction to the topic in the Stanford Encyclopedia of Philosophy section on Russell's Paradox in Contemporary Logic.


6

To the best of my knowledge, the Theory of Types http://en.wikipedia.org/wiki/Type_theory , was designed specifically to address this. Basically you restrict the objects you can refer to , by the choice of types.


6

Another way of escaping from Russell's paradox, not yet mentioned in the answers here, is Morse-Kelley set theory. In MK set theory, there are good collections (sets) and bad collections (classes) and only the good collections (sets) are allowed to be members; unless $x$ is a set, $x\notin y$ holds for all $y$. Suppose $\Phi$ is some property. In naïve ...


6

The complex numbers can be ordered. It cannot be made into an ordered field with the usual addition and multiplication. And that's different. We can, for example, define $(a+bi)\preceq(c+di)$ if and only if $a<c$ or $a=c$ and $b\leq d$. This defines a linear ordering of the complex numbers. Another way would be to note that $\Bbb C$ and $\Bbb R$ have ...


6

One way: You can adapt the proof of Cantor's theorem directly: Suppose $f:X\to\mathcal P(\mathcal P(X))$ and consider $$ \{\{x\}\mid x \in X, \{x\} \notin f(x) \} \subseteq \mathcal P(X)$$ This can't be in the image of $f$. Thus there is no surjection $X\to\mathcal P(\mathcal P(X))$. Another: It is trivial that there are injections $X\to\mathcal P(X)$ and ...


6

Here is a general road map: Show that $\Bbb{R^N}$, all the sequences of real numbers has cardinality $2^{\aleph_0}$. Find a surjection from $\Bbb{R^N}$ onto the set of all countable subsets of $\Bbb R$. Conclude (using what you already know) that the cardinals are equal. Let me give you an additional hint that the axiom of choice is used in the third ...


6

It breaks reading backwards here: $x \in A$ and $x \in B$ $\Leftrightarrow f(x) \in f(A)$ and $f(x)\in f(B)$ You can't guarantee that it is the same $x$ that gives the value $f(x)$. To be more exact, you should have taken $y \in f(A)\cap f(B)$. Then $y \in f(A)$ and $y \in f(B)$. So exists $x_1\in A$ and $x_2 \in B$ such that $f(x_1)=f(x_2) = y$. ...


5

All non-empty subsets is $2^8 - 1$. There are $2^4 - 1$ non-empty subsets that consist only of even numbers, and $2^4 - 1$ non-empty ones that only have odd numbers. These are mutually exclusive sets. We substract these last 2 from the first to get the right answer. This was my first approach. Your answer is also correct, any good set can be seen as a ...


5

First let's make things slightly simpler. Note that if $f(x+y)=f(x)f(y)$, then $\log f(x+y)=\log f(x)+\log f(y)$. So it sufficient to talk about $g(x+y)=g(x)+g(y)$. Moreover, $f$ is continuous if and only if $g$ is continuous. Why is this simpler? Because now it's not difficult to show that $g$ is a linear function from $\Bbb R$ to itself, as a vector space ...


5

They're equal. Indeed, it's not too hard to show that the function $f\colon [1, 2] \to [1, 10]$ defined by: $$ f(x) = 9x - 8 $$ is a bijection (which shows that the two sets have equal cardinality).


5

The symbol $\subset$ can be ambiguous. $A\subset B$ usually allows the possibility that $A=B$, but some authors use it to mean that $A$ is a proper subset of $B$, so that $A\subset B$ implies $A\ne B$. A variety of symbols have been invented to clear up this ambiguity and make explicit whether the $A=B$ possibility is intended: $$\begin{array}{cl} ...


4

Your set is a group under addition and it is isomorphic to the additive group of maps $f\colon \mathbb N\to\mathbb Z$ where $f(n)=0$ for all but finitely many $n$; or to the direct sum of infinitely many copies of $\mathbb Z$. But the most strikingly simple example of a group isomorphic to yours is: $$\mathbb Q_{>0}, $$ the group of positive rational ...


4

The product of two relations $R,S$ is $R S = \{(a,c) : \exists b (a,b) \in R \wedge (b,c) \in S\}$. It is now clear what $R^n$ is. (In order to avoid confusions, one should better write $R \circ S$ and $R^{\circ n}$.)


4

If $f$ is not injective, there might be some $y\notin A\cap B$ such that $f(y)=f(x)$. For example if you take $A=B=\{x\}$ you have that $\{y,x\}\subseteq\{w\mid f(w)=f(x)\}$. But of course $y\notin A\cap B=\{x\}$.


3

Your answer to the "disjoint" part is fine. You could perhaps make it just slightly quicker: Assume $l<k$ and $x\in F_l$. Then $x\in E_l\subseteq\bigcup_{j=1}^{k-1}E_j$, so $x\notin F_k$. Hence $F_l\cap F_k=\emptyset$. To prove the unions are equal, you would do exactly as you have done to show $\bigcup F_j\subseteq \bigcup E_j$, but unfortunately it ...


3

Functions $f$ and $g$ fail to commute if for some $x$, $g(f(x)) \ne f(g(x))$. Take any $f$ such that $f(x) \ne x$ for some $x$. Now $g(f(x))$ can be chosen independently of $g(x)$, and in particular it can be some element other than $f(g(x))$.


3

This is a classic riddle, whose solution surprisingly requires the axiom of choice as discussed here. The solution, however, is short and clever. Encode the colors into $0$ and $1$, and define the equivalence relation on $2^\Bbb N$, $\langle x_i\rangle\sim\langle y_i\rangle$ if and only if there is some $k$ such that for all $n\geq k$, $x_n=y_n$. Using the ...


3

Since the $X_i$ are distinct, there is an $m\in\omega$ such that the sets $X_i\cap m$ are distinct. It follows that the $k$ sets $X_i\cap n$ are distinct for each $n\ge m$. Thus, for each $n\ge m$ there is an $f_n\in{}^{\wp(n)}\wp(n)$ such that $f_n[X_i\cap n]=Y_i\cap n$ for each $i<k$, and $\{\langle n,f_n\rangle:n\ge m\}$ is an infinite subset of ...


3

The way around Russell's paradox which Georg Cantor chose (and if you read Russell's letter describing the paradox to Frege, who fell into it, so to speak--this is found on pp 124-5 of van Heijenoort's book "From Frege to Goedel: A Source Book in Mathematical Logic, 1879-1931"--you find that Russell held that his paradox showed "that under certain ...


3

Here's another option; we shall use the Cantor-Schroeder-Bernstein Theorem. Suppose for the sake of a contradiction that you have a bijection $f:\mathcal{P}(\mathcal{P}(X))\rightarrow X$, which in particular is an injection. Next, $X$ injects into $\mathcal{P}(X)$, so let $g$ be such an injection. Then $g\circ f:\mathcal{P}(\mathcal{P}(X)) \to ...


3

It means proper inclusion, i.e. $A\subsetneqq B$ if and only if $A\subseteq B$ and $A\neq B$. It is used rather than $\subset$ to emphasise that there is definitely not equality between the two sets.


3

Let's look at the general case to understand what is going on here: $$(a,b] = \{x\in\Bbb R: a< x\le b\}.$$ In this case, $(1,1] = \{x\in\Bbb R: 1 < x\le 1\}.$ That is to say that if $x\in (1,1]$, it is simultaneously greater than $1$ and less than or equal to $1$. What does this tell you?


3

Not even the empty set has that property. For any set $A$ we can show $A\ne\{x\mid x\notin A\}$. Namely, either $42\in A$ (in which case $42\notin \{x\mid x\notin A\}$), or $42\notin A$ (in which case $42\in \{x\mid x\notin A\}$). In both cases we have found something that is a member of exactly one of the collections, so they're not the same.


3

Given these conditions you will only be able to show that $h$ is injective if $f$ is surjective. Then you would have $$\begin{align}h(x') = h(y') &\Rightarrow h(f(x)) = h(f(y)) , \text{for some}\ \ x,y \in X \\ &\Rightarrow(h \circ f)(x)=(h\circ f)(y) \Rightarrow x = y \Rightarrow x' =f(x) = f(y) = y'\\&\Rightarrow x' = y'\end{align}$$ We ...


2

$h$ need not be injective. As an example, let $f$ be the embedding of the integers in the real numbers, and $h$ be the floor function. It is only necessary that the restriction of $h$ to the image of $f$ is injective.


2

There is no difference between the two. The author simply chose to use different notation.


2

I think $R^n$ is the set of ordered pairs $(x, y)$ such that $y-x\geq n$. Also, $<$ is already transitive, so it's its own transitive closure. $R^n$ is also transitive.


2

The complement of $A$, $A^c$ is such that $$A^c = \{x\mid x\notin A\}$$ A set cannot also be its own complement, and we have $A\neq A^c \implies A\neq \{x\mid x \notin A\}$



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