Tag Info

Hot answers tagged

23

Cantor's diagonal argument proves (in any base, with some care) that any list of reals between $0$ and $1$ (or any other bounds, or no bounds at all) misses at least one real number. It does not mean that only one real is missing. In fact, any list of reals misses almost all reals. Cantor's argument is not meant to be a machine that produces reals not in ...


19

There is no contradiction. The set of all $x$ such that $x\in A$ and $x\notin A$ is empty. Since it is impossible that $x$ is both in $A$ and not in $A$ simultaneously.


15

The other answers are, of course, all correct. But here's another way to think about it, that will, perhaps, build on your intuition. You're right that there is a contradiction. The statements "$x \in A$" and $x \notin A$ are mutually exclusive, or contradictory. Therefore, the statement that "$x \in A \mathrel{\mathrm{and}} x \notin A$" must be false for ...


15

The definition of equicardinal is that there exists a bijection between the sets. You are trying to define "not equicardinal" as "there exists a bijection between one set and a strict subset of another". This definition is not a good one, as all Dedekind infinite sets (such as $\mathbb{Z}, \mathbb{R}$) have the property that they are bijective with strict ...


12

There is no element that is in $A$ and not in $A$ at the same time, so the answer is the empty set.


12

If n is a natural number, n can never take $\infty$ because $\infty$ is not a natural number, so it only holds for finite values of n. As far as I know it's not even well-defined to ask "does it hold for n=$\infty$?", in the sense that people don't know what you mean, specifically ($\infty$ is not a number). But if you've proven something by induction, then ...


8

That won't quite work - as described, $n+0.1 \mapsto 2n+0.1$ and $2n \mapsto 2n+0.1$, so it isn't a bijection. The easiest way I can think of for $\mathbb{R} \rightarrow \mathbb{R} \setminus \mathbb{N}$ would be to biject $\mathbb{Z} \rightarrow \mathbb{Z} \setminus \mathbb{N}$ and let all non-integers remain fixed. (For example, map $\mathbb{N}$ to ...


7

The statement is not true in general, even for finite sets. A very simple counterexample is obtained by letting your universal set, $A$, and $B$ all be $\{0\}$: then $A\cap B=\{0\}$, so $|A\cap B|=1$, but $A^C=\varnothing$, so $|A^C|=0$. Clearly this idea can be extended to any non-empty universal set $U$: just take $A=B=U$, in which case $|A\cap ...


7

The order of the binary numbers $s_n$ are arbitrary. For example, if we swapped the places of $s_2$ and $s_3$, a different number will be formed. Hence there are still an infinite number of irrational numbers that can be generated.


6

It is useful to note that $A - B = A \cap B^C$. Taking $B = A$, we see $A- A = A \cap A^C = \emptyset$ by definition of complement.


5

As mentioned by others as well, the statement is that $A\sim B \Leftrightarrow \exists \phi:A\leftrightarrow B$ (i.e., $A$ and $B$ are of the same cardinality if there exists a bijection between $A$ and $B$) That is not to say that all maps between them must be bijective, just that there must be at least one such map. Consider $A=\mathbb{N}$ and ...


5

As far as I know, there isn't. The concept of a "non-surjective and non-injective function" just doesn't generally arise often enough to need a special term.


5

The key point you're missing is that sets are only about membership; they have no concept of "repetition". Either a set contains $0$ or it doesn't; there is only those two options. Here is a proof: $x \in \{ 0, 0 \}$ if and only if $x = 0$ or $x = 0$. Therefore, $x \in \{ 0, 0 \}$ if and only if $x = 0$ Also, $x \in \{ 0 \}$ if and only if ...


5

Consider $A=\{3,7\}$, $B=\{3,7,9001\}$ and $f$ defined by $f(3):=3$ $f(7):=7$. As long as $g$ maps $3$ back to $3$ and $7$ back to $7$, the function $g\circ f$ will be the identity on $A$, while there are two options to where $g$ may map $9001$ to.


4

It would be very unusual to set up things such that the set of real numbers is the same set as $\mathcal P(\mathbb N)$. What you can do -- in several different ways -- is to show that there is a bijection between the two sets. One fairly painless way is to start by knowing that $\mathbb Q$ is countable such that there is a surjection $f:\mathbb N\to\mathbb ...


4

HINT: If $q_n\to 0$, then given any infinite subset of $\Bbb N$, $A$, replacing $q_n$ for $n\in A$, with $0$ is again a Cauchy sequence converging to $0$.


4

Regular inductive proofs work only over $\mathbb{N}$, the set of natural numbers. The proof that "inductive proofs work" depends on the well-ordering property of $\mathbb{N}$, and $\infty \not\in \mathbb{N}$. As people in the comments have pointed out, induction can be extended to other well-ordered sets as well. Regardless, it is meaningless to ask if a ...


4

I think the fundamental error here is a mistaken notion of what the Pigeonhole Principle is. Nowhere in the Wikipedia page cited in the question does it say there is any rule over which hole each pigeon may go into. As is evident from some comments on other answers the argument in the question is based on the misconception that the Pigeonhole Principle ...


4

Finite set is a set that for some natural number $k$, there is a bijection between the set and $\{1,\ldots,k\}$. An infinite set is a set which is not finite. $\Bbb N$ is not finite, so it is infinite. Countably infinite set is a set that has a bijection between itself and $\Bbb N$. An uncountable set is a[n infinite] set which is not countable. So an ...


4

The standard (Bourbaki) definition (which is said to be canonical) of a function from a set $X$ to $Y$ is: a function is $(f,X,Y)$ with $f\subset X\times Y$ such that for every $x\in X$ there is a unique $y\in Y$ with $(x,y)\in f$ (it is common to write $y=f(x)$ for the statement $(x,y)\in f$). Thus both 1. and 2. are correct ("unique"="there is at least ...


3

It denotes a collection $\mathscr A$ of objects, and it means there is surjection $f: I\rightarrow \mathscr A$. One often has that $f$ is injective, so that objects $f(i) = A_i\in \mathscr A$ and $f(j)= A_j\in\mathscr A$ corresponding to distinct indices $i\in I$ and $j\in I$ are themselves distinct, but this need not be the case. It simply means that ...


3

Your question has nothing to do with group theory; the fact that inverse functions are necessarily bijective is a matter of set theory. And if you know, as a suppose, that in order to have an inverse function, a function $f$ must be bijective, it is pretty obvious that the inverse $f^{-1}$ will always be bijective. After all the requirement for an inverse is ...


3

Given an infinite set of $A$ we can define an injection from $A$ to $\mathbb N$ by the inclusiom mapping. define the injective map from $\mathbb N$ to $A$ where $1$ goes to the minimum element of $\mathbb A$, where $2$ goes to the minimum element of $A\setminus f(1)$ and in general map $n$ to the minimum element of $A\setminus \{f(i)|1\leq i\leq(n-1)\}$. So ...


3

By definition, we have that $$x\in B\cap C\stackrel{def.}\iff x\in B\;\;\wedge\,x\in C$$ The logical negation of the above is $$x\notin B\cap C\iff \neg\left(x\in B\wedge\,x\in C\right)$$ Now you just need to convince yourself that the logical negation of the conjuction is the disjunction of the negation of each factor, i.e. $$\neg\left(A\wedge ...


3

If by group you mean "set", sure. It's a legitimate set. Note that if $A$ is a set, then the empty set is an element of the power set of $A$. And yes, you have computed the power set correctly.


3

I think that the issue here is mostly linguistic. Saying that something is infinite simply says that it is not finite. Saying that I have more than two students in my class tells you nothing about whether there are three, or six, or 42 students in my class. It is true that both $\Bbb N$ and $\Bbb R$ are infinite. But it tells you nothing about comparing ...


3

There is an informal concept of "function", which says that a function is any correspondence (itself an informal term) that assigns one definite output value to each input value of the function. This informal concept has various formalizations, depending on the precise use one has for it. The set-based concept of a function as a set of ordered pairs such ...


3

The set $f(A)$ contains at most $|A|$ elements. If $f(A)=B$ then $|A|\ge |f(A)|=|B|$.


3

It is meaningless to say that "$n$ takes $\pm \infty$" so long as $n\in \mathbb{N}$ simply because $\pm \infty \not \in \mathbb{N}$. So if $n$ is finite then the Induction Principle says that the integer $n$ can be reached starting from $1$ (if the Induction Basis exists) in finitely many steps, however large. Hence one claims that for all $n\in \mathbb{N}$ ...


3

This is true. If $f\colon A\to B$ is injective, then $S_f(X)=f(X)$ is injective as a function from $\mathcal P(A)$ to $\mathcal P(B)$. To prove this, verify the definition of "injective", namely take $X$ and $Y$ which are different and show that $f(X)\neq f(Y)$. HINT: Suppose that $x\in X$ and $x\notin Y$, can $f(x)$ be an element of $f(Y)$? For the ...



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