Tag Info

New answers tagged

0

Let Go be the set of students who only took Greek and let LG, SG and LSG be the sets of intersections of L and G, S and G and L, S and G respectively. Then |Go|=|G|-|LG|-|SG|+|LSG|.


0

The Cantor-Schroder-Bernstein theorem tells you that if there exists an injection from set A to set B and an injection from set B to set A, there exists a bijection between $A$ and $B$ and they have the same cardinality. An injection $f:\mathbb{R}^+ \to \mathbb{R}$ is easy - just use the inclusion map ($f(x)=x$). An injection $g:\mathbb{R} \to \mathbb{R}+$ ...


0

Two sets $A$ and $B$ are said to be equicardinal if there exist at least one bijective function from $A$ to $B$. What you have shown is that a certain $f$ between $\mathbb{R}$ and $\mathbb{R}^+$ is not bijective. But that doesn't prove that each function between $\mathbb{R}$ and $\mathbb{R}^+$ isn't bijective.


1

A simple proof can be given easily. Just note that $\varphi\circ \varphi^{-1}=\text{id}$ implies $\varphi^{-1}$ is injective since $\text{id}$ is injective and again $\varphi^{-1}\circ \varphi=\text{id}$ implies that $\varphi^{-1}$ is surjective since $\text{id}$ is surjective . Hence $\varphi^{-1}$ is bijective. I have used the following two theorems, ...


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 ...


1

I think there might be some issues in your notation (you mixed up some variables). We're talking about $\varphi^{-1}:H \rightarrow G$. For injectivity of $\varphi^{-1}$, we want to show that for all $h_1, h_2 \in H$, we have $\varphi^{-1}(h_1)=\varphi^{-1}(h_2) \Rightarrow h_1 = h_2$. So $$\color{blue}{\varphi^{-1}(h_1)=\varphi^{-1}(h_2)} \Rightarrow ...


0

I think just applying the map $\phi$ to both sides of the equation $\phi^{-1}(g_1) = \phi^{-1}(g_2)$ to get $g_1 = g_2$ is fine. You have probably defined $\phi^{-1}(g_1)$ as "the element that $\phi$ maps to $g_1$" so $\phi(\phi^{-1}(g_1)) = g_1$ is just true by definition.


3

Formal Defintion: Given sets $A$ and $B$, the Cartesian product of $A$ and $B$, denoted $A × B$ and read “$A\: \mbox{cross} \: B$,” is the set of all ordered pairs $(a, b)$, where $a$ is in $A$ and $b$ is in $B$. Symbolically: $A × B = \left\{(a, b) \: | \:a \: \in \: A \: \mbox{and} \: b \in B\right\}$ Thus we have: $\mathbb{R} × \mathbb{R}$ is the set ...


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 ...


2

It's important to note that $V$ is a finite set (or the induction would not work). So suppose $f$ satisfies the submodular condition (as the first condition is named in the linked proof). Note that $A = (A \cap B) \cup (A \setminus B)$. If $A \subseteq B$ (i.e. $A \setminus B = \emptyset$, then $A \cap B = A, A \cup B = B$ and the inequality is an ...


0

Let $S=\{s_1,s_2,\ldots, s_n\}$ be the set of students and $C$ be the set of available classes. Denote by $c(s)$ the class student $s$ takes. Given a particular student $s'$ the set $X$ of all students that take the same class as $s'$ is denoted by $$X:=\bigl\{s\in S\>\bigm|\> c(s)=c(s')\bigr\}\ .$$ Here the chosen student $s'$ is a member of $X$. If ...


0

Take $A_1=\{a_{11},a_{12},...\},A_2=\{a_{21},a_{22},...\},...,A_n=\{a_{n1},a_{n2},...\}$ be your countable sets. Every countable set can be enumerated. Now the union $\cup_{j=1}^{\infty} A_{i}$ is a matrix which is infinite horizontically and vertically. Now take $B_{1}=\{a_{11}\},B_2=\{a_{21},a_{12}\},B_3=\{a_{31},a_{22},a_{13}\},...$ and so on ...


1

As counterexample let $A=X$ and $B=Y$. We always have $f^{-1}(Y)=X$ but $Y\subset f(X)$ is only true if $f$ is surjective which does not have to be the case.


1

Hint: supposing that the $S_n$ are disjoint, use the bijection $\Bbb{N\times N}\longrightarrow\Bbb N$ ($\Bbb N$ starting form 0) $$(n,m)\longmapsto\frac{(n+m)(n+m+1)}2 + n.$$


2

First of all, let me assure you there is no general "explicit" bijection. The reason is that the axiom of choice is needed to choose enumerations for each countable set (separately). In its absence, it is consistent that a countable union of countable sets can be uncountable (in fact, it could be equal to the real numbers!). But suppose that we are given ...


0

No it is not true that $x \sim x^2$ for all $x$. For example let $x=p$. Then $p^2 | x^2$ but $p^2 \not | x $. Regarding the actual proof, here is a little hint: Is it possible that $p | x $ and $x \sim x^2$?


2

$x \sim x^2$ is not true for all $x$ - for example, $p \not \sim p^2$ (consider $n = 2$ in the condition). In fact, if $p | x$ then, if $k$ is the largest $k \in \mathbb{N}$ such that $p^k | x$, we have that $p^{2k} | x^2$ and $p^{2k} \not | x$, hence $x \not \sim x^2$. If, however, $p \not | x$ then also $p \not | x^2$, and hence $x \sim x^2$. So $x \sim ...


0

Your are looking at $\mathbf{R} / \pi \mathbf{Q}$. A class has the same cardinal as $\mathbf{Q}$ (all classes are in bijection with $\pi\mathbf{Q}$, thus with $\mathbf{Q}$, and the set of classe has the same cardinal as $\mathbf{R}$.


2

The given relation is not total, but you could use the following modification: $$n \prec m \Leftrightarrow D(n) < D(m) \text{ or } (D(n) = D(m) \text{ and } n \leq m)$$ I think this should work out ok.


1

By the definition of set builder notation, $$y \in \{ x \in A \mid x \notin A \} $$ if and only if $$ y \in A \wedge y \notin A $$ Since the latter is a contradiction, we've proven that, for all $y$, $$ y \notin \{ x \in A \mid x \notin A \} $$ However, we already know a set that tabulates that membership relation: i.e. we have $$y \notin ...


0

You can also see easily without an explicit construction that the intersection of all equivalence relations containing $R$ is an equivalence relation.


2

No, I’m afraid that this argument doesn’t work. It’s true that $\#(E_n)=2^n$ for each $n$, and it’s true that $E\subseteq C$. However, $E$ is the union of countably many finite sets, so $E$ is only countable: all you’ve shown is that $C$ is infinite. And no, $E$ is not all of $C$. As a matter of fact, $E$ consists of those numbers in $[0,1]$ having ...


1

No, the number of disjoint intervals, hence also their endpoints, is countable.


14

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 ...


4

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.


18

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.


10

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


0

This isn't a formal or complete proof: I'll leave it to you to fill in the details. There are three cases: $|x| \ge 1$ $0 < |x| < 1$, and $x = 0$. If $|x| > 1$, then $x^2 \le x^{2n}$ for any $n = 1, 2, \ldots$, so any point in $A_n$ which is outside of the strip $|x| \le 1$ is also contained in $A_1$. If $0 < |x| < 1$, then $\lim\limits_{n ...


1

Divide the real plane into $N = \{(x, y): -1 < x < 1\}$ and $F = \mathbb{R}^2 - N$, where N stands for "near y axis" and F stands for "far from y axis". Show that $\bigcup A_n = \bigcup (A_n \cap N) \cup \bigcup (A_n \cap F)$. Show that $A_n \cap F \supset A_{n+1} \cap F$ and thus $\bigcup (A_n \cap F) = A_1 \cap F$ Show that $A_n \cap N \subset ...


0

As I commented, this is false for infinite sets. To understand why, I think it is simplest to forget about elements of $T$ that are not in the range of $R$ and then to forget about the distinction between different elements of $S$ that have the same image under $R$ in $T$. When you have done that, you can also forget about induction. In more detail: The ...


1

If you translate the definition into words, you'll see that it says that $X$ is such that no proper subset of $X$ has the same cardinality as $X$. In other words, this means that if $f\colon X\to X$ is injective, then it is surjective. This is Dedekind's definition for finiteness. Of course finite sets have this property, but without the axiom of choice (or ...


1

Let $g : A \to B$ and $f : B \to C$ where $X, Y \subseteq A$. Define $h : A \to C$ by $g = f \circ g$. Let $b \in h(X \cap Y)$, then there exists $a \in X \cap Y$ such that $h(a) = b$. Since $a \in X$, then $b = h(a) \in h(X)$. Since $a \in Y$, then $b = h(a) \in h(Y)$. Hence $b \in h(X) \cap h(Y)$. We've shown that an arbitrary element in $h(X \cap ...


0

First of all, this is not Cantor's theorem. Cantor's theorem says that if $X$ is a set, then $|X|<|\mathcal P(X)|$. Now you can use this to show that if $|\mathcal P(X)|\leq\aleph_0$, then $|\mathcal P(X)|<\aleph_0$. Therefore, if $X$ was infinite, it has to be the case that $\mathcal P(X)$ is uncountable.


0

Alternative, from David Mitra's comment: f is a bijection from rationals to naturals. For each irrational number $a$ choose one of rational sequences converging to it, $\{x_n\}$ and define the set $A_a=\{f(x_n):n\in N\}$. Then $$S=\{A_a:a\in R\setminus Q\}$$ As pointed out earlier, any two sequences and therefore any two sets $A_a$ and $A_b$ will only ...


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 ...


2

For every real $\alpha\in [0,1)$ with $\alpha=0.a_1a_2a_3\ldots$ the digits of $\alpha$, let $A_{\alpha}=\{1,1a_1, 1a_1a_2, 1a_1a_2a_3, \ldots\}\in P(\mathbb{N})$. For $\beta\neq \alpha$, the sets $A_{\alpha}$ and $A_{\beta}$ will not agree after some finite number of elements in the sequence because $\alpha$ and $\beta$ stop agreeing after some finite ...


2

This answer is specifically about the Pigeonhole Principle, unlike some other answers which have been about infinity. A correct use of the Pigeonhole Principle requires the following: I define what my pigeonholes and pigeons are. The cardinality of the pigeons must be strictly larger than the cardinality of the pigeonholes. My nemesis assigns pigeons to ...


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 ...


1

The fault in the logic in your argument is that the Pigeonhole Principle only applies to finite numbers. From Wikipedia, the statement of the Pigeonhole Principle is: "if $n$ items are put into $m$ containers, with $n>m$, then at least one container must contain more than one item" Your argument attempts to use the Pigeonhole Principle on an ...


0

$ a, b, c \in \mathbb{Q} $ simply says that $ a, b, c $ are rational. $ \{ a, b, c \} \subset \mathbb{Q} $ says more or less the same thing but also creates a particular subset of $ \mathbb{Q} $. $ (a, b, c) \in \mathbb{Q}^3 $ may refer to an ordered pair in the space $ \mathbb{Q}^3 $. So in summary, perhaps $ a, b, c \in \mathbb{Q} $ is the simplest ...


2

I'm not sure that your formula is correct. Judging by your comment, I will assume that you want pairs in the following order: $$\def\p#1#2{(#1,#2)} \p00,\ \p01,\ \p10,\ \p02,\ \p11,\ \p20,\ \p03,\ \p12,\ldots\ .$$ Write these in tabular form $$\eqalign{ &\p00\cr &\p01\quad\p10\cr &\p02\quad\p11\quad\p20\cr ...


0

Of course not. This would be a useless notion (so there is no need for such terminology). Most functions are not surjective or injective (in the sense that if you take a "random" one, then you cannot expect it to be surjective or injective), mind you. We are mostly interested in the special class of mappings called injections and surjections, and for this ...


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.


1

The definition of a function $f$ from $A$ to $B$, regardless to injectivity or surjectivity, is that the domain of $f$ is $A$, in its entirety. This means that if $f\colon A\to B$, then for every $a\in A$, there is a unique $b\in B$ such that the pair $(a,b)\in f$. So the converse holds just for it to be a function from $A$ to $B$.


0

No (to your title question), a function $f : A \to B$, by definition, gives each $x \in A$ a value $f(x) \in B$. To be precise, you should have said that "for every element in the codomain, there is (at least) one element which is mapped to it by $f$" for your definition of surjectivity.


0

A typical beginning use of the distinction between infinities is the following theorem: Let $f(x)$ be an increasing function on the real line. There can be at most countably many discontinuities of $f(x)$. Indeed, we can find a function which is increasing and with discontinuities at every rational number, but we can't find an increasing function that ...


0

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \unicode{x201c}\text{#2}\unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} \newcommand{\empty}{\varnothing} \newcommand{\diff}{\mathbin \triangle} ...


0

Is the following set legal: $x = \{1,2, \emptyset \} $ ? Yes. If so, is $P(x) = \{ \emptyset, \{1\}, \{2\}, \{1,2\}, \{\emptyset\}, \{1, \emptyset\}, \{2,\emptyset\}, \{1,2,\emptyset\} \} $ ? Yes.


0

I just wanted to get the selfie badge. The solution I found at the end is the following: We want an injection from $\mathbb R^2 $ to $\mathbb R$ we take a surjection from $\mathbb R$ to $\mathbb R^2$ and what we want is the right inverse. As an example of a surjection I took the following: let the number in $\mathbb R$ be $(-1)^n(k+.d_1d_2d_3\dots)$ if $k$ ...



Top 50 recent answers are included