User - MathOverflow

To prove the Nullstellensatz, how can the general case of an arbitrary algebraically closed field be reduced to the easily-proved case of an uncountable algebraically closed field?

2010-02-17T19:15:30Z

In his answer to a question about simple proofs of the Nullstellensatz (http://mathoverflow.net/questions/15226/elementary-interesting-proofs-of-the-nullstellensatz), Qiaochu Yuan referred to a really simple proof for the case of an uncountable algebraically closed field.

Googling, I found this construction also in Exercise 10 of a 2008 homework assignment from a course of J. Bernstein (see the last page of http://www.math.tau.ac.il/~bernstei/courses/2008%20spring/D-Modules_and_applications/pr/pr2.pdf). Interestingly, this exercise ends with the following (asterisked, hard) question:

(*) Reduce the case of arbitrary field $k$ to the case of an uncountable field.

After some tries to prove it myself, I gave up and returned to googling. I found several references to the proof provided by Qiaochu Yuan, but no answer to exercise (*) above.

So, my question is: To prove the Nullstellensatz, how can the general case of an arbitrary algebraically closed field be reduced to the easily-proved case of an uncountable algebraically closed field?

The exercise is from a course of Bernstein called 'D-modules and their applications.' One possibility is that the answer arises somehow when learning D-modules, but unfortunately I know nothing of D-modules. Hence, proofs avoiding D-modules would be particularly helpful.

If F is left adjoint to G, when does FG preserve limits? When do counits interchange with limits?

2010-03-22T10:45:42Z

Motivation

Suppose that $F\colon X\to A$ is left adjoint to $G\colon A\to X$, and let $\varepsilon\colon FG\stackrel{.}{\to}I_A$ be the counit of the adjunction. Suppose also that $A$ is $J$-complete (for some category $J$), so that $\operatorname{Lim}$ is a functor $C^J\to C$, where for an arrow $\alpha\colon T_1\stackrel{.}{\to} T_2$ of $C^J$, $\operatorname{Lim}(\alpha)$ is the unique arrow of $A$ for which the following diagram is commutative:

$$ \begin{matrix} \operatorname{Lim}(T_1)& \stackrel{\text{limiting cone}}{\longrightarrow} & T_1\\ | & & |\\ \operatorname{Lim}(\alpha) & & \alpha\\ \downarrow & & \downarrow \\ \operatorname{Lim}(T_2)& \stackrel{\text{limiting cone}}{\longrightarrow} & T_2 \end{matrix} $$

Let $T\colon J\to A$ be a functor. We have the natural transformation $\varepsilon T\colon FGT\stackrel{.}{\to} T$, and $\operatorname{Lim}(\varepsilon T)$ is the dotted line making the following diagram commutative:

$$ \begin{matrix} \operatorname{Lim}(FGT)& \stackrel{\text{limiting cone}}{\longrightarrow} & FGT\\ | & & |\\ \operatorname{Lim}(\varepsilon T) & & \varepsilon T\\ \downarrow & & \downarrow \\ \operatorname{Lim}(T)& \stackrel{\text{limiting cone}}{\longrightarrow} & T \end{matrix} $$

If $FG$ preserves $J$-limits, and $\tau\colon \operatorname{Lim}(T)\stackrel{.}{\to}T$ is the lower limiting cone, then $FG\tau\colon FG\operatorname{Lim}(T)\stackrel{.}{\to}FGT$ is the upper limiting cone, and the above diagram becomes

$$ \begin{matrix} FG\operatorname{Lim}(T)& \stackrel{FG\tau}{\longrightarrow} & FGT\\ | & & |\\ \operatorname{Lim}(\varepsilon T) & & \varepsilon T\\ \downarrow & & \downarrow \\ \operatorname{Lim}(T)& \stackrel{\tau}{\longrightarrow} & T \end{matrix} $$

Since the naturality of $\varepsilon$ implies that for all $j\in \operatorname{obj}(J)$ the diagram $$ \begin{matrix} FG\operatorname{Lim}(T)& \stackrel{FG\tau_j}{\longrightarrow} & FGT(j)\\ | & & |\\ \varepsilon_{\mathrm{Lim}T}& & \varepsilon_{T(j)}\\ \downarrow & & \downarrow \\ \operatorname{Lim}(T)& \stackrel{\tau_j}{\longrightarrow} & T(j) \end{matrix} $$

is commutative, it follows that $\varepsilon_{\mathrm{Lim}T}$ can replace $\operatorname{Lim}(\varepsilon T)$ in the last but one diagram while keeping it commutative. By uniqueness, we get the nice equation
$$ \varepsilon_{\mathrm{Lim}T} = \operatorname{Lim}(\varepsilon T). $$ Note that it seems that all depends on $FG$ preserving $J$ limits.

Question

If $F\colon X\to A$ is left adjoint to $G\colon A\to X$ and $A$ has $J$-limits, when does $FG$ preserve $J$-limits? This is obviously true when $F$ preserves limits (for example, when there is also a left adjoint to $F$), but are there other interesting situations?

Background

For solving an exercise from Mac Lane, I used some results from A. Gleason, ''Universally locally connected refinements,'' Illinois J. Math, vol. 7 (1963), pp. 521--531. In that paper, Gleason constructs a right adjoint to the inclusion functor $\mathbf{L\ conn}\subset \mathbf{Top}$ ($\mathbf{L\ conn}=$ locally connected spaces with continuous maps), and proves that the counit
of the product of two topological spaces is the product of the counits (Theorem C). This made me curious when do counits and limits interchange.

What is the motivation for maps of adjunctions?

2010-03-01T10:49:37Z

In Mac Lane, there is a definition of an arrow between adjunctions called a map of adjunctions. In detail, if a functor $F:X\to A$ is left adjoint to $G:A\to X$ and similarly $F':X'\to A'$ is left adjoint to $G':A'\to X'$, then a map from the first adjunction to the second is a pair of functors $K:A\to A'$ and $L:X\to X'$ such that $KF=F'L$, $LG=G'K$, and $L\eta=\eta'L$, where $\eta$ and $\eta'$ are the units of the first and second adjunction. (The last condition makes sense because of the first two conditions; also, there are equivalent conditions in terms of the co-units, or in terms of the natural bijections of hom-sets).

As far as I can see, after the definition, maps of adjunctions do not appear anywhere in Mac Lane. Googling, I found this definition also in the unapologetic mathematician, again with the motivation of being an arrow between adjunctions.

But what is the motivation for defining arrows between adjunctions in the first place? I find it hard to believe that the only motivation to define such arrows is, well, to define such arrows...

So my question is: What is the motivation for defining a map of adjunctions? Where are such maps used?

Besides the unapologetic mathematician, the only places on the web where I found the term ''map of adjunctions'' were sporadic papers, from which I was not able to get an answer to my question (perhaps ''map of adjunctions'' is non-standard terminology and I should have searched with a different name?).

I came to think about this when reading Emerton's first answer to a question about completions of metric spaces. In that question, $X$ is metric spaces with isometric embeddings, $A$ is complete metric spaces with isometric embeddings, $X'$ is metric spaces with uniformly continuous maps, $A'$ is complete metric spaces with uniformly continuous maps, and $G$ and $G'$ are the inclusions. Now, if I understand the implications of Emerton's answer correctly, then it
is possible to choose left adjoints $F$ and $F'$ to $G$ and $G'$ such that the (non-full) inclusions $A\to A'$ and $X\to X'$ form a map of adjunctions. This made me think whether the fact that we have a map of adjunctions has any added value. Then I realized that I do not even know what was the motivation for those maps in the first place.

[EDIT: Corrected a typo pointed out by Theo Johnson-Freyd (thanks!)]

If G is monadic and the comparison functor is an equivalence that is not an isomorphism, does G create limits?

2010-05-12T11:23:46Z

Background

Recall that a functor $G\colon A\to X$ is called monadic if it has a left adjoint $F$ for which the Eilenberg--Moore comparison functor $K\colon A\to X^{\mathbb{T}}$ is an equivalence of categories, where $\mathbb{T}$ is the monad in $X$ defined by the adjunction $\langle F,G,\ldots\rangle\colon X\rightharpoonup A$, and $X^{\mathbb{T}}$ is the category of $\mathbb{T}$-algebras in $X$.

This means that a monadic functor is the forgetful functor $G^{\mathbb{T}}\colon X^{\mathbb{T}}\to X$ up to composition with an equivalence of categories (the comparison functor $K$). Now, it can be verified that $G^{\mathbb{T}}$ creates
limits (Ex. 6.2.2 of Mac Lane). If the comparison functor is an isomorphism, then it is straightforward to verify that $G$ creates limits. In fact, I think that even if it is only assumed that $K$ is an equivalence for which the object function is surjective, then $G$ creates limits.

However, in Proposition 4.4.1 on p. 178 of Mac Lane--Moerdijk, it is stated that any monadic functor creates limits. The proof starts with the following words (with minor omissions):

Let $G$ be monadic. Then by definition, $G$ is the forgetful functor $G^\mathbb{T}$ up to an equivalence of categories. It thus suffices to show that such a forgetful functor $G^\mathbb{T}$ creates limits.

I simply do not understand this statement: In general, the composition of an equivalence and a functor that creates limits need not create limits. For example, the identity $\mathbf{Set}\to\mathbf{Set}$ creates limits, and for any skeleton $X$ of $\mathbf{Set}$ the inclusion $X\subseteq \mathbf{Set}$ is an equivalence. Let $X$ be some skeleton of $\mathbf{Set}$ (for which I am happy to assume any necessary axiom of choice), and take a one-element set $1$ that is not in $X$. Then $1$ is a limit of the functor obtained by composing the unique functor from the empty category to $X$ with $X\subset\mathbf{Set}\stackrel{\operatorname{Id}}{\to}\mathbf{Set}$, but $1$ has no lifting in $X$.

So it seems that there are 4 possibilities:

The above Proposition 4.4.1, as stated, is wrong. There is a counter example where a monadic functor (for which the comparison functor is not an isomorphism) does not create limits.
The proof in ML-M covers just some of the cases, and for the other cases it is not known if the assertion is true (namely, for a monadic functor $G$ for which the comparison functor is not an isomorphism, it is not known whether in general $G$ creates limits).
The proposition is correct because the comparison functor has some additional special property (e.g., its object function must be surjective whenever it is an equivalence).
(Most likely) I am wrong, and the quoted argument from Mac Lane--Moerdijk is correct.

I would like to note that in Theorem 3.4.2 on p. 105 of Barr-Wells, it is only claimed that monadic functors reflect limits.

Question

Which one of the above 4 possibilities is true? In essence, my question is: If $G$ is monadic and the comparison functor is an equivalence that is not an isomorphism, does $G$ create limits?

Answer by unknown (google) for When does a "representable functor" into a category other than Set preserve limits?

2010-05-05T12:51:46Z

[Collecting my sporadic comments into one (hopefully) coherent answer.]

A more general question is as follows: For functors $C\stackrel{F}{\to}D\stackrel{U}{\to}E$ and for an index category $J$ such that $UF$ preserves $J$-limits, when does $F$ preserve $J$ limits?

A useful sufficient condition is that if $U$ creates $J$-limits, then in the above situation $F$ preserves $J$-limits. Proof: Let $T\colon J\to C$ be a functor, and suppose that $\tau\colon \ell\stackrel{\cdot}{\to} T$ is a limiting cone in $C$. Since $UF$ preserves $J$-limits, $UF\tau\colon UF\ell\stackrel{\cdot}{\to} UFT$ is a limiting cone in $E$. As $U$ creates $J$-limits, there is a unique lifting of $UF\tau$ to a cone in $D$, and this cone is a limiting cone. But $F\tau\colon F\ell\stackrel{\cdot}{\to} FT$ is such a lift, and hence we're done.

This condition is quite useful, because many forgetful functors are monadic, and monadic functors create all limits (by combining their definition on pp. 143--144 of Mac Lane and Ex. 6.2.2 on p. 142 of Mac Lane, or by Proposition 4.4.1 on p. 178 of Mac Lane--Moerdijk, or really by a comment of Tom Leinster from which I learned this :)).

For example, consider the category of all small algebraic systems of some type. From the AFT, we know that the forgetful functor to $\mathbf{Set}$ has a left adjoint, and it is the content of Theorem 6.8.1, p. 156 of Mac Lane that this forgetful functor is monadic.

Returning to the original question, this means that whenever the category $D$ is one of $\mathbf{Grp}$, $\mathbf{Rng}$, $\mathbf{Ab}$,... and $U\colon D\to \mathbf{Set}$ is the forgetful functor, then for any $J$, $UF$ preserves $J$-limits implies $F$ preserves $J$ limits. In particular, if $UF$ is a representable functor (and hence preserves all limits), then $F$ preserves all limits.

Next, let me try to comment on your motivating examples (the one from Q. 23188 and the one from the 'Edit' part of the current question.)

Regarding your example in Q. 23188: Unfortunately I know nothing of Hopf algebras, so I can't understand all the details of your construction. If I understand correctly, you construct a functor $F\colon\mathbf{Rng}\to\mathbf{Grp}$ whose composition with the forgetful functor $U\colon \mathbf{Grp}\to \mathbf{Set}$ is representable. If this is indeed the case, then by the above $F$ itself preserves all limits.

[EDIT: corrected the part concerning the last example.]

Finally, regarding your example in the edited question: While I know nothing of dynamical systems, from a quick glance at Terence Tao's blog it seems that the category of dynamical systems is the category whose objects are pairs $\langle X,f\colon X\to X\rangle$ with $X$ a (small) set and whose arrows $\phi\colon\langle X, f\rangle\to\langle Y, g\rangle$ are those functions $\phi\colon X\to Y$ with $g\circ\phi =\phi\circ f$.

To show that the above sufficient condition works in this case, we would like to show that the forgetful functor to $\mathbf{Set}$ crates limits. More generally, we will show that if $C$ is a category and $D$ is the category whose objects are pairs $\langle x,f\colon x\to x\rangle$ (where $x\in\operatorname{obj}(C)$, $f\in\operatorname{arr}(C)$), and whose arrows $\phi\colon \langle x,f\rangle\to \langle y,g\rangle$ are those arrows $\phi\colon x\to y$ with $g\circ\phi =\phi\circ f$, then the forgetful functor $U\colon D\to C$ creates limits.

[I'm sure that this follows from some well-known result, but since I don't see it, I'll just continue with a direct proof.]

So, let $J$ be an index category, let $F\colon J\to D$ be a functor, and suppose that $\tau\colon x\stackrel{.}{\to} UF$ is a limiting cone in $C$. We would like to show that there exists a
unique cone $\sigma\colon L\stackrel{.}{\to} F$ in $D$ such that $U\sigma=\tau$, and that this unique cone is a limiting cone.

For uniqueness, suppose that $\sigma\colon L\stackrel{.}{\to} F$ satisfies $U\sigma = \tau$. Write $F_j:=\langle y_j,f_j\rangle$. Then we must have for all $j$ $$ \sigma_j=(x\stackrel{f}{\to}x)\stackrel{\tau_j}{\to}(y_j\stackrel{f_j}{\to}y_j) $$ for some $f\colon x\to x$ (hence we immediately see that $\sigma$ is determined up to $f$). Now, since by the above we see that $\tau_j$ must be an arrow $$ (x\stackrel{f}{\to}x)\stackrel{\tau_j}{\to}(y_j\stackrel{f_j}{\to}y_j) $$ of $D$, the following diagram must be commutative for all $j$: $$ \begin{matrix} x & \stackrel{\tau_j}{\longrightarrow} & y_j =UF_j\\ f\downarrow & & f_j\downarrow\\ x&\stackrel{\tau_j}{\longrightarrow} & y_j = UF_j. \end{matrix} \quad \text{(Diagram 1)} $$

Now we claim that the $\to\downarrow$ part of the above diagram forms a cone to $UF$, that is, we claim that the family ${f_j\tau_j}$ forms a cone $x\stackrel{.}{\to} UF$. Indeed, for an arrow $g:j\to j'$ of $J$, consider the following diagram: $$ \begin{matrix} &&&&x\\ &&&\stackrel{\tau_j}{\swarrow}&&\stackrel{\tau_{j'}}{\searrow}\\ &&y_j && \stackrel{UFg}{\longrightarrow} && y_{j'}\\ &\stackrel{f_j}{\swarrow} &&&&&&\stackrel{f_{j'}}{\searrow}\\ y_j&&&&\stackrel{UFg}{\longrightarrow}&&&&y_{j'} \end{matrix} $$

The upper triangle is commutative because $\tau$ is a cone to the base $UF$, and the lower trapezoid is commutative because $F$ is a functor, and hence $Fg$ is an arrow $F_j\to F_{j'}$ in $D$. Hence the outer triangle commutes, as required. From the universality of $\tau$, it follows that there is a unique $f$ for which Diagram 1 is commutative, and we have uniqueness.

For existence, we can take $f$ to be the unique arrow $x\to x$ for which Diagram 1 is commutative, and we get a cone $$ \sigma=\{\sigma_j=\tau_j\colon (x\stackrel{f}{\to}x)\to F_j=(y_j\stackrel{f_j}{\to}y_j)\} $$ with $U\sigma=\tau$. We claim that this is a limiting cone.

To see this, let $\alpha\colon(z\stackrel{g}{\to}z)\stackrel{.}{\to}F$ be a cone, so that for all $j$ the following diagram is commutative: $$ \begin{matrix} z & \stackrel{\alpha_j}{\longrightarrow} & y_j\\ g\downarrow & & f_j\downarrow\\ z &\stackrel{\alpha_j}{\longrightarrow} & y_j. \end{matrix} \quad\text{(Diagram 2)} $$

Then $U\alpha$ is a cone $z\stackrel{.}{\to} UF$ in $C$, and by the universality of $\tau$ there exists a unique arrow $h\colon z\to x$ for which the following diagram is commutative for all $j$: $$ \begin{matrix} z & \stackrel{\alpha_j}{\longrightarrow} & y_j\\ h\downarrow& \stackrel{\tau_j}{\nearrow}\\ x& \end{matrix}\quad\text{(Diagram 3)} $$

If this $h$ is an arrow $(z\stackrel{g}{\to}z)\to (x\stackrel{f}{\to}x)$ in $D$, then we're done. In other words, all that remains to do is to show that the outer rectangle of the following diagram is commutative: $$ \begin{matrix} z && \stackrel{h}{\longrightarrow} && x\\ & \stackrel{\alpha_j}{\searrow} && \stackrel{\tau_j}{\swarrow}\\ && y_j\\ g\downarrow&& \downarrow f_j && \downarrow f\\ && y_j\\ & \stackrel{\alpha_j}{\nearrow} && \stackrel{\tau_j}{\nwarrow}\\ z && \stackrel{h}{\longrightarrow} && x\\ \end{matrix} $$ Now, the left trapezoid is just Diagram 2, the upper and lower triangles are just Diagram 3, and the right trapezoid is commutative for all $j$ by the definition of $f$. It follows that both paths of the outer rectangle have the same composition with the limiting cone $\tau$, and hence the outer rectangle is commutative, as required.

Answer by unknown (google) for What are some examples of colorful language in serious mathematics papers?

2010-04-30T21:43:50Z

Not from a paper but rather from a book, the first page of the introduction to G. R. Kempf's Algebraic Varieties reads:

"Algebraic geometry is a mixture of the ideas of two Mediterranean cultures. It is the superposition of the Arab science of the lightning calculation of the solutions of equations over the Greek art of position and shape. This tapestry was originally woven on European soil and is still being refined under the influence of international fashion. Algebraic geometry studies the delicate balance between the geometrically
plausible and the algebraically possible. Whenever one side of this mathematical teeter-totter outweighs the other, one immediately loses interest and runs off in search of a more exciting amusement."

Answer by unknown (google) for Baer's criterion for functors

2010-04-24T12:03:56Z

Regarding the original question (with $A=R$-$\mathbf{Mod}$), I think that by SAFT any continuous functor $A^{\mathrm{op}}\to \mathbf{Set}$ is representable, and hence the assertion in the original question does not generalize Baer's theorem.

In detail (with $A=R$-$\mathbf{Mod}$):

(*) $R$ is a generator in $A$, and hence a cogenerator in $A^{\mathrm{op}}$.

(*) $A$ is co-well-powered, because there is a bijection between the quotient objects of $M\in A$ and the set of submodules of $M$, and the latter set is small (since by assumption $M$ is small). It follows that $A^{\mathrm{op}}$ is well-powered.

(*) $A$ is small cocomplete (as is any $\tau$-algebra, for $\tau=$(operations, identities)), and hence $A^{\mathrm{op}}$ is small complete.

(*) Both $A^{\mathrm{op}}$ and $\mathbf{Set}$ have small hom-sets.

So, all the conditions of SAFT hold for a functor $A^{\mathrm{op}}\to\mathbf{Set}$, and hence any such continuous functor has a left adjoint. Now, if a functor $G\colon A^{\mathrm{op}}\to\mathbf{Set}$ has a left adjoint then it is surely representable: Saying that a functor $G$ is representable is like saying that there is a universal arrow from a one-object set $1$ to $G$ (Prop. 3.2.2, p. 60 in Mac Lane), and for this we can take the unit $\eta_1\colon 1\to G(F1)$ (with $F$ the left adjoint of $G$).

(See also the discussion on Watt's theorem on p. 131 of Mac Lane).

I am not sure about the general case of the edited question (where $A$ is an arbitrary abelian category with a generator + AB3--AB5). Cocompleteness holds by AB3 (as I have seen in Wikipedia ), but I do not know enough to say anything about the question of being co-well-powered.

What is a reference for an explicit, logic-based, statement of duality in category theory (in ''complicated'' situations)? And what are the prerequisites for a beginner in logic?

2010-04-04T21:59:44Z

Background

In the course of reading Mac Lane linearly (currently in Chapter VI), I have seen again and again that duality can make life much easier. My problem is that I have almost no background in logic, and duality is a theorem in logic about category theory.

When I first read about duality in Chapter II of Mac Lane in the context of the elementary theory of a single category, everything was pretty clear even without knowing any logic. However, when I got to the chapter on adjunctions, involving two categories and functors between them, a bijection of hom-sets, and two natural transformations, I got confused to the point that I wasn't even sure how to use duality (let alone, why it is correct).

At this stage, I made a rather long pause and read the first three chapters of Ebbinghaus, Flum, and Thomas' ''Mathematical logic'' (so, I have read about the syntax and semantics of first-order logic). From this, I built my own (hopefully correct) ''poor man's proof of duality'' up to the situation of a single adjunction. This has both clarified the validity of duality for formulas involving adjunctions, and helped me understand how to use duality in such situations.

But a single adjunction is far from the most ''complicated'' situation one meets. There are composition of adjunctions, pointwise limits in functor categories, and many other situations in which I am still not totally convinced that I understand duality (both theoretically and practically).

For example, in one answer to a recent question on pointwise limits in functor categories, it was stated that the reference for limits is Mac Lane, while the reference for colimits is Mac Lane--Moerdijk. I really wanted to comment that the assertion on colimits is just the dual of the one on limits, but then I realized that I am not totally sure. I would be most grateful for some solid source that I can consult whenever I have doubts in what I get after doing the intuitive things (reverse arrows but not functors, etc.).

Questions

What is a good reference for an explicit, logic-based, statement of a duality theorem of category theory in ''complicated situations?''
What are the prerequisites in logic? For example, up to which point of Ebbinghaus--Flum--Thomas should I read?

Answer by unknown (google) for Calculating fourier transform at any frequency

2010-01-12T20:16:22Z

If what you need is a simple practical method to do the interpolation, then just multiply the "time domain" samples by the linear-phase signal $\{\exp\left(\alpha\cdot i 2\pi k /N\right)\}_{k=0}^{N-1}$, where $\alpha\in(0,1)$ is the sub-sample shift in the "frequency domain." (I'm not sure if an additional constant of absolute value 1 is required here). As already noted in previous answers, the motivation for this is the assumption that your samples vector $\{x_k\}$ comes from sampling some continuous-time signal $\{X(t)\}_{t\in \mathbb{R}}$, as in $x_k=X(kT_s)$ for $k=0,\ldots, N-1$, where $T_s\in \mathbb{R}_{++}$ is the sampling period. If the continuous-time signal has a compactly
supported Fourier transform, than by Shannon's sampling theorem $X$ is determined by the infinite sequence $\{X(kT_s)\}_{k\in \mathbb{Z}}$ for small enough $T_s$. Since we only have $N$ entries of the infinite sequence, we loose some information on $X$. But if $X$ decays rapidly (rather than having a compact support), then at least intuitively we don't loose much (I know that this is a dangerous and imprecise statement :) ).

For example, try the following Matlab lines:

ttt=-32:31;

x_time=exp(-ttt.^2/10);

figure;plot(x_time);

x_freq = fft(x_time);

figure;plot(fftshift(abs(x_freq)));

figure

for alpha=-4:0.5:4

x_time_2 = x_time .* exp(2 * pi * i * (0:63)/64 * alpha);

x_freq=fft(x_time_2);

plot(fftshift(abs(x_freq)));

axis([26,37,0,10]);

grid on;

pause(1);

end

Answer by unknown (google) for Can epi/mono for natural transformations be checked pointwise?

2010-03-12T09:30:40Z

This is only a partial answer. Regarding your first question (mono/epi iff pointwise mono/epi): At least for the case where the target category $\mathcal{D}$ is $\mathbf{Set}$, it is true that pointwise mono/epi implies mono/epi, see p. 91 of the 1998 edition of Mac Lane.

As for the second question, the answer is that pointwise limits implies limits in functor categories, by the ``limit with parameters'' theorem (Theorem V.3.1 of Mac Lane).

What are the 'standard' applications of the duals of the adjoint functor theorems?

2010-03-07T19:40:32Z

There are some 'standard' applications of the adjoint functor theorem (AFT) and the special adjoint functor theorem (SAFT), for example, the existence of a free $\tau$-algebra (where $\tau=$(operations,identities)) on a small set by the AFT,
Stone-Cech compactification by the SAFT, and, if I am not mistaken, the proof that the category of $\tau$-algebras is cocomplete (by using the AFT to establish a left adjoint to the appropriate diagonal functor).

However, I was not able to find any applications of the duals of the AFT and the SAFT, neither in MacLane, nor in the Joy of Cats.

The Joy of Cats contains the following intriguing remark on p. 311:

Since many familiar categories have separators but fail to have coseparators, the dual of the Special Adjoint Functor Theorem is applicable even more often than the theorem itself.

But what are the mentioned application of the dual of the SAFT?

So my questions is: What are the 'standard' applications of the duals of the AFT and the SAFT?

Googling for combinations of phrases like ''adjoint functor theorem'' and ''dual'' is not very useful, so I have tried ''dual of the adjoint functor theorem'' and ''dual of the special adjoint functor theorem.'' This resulted in a total of 7 papers/books, from which I was not able to get a clear answer to the current question. I have also tried in The Wikipedia article on adjoint functors, in nLab's article on the adjoint functor theorems, and in some MO questions, but without success.

Answer by unknown (google) for Different ways of proving that two sets are equal

2010-02-26T23:26:12Z

To show that two sets are equal, show that both satisfy a condition $P$ for which it is known that there exists a unique set $X$ with $P(X)$. What I really have in mind here is to use the uniqueness part of universality. For example, if two arrows to a limit (in some category) have the same compositions with the limiting cones, then they are the same. We can think of these arrows as sets (e.g., in ZFC without urelements), and so we proved that two sets are the same. (In any case, we can restrict attention to $\mathbf{Set}$ where arrows (function) are sets.)

As another example, if a functor $V:A\to X$ is known to creates $J$-limits, and two cones $\nu$ and $\tau$ in $A$ happen to satisfy $V\nu=V\tau=$ a limiting cone in $X$, then $\nu=\tau$.

Answer by unknown (google) for Various concepts of "closure" or "completion" in mathematics

2010-02-07T19:01:45Z

In general, if $A\subset B$ is a full reflective subcategory, then each object $a\in A$ is isomorphic to its image under the reflector. This seems to include many cases: $\mathbf{Ab}\subset \mathbf{Grp}$, $\mathbf{CompMet}\subset\mathbf{Met}$, $\mathbf{Top}_{n+1}\subseteq \mathbf{Top}_{n}$ (as in http://mathoverflow.net/questions/9504/why-is-top4-a-reflective-subcategory-of-top3), etc.

EDIT: Following Pete L. Clark's comment, here is a clarification: The subcategory $A$ above is called reflective if the inclusion functor $A\subset B$ has a left adjoint, and full if this inclusion functor is full. In case $A$ is a reflective subcategory, the left adjoint to the inclusion functor is called a reflector.

Answer by unknown (google) for characterization of a submodule

2010-02-11T13:45:54Z

In Hungerford everything is defined without assuming that rings have identity (or that they are commutative). At least according to Definition IV.1.3 on p. 171 of Hungerford, the answer to your first question is affirmative. Quoting:

Definition 1.3. Let $R$ be a ring, $A$ an $R$-module and $B$ a nonempty subset of $A$. $B$ is a submodule of $A$ provided that $B$ is an additive subgroup of $A$ and $rb\in B$ for all $r\in R$, $b\in B$.

[I hope that my interpretation of the question was correct. I understood 'characterization of submodule' as 'definition of submodule.']

EDIT: Google books links to the definition of a module, a submodule, and a ring in Hungerford:

http://books.google.com/books?id=t6N_tOQhafoC&lpg=PP1&dq=hungerford&hl=iw&pg=PA169#v=onepage&q=&f=false

http://books.google.com/books?id=t6N_tOQhafoC&lpg=PP1&dq=hungerford&hl=iw&pg=PA171#v=onepage&q=&f=false

http://books.google.com/books?id=t6N_tOQhafoC&lpg=PP1&dq=hungerford&hl=iw&pg=PA115#v=onepage&q=&f=false

Answer by unknown (google) for Your favorite surprising connections in Mathematics

2010-02-08T14:06:53Z

Goppa’s construction of error-correcting codes from curves, leading to the Tsfasman-Vladut-Zink bound (the first improvement over the Gilbert-Varshamov bound). An error-correcting code may be regarded as a combinatorial structure, and I think that this is a surprising connection between algebraic geometry and combinatorics.

Answer by unknown (google) for Looking for an introductory textbook on algebraic geometry for an undergraduate lecture course

2010-02-06T11:41:12Z

Cox Little and O'Shea's "Ideals varieties and algorithms" (http://www.amazon.com/Ideals-Varieties-Algorithms-Computational-Undergraduate/dp/0387356509/ref=sr_1_1?ie=UTF8&s=books&qid=1265456210&sr=1-1) is very accessible, assumes almost no background in commutative algebra, and has many examples. The emphasis is on computational algebraic geometry (including Groebner bases).

BTW, Milne's "Algebraic Geometry" (http://jmilne.org/math/CourseNotes/AG.pdf) includes an "Annotated Bibliography" Appendix with an "Elementary Algebraic Geometry" section, and perhaps this is a good place to start the search.

Answer by unknown (google) for Existence of hyperelliptic curve with specific number of points in a family

2010-02-01T06:13:00Z

I think that this is equivalent to a known open question. Here are the details. For $K:=\mathbb{F}_{2^n}$, the function $f:y\mapsto y+y^2:K\to K$ is $\mathbb{F}_2$-linear, and its kernel $\{0,1\}$ has dimension 1. The image is therefore of dimension $n-1$, and for $z$ in the image, the fiber $f^{-1}(z)$ has exactly 2 elements.

Hence, to prove that $y^2+y=x^k+ax$ has exactly $2^n$ solutions for some fixed $a\in K$, we have to show that $|\{x\in K|x^k+ax\in \mathrm{Im}(f)\}|=2^{n-1}$.

Since $\sigma:y\mapsto y^2$ is a generator of the Galois group of $K/\mathbb{F}_2$, Hilbert's Theorem 90 (in additive form) says that $z\in \mathrm{Im}(f)$ if and only if $\mathrm{Tr}(z)=0$, where $\mathrm{Tr}$ stands for the trace map from $K$ to $\mathbb{F}_2$.

So the problem is equivalent to showing that there exists an $a\neq 0$ in $K$ such that $|\{x\in K|\mathrm{Tr}(x^k+ax)=0\}|=2^{n-1}$. In other words, we would like to show that there exists a nonzero $a\in K$ such that $$ S_k(a):=\sum_{x\in K}(-1)^{\mathrm{Tr}(x^k+ax)}=0. $$

Apparently, this question was addressed in the coding community. In detail, in [1, p. 258], the following conjecture (of Helleseth) is mentioned:

``Conjecture 3. For any $m$ and $k$ such that $\mathrm{gcd}(2^m-1,k)=1$, the sum $\sum_{x\in\mathbb{F}_{2^m}}(-1)^{\mathrm{Tr}(x^k+ax)}$ is null for at least one nonzero $a$.'' (Note that $n$ in the current question is $m$ in [1]).

It seems that in [1, Corollary 1, p. 253], Conjecture 3 is proved for even $m$ and for certain values of $k$ (the ``Niho exponents,'' defined on p. 252 of [1]).

Interestingly, at least at a first glance it seems that [1] has nothing to say on $k\in\{1,\ldots,2^{n-1}\}$, but to me it seems that this case is trivial (am I missing something?): Consider a normal basis for $K/\mathbb{F}_2$, that is, a basis $B$ consisting of an orbit of an element $\gamma\in K$ under the Galois group of $K/\mathbb{F}_2$ (the $i$th element of $B$ is $b_i:=\gamma^{2^i}$ for $i\in\{0,\ldots,n-1\}$).

From the linearity of the trace and the fact that the trace is onto, we must have $\mathrm{Tr}(b)=1$ for at least one element $b\in B$, and from $\mathrm{Tr}(b^2)=\mathrm{Tr}(b)$ we then have $\mathrm{Tr}(b)=1$ for all $b\in B$. So the trace of an element in $K$ is just the modulo-2 sum of the coefficients in its decomposition according to the basis $B$.

Let $a$ be any element in the trace-dual basis of $B$, say $\mathrm{Tr}(ab_i)=\delta_{i,0}$. Then for $k=2^j$, if we write $x=\sum_i \alpha_i b_i$, we get: $\mathrm{Tr}(ax)=\alpha_0$, $\mathrm{Tr}(x^k)=\mathrm{Tr}(x)=\sum \alpha_i$ (sum in $\mathbb{F}_2$). These agree for half of the $x\in K$, as required.

That's about it. I hope at least some of this makes sense :) I also hope that the original person asking this question didn't actually want to solve the above open question by converting it to a question about curves, for then this answer is useless.

[1] P. Charpin, ``Cyclic codes with few weights and Niho exponents,'' Journal of Combinatorial Theory, Series A 108 (2004) 247--259.

Answer by unknown (google) for Between abstract and concrete: What's the right way to think of specific categories?

2010-01-22T16:34:13Z

Regarding the vivid discussion in the comments after the question (and hopefully, also of some interest for the question itself): I think that a "metacategory" is a definition by axioms, using only first order language, while "interpretation" means: an interpretation as in logic (say, as in p. 29 of Ebbinghaus-Flum-Thomas).

So such an interpretation (a category) is a set, or for convenience, several sets: A set of "objects," a set of "arrows" two function (that is, two more sets) "dom, cod" from the set of arrows to the set of objects, a function "1" from the objects to the arrows, a function "$\circ$" on the pairs of composable arrows, etc., that satisfy the first order axioms of a metacategory.

In summary, I agree with the comment of Qiaochu Yuan: set theory is involved, but not because the objects should somehow be "sets with structure."

Answer by unknown (google) for What are interesting families of subsets of a given set?

2009-12-30T08:56:44Z

How about matroids? [Wikipedia link: http://en.wikipedia.org/wiki/Matroid]

Here is a motivating example. Let $V$ be a vector space over some field $K$, and let $S$ be a finite set of vectors from $V$. Let $I$ be the set of all subsets of $S$ that are linearly independent over $K$ (including the empty set). Then $I$ has the following three properties: (1) It includes the empty set, (2) it is closed under subsets: if $T\in I$ and $T'\subseteq T$ then $T'\in I$, and (3) if $T_1,T_2\in I$ satisfy $|T_1|<|T_2|$ then there exists a $v\in T_2$, $v\notin T_1$, such that $T_1\cup {v}\in I$.

In general, a matroid is a pair $(S,I)$ with $S$ a finite set and $I\subseteq P(S)$ ("$P$" for power set) having the above three properties.

I came across this notion in the context of information theory, in the following presentation: http://www-syscom.univ-mlv.fr/~vignat/EPFL09/abbe.pdf

Surely, information theory is not the main area of mathematics for matroids, and unfortunately I don't know what is (Wikipedia relates it to combinatorics).

Why is Top_4 a reflective subcategory of Top_3?

2009-12-21T20:41:24Z

Hi,

I’m studying some category theory by reading Mac Lane linearly and solving exercises.

In question 5.9.4 of the second edition, the reader is asked to construct left adjoints for each of the inclusion functors Top_{n+1} in Top_n, for n=0, 1, 2, 3, where Top_n is the full subcategory of all T_n-spaces in Top, with T_4=Normal, T_3=Regular, etc.

For n=0, 1, 2, it seems to me that I can use the AFT, with the solution set constructed similarly to the one constructed for proving that Haus (=Top_2) is a reflective subcategory of Top (Proposition 5.9.2, p. 135 of Mac Lane).

But I can’t figure out what should I do with the case of n=3, that is, with the inclusion functor Top_4 in Top_3: Top_4 doesn’t even have products, so it seems that I cannot use the AFT.

Is there some direct construction of this left adjoint (by universal arrows, perhaps)? Answers including a reference would be especially helpful.

Comment by

2010-05-17T21:36:35Z

[deleted the comment referred to in the OP's comment from Mar. 5, 4:37]

Comment by

2010-05-17T21:34:55Z

[deleted previous comments]

Comment by

2010-05-17T21:34:20Z

[deleted previous comments]

Comment by

2010-05-17T20:47:12Z

I honestly don't know [deleted previous comment]

Comment by

2010-05-17T14:25:54Z

There seem to be some discussion on the subject of permutation polynomials in Ch. 7 of Lidl-Niederreiter‏ (books.google.com/…). [I hope I understood the question correctly. In the title shouldn’t $x\mapsto f(x)$ really be $c\mapsto f(c)$?]

Comment by

2010-05-15T16:11:35Z

Perhaps instead of category theory, you should look at some basic book on universal algebra, for example, you can try part 3 of Cohn’s algebra.

Comment by

2010-05-14T18:07:48Z

Thanks for the pointers! The link doesn't seem to work, but I will look at nLab now that I know what to look for. I suppose that at the moment (before finished reading Mac Lane) I'll stick to the foundations described in Section 1.6 of Mac Lane. Although limited (as I now see..), these foundations seem to be sufficient in Mac Lane (as Mike Shulman told me in a comment...), and I should probably not "dive" into something else right now. Thanks again for your help.

Comment by

2010-05-14T13:09:49Z

Thank you very much! Having such tips from an expert is extremely helpful. I have a million more question to ask, but I guess these comments aren't the right place for such a mini course...

Comment by

2010-05-14T12:49:48Z

Thank you very much for your answer! I hope it is OK that I ask another silly question: Is my comment above correct, but just useless, because (for some reason that I still don't understand) "locally small" can refer to non-small hom-sets that are in bijection with small sets? [I'm assuming a single universe, as in Mac Lane.]

Comment by

2010-05-13T22:52:18Z

@Todd Trimble: Is this simple argument wrong? Consider a non-empty hom-set $\widehat{C}(F,G)$, and let $\tau$ be in this hom-set. If the hom-set is small, then by transitivity of the universe, $\tau$ is small too. But $\tau$ is just a function with domain $\operatorname{obj}(C)$ (so $\tau$ is a triple with $\operatorname{obj}(C)$ as its first component). But then from transitivity again we get $\operatorname{obj}(C)\in U$, a contradiction. (So, in general,the answer to the original question is ``no'')

Comment by

2010-05-13T06:37:06Z

@Mike Shulman: Thanks for your answers!

Comment by

2010-05-13T06:32:54Z

..and thank you for the second comment. But isn't this "mixture" exactly what happens in ML-M? Also, I believe that Barr-Wells define creates a-la CWM, and "monadic" with equivalence, but they don't get into trouble because they just do not claim that monadic implies creates.

Comment by

2010-05-13T06:30:16Z

@Mike Shulman: I do not claim that the "old" definition is somehow better. But I believe that anyone that is learning from the standrad (!) textbooks and then, say, chooses not to read the proof in ML-M and just use the assertion "as is" might have the wrong conclusion. Such a person may be assuming that monadic functors create limits in the old way, which is wrong. I beleive (but perhaps I'm wrong) that many mathematicians that are not categorists (but do use category theory) are not necessarily aware that a different, probably more meaningful, definition of "creates" is out there.

Comment by

2010-05-13T04:48:35Z

Thank you so much for this answer! I've been banging my head against the wall trying to figure out where I was wrong, because I just couldn't believe that such an inaccuracy appears in ML-M.

Comment by

2010-05-12T14:43:01Z

Thank you for your answer. Calling this definition "non-standard" is a little strange: first, ML-M themselves use a reference to CWM for the definition of creation (so, is their proposition, as stated, correct?) Second, this is the definition in the Joy of Cats (p. 227), and, if I understand the notation correctly , Barr-Wells (p. 37) also use this definition. If that's not standard, then what is?