"Suppose the field $F$ is finite. If $f\colon F\to F$ is any bijection, then we can conclude that $\sum_{x\in F}x=\sum_{x\in F}f(x)$. Let $\alpha\in F$ such that $\alpha\ne 0$. Then $x\mapsto \alpha x$ is a bijection. We conclude that $\sum_{x\in F} x=\sum_{x\in F}\alpha x$, i.e. $(1-\alpha)\sum x=0$. If $F$ has more than two elements, we can pick $\alpha\in F\setminus\{0,1\}$ and are done."  1) How can you just assume F to F is a bijection, and  2) What is going on when there is an $\alpha$ picked from F, as seen in the last line, and can you go into more detail about how that proves our point?  Please explain it to someone who's not too comfortable with fields yet.
121277
This statement seems so simple yet I don't quite know how to start with this proof in a substantial way.  Can anybody help me here?
6982
Function is bijective when it is injective and surjective. Function is injective if $$(\forall x_1,x_2 \in A)f(x_1)=f(x_2)\Rightarrow x_1=x_2$$ and surjective if $$(\forall y \in B)(\exists x \in A)y=f(x)$$ Is it possible to transform a function, so that it is given in explicit form? I don't know how to manipulate with function in this form ($f(x,y)=(2x-y,x-4y)$).  Thanks for replies.
12934
Given any set $X$, let $P(X)$ be the set of all subsets of $X$, and let $\{0,1\}^X$ be the set of all functions $X \rightarrow \{0,1\}$. Construct a bijection (and its inverse) between P(X) and $\{0,1\}^X$.    Let us define $f: P(X) \rightarrow \{0,1\}^X$ by $f(\alpha) = g_{\alpha}$ where $\alpha \in P(X)$ and $g_{\alpha} : X \rightarrow \{0,1\}$ is defined by  $$g_{\alpha}(x) =\begin{cases}        1 &amp; x \in \alpha \\       0 &amp; x \in X-\alpha     \end{cases}$$  We need to check if this function is well-defined. Let $\alpha, \beta \in P(X)$. If $\alpha=\beta$, then $\alpha$ and $\beta$ correspond to the same set, and so correspond to the same function since both $g_{\alpha}$ and $g_{\beta}$ send that set to 1 and the ($X-$that set) to 0.   If we have a function $g_{\alpha} \in \{0,1\}$, then $\alpha$ is a set in $X$ that is sent to 1. But since $P(X)$ is the set of all sets of $X$, we must have $\alpha \in P(X)$. So the function is surjective.  Finally, if $g_{\alpha}=g_{\beta}$ then both $g_{\alpha}$ and $g_{\beta}$ send the set $\alpha$ or $\beta$ to 1. So $\alpha$ and $\beta$ must be same set. In other words, the function is injective; and hence bijective.   The inverse function is $f^{-1}: \{0,1\}^X \rightarrow P(X)$ where $f^{-1}(g_{\alpha}) = \alpha$.     Another way to prove this is to first construct the inverse function, show that it is well defined, and then show that $ff^{-1}$ and $f^{-1}f$ are the identity functions, right?  So if we let $g_{\alpha}=g_{\beta}$, then $\alpha=\beta$, because otherwise $g_{\alpha} (\beta)=0$ and $g_{\beta} (\beta)=1$; a contradiction.   Now we have $f \circ f^{-1} (g_{\alpha}) = f(\alpha) = g_{\alpha}$ and $f^{-1} \circ f(\alpha) = f^{-1}(g_{\alpha}) = \alpha$ , and so $f$ and $f^{-1}$ must be bijective.
95019
I would like to construct an explicit bijection from $\alpha^*$ to $\alpha$, where $\alpha$ is an infinite ordinal. I have been told a possible bijection would be:  \begin{equation} f(\beta) = \begin{cases} 0 &amp; \text{if } \beta = \alpha \\ \beta^* &amp; \text{if } \beta \text{ is finite} \\ \beta &amp; \text{otherwise} \end{cases} \end{equation}  I don't understand how this is constructed, or why it is a bijection.
73071
Here the problem 1.4.26 from Sohrab, Basic Real Analysis  Duplicate  This are not duplicate of this question:    the answer gives no proof  despite the title is not really connected  only finite set   Problem  Show that, if $A$ is an infinite set, then $|A\times\mathbb{N}|=|A|$. Hint: Let $\mathcal{F}$ denote the set of all bijective maps $f:S\times\mathbb{N}\to S$, where $S\subset A$. Since $|\mathbb{N}\times\mathbb{N}|=|\mathbb{N}|$, we have $\mathcal{F}\neq \varnothing$ (Why?) Show that Zorn's Lemma can be applied in $\mathcal{F}$ to produce a maximal bijection $h:B\times\mathbb{N}\to B$, with $B\subset A$, and that we must have $B=A$, by examining the cases where $S\setminus B$ is finite or infinite.  Proof  Let $\mathcal{F}$ denote the set of all bijective maps $f:S\times\mathbb{N}\to S$, where $S\subset A$. Since $|\mathbb{N}\times\mathbb{N}|=|\mathbb{N}|$ (see exercise 1.4.10(i)), we have $\mathcal{F}\neq \varnothing$ (From Exercise 1.4.22(d) we know that for a infinite set $A$, we have $|A|\geq\aleph_0$, and $|\mathbb{N}|=\aleph_0$, thus there is an injection from $g:\mathbb{N}\to A$, and, by defining $S:=g(\mathbb{N})\subset A$, we get a bijective map (composition of two bijective maps) $S\times\mathbb{N}\to\mathbb{N}\times\mathbb{N}\to\mathbb{N}\in\mathcal{F}$).  If we consider the inclusion as partial order, then every chain $S_i\subset A$, $i\in I$, has $A$ as upper bound and applying Zorn's Lemma, we get the existence of a maximal $\bar{S}$ and hence a bijection $h:\bar{S}\times\mathbb{N}\to\bar{S}$, with $\bar{S}\subset A$.  Now we prove that $\bar{S}=A$. $R:=A\setminus \bar{S}$. $\bar{S}$ is infinite, since the example of element of $\mathcal{F}$, that we gave above is bijective to $\mathbb{N}$. We have to do this. The second is trying to follow the hint and is incomplete:   Consider that $A\neq\bar{S}$, then there is $r\in R:=A\setminus\bar{S}$. We chose an element $s\in\bar{S}$ and define the bijection $h':\bar{S}\cup\{r\}\times\mathbb{N}\to \bar{S}\cup\{r\}$ as follow  $h'(a,n)=\begin{cases}h(s,2n-1)&amp;\text{for }a=s\\ r&amp;\text{for }a=r,n=1\\ h(s,2n-2)&amp;\text{for }a=r,n\neq 1\\ h(a,n)&amp;\text{otherwise}\end{cases} $  Since $\bar{S}\subsetneq \bar{S}\cup\{r\}$ we get a contradiction to the maximality of $\bar{S}$. Now either $R$ is finite or infinite. 1) $R$ finite, let say $R=\{r_1,\cdots,r_n\}$. Then chose $n$ elements $s_1,\cdots,s_n\in\bar{S}$ and we define the bijection $h':A\times\mathbb{N}\to A$ as follow $h'(a,n)=\begin{cases}h(a,2n-1)&amp;\text{for }a\in\{s_1,\cdots,s_n\}\\ a&amp;\text{for }n=1,a\in\{r_1,\cdots,r_n\}\\ h(s_i,2n-2)&amp;\text{for }a=r_i\\ h(a,n)&amp;\text{otherwise}\end{cases}$  In case $n&gt;0$ we get a contradiction with $\bar{S}$ being the maximal element.   Thus we have only to exclude the case 2) $R$ infinite. HOW TO DO THAT?   Question  Above I tried two proofs. The first part is the same. The two second parts are given by the two bullets.  The second proof tries to follow the hint.  My questions are:   - Is my proof correct?   - In which direction should go the proof from the hint?
59530
I'm an intro analysis student trying to prove that any field $f$ that contains the integers contains the rationals as a subfield. I'm asked to proceed by proving  that there exists a subset $F'$ of $F$ and a function $Φ: F'→\mathbb{Q}$ such that $\mathbb{Z} ⊂ \mathbb{Q}$ and $Φ$  satisfies the three following properties:    $Φ $ is bijective  $Φ(a + b) = Φ(a) + Φ(b)$, for $a$, $b$ ∈ $F$ $Φ(a.b) = Φ(a).Φ(b)$, for $a$, $b ∈ F$   I have gone through a few answers for similar questions but I am not sure how to proceed. We have not covered isomorphisms in the course yet so I am unsure how this is related to it (though other posts like  and  indicate that there's a connection). Any help would be greatly appreciated.
69594
Is this statement true? i.e. If $f(n)$ is injective and $p_n \rightarrow L$, does $p_{f(n)} \rightarrow L$?? (I realize that it's technically only a rearrangement if $f(n)$ is bijective.)   My attempt at a proof:  Since $p_n \rightarrow L$, we have that, for all $n$ except $n \le N$, $d(p_n, L) &lt; \epsilon$.  Let $S = \{n \ | \ f(n)\le N\}$, let $n_0$ be the largest $n \in S$, we know there is such a largest $n$ because $f(n)$ is injective. Now we have that $\forall \ n &gt; n_0 \ f(n) &gt; N$ which implies that $p_{f(n)} \rightarrow L$, as required.  Is this correct? Does my proof work?
24974
Let $F$ be a field, let $p , q$ be two coprime natural numbers and we consider the two polynomials $$ f(X) = \sum_{i = 0}^{p - 1} X^{k i} \qquad \mbox{ and } \qquad g(X) = \sum_{j = 0}^{q - 1} X^{k j} $$ in $F[X]$, where $k \in \mathbb{N}$. If $x$ is an arbitrary element in $F$, how can I show that $\gcd(f(x) , g(x)) = 1$?
65235
I am stuck on this problem:  Define $f: N\times N \rightarrow N$ by   $f(i,j)=\frac{(i+j-1)(i+j-2)}{2}+i$.   How do you prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically equivalent?  Work: First I tried to prove that $f$ is injective by setting $f(i,j)=f(x,y)$. However, from here I am stuck and I cannot reduce it properly. My work really does not get anywhere significant and its really messy.
15942
Let $K$ be a field and $f(x)\in K[x]$. Prove that $K[x]/(f(x))$ is a field if and only if $f(x)$ is irreducible in $K[x]$.   How to prove? I really have no idea... Thank you a lot.
73406
I'm studying logic and unfortunately, I'm a newbie at this, so I don't see the stuff everyone sees at the moment. I want to solve following exercise, but get nowhere:      Let $A$ be an infinite set and let $B$ be a finite set. Use the AC to   prove that $|A| +|B| = |A|$.   I've proved this one though:      If $X$ is an infinite set, there is an injective function $\mathbb{N}  \rightarrow X$, hence $\omega \leq |X|$.   But I don't see how I could use this. What's the logic here?
60056
I'm trying to prove that, for a finite set $A$, if the map $f: A\rightarrow A$ is a surjection, then it's an injection.  I've looked at this post:  but the arguments there seem very round-about, proving that injectivity implies surjectivity first.  I think I've seen other proofs, too, but they all sound kind of flimsy.  They tend to go something like "If the function is surjective then no two arguments can go to the same image, since that would require some element of the range not being the image of any element."  While that's true and I see what the argument has in mind, it's no more convincing than the statement of the claim that we're trying to prove!  Without a more rigorous proof, both seem to rely on the intuition that everything has to go to one and only one thing, but we're supposed to be proving that.  But I've been trying to develop a more thorough and direct proof, and haven't been able to.  I've tried induction:     The theorem holds trivially if $|A|=0$.  Suppose the theorem holds up to $n=|X|$, and let $|A|=n+1$ and $f:A\rightarrow A$ be a surjection.  Then let $x\in A$ and $f^{-1}(x)$ be the set of all elements $y\in A$ such that $f(y)=x$...   But at this stage I want to restrict my function, but that has the disadvantage that if $f(y)$ has more than one element in it, when I pluck it out of $A$ as the domain and pluck $x$ out of $A$ as the range, then I may not be dealing with a function mapping from a set to itself and so I don't get to use the inductive hypothesis.  Any other proofs you know about?
118287
I'm a little stuck with this proof. Not sure where to go. I was thinking that I could first assume that $f$ is one to one and prove that it's onto, and then assume it's onto and prove that it's one to one... but I'm not sure what to do with the knowledge that $|A|=|B|=m\in\mathbb{Z}\geq 0$.  I've tried to start by defining what it means for $f$ to be one-to-one, and going from there...  \begin{align*} f\text{ is one-to-one}&amp;\Longrightarrow f=\{(a,b)\in A\times B\mid b=f(a)\wedge f^{-1}(b)=a\}\\ &amp;\Longrightarrow \dots\\ &amp;\Longrightarrow \text{$f$ is onto} \end{align*}  but not sure where to go from there... I have a feeling that my definition is too presumptuous to begin with, since I'm trying to show that $f$ is onto... not assume that it is.
123202
This is problem 31b) from Dummit and Foote chapter 14.2. I am looking for a hint on how to attack the problem, since I have been thinking about it for a couple of hours but I don't even know where to start. The problem says:  Let $K$ be a finite extension of $F$ of degree $n$. Let $\alpha$ be an element of $K$. Prove that the minimal polynomial for $\alpha$ over $F$ is the same as the minimal polynomial for the linear transformation $T_{\alpha}$. In this problem, $T_{\alpha}$ is an $F$-linear transformation of $K$ that arises from $\alpha$ acting by left multiplication on $K$.  I appreciate any helpful suggestions on how to start attacking the problem or any possible hint. Thanks!
73143
Assuming the axiom of choice, show that there exists a sequence of function $\langle f_\alpha\mid\alpha&lt;\omega_1\rangle$ such that: (1) each $f_\alpha:\alpha\rightarrow\omega$ is injective and (2) for all $\alpha&lt;\beta$, the set $\{\gamma&lt;\alpha\mid f_\alpha(\gamma)\not=f_\beta(\gamma)\}$ is finite.   My knee-jerk reaction in trying to solve this problem is to define the sequence by recursion. But I don't see how to actually carry out the construction (in particular, I don't see how I could ensure that (2) remains to be the case once I pass $\omega$). Any help is appreciated.
91654
Let $K$ be a field and $f \in K[x]$ a polynomial of degree $n&gt;0$. Assume that $E$ is an extension of $K$ such that $f$ can be expressed as a product of linear factors over $E$:  $$f(x)=\gamma (x-\alpha_1)(x-\alpha_2)\dots(x-\alpha_n).$$  I want to show that $\lvert K(\alpha_1,\dots,\alpha_2) : K \rvert$ is a divisor of $n!$. I also want to show that if $\lvert K(\alpha_1,\dots,\alpha_n): K \geq (n-1)!$ then $f$ is irreducible over $K$ or $f$ already has a root in $K$.  The problem has a hint. It says: "Use induction on $n=\deg f$. If $f=gh$ in $K[x]$ with $\deg g =r$ and $\deg h=n-r$, then $r!(n-r)!$ is a divisor of $n!$.  Any idea for solving this problem would be appreciated.
33608
Let $f$ and $g$ be functions such that $f\colon A\to B$ and $g\colon B\to C$. Prove or disprove the following a) If $g\circ f$ is injective, then $g$ is injective  Here's my proof that this is true. Let $A = \{4,5\}$, $B = \{3,9\}$, $C = \{1,2\}$ $f(4) = 3$; $f(5) = 9$ $g\circ f(4) = 1$ and $g\circ f(5) = 2$ Since no 2 elements map to the same element in the range $g\circ f$ and $g$ are both injective.  b) If $f$ and $g$ are surjective, then $g\circ f$ is surjective.  Here's my proof that this is true. Let $A = \{1,2\}$, $B = \{4\}$, $C = \{5\}$, $f(1) = 4$; $f(2) = 4$ $g\circ f(1) = 5$ and $g\circ f(2) = 5$. Since no elements are left unmapped then $g\circ f$ and $f$ and $g$ are surjective Are these proofs valid? **Edit: Ok so I revised my proof for a. I will disprove it using a counterexample. Let A = {4}, B = {3,9}, C={1}. g∘f(4) = 1 and g(3) = 1 and g(9) = 1 g∘f is injective but g is not injective because 3 and 9 both map to 1. Is that a valid disproof? Now I'm just having some trouble disproving or proving b. If anyone could lend some tips. Also this is not homework. Just reviewing for an exam.