text:
New Titles  |  FAQ  |  Keep Informed  |  Review Cart  |  Contact Us Quick Search (Advanced Search ) Browse by Subject General Interest Logic & Foundations Number Theory Algebra & Algebraic Geometry Discrete Math & Combinatorics Analysis Differential Equations Geometry & Topology Probability & Statistics Applications Mathematical Physics Math Education

Solving Systems of Polynomial Equations
Bernd Sturmfels, University of California, Berkeley, CA
A co-publication of the AMS and CBMS.
 SEARCH THIS BOOK:
CBMS Regional Conference Series in Mathematics
2002; 152 pp; softcover
Number: 97
ISBN-10: 0-8218-3251-4
ISBN-13: 978-0-8218-3251-6
List Price: US$38 Member Price: US$30.40
All Individuals: US\$30.40
Order Code: CBMS/97

A classic problem in mathematics is solving systems of polynomial equations in several unknowns. Today, polynomial models are ubiquitous and widely used across the sciences. They arise in robotics, coding theory, optimization, mathematical biology, computer vision, game theory, statistics, and numerous other areas.

This book furnishes a bridge across mathematical disciplines and exposes many facets of systems of polynomial equations. It covers a wide spectrum of mathematical techniques and algorithms, both symbolic and numerical.

The set of solutions to a system of polynomial equations is an algebraic variety--the basic object of algebraic geometry. The algorithmic study of algebraic varieties is the central theme of computational algebraic geometry. Exciting recent developments in computer software for geometric calculations have revolutionized the field. Formerly inaccessible problems are now tractable, providing fertile ground for experimentation and conjecture.

The first half of the book gives a snapshot of the state of the art of the topic. Familiar themes are covered in the first five chapters, including polynomials in one variable, Gröbner bases of zero-dimensional ideals, Newton polytopes and Bernstein's Theorem, multidimensional resultants, and primary decomposition.

The second half of the book explores polynomial equations from a variety of novel and unexpected angles. It introduces interdisciplinary connections, discusses highlights of current research, and outlines possible future algorithms. Topics include computation of Nash equilibria in game theory, semidefinite programming and the real Nullstellensatz, the algebraic geometry of statistical models, the piecewise-linear geometry of valuations and amoebas, and the Ehrenpreis-Palamodov theorem on linear partial differential equations with constant coefficients.

Throughout the text, there are many hands-on examples and exercises, including short but complete sessions in Maple®, MATLAB®, Macaulay 2, Singular, PHCpack, CoCoA, and SOSTools software. These examples will be particularly useful for readers with no background in algebraic geometry or commutative algebra. Within minutes, readers can learn how to type in polynomial equations and actually see some meaningful results on their computer screens.

Prerequisites include basic abstract and computational algebra. The book is designed as a text for a graduate course in computational algebra.

® Waterloo Maple, Inc., Ontario, Canada.

® MATLAB, The MathWorks, Inc., Natick, MA.

PHCpack ©1998, Katholieke Universiteit Leuven, Department of Computer Science, Heverlee, Belgium.

CoCoA, A. Capani, G. Niesi, L. Robbiano, a system for doing Computations in Commutative Algebra, available via anonymous ftp from: http://cocoa.dima.unige.it.

SOSTools is a MATLAB® toolbox and freely available under the GNU license at http://www.cds.caltech.edu/sostools or http://www.aut.ee.ethz.ch/ parrilo/sostools.

Graduate students and research mathematicians interested in computational algebra and its applications.

Reviews

"Methods for solving systems of polynomial equations in the tropical semiring promise to have wide-ranging applications and have not been treated in monograph before. The book is written in an lively style with many examples, comments, computer algebra sessions and a generous dose of tempting exercises. It can be read with a reasonably good knowledge of basic algebra and is well suited for a lecture course on the graduate level. For the researcher who wants to get an accessible introduction to current techniques in polynomial system solving it can be highly recommended."

-- Zentralblatt Math

• Polynomials in one variable
• Gröbner bases of zero-dimensional ideals
• Bernstein's theorem and fewnomials
• Resultants
• Primary decomposition
• Polynomial systems in economics
• Sums of squares
• Polynomial systems in statistics
• Tropical algebraic geometry
• Linear partial differential equations with constant coefficients
• Bibliography
• Index


text:
# Are these two bounds close to each other?

Recently I proved a some bound about something. The bound is (details : come soon)

Upper bound $f(k)< k^{k^{O(k)}}$.

Lower bound $f(k)< k^{k^2-o(k)}$

My question is

1. Are these two bounds close? For general meaning.

2. What should I call the lower bound? An exponential function? Or something other looks like a litter larger. Clearly it is not as large as double exponential.

3. Should I need to stress that the exponent in the lower bound is $k^2$.

-

For large, and even medium-sized $k$, the upper bound is hugely bigger than the lower bound. But for $k$ not too large, the two bounds might be not far from each other if the implied constant in the $O(k)$ is very close to $0$.
The $O(k)$ means that for the upper bound, all we know is that the exponent of $k$ is, for large $k$, less than $k^{ck}$ for some constant $c$. The lower bound is not quite put in lower bound language: a lower bound means a floor below which a function does not go, so I assume that what is meant is $f(k)\gt k^{k^2-o(k)}$. Thus the exponent of $k$ is of size roughly $k^2$.
So already for the upper bound, the exponent of $k$ is a fast growing function, while the exponent in the lower bound grows relatively slowly.

format: plain


text:
The lactose permease (LacY) of Escherichia coli is the prototype of the major facilitator superfamily, one of the largest families of membrane transport proteins. Structurally, two pseudo-symmetrical six-helix bundles surround a large internal aqueous cavity. Single binding sites for galactoside and H+ are positioned at the approximate center of LacY halfway through the membrane at the apex of the internal cavity. These features enable LacY to function by an alternating-access mechanism that can catalyze galactoside/H+ symport in either direction across the cytoplasmic membrane. The H+-binding site is fully protonated under physiological conditions, and subsequent sugar binding causes transition of the ternary complex to an occluded intermediate that can open to either side of the membrane. We review the structural and functional evidence that has provided new insight into the mechanism by which LacY achieves active transport against a concentration gradient.

### Introduction

The lacY gene, the second structural gene in the lac operon (Müller-Hill, 1996), encodes lactose permease (LacY), the polypeptide solely responsible for β-galactoside transport in Escherichia coli. LacY (TCDB 2.A.1.5.1) is a member of the oligosaccharide/H+ symporter subfamily of the major facilitator superfamily (MFS), and it recognizes disaccharides with a D-galactopyranosyl ring and D-galactose, with no affinity for glucopyranosides or glucose. The natural substrate of LacY is lactose, a disaccharide containing a galactopyranosyl and a glucopyranosyl motiety in a β-1→4 glycosidic linkage. LacY catalyzes reversible translocation of one galactoside with one H+, and coupled translocation in the same direction is obligatory (symport).

The lacY gene is the first gene encoding a membrane transport protein to be cloned and sequenced (Büchel et al., 1980), the first symporter to be purified to homogeneity in a functional state (Newman et al., 1981) and the first symporter to have a structure determined (Abramson et al., 2003). LacY has 417 amino acid residues (65–70% of which are hydrophobic) and a molecular weight of 46,517 D, and each of the 417 residues has undergone Cys-scanning mutagenesis (reviewed in Frillingos et al., 1998) and site-directed alkylation (reviewed in Kaback et al., 2007; Nie et al., 2007) and/or other site-directed mutagenesis. Notably, only nine residues are essentially irreplaceable with regard to active lactose transport: Glu126 (helix IV), Arg144 (helix V), Trp151 (helix V), Tyr236 (helix VII), Glu269 (helix VIII), Asn272 (helix VIII), and His322 (helix X) form the galactoside-binding site (Kumar et al., 2014, 2015); and Arg302 (helix IX) and Glu325 (helix X) are essential for coupled H+ translocation (Carrasco et al., 1989; Sahin-Tóth and Kaback, 2001). All nine side chains are located in or near the aqueous cavity in the approximate middle of the LacY molecule (Fig. 1 a and Fig. 2 a).

LacY is a chemiosmotic nano-machine that performs coupled transport of a galactopyranoside with an H+ across the cytoplasmic membrane of E. coli (i.e., galactoside/H+ symport). Active transport (i.e., transport against a concentration gradient) is achieved by transduction of the free energy released from energetically favorable movement of H+ down the electrochemical H+ gradient ($Δμ˜H+;$ interior negative and/or alkaline) as postulated by the chemiosmotic hypothesis of Mitchell (1967, 1968; Fig. 3 a). Conversely, downhill galactoside transport drives uphill H+ flux and generation of $Δμ˜H+,$ the polarity of which depends upon the direction of the sugar concentration gradient (Fig. 3, b and c). Importantly, LacY also catalyzes transmembrane exchange of internal for external galactoside in a manner that is independent of $Δμ˜H+$ (Fig. 3, d and e). Thus, the primary driving force for “alternating access” (Jardetzky, 1966) of the H+- and sugar-binding sites to either side of the membrane is binding and dissociation of galactoside by protonated LacY. Without bound sugar, LacY cannot translocate H+ with or without $Δμ˜H+,$ and unprotonated LacY cannot bind a galactoside because of low affinity. Therefore, binding of both sugar and H+ is required for symport.

Despite a number of structures of MFS members, including 10 of LacY, mechanisms of these dynamic proteins are not completely understood. It has been demonstrated that sugar binding to highly dynamic protonated LacY triggers a global conformational change in which sugar- and H+-binding sites gain alternating access to either side of the membrane. Sugar binding and dissociation drive this conformational change through an induced-fit mechanism, while the proton electrochemical gradient accelerates the rate of deprotonation. LacY behaves much like an enzyme except that the transition state involves the protein rather than the substrate. X-ray structures of LacY inward- and almost occluded outward-facing conformations provide the structural basis for the alternating access mechanism. Alternating access has been documented almost unequivocally by applying pre–steady-state kinetics, as well as multiple biochemical and spectroscopic approaches, and by using kinetic data obtained in real time for several steps in the transport cycle. Thirty-one camelid nanobodies (Nbs) allow stabilization of LacY in different intermediate states that are providing an understanding of the structural changes underlying the symport mechanism.

### Oligomeric state

LacY is a monomer both in detergent and in the membrane. The polypeptide reconstitutes as a monomer, as shown by fluorescence anisotropy (Vogel et al., 1985) and by freeze-fracture EM in the absence or presence of an imposed (Costello et al., 1987). Initial rates of $Δμ˜H+−$driven lactose transport in proteoliposomes reconstituted at various protein-to-lipid ratios vary linearly. The linearity of the data and particularly the complete lack of sigmoidicity at very low ratios are consistent with the conclusion that LacY functions as a monomer. Furthermore, an engineered fusion protein encoded by two tandemly fused lacY open reading frames exhibits good transport activity, and negative dominance is not observed with either mutations or chemical modification in either half of the covalent dimer (Sahin-Tóth et al., 1994). Finally, cross-linking of LacY single-Cys mutants in the plane of the membrane is stochastic (Guan et al., 2002). Taken together, the findings indicate that LacY is both structurally and functionally a monomer (reviewed in Guan and Kaback, 2006).

### 3-D structure

LacY is organized into two six-helix bundles connected by a relatively long cytoplasmic loop between helices VI and VII, which exhibit twofold pseudo-symmetry when viewed parallel to the plane of the membrane (Fig. 1, a and b). Within each domain, there are two three-helix repeats with inverted topology. These structural features are observed in both inward- and outward-facing conformations. The protein is 86% α-helix in the x-ray structure (85% by circular dichroism; Foster et al., 1983) and contains twelve transmembrane helices traversing the membrane in zigzag fashion connected by very short hydrophilic loops with both N and C termini on the cytoplasmic side of the membrane. Most of the helices are irregular and distorted with bends and kinks. Helices III, VI, IX, and XII are largely embedded in the membrane, and the cytoplasmic regions of helices I, II, IV, and V from the N-terminal domain and helices VII, VIII, X, and XI from the C-terminal domain line a hydrophilic cavity. The inward-facing conformation may represent the resting state of the molecule (Nie and Kaback, 2010; Smirnova et al., 2011b; Kaback, 2015).

The initial structure was obtained with a conformationally constrained mutant, C154G LacY (Abramson et al., 2003), and a similar crystal structure was obtained for the WT a few years later (Guan et al., 2007). Viewed perpendicular to the membrane, both structures display heart-shaped molecules with a deep hydrophilic cavity open on the cytoplasmic side and sealed on the periplasmic side, an inward (cytoplasmic)–facing conformation (Fig. 1 a) with largest dimension of 60 × 60 Å. Viewed parallel to the plane of the membrane from the cytoplasmic side (Fig. 1 b), the molecules have a distorted oval shape that measures 30 × 60 Å. Calculation of the electrostatic surface potential reveals a positively charged ring around the cytoplasmic opening (Fig. 1, c–e; Yousef and Guan, 2009) and preferential distribution of negatively charged residues on the periplasmic side (Fig. 1 f). It is apparent that LacY conforms to the positive inside rule (von Heijne, 1992). Remarkably, LacY can be expressed in two fragments in vivo that find each other in the membrane and form a functional complex (Bibi and Kaback, 1990; Zen et al., 1994).

Four x-ray structures from LacY mutant G46W/G262W in a partially outward (periplasmic)–open conformation with a tightly sealed cytoplasmic side (Kumar et al., 2014, 2015, 2018; Jiang et al., 2016) have also been obtained (Fig. 2 a). Three of the structures (8, 9, and 27) are in an occluded conformation with a narrow periplasmic opening and a single galactoside molecule in the central sugar-binding site. The opening on the periplasmic side is too narrow to allow entrance or exit of the sugar (∼3 Å at the narrowest point), and the bound galactoside is occluded. Mutant G46W/G262W is clearly able to open sufficiently to bind galactoside at rates approaching diffusion (Smirnova et al., 2013), and upon binding, the mutant tries to transit into an occluded conformation. However, it cannot do so completely because the bulky Trp residues block complete closure. Thus, the mutant binds galactoside, which initiates transition into an occluded intermediate state, but it cannot complete the operation, which accounts for why the mutant is completely unable to catalyze transport of any type. It is also clear that an occluded intermediate is part of the transport cycle.

### Galactoside binding and specificity

There is one sugar-binding site in LacY that is selective for galactose or disaccharides containing a galactosyl moiety, and the symporter transports a single molecule per transport cycle. Two lactose analogues, β-D-galactopyranosyl 1-thio-β-D-galactopyranoside (TDG) and 4-nitrophenyl-α-D-galactopyranoside (α-NPG), as well as other homologues (Smirnova et al., 2018), bind to LacY with micromolar Kd. The natural substrate lactose has poor affinity with a Kd of ∼1 mM (Guan and Kaback, 2004), and galactose is the most specific substrate for LacY with the lowest affinity. Various adducts (particularly if they are hydrophobic) at the anomeric carbon (C1) of the galactopyranosyl ring greatly increase affinity with little or no effect on specificity (Sahin-Tóth et al., 2000). Although glucose is an epimer of galactose, neither glucose nor glucosides are recognized by LacY. The C4 OH on the galactopyranosyl ring is probably the most important determinant for specificity, with the C5, C3, and C6 OH groups playing varying roles in determining affinity/specificity, while C1 and C2 OH are of little importance (Sahin-Tóth et al., 2000, 2001).

Sugar-bound LacY in the inward-facing or partially outward-facing conformation has been resolved crystallographically (Chaptal et al., 2011; Kumar et al., 2014, 2015, 2018). Both of the inward-facing and outward-facing structures contain a single galactoside that occupies the central cavity lined by the same residues regardless of the conformation of LacY, further confirming the conclusion that there is only a single sugar-binding site (Guan and Kaback, 2004). The site is located at the apex of the internal cavity in the middle of LacY, which enables transport in either direction.

The sugar-bound, inward-facing structure is from single-Cys V122C LacY with covalently bound methanethiosulfonyl-galactoside (Chaptal et al., 2011), a suicide inactivator for the mutant (Guan et al., 2003b). Sugar-bound outward-facing structures have been obtained for the G46W/G262W mutant (Smirnova et al., 2013) with bound TDG or α-NPG (Kumar et al., 2014, 2015, 2018). The position of the galactosyl moiety in these structures is almost identical (Fig. 2, b and c), which provides strong evidence that it is indeed the galactosyl moiety that determines specificity.

Cys-scanning and site-directed mutagenesis have been used extensively to study the sugar-binding site in LacY (Frillingos et al., 1998), and the results from genetic engineering in combination with biochemical and biophysical characterization are largely confirmed crystallographically (Chaptal et al., 2011; Kumar et al., 2014, 2015, 2018). The LacY structures show that the galactopyranosyl ring of α-NPG or TDG stacks hydrophobically with Trp151 in helix V (Fig. 2, b and c), which is suggested to play important roles in orienting the galactopyranosyl ring and facilitating specific hydrogen bonding, in addition to increasing affinity (Guan et al., 2003a). Replacement of Trp151 with a Tyr or Phe residue decreases affinity for galactosides, but has little effect on lactose transport (Guan et al., 2003a; Vázquez-Ibar et al., 2003; Smirnova et al., 2009b). Glu269 in helix VIII forms two hydrogen bonds with the C4 and C3 OH groups on the galactopyranosyl ring (Fig. 2, b and c), which explains why the Glu269 residue may be the primary determinant for sugar specificity (Weinglass et al., 2003). These important interactions are further stabilized by hydrogen bond interactions between the C4 and C3 OH with Asn272 (helix VIII) and between His322 (helix X) and the C3 OH. The Asn272 side chain can be replaced with Gln exclusively without a significant loss of sugar-binding affinity. Glu269 and His322 are irreplaceable with respect to sugar-binding and transport activities. Two other irreplaceable residues, Arg144 and Glu126 in the N-terminal domain, form a salt bridge, and Arg144 serves directly as a hydrogen-bond donor to the C5 and C6 OH groups of the galactopyranosyl ring of TDG or α-NPG, and the C2′ OH group in another galactopyranosyl ring. As described above, the glucopyranosyl ring in lactose can be replaced by various adducts that affect binding affinity only. Glu126, in addition to stabilizing the position of Arg144, also forms multiple hydrogen bonds with the C2′ and C3′ OH groups of TDG. Arg144 cannot be replaced with positively charged Lys, and Asp replacement for Glu126 also decreases affinity for galactosides significantly (Smirnova et al., 2009a).

### Sugar binding and induced fit

Methanethiosulfonyl-galactose is a unique suicide substrate for a LacY mutant with Cys in place of Ala122 (Guan et al., 2003b). The x-ray structure (Chaptal et al., 2011) reveals that a molecule of methanethiosulfonyl-galactose is covalently bound to a Cys engineered at position 122 near the sugar-binding site, and the overall conformation of LacY remains in an inward-open conformation, although typically galactoside binding shifts LacY to the outward-open state (reviewed in Smirnova et al., 2011b). However, many side-chain interactions with the galactopyranoside ring are perturbed; for example, Asn272, His322, and Arg144 are no longer sufficiently close to interact with the galactopyranosyl ring. Therefore, although the binding site is partially occupied, critical interactions with these important side chains are sufficiently disturbed that the interactions are insufficient to drive transition into the occluded state.

### H+ binding

Unexpectedly, LacY exhibits a perturbed apparent pK of ∼10.5 with respect to galactoside-binding affinity, and the pH-dependent apparent pK is abrogated when Glu325 (helix X) is replaced with a neutral side chain (Smirnova et al., 2008; Fig. 4). Mutant E325A binds sugar with an affinity similar to WT, but affinity is independent of pH up to at least pH 11. Even more remarkably, Glu325 also exhibits a pKa of 10.5 by direct measurement with surface enhanced infrared absorption spectroscopy (SEIRAS; Grytsyk et al., 2017; Fig. 5). The perturbed pKa is due to location in a hydrophobic pocket between helices IX and X (Figs. 5 and 6). Therefore, Glu325 is clearly the primary (and possibly the only) functional H+-binding site in LacY. A pKa value of 10.5 translates to a Kd for H+ of less than ∼30 pM, so Glu325 is completely protonated over a very broad pH range. The overall conclusion is that the galactoside-binding site in LacY is remarkably stable to alkaline pH, but in order to elicit this property, Glu325 must be replaced with a neutral side chain.

Of potential importance, Glu325 is in close proximity to an electrostatic/hydrogen-bond network involving His322 and Lys319 on helix X, Tyr236 and Asp240 on helix VII, and Arg302 on helix IX (Fig. 6). Glu269 and particularly His322, initially thought to be involved in H+ translocation, are both ligands for the galactopyranosyl moiety in the sugar-binding site (Fig. 2, b and c). Mutation of Glu269, His322, or Tyr236 causes a marked decrease in sugar-binding affinity (Smirnova et al., 2008). Another salt bridge (Asp237 in helix VII and Lys358 in helix XI) also lies in the cavity, but does not make a direct contact with either site and is not involved in sugar or H+ binding. However, this salt bridge is essential for the insertion of LacY into the membrane and for maintaining protein stability (Kaback et al., 2001).

Since transmembrane exchange does not involve $Δμ˜H+,$ it is apparent that alternating access is driven by binding and dissociation of sugar, and does not involve turnover of H+ (Kaback, 2015). Because the driving force for accumulation against a gradient is $Δμ˜H+$ and E. coli has a stable internal pH of 7.6 (Padan et al., 1976; Ramos et al., 1976; Zilberstein et al., 1979), a pKa of 10.5 for LacY (Smirnova et al., 2008; Grytsyk et al., 2017) implies that decreasing the pKa by three orders of magnitude to cytoplasmic pH would release only ∼50% of the transported lactose from LacY. How to increase the rate of deprotonation without decreasing the H+ concentration of the E. coli cytoplasm? Arg302 is relatively close to Glu325 (∼6 Å), and mutants R302A or R302S cannot perform active transport, but catalyze transmembrane exchange (Sahin-Tóth et al., 2001; Weinglass et al., 2002). A recent SEIRAS study (Grytsyk et al., 2019) on the effect of mutating residues in the immediate vicinity of Glu325 shows that only mutation R302K alters the Glu325 pKa, causing over a 2-pH U acid shift. Overall, the findings support the idea that H+ is extracted from Glu325 by spatial fluctuations in the position of Arg302, expelling H+ by moving near Glu325 (Weinglass et al., 2001) or vice versa.

Although nothing more is known at present, neutral replacements for specific carboxyl residues in the E. coli melibiose (Ethayathulla et al., 2014), fucose (Dang et al., 2010), and xylose permeases (Sun et al., 2012), as well as the Staphylococcus epidermidis glucose permease (Iancu et al., 2013), behave functionally in a manner similar to neutral replacement mutants for Glu325 in LacY. Thus, each of these sugar permease mutants is defective with respect to active transport (i.e., H+/sugar symport), but still able to catalyze transmembrane exchange reactions. At the least, the findings indicate that these MFS family members likely have an ordered kinetic mechanism similar to that found with LacY.

### Alternating access and the symport mechanism

An alternating-access type of mechanism is widely accepted to explain membrane transport; thus, H+ symporters expose both H+- and cargo-binding sites alternatively to either side of the membrane through conformational changes. In LacY, both the sugar- and H+-binding sites are located at the approximate middle of the molecule at the apex of the cavity, providing a structural basis for such an alternating-access mechanism.

The periplasmic- and cytoplasmic-open conformations with bound galactoside and H+ reflect static states. However, LacY must undergo dynamic conformational changes to expose both the sugar- and H+-binding sites to either side of the membrane. Multiple independent experimental methods (Smirnova et al., 2011a), e.g., site-directed alkylation of single-Cys mutants; thiol cross-linking; single molecule FRET; double electron–electron resonance spectroscopy; and time-resolved FRET techniques to detect conformational change, sugar-binding kinetics, and nanobodies, have been used to examine sugar-induced conformational changes which provide independent converging evidence that periplasmic and cytoplasmic cavities open reciprocally and that opening of the periplasmic cavity controls closing of the cytoplasmic cavity (Kaback et al., 2011; Smirnova et al., 2017). In the absence of a galactoside, LacY may favor an inward-facing conformation, the resting state, as indicated by the crystal structure (Fig. 1), but galactoside binding causes LacY to populate intermediate occluded and outward-open conformations.

The LacY transport cycle includes alternating-access and several other steps that are explained by a simplified eight-step kinetic scheme (Fig. 7). Based upon an ordered-binding model (Kaczorowski et al., 1979), different transport modes are explained in detail below.

### Active transport

Active transport of lactose against a lactose concentration gradient is driven by $Δμ˜H+$ (interior negative and/or alkaline). LacY is completely protonated in the outward-open state, which primes it for sugar binding with relatively high affinity (1). Binding of galactoside from the periplasm (2) to protonated LacY induces the formation of an occluded intermediate (3), in which sugar and H+ are bound and both solvent accessible pathways from either side of protein are closed. The intermediate with a bound sugar and H+ then opens to the cytoplasm (4), sugar dissociates (5) followed by deprotonation of Glu325 (6) to the cytoplasm, unloaded LacY returns to the outward-facing conformation by steps (7 and 8), and Glu325 is protonated immediately (1), ready for the next transport cycle. Notably, the ordered mechanism, with H+ on first and off second, makes it particularly difficult to develop a H+ leak.

LacY drives accumulation of lactose against a 50- to 100-fold concentration gradient (Robertson et al., 1980) with a turnover number of ∼20 s−1. Both ΔΨ (interior negative) and ΔpH (interior alkaline) have quantitatively the same effect on transport, with a 50- to 100-fold decrease in Km and the same thermodynamic equilibrium. In opposition to time-honored conjecture, the Kd for galactosides on either side of the membrane is essentially the same in the absence or presence of $Δμ˜H+$ (Guan and Kaback, 2004). In the absence of $Δμ˜H+,$ there is three- to fourfold inhibition of lactose transport in the presence of deuterium oxide (D2O), indicating that deprotonation is rate limiting (Viitanen et al., 1983; Garcia-Celma et al., 2009, 2010; Gaiko et al., 2013). However, when there is a driving force on the H+ in the presence of $Δμ˜H+,$ deprotonation is no longer rate-limiting, and the transport rate is unaffected by D2O. It is particularly noteworthy that a number of experimental findings indicate that $Δμ˜H+$ functions kinetically as a driving force on the H+, but alternating access itself is driven by galactoside binding and dissociation and independent of $Δμ˜H+$ (Guan and Kaback, 2006).

### Transport down a concentration gradient

Inwardly directed flux (influx) or outwardly directed flux (efflux) down lactose concentration gradients (Fig. 3, b and c) occurs in a similar fashion, starting at step 1 for influx and step 6 for efflux and proceeding around the circle. Both transport modes generate the polarity of which depends on the direction of the flux, and the limiting step involves deprotonation of Glu325. Both reactions exhibit deuterium isotope effects; i.e., influx and efflux are inhibited by D2O.

### Transmembrane exchange

Equilibrium exchange and counterflow represent alternating access of the galactoside-binding site to alternative sides of the membrane. In either reaction, LacY binds a sugar molecule on the external side of the membrane (unlabeled if equilibrium exchange; labeled if counterflow) and exchanges that sugar molecule for its opposite member on internal side of membrane. With equilibrium exchange, the concentrations are the same on both sides of the membrane; with counterflow, the internal concentration of unlabeled galactoside is much higher than the external concentration of labeled sugar. Under both conditions, the H+ does not dissociate from LacY, and both reactions are unaffected by ambient pH or $Δμ˜H+$ and do not exhibit a deuterium isotope effect. Only steps 2 through 5 in Fig. 7 are engaged. For counterflow, the initial 1/1 exchange of internal unlabeled substrate for external labeled galactoside leads to a rapid increase in internal radioactivity until all of the internal unlabeled sugar inside is exchanged for external labeled galactoside. At this point, the increase in radioactivity stops, and the internal radioactivity decreases with time as the concentrations equilibrate and the specific activity of the external labeled substrate decreases, thereby causing the typical “overshoot” profile that is observed.

Ordered binding and release of H+ and galactoside are strongly supported by the behavior of neutral replacement mutants in Glu325 that do not catalyze any reactions involving net H+ translocation (i.e., electrogenic transport), but catalyze transmembrane exchange (i.e., electroneutral transport) at the same rate as WT LacY (Carrasco et al., 1989).

### Outward-facing conformers stabilized by Nbs

Single-domain camelid Nbs raised against a LacY mutant immobilized in an outward-open conformation bind to LacY completely inhibiting transport and stabilizing the open-outward conformers of the WT (Smirnova et al., 2014). Using site-directed, distance-dependent Trp quenching/unquenching of fluorescent probes on opposite surfaces of LacY, conformational states of LacY complexed with each of eight unique, high-affinity Nbs that bind exclusively to the periplasmic side and block transport, but increase accessibility of the sugar-binding site, were examined (Smirnova et al., 2015). Each Nb induces quenching with three pairs of cytoplasmic Trp/bimane probes, indicating closure of the cytoplasmic cavity. In reciprocal fashion, the same Nbs induce unquenching of fluorescence in three pairs of periplasmic probes due to opening of the periplasmic cavity. Since the extent of fluorescence change with various Nbs differs and the differences correlate with changes in the stopped-flow rate of sugar binding, it is also concluded that the Nbs stabilize several different outward-open conformations of LacY. Thus, Nb binding clearly involves conformational selection of LacY molecules, which has been confirmed by thermodynamic studies with isothermal titration calorimetry (Hariharan et al., 2016). X-ray crystal structures of three Nb/LacY complexes, one apo structure (Jiang et al., 2016) with no bound sugar substrate, and two with bound lactose analogues (Kumar et al., 2015, 2018), confirm the biochemical data indicating that the Nbs bind stoichiometrically to the periplasmic face of the C-terminal six-helix bundle with nanomolar affinities.

### IIAGlc regulation of lactose utilization by catabolite repression

Transcription of the lacY gene and LacY transport activity are down-regulated by the phosphoenolpyruvate:glucoside phosphotransferase system (PTS; Postma et al., 1993; Park et al., 2006). A phosphotransfer protein IIAGlc of the PTS, the most abundant cytosolic protein in E. coli, plays a key role in the regulating carbohydrate metabolism by binding to various families of sugar transporters and many other soluble proteins, modulating their activities (Deutscher et al., 2014; Hariharan and Guan, 2014; Vogt et al., 2014; Hariharan et al., 2015). Binding measurements (Hariharan et al., 2015) show that unphosphorylated IIAGlc binds to LacY in the absence or presence of galactoside. Glucose transport by PTS-mediated vectorial phosphorylation (Kaback, 1968) leads to preponderance of unphosphorylated IIAGlc, which binds to LacY and inhibits galactoside binding and subsequent inducer formation. By this means, synthesis of inducer is prevented so that the cell preferentially utilizes glucose via the PTS. The phenomenon is known as “inducer exclusion.”

### Summary and future prospects

Studies with LacY have provided new insights into the mechanism of H+/galactoside symport as follows. (1) High-resolution structural information of at least two important conformations of LacY in apo and substrate-bound forms have been obtained. (2) Detailed understanding of galactoside and H+ binding and symport, much of which was unanticipated, has been obtained. (3) Although chemiosmosis is the driving force for the overall process by which lactose is accumulated against a concentration gradient, the basic alternating access conformational change itself is independent of $Δμ˜H+.$ (4) Active transport does not involve a change in affinity for galactoside on either side of the membrane. Rather, there is a marked change in affinity for H+ driven by And perhaps most surprisingly, (5) The mechanism of coupling between H+ and galactoside binding is relatively simple—in order to bind/transport galactoside, Glu325 must be protonated.

Despite these advances, several fundamental questions remain unsolved, some of which are the following: How generalized are the findings with LacY with respect to other permeases? Why does a negative charge on Glu325 block galactoside binding? Is Glu325 the only side chain in LacY directly involved in coupled H+ translocation? Although there is no change in Kd for galactosides, why kinetically is there is a decrease in Km in the presence of $Δμ˜H+?$ What structural changes resulting from release of sugar during the transport cycle cause LacY deprotonation? Is an increase in water accessibility involved with deprotonation of Glu325? Does the transport mechanism in other symporters involve a carboxyl side chain with a perturbed pKa that can be detected by SEIRAS? By using Nbs, can cryo-EM be applied successfully to a protein the size of LacY?

The work was supported by National Institutes of Health grant R01GM120043 and National Science Foundation Eager grant MCB1747705 to H.R. Kaback, as well as National Institutes of Health grants R01GM122759 and R21NS105863 to L. Guan. H.R. Kaback also gratefully acknowledges support from the University of California, Los Angeles, and a gift from Ruth and Bucky Stein.

The authors declare no competing financial interests.

Lesley C. Anson served as editor.

Abramson
,
J.
,
I.
Smirnova
,
V.
Kasho
,
G.
Verner
,
H.R.
Kaback
, and
S.
Iwata
.
2003
.
Structure and mechanism of the lactose permease of Escherichia coli
.
Science.
301
:
610
615
.
Bibi
,
E.
, and
H.R.
Kaback
.
1990
.
In vivo expression of the lacY gene in two segments leads to functional lac permease
.
87
:
4325
4329
.
Büchel
,
D.E.
,
B.
Gronenborn
, and
B.
Müller-Hill
.
1980
.
Sequence of the lactose permease gene
.
Nature.
283
:
541
545
.
Carrasco
,
N.
,
I.B.
Püttner
,
L.M.
Antes
,
J.A.
Lee
,
J.D.
Larigan
,
J.S.
Lolkema
,
P.D.
Roepe
, and
H.R.
Kaback
.
1989
.
Characterization of site-directed mutants in the lac permease of Escherichia coli. 2. Glutamate-325 replacements
.
Biochemistry.
28
:
2533
2539
.
Chaptal
,
V.
,
S.
Kwon
,
M.R.
Sawaya
,
L.
Guan
,
H.R.
Kaback
, and
J.
Abramson
.
2011
.
Crystal structure of lactose permease in complex with an affinity inactivator yields unique insight into sugar recognition
.
108
:
9361
9366
.
Costello
,
M.J.
,
J.
Escaig
,
K.
Matsushita
,
P.V.
Viitanen
,
D.R.
Menick
, and
H.R.
Kaback
.
1987
.
Purified lac permease and cytochrome o oxidase are functional as monomers
.
J. Biol. Chem.
262
:
17072
17082
.
Dang
,
S.
,
L.
Sun
,
Y.
Huang
,
F.
Lu
,
Y.
Liu
,
H.
Gong
,
J.
Wang
, and
N.
Yan
.
2010
.
Structure of a fucose transporter in an outward-open conformation
.
Nature.
467
:
734
738
.
Deutscher
,
J.
,
F.M.
Aké
,
M.
Derkaoui
,
A.C.
Zébré
,
T.N.
Cao
,
H.
Bouraoui
,
T.
Kentache
,
A.
Mokhtari
,
E.
Milohanic
, and
P.
Joyet
.
2014
.
The bacterial phosphoenolpyruvate:carbohydrate phosphotransferase system: regulation by protein phosphorylation and phosphorylation-dependent protein-protein interactions
.
Microbiol. Mol. Biol. Rev.
78
:
231
256
.
Ethayathulla
,
A.S.
,
M.S.
Yousef
,
A.
Amin
,
G.
Leblanc
,
H.R.
Kaback
, and
L.
Guan
.
2014
.
Structure-based mechanism for Na(+)/melibiose symport by MelB
.
Nat. Commun.
5
:
3009
.
Foster
,
D.L.
,
M.
Boublik
, and
H.R.
Kaback
.
1983
.
Structure of the lac carrier protein of Escherichia coli
.
J. Biol. Chem.
258
:
31
34
.
Frillingos
,
S.
,
M.
Sahin-Tóth
,
J.
Wu
, and
H.R.
Kaback
.
1998
.
Cys-scanning mutagenesis: a novel approach to structure function relationships in polytopic membrane proteins
.
FASEB J.
12
:
1281
1299
.
Gaiko
,
O.
,
A.
Bazzone
,
K.
Fendler
, and
H.R.
Kaback
.
2013
.
Electrophysiological characterization of uncoupled mutants of LacY
.
Biochemistry.
52
:
8261
8266
.
Garcia-Celma
,
J.J.
,
I.N.
Smirnova
,
H.R.
Kaback
, and
K.
Fendler
.
2009
.
Electrophysiological characterization of LacY
.
106
:
7373
7378
.
Garcia-Celma
,
J.J.
,
J.
Ploch
,
I.
Smirnova
,
H.R.
Kaback
, and
K.
Fendler
.
2010
.
Delineating electrogenic reactions during lactose/H+ symport
.
Biochemistry.
49
:
6115
6121
.
Grytsyk
,
N.
,
J.
Sugihara
,
H.R.
Kaback
, and
P.
Hellwig
.
2017
.
pKa of Glu325 in LacY
.
114
:
1530
1535
.
Grytsyk
,
N.
,
A.F.
Santos Seiça
,
J.
Sugihara
,
H.R.
Kaback
, and
P.
Hellwig
.
2019
.
Arg302 governs the pKa of Glu325 in LacY
.
116
:
4934
4939
.
Guan
,
L.
, and
H.R.
Kaback
.
2004
.
Binding affinity of lactose permease is not altered by the H+ electrochemical gradient
.
101
:
12148
12152
.
Guan
,
L.
, and
H.R.
Kaback
.
2006
.
Lessons from lactose permease
.
Annu. Rev. Biophys. Biomol. Struct.
35
:
67
91
.
Guan
,
L.
,
F.D.
Murphy
, and
H.R.
Kaback
.
2002
.
Surface-exposed positions in the transmembrane helices of the lactose permease of Escherichia coli determined by intermolecular thiol cross-linking
.
99
:
3475
3480
.
Guan
,
L.
,
Y.
Hu
, and
H.R.
Kaback
.
2003
a
.
Aromatic stacking in the sugar binding site of the lactose permease
.
Biochemistry.
42
:
1377
1382
.
Guan
,
L.
,
M.
Sahin-Tóth
,
T.
Kálai
,
K.
Hideg
, and
H.R.
Kaback
.
2003
b
.
Probing the mechanism of a membrane transport protein with affinity inactivators
.
J. Biol. Chem.
278
:
10641
10648
.
Guan
,
L.
,
O.
Mirza
,
G.
Verner
,
S.
Iwata
, and
H.R.
Kaback
.
2007
.
Structural determination of wild-type lactose permease
.
104
:
15294
15298
.
Hariharan
,
P.
, and
L.
Guan
.
2014
.
Insights into the inhibitory mechanisms of the regulatory protein IIA(Glc) on melibiose permease activity
.
J. Biol. Chem.
289
:
33012
33019
.
Hariharan
,
P.
,
D.
Balasubramaniam
,
A.
Peterkofsky
,
H.R.
Kaback
, and
L.
Guan
.
2015
.
Thermodynamic mechanism for inhibition of lactose permease by the phosphotransferase protein IIAGlc
.
112
:
2407
2412
.
Hariharan
,
P.
,
M.
,
X.
Jiang
,
E.
Pardon
,
J.
Steyaert
,
H.R.
Kaback
, and
L.
Guan
.
2016
.
Thermodynamics of Nanobody Binding to Lactose Permease
.
Biochemistry.
55
:
5917
5926
.
Iancu
,
C.V.
,
J.
Zamoon
,
S.B.
Woo
,
A.
Aleshin
, and
J.Y.
Choe
.
2013
.
Crystal structure of a glucose/H+ symporter and its mechanism of action
.
110
:
17862
17867
.
Jardetzky
,
O.
1966
.
Simple allosteric model for membrane pumps
.
Nature.
211
:
969
970
.
Jiang
,
X.
,
I.
Smirnova
,
V.
Kasho
,
J.
Wu
,
K.
Hirata
,
M.
Ke
,
E.
Pardon
,
J.
Steyaert
,
N.
Yan
, and
H.R.
Kaback
.
2016
.
Crystal structure of a LacY-nanobody complex in a periplasmic-open conformation
.
113
:
12420
12425
.
Kaback
,
H.R.
1968
.
The role of the phosphoenolpyruvate-phosphotransferase system in the transport of sugars by isolated membrane preparations of Escherichia coli
.
J. Biol. Chem.
243
:
3711
3724
.
Kaback
,
H.R.
2015
.
A chemiosmotic mechanism of symport
.
112
:
1259
1264
.
Kaback
,
H.R.
,
M.
Sahin-Tóth
, and
A.B.
Weinglass
.
2001
.
The kamikaze approach to membrane transport
.
Nat. Rev. Mol. Cell Biol.
2
:
610
620
.
Kaback
,
H.R.
,
R.
Dunten
,
S.
Frillingos
,
P.
Venkatesan
,
I.
Kwaw
,
W.
Zhang
, and
N.
Ermolova
.
2007
.
Site-directed alkylation and the alternating access model for LacY
.
104
:
491
494
.
Kaback
,
H.R.
,
I.
Smirnova
,
V.
Kasho
,
Y.
Nie
, and
Y.
Zhou
.
2011
.
The alternating access transport mechanism in LacY
.
J. Membr. Biol.
239
:
85
93
.
Kaczorowski
,
G.J.
,
D.E.
Robertson
, and
H.R.
Kaback
.
1979
.
Mechanism of lactose translocation in membrane vesicles from Escherichia coli. 2. Effect of imposed delata psi, delta pH, and Delta mu H+
.
Biochemistry.
18
:
3697
3704
.
Kumar
,
H.
,
V.
Kasho
,
I.
Smirnova
,
J.S.
Finer-Moore
,
H.R.
Kaback
, and
R.M.
Stroud
.
2014
.
Structure of sugar-bound LacY
.
111
:
1784
1788
.
Kumar
,
H.
,
J.S.
Finer-Moore
,
H.R.
Kaback
, and
R.M.
Stroud
.
2015
.
Structure of LacY with an α-substituted galactoside: Connecting the binding site to the protonation site
.
112
:
9004
9009
.
Kumar
,
H.
,
J.S.
Finer-Moore
,
X.
Jiang
,
I.
Smirnova
,
V.
Kasho
,
E.
Pardon
,
J.
Steyaert
,
H.R.
Kaback
, and
R.M.
Stroud
.
2018
.
Crystal Structure of a ligand-bound LacY-Nanobody Complex
.
115
:
8769
8774
.
Mitchell
,
P.
1967
.
Translocations through natural membranes
.
Adv. Enzymol. Relat. Areas Mol. Biol.
29
:
33
87
.
Mitchell
,
P.
1968
.
Chemiosmotic coupling and energy transduction.
Glynn Research Ltd
,
Bodmin, UK
.
Müller-Hill
,
B.
1996
.
The lac Operon: A Short History of a Genetic Paradigm.
Walter de Gruyter
,
Berlin, NY
.
Newman
,
M.J.
,
D.L.
Foster
,
T.H.
Wilson
, and
H.R.
Kaback
.
1981
.
Purification and reconstitution of functional lactose carrier from Escherichia coli
.
J. Biol. Chem.
256
:
11804
11808
.
Nie
,
Y.
, and
H.R.
Kaback
.
2010
.
Sugar binding induces the same global conformational change in purified LacY as in the native bacterial membrane
.
107
:
9903
9908
.
Nie
,
Y.
,
N.
Ermolova
, and
H.R.
Kaback
.
2007
.
Site-directed alkylation of LacY: effect of the proton electrochemical gradient
.
J. Mol. Biol.
374
:
356
364
.
,
E.
,
D.
Zilberstein
, and
H.
Rottenberg
.
1976
.
The proton electrochemical gradient in Escherichia coli cells
.
Eur. J. Biochem.
63
:
533
541
.
Park
,
Y.H.
,
B.R.
Lee
,
Y.J.
Seok
, and
A.
Peterkofsky
.
2006
.
In vitro reconstitution of catabolite repression in Escherichia coli
.
J. Biol. Chem.
281
:
6448
6454
.
Postma
,
P.W.
,
J.W.
Lengeler
, and
G.R.
Jacobson
.
1993
.
Phosphoenolpyruvate:carbohydrate phosphotransferase systems of bacteria
.
Microbiol. Rev.
57
:
543
594
.
Ramos
,
S.
,
S.
Schuldiner
, and
H.R.
Kaback
.
1976
.
The electrochemical gradient of protons and its relationship to active transport in Escherichia coli membrane vesicles
.
73
:
1892
1896
.
Robertson
,
D.E.
,
G.J.
Kaczorowski
,
M.L.
Garcia
, and
H.R.
Kaback
.
1980
.
Active transport in membrane vesicles from Escherichia coli: the electrochemical proton gradient alters the distribution of the lac carrier between two different kinetic states
.
Biochemistry.
19
:
5692
5702
.
Sahin-Tóth
,
M.
, and
H.R.
Kaback
.
2001
.
Arg-302 facilitates deprotonation of Glu-325 in the transport mechanism of the lactose permease from Escherichiacoli
98
:
6068
6073
.
Sahin-Tóth
,
M.
,
M.C.
Lawrence
, and
H.R.
Kaback
.
1994
.
Properties of permease dimer, a fusion protein containing two lactose permease molecules from Escherichia coli
91
:
5421
5425
.
Sahin-Tóth
,
M.
,
K.M.
Akhoon
,
J.
Runner
, and
H.R.
Kaback
.
2000
.
Ligand recognition by the lactose permease of Escherichia coli: specificity and affinity are defined by distinct structural elements of galactopyranosides
Biochemistry.
39
:
5097
5103
.
Sahin-Tóth
,
M.
,
M.C.
Lawrence
,
T.
Nishio
, and
H.R.
Kaback
.
2001
.
The C-4 hydroxyl group of galactopyranosides is the major determinant for ligand recognition by the lactose permease of Escherichia coli
Biochemistry.
40
:
13015
13019
.
Smirnova
,
I.N.
,
V.
Kasho
, and
H.R.
Kaback
.
2008
.
Protonation and sugar binding to LacY
.
105
:
8896
8901
.
Smirnova
,
I.
,
V.
Kasho
,
J.
Sugihara
,
J.Y.
Choe
, and
H.R.
Kaback
.
2009
a
.
Residues in the H+ translocation site define the pKa for sugar binding to LacY
.
Biochemistry.
48
:
8852
8860
.
Smirnova
,
I.
,
V.
Kasho
,
J.
Sugihara
, and
H.R.
Kaback
.
2009
b
.
Probing of the rates of alternating access in LacY with Trp fluorescence
.
106
:
21561
21566
.
Smirnova
,
I.
,
V.
Kasho
, and
H.R.
Kaback
.
2011
a
.
Lactose permease and the alternating access mechanism
.
Biochemistry.
50
:
9684
9693
.
Smirnova
,
I.
,
V.
Kasho
,
J.
Sugihara
, and
H.R.
Kaback
.
2011
b
.
Opening the periplasmic cavity in lactose permease is the limiting step for sugar binding
.
108
:
15147
15151
.
Smirnova
,
I.
,
V.
Kasho
,
J.
Sugihara
, and
H.R.
Kaback
.
2013
.
Trp replacements for tightly interacting Gly-Gly pairs in LacY stabilize an outward-facing conformation
.
110
:
8876
8881
.
Smirnova
,
I.
,
V.
Kasho
,
X.
Jiang
,
E.
Pardon
,
J.
Steyaert
, and
H.R.
Kaback
.
2014
.
Outward-facing conformers of LacY stabilized by nanobodies
.
111
:
18548
18553
.
Smirnova
,
I.
,
V.
Kasho
,
X.
Jiang
,
E.
Pardon
,
J.
Steyaert
, and
H.R.
Kaback
.
2015
.
Transient conformers of LacY are trapped by nanobodies
.
112
:
13839
13844
.
Smirnova
,
I.
,
V.
Kasho
,
X.
Jiang
, and
H.R.
Kaback
.
2017
.
An Asymmetric Conformational Change in LacY
.
Biochemistry.
56
:
1943
1950
.
Smirnova
,
I.
,
V.
Kasho
,
X.
Jiang
,
H.M.
Chen
,
S.G.
Withers
, and
H.R.
Kaback
.
2018
.
Oversized galactosides as a probe for conformational dynamics in LacY
.
115
:
4146
4151
.
Sun
,
L.
,
X.
Zeng
,
C.
Yan
,
X.
Sun
,
X.
Gong
,
Y.
Rao
, and
N.
Yan
.
2012
.
Crystal structure of a bacterial homologue of glucose transporters GLUT1-4
.
Nature.
490
:
361
366
.
Vázquez-Ibar
,
J.L.
,
L.
Guan
,
M.
Svrakic
, and
H.R.
Kaback
.
2003
.
Exploiting luminescence spectroscopy to elucidate the interaction between sugar and a tryptophan residue in the lactose permease of Escherichia coli
100
:
12706
12711
.
Viitanen
,
P.
,
M.L.
Garcia
,
D.L.
Foster
,
G.J.
Kaczorowski
, and
H.R.
Kaback
.
1983
.
Mechanism of lactose translocation in proteoliposomes reconstituted with lac carrier protein purified from Escherichia coli. 2. Deuterium solvent isotope effects
.
Biochemistry.
22
:
2531
2536
.
Vogel
,
H.
,
J.K.
Wright
, and
F.
Jähnig
.
1985
.
The structure of the lactose permease derived from Raman spectroscopy and prediction methods
.
EMBO J.
4
:
3625
3631
.
Vogt
,
A.D.
,
N.
Pozzi
,
Z.
Chen
, and
E.
Di Cera
.
2014
.
Essential role of conformational selection in ligand binding
.
Biophys. Chem.
186
:
13
21
.
von Heijne
,
G.
1992
.
Membrane protein structure prediction. Hydrophobicity analysis and the positive-inside rule
.
J. Mol. Biol.
225
:
487
494
.
Weinglass
,
A.B.
,
I.N.
Smirnova
, and
H.R.
Kaback
.
2001
.
Engineering conformational flexibility in the lactose permease of Escherichia coli: use of glycine-scanning mutagenesis to rescue mutant Glu325-->Asp
.
Biochemistry.
40
:
769
776
.
Weinglass
,
A.B.
,
M.
Sondej
, and
H.R.
Kaback
.
2002
.
Manipulating conformational equilibria in the lactose permease of Escherichia coli
.
J. Mol. Biol.
315
:
561
571
.
Weinglass
,
A.B.
,
J.P.
Whitelegge
,
Y.
Hu
,
G.E.
Verner
,
K.F.
Faull
, and
H.R.
Kaback
.
2003
.
Elucidation of substrate binding interactions in a membrane transport protein by mass spectrometry
.
EMBO J.
22
:
1467
1477
.
Yousef
,
M.S.
, and
L.
Guan
.
2009
.
A 3D structure model of the melibiose permease of Escherichia coli represents a distinctive fold for Na+ symporters
.
106
:
15291
15296
.
Zen
,
K.H.
,
E.
McKenna
,
E.
Bibi
,
D.
Hardy
, and
H.R.
Kaback
.
1994
.
Expression of lactose permease in contiguous fragments as a probe for membrane-spanning domains
.
Biochemistry.
33
:
8198
8206
.
Zilberstein
,
D.
,
S.
Schuldiner
, and
E.


text:
# Roots of a Complex Number

Root of a complex number can be expressed in the standard form A + iB, where A and B are real.

In words we can say that any root of a complex number is a complex number

Let, z = x + iy be a complex number (x ≠ 0, y ≠ 0 are real) and n a positive integer. If the nth root of z be a then,

$$\sqrt[n]{z}$$ = a

⇒ $$\sqrt[n]{x + iy}$$ = a

⇒ x + iy = a$$^{n}$$

From the above equation we can clearly understand that

(i) a$$^{n}$$ is real when a is purely real quantity and

(ii) a$$^{n}$$ is either purely real  or purely imaginary quantity when a is purely imaginary quantity.

We already assumed that, x ≠ 0 and y ≠ 0.

Therefore, equation x + iy = a$$^{n}$$ is satisfied if and only if a is an imaginary number of the form A + iB where A ≠ 0and B ≠ 0 are real.

Therefore, any root of a complex number is a complex number.

Solved examples on roots of a complex number:

1. Find the square roots of -15 - 8i.

Solution:

Let $$\sqrt{-15 - 8i}$$ = x + iy. Then,

$$\sqrt{-15 - 8i}$$ = x + iy

⇒ -15 – 8i = (x + iy)$$^{2}$$

⇒ -15 – 8i = (x$$^{2}$$ - y$$^{2}$$) + 2ixy

⇒ -15 = x$$^{2}$$ - y$$^{2}$$ .................. (i)

and 2xy = -8 .................. (ii)

Now (x$$^{2}$$ + y$$^{2}$$)$$^{2}$$ = (x$$^{2}$$ - y$$^{2}$$)$$^{2}$$ + 4x$$^{2}$$y$$^{2}$$

⇒ (x$$^{2}$$ + y$$^{2}$$)$$^{2}$$ = (-15)$$^{2}$$ + 64 = 289

⇒ x$$^{2}$$ + y$$^{2}$$ = 17 ................... (iii) [x$$^{2}$$ + y$$^{2}$$ > 0]

On Solving (i) and (iii), we get

x$$^{2}$$ = 1 and y$$^{2}$$ = 16

⇒ x = ± 1 and y = ± 4.

From (ii), 2xy is negative. So, x and y are of opposite signs.

Therefore, x = 1 and y = -4 or, x = -1 and y = 4.

Hence, $$\sqrt{-15 - 8i}$$ = ± (1 - 4i).

2. Find the square root of i.

Solution:

Let √i = x + iy. Then,

√i = x + iy

⇒ i = (x + iy)$$^{2}$$

⇒ (x$$^{2}$$ - y$$^{2}$$) + 2ixy = 0 + i

⇒ x$$^{2}$$ - y$$^{2}$$ = 0 .......................... (i)

And 2xy = 1 ................................. (ii)

Now, (x$$^{2}$$ + y$$^{2}$$)$$^{2}$$ = (x$$^{2}$$ - y$$^{2}$$)$$^{2}$$ + 4x$$^{2}$$y$$^{2}$$

(x$$^{2}$$ + y$$^{2}$$)$$^{2}$$ = 0 + 1 = 1 ⇒ x$$^{2}$$ + y$$^{2}$$ = 1 ............................. (iii), [Since, x$$^{2}$$ + y$$^{2}$$ > 0]

Solving (i) and (iii), we get

x$$^{2}$$ = ½ and y$$^{2}$$ = ½

⇒ x = ±$$\frac{1}{√2}$$ and y = ±$$\frac{1}{√2}$$

From (ii), we find that 2xy is positive. So, x and y are of same sign.

Therefore, x = $$\frac{1}{√2}$$ and y = $$\frac{1}{√2}$$ or, x = -$$\frac{1}{√2}$$ and y = -$$\frac{1}{√2}$$

Hence, √i = ±($$\frac{1}{√2}$$ + $$\frac{1}{√2}$$i) = ±$$\frac{1}{√2}$$(1 + i)


text:
# Problem

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.

Example 1:

Input:m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
Explanation:

Example 2:

Input:m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12
Explanation:

Note:

1. Once you move the ball out of boundary, you cannot move it back.
2. The length and height of the grid is in range [1,50].
3. N is in range [0,50].

# Solution

Time complexity: O(m*n + N * m * n)

Space complexity: O(N*m*n) -> O(m*n)

C++

Recursion with memorization

no loops

# Related Problems

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode

## Be First to Comment

Mission News Theme by Compete Themes.


text:
Address 2918 Nancy Pl, Garden City, KS 67846 (620) 275-1977

# mean square error statistics Copeland, Kansas

Contents 1 Definition and basic properties 1.1 Predictor 1.2 Estimator 1.2.1 Proof of variance and bias relationship 2 Regression 3 Examples 3.1 Mean 3.2 Variance 3.3 Gaussian distribution 4 Interpretation 5 error as a measure of the spread of the y values about the predicted y value. more stack exchange communities company blog Stack Exchange Inbox Reputation and Badges sign up log in tour help Tour Start here for a quick overview of the site Help Center Detailed To do this, we use the root-mean-square error (r.m.s.

T Score vs. However, a biased estimator may have lower MSE; see estimator bias. Thus, argue that the graph of MSE is a parabola opening upward. 2. The fourth central moment is an upper bound for the square of variance, so that the least value for their ratio is one, therefore, the least value for the excess kurtosis

It does this by taking the distances from the points to the regression line (these distances are the "errors") and squaring them. A symmetric, unimodal distribution. The difference occurs because of randomness or because the estimator doesn't account for information that could produce a more accurate estimate.[1] The MSE is a measure of the quality of an so that ( n − 1 ) S n − 1 2 σ 2 ∼ χ n − 1 2 {\displaystyle {\frac {(n-1)S_{n-1}^{2}}{\sigma ^{2}}}\sim \chi _{n-1}^{2}} .

To construct the r.m.s. New York: Springer. Since an MSE is an expectation, it is not technically a random variable. In statistics, the mean squared error (MSE) or mean squared deviation (MSD) of an estimator (of a procedure for estimating an unobserved quantity) measures the average of the squares of the

It tells us how much smaller the r.m.s error will be than the SD. Dividing the MS (term) by the MSE gives F, which follows the F-distribution with degrees of freedom for the term and degrees of freedom for error. Addison-Wesley. ^ Berger, James O. (1985). "2.4.2 Certain Standard Loss Functions". Thanks for the attention.

Then work as in the normal distribution, converting to standard units and eventually using the table on page 105 of the appendix if necessary. However, you are right about personal preferences, so feel free to roll back with apologies. In order to examine a mean squared error, you need a target of estimation or prediction, and a predictor or estimator that is a function of the data. Find a Critical Value 7.

Thus, the best measure of the center, relative to this measure of error, is the value of t that minimizes MSE. 1. The variation within the samples is represented by the mean square of the error. This is a subtlety, but for many experiments, n is large aso that the difference is negligible. Mean squared error is the negative of the expected value of one specific utility function, the quadratic utility function, which may not be the appropriate utility function to use under a

The treatment mean square is obtained by dividing the treatment sum of squares by the degrees of freedom. Vernier Software & Technology Caliper Logo Vernier Software & Technology 13979 SW Millikan Way Beaverton, OR 97005 Phone1-888-837-6437 Fax503-277-2440 [email protected] Resources Next Generation Science Standards Standards Correlations AP Correlations IB Correlations asked 1 year ago viewed 9244 times active 1 year ago 11 votes · comment · stats Related 4Variance-covariance matrix of the errors in linear regression0Calculate the error variance in a Compute the Eulerian number I cannot figure out how to go about syncing up a clock frequency to a microcontroller Schiphol international flight; online check in, deadlines and arriving Red balls

H., Principles and Procedures of Statistics with Special Reference to the Biological Sciences., McGraw Hill, 1960, page 288. ^ Mood, A.; Graybill, F.; Boes, D. (1974). Browse other questions tagged residuals mse or ask your own question. Mean Square Error In a sense, any measure of the center of a distribution should be associated with some measure of error. So if that's the only difference, why not refer to them as both the variance, but with different degrees of freedom?

Statisticshowto.com Apply for $2000 in Scholarship Money As part of our commitment to education, we're giving away$2000 in scholarships to StatisticsHowTo.com visitors. Compute the min, max, mean and standard deviation by hand, and verify that you get the same results as the applet. Tech Info LibraryWhat are Mean Squared Error and Root Mean SquaredError?About this FAQCreated Oct 15, 2001Updated Oct 18, 2011Article #1014Search FAQsProduct Support FAQsThe Mean Squared Error (MSE) is a measure of Addison-Wesley. ^ Berger, James O. (1985). "2.4.2 Certain Standard Loss Functions".

Estimator The MSE of an estimator θ ^ {\displaystyle {\hat {\theta }}} with respect to an unknown parameter θ {\displaystyle \theta } is defined as MSE  ( θ ^ ) However, a biased estimator may have lower MSE; see estimator bias. Suppose the sample units were chosen with replacement. ISBN0-387-98502-6.

Step 6: Find the mean squared error: 30.4 / 5 = 6.08. Schiphol international flight; online check in, deadlines and arriving What is a TV news story called? errors of the predicted values. error will be 0.


text:
Article Content

The Raven paradox is a paradox proposed by the German logician Carl Hempel[?] in the 1940s to illustrate a problem where inductive logic violates intuition.

When numerous people over thousands of years observe something like the law of gravity, we tend to believe that it is true with very high probability. This type of reasoning could be summarized by the principle of induction:

• If an instance X is observed that is consistent with theory T, then the probability that T is true increases
Hempel gives an example of the principle of induction. The theory is that all ravens are black. We go out and examine a million ravens, and observe that they are all black. After each observation, our belief in the theory "all ravens are black" will rise slightly. The principle of induction looks reasonable here.

Now comes the problem. The statement "all ravens are black" is logically equivalent to the statement "all non-black-things are non-ravens". If we observe a red apple, that is consistent with that statement. A red apple is a non-black-thing, and when we examine it, we observe that it is a non-raven. So by the principle of induction, observing a red apple should increase our belief that all ravens are black! This problem has been humorously summarized as:

     I never saw a purple cow
But if I were to see one
Would the probability ravens are black
Have a better chance to be one?

Philosophers have offered many solutions to this violation of intuition. The American logician Nelson Goodman[?] has suggested adding restrictions to our reasoning, such as never considering an instance as support for "All P are Q" if it would also support "No P are Q".

Other philosophers have questioned the "principle of equivalence". Perhaps the red apple should increase our belief in the theory "all non-black-things are non-ravens", without increasing our belief that "all ravens are black". That suggestion has been questioned, though, on the grounds that you can't have a different degree of belief in two different statements, if you know they are either both true or both false.

Some philosophers have argued that it's only our intuition that is flawed. Observing a red apple really does increase the probability that all ravens are black! After all, if someone gave you all the non-black things in the universe, and you noticed that there were no ravens in the collection, then you could indeed conclude that all ravens are black. The example only seems counterintuitive because the set of non-black-things is far, far larger than the set of ravens. Thus observing one more non-black-thing which is not a raven should make a tiny difference to our degree of belief in the proposition compared to the difference made by observing one more raven which is black.

There is an alternative to the "principle of induction" described above.

Let X represent an instance of theory T, and I represent all of our background information.
Let $\Pr(\bullet | \circ)$ represent the probability of $\bullet$ given $\circ$. Then,

$\Pr(T|XI) = \frac{\Pr(T|I) \cdot \Pr(X|TI)}{\Pr(X|I)}$

This principle is known as "Bayes' theorem". It is foundational to the mathematics of probability and statistics. When scientists publish analyses of experimental results and calculate that they are "statistically significant", they are implicitly using this principle. It could be argued that this principle is a better representation of how scientists actually reason than the original "principle of induction" described above.

Using this principle, the paradox does not arise. If you ask someone to select an apple at random and show it to you, then the probability of seeing a red apple is independent of the colors of ravens. The numerator will equal the denominator, the ratio will equal one, and the probability will remain unchanged. Seeing a red apple will not affect your belief about whether all ravens are black.

If you ask someone to select a non-black-thing at random, and they show you a red apple, then the numerator will exceed the denominator by an extremely small amount. Seeing the red apple will only slightly increase your belief that all ravens are black. You'll have to see almost every non-black-thing in the universe (and see they're all non-ravens) before your belief in "all ravens are black" increases appreciably. In both cases, the result agrees with intuition.

References:

• Hempel, Carl. G. A Purely Syntactical Definition of Confirmation. J. Symb. Logic 8, 122-143, 1943.
• Hempel, Carl. G. Studies in Logic and Confirmation. Mind 54, 1-26, 1945.
• Hempel, Carl. G. Studies in Logic and Confirmation. II. Mind 54, 97-121, 1945.
• Hempel, Carl G, Studies in the Logic of Confirmation. In Marguerite H. Foster and Michael L. Martin (http://www.bu.edu/philo/faculty/martin), eds. Probability, Confirmation, and Simplicity. New York: Odyssey Press, 1966. Pp 145-183
• Falletta, Nicholas. The Paradoxicon: a Collection of Contradictory Challenges, Problematical Puzzles, and Impossible Illustrations. 1983. Pp 126-131. ISBN 0385179324

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 Ludvika ... Gagnef  |  Hedemora  |  Leksand  |  LudvikaMalung  |  Mora  |  Orsa  |  Rättvik  |  ...


text:
# Locus of centre of ellipse sliding along coordinate axes?

An ellipse of major and minor axes of length √3 and 1 respectively, slides along the co-ordinate axes and always remains confined in the first quadrant. The locus of the centre of the ellipse will be the arc of a circle the length of which is:

The answer given is 0.52. In the solution it is given that locus of centre is $x^2+y^2=1$ and difference in parametric angles at two extreme positions is π/6. (This is because the two extreme positions are $tan^{-1} (π/6)$ and $tan^{-1} (π/3)$). I am actually having difficulty understanding why locus of centre is $x^2+y^2=1$. I understand that at the two extreme positions(major axis parallel to x axis and y axis respectively) the distance of the centre from the origin is 1 ($1^2 = (√3/2)^2 + (1/2)^2$), but what about the other positions in between these two? I only have an intuition about the fact that the distance of centre from origin remains 1 as ellipse slides, and would welcome some clearer guidance.

• See the animation of another answer here. May 23, 2018 at 14:01

You can look at it in another way. We know that for an ellipse, if two mutually perpendicular tangents are drawn, then the intersection of these tangents lies on director circle $x^2+y^2=a^2+b^2 = 1$. This equation is valid when $C(0,0)$ is centre of ellipse.
Now here, the origin of coordinates $O(0,0)$ is fixed, but the centre $C$ of ellipse is moving relative to it, so it will also lie on same curve, that is $x^2+y^2 = 1$.


text:
# Variants of Szemeredi's regularity lemma

I've noticed that the name 'Szemeredi's regularity lemma' is used for several closely related yet different statements about graphs.

Specifically, I'm interested in the distinction between two of them:

Variant 1 Given $\varepsilon>0$ and $l>0$, there exists an $L=L(\varepsilon,l)$ such that any graph $G$ can be partitioned into sets $V_1,\ldots,V_k$ of as-equal-as-you-can-get sizes for some $l\leq k\leq L$, such that at most $\varepsilon {k\choose 2}$ of the pairs $(V_i,V_j)$ are not $\varepsilon$-regular.

Variant 2 As above, except that we have an additional "junk" part $V_0$ of size $\leq \varepsilon |G|$, and the $V_i$ have equal sizes. In this case we consider only regular pairs $(V_i,V_j)$ for $1\leq i<j\leq k$.

Can anybody with more experience of using the lemma weigh in? Specifically, under what parameters are these two equivalent, and what are the benefits of using one over the other? Cheers!

• This paper of Fox and Lovász discusses a few different versions of the regularity lemma, and why it is preferable to state the lemma one way rather than another: arxiv.org/abs/1403.1768 Jan 16 '16 at 21:18
• I'll just quote that paper: "A vertex partition of a graph is equitable if any two parts differ in size by at most one. In the statement of the regularity lemma, it is often added that the vertex partition is equitable. There are several good reasons not to add this requirement to the regularity lemma. First, our main result, which gives a lower bound on M(epsilon) whose height is on the same order as the upper bound, does not need this requirement. Second, the proof of the upper bound is cleaner without it.... Jan 17 '16 at 0:24
• ... Finally, it is further shown in [6] that whether or not an equitable partition is required has a negligible effect on M(epsilon)." [6] cites J Fox, A. Grinshpun, L. M. Lovász, and Y. Zhao, On regularity lemmas and their applications, In preparation. Jan 17 '16 at 0:25


text:
# Solutions to The Rising Sea (Vakil)

### Section 2.1: Motivating Example: The Sheaf of Differentiable Functions

###### Exercise 2.1.A:
Show that this is the only maximal ideal of $$\OO_p$$. (Hint: Show that every element of $$\OO_p \backslash \mm_p$$ is invertible.)

###### Exercise 2.1.B:
Notice that $$\mm_p / \mm_p^2$$ is a module over $$\OO_p / \mm_p \cong \mathbb{R}$$, i.e., it is a real vector space. It turns out to be naturally (whatever that means) the cotangent space to the smooth manifold at $$p$$. This insight will prove handy later, when we define tangent and cotangent spaces of schemes. Prove this. (Rhetorical question for experts: what goes wrong if the sheaf of continuous functions is substituted for the sheaf of differentiable functions?)

### Section 2.2: Definition of a Sheaf and Presheaf

###### Exercise 2.2.A:
Given any topological space, we have a "category of open sets" (Example 1.2.9), where the objects are the open sets and the morphisms are inclusions. Verify that the data of a presheaf is precisely the data of a contravariant functor from the category of open sets of $$X$$ to the category of sets. (This interpretation is surprisingly useful.)

###### Exercise 2.2.B:
Show that the following are presheaves on $$\mathbb{C}$$ (with the classical topology), but not sheaves: (a) bounded functions, (b) holomorphic functions admitting a holomorphic square root.

###### Exercise 2.2.C:
The identity and gluability axioms may be interpreted as saying that $$\FF ( \bigcup_{i \in I} U_i )$$ is a certain limit. What is this limit?

###### Exercise 2.2.D:
1. Verify that the examples of §2.1 are indeed sheaves of differentiable function, or continuous functions, or smooth functions, or of functions on a manifold of $$\mathbb{R}^n$$)
2. Show that real-valued continuous functions on (open sets of) a topological space $$X$$ form a sheaf.

###### Exercise 2.2.E:
Now let $$\FF(U)$$ be the maps to $$S$$ that are locally constant, i.e., for any point $$p \in U$$, there is an open neighborhood of $$p$$ where the function is constant. Show that this is a sheaf. (A better description is this: endow $$S$$ with the discrete topology, and let $$\FF(U)$$ be the continuous maps $$U \to S$$.) This is called the constant sheaf (associated to $$S$$); do not confuse it with the constant presheaf. We denote this sheaf $$\underline{S}$$.

###### Exercise 2.2.F:
Suppose $$Y$$ is a topological space. Show that "continuous maps to $$Y$$" form a sheaf of sets on $$X$$. More precisely, to each open set $$U$$ of $$X$$, we associate the set of continuous maps of $$U$$ to $$Y$$. Show that this forms a sheaf. (Exercise 2.2.D(b), with $$Y = \mathbb{R}$$, and Exercise 2.2.E, with $$Y = S$$ with the discrete topology are both special cases.)

###### Exercise 2.2.G:
This is a fancier version of the previous exercise.
1. (sheaf of sections of a map) Suppose we are given a continuous map $$\mu : Y \to X$$. Show that "sections of $$\mu$$" form a sheaf. More precisely, to each open set $$U$$ of $$X$$, associate the set of continuous maps $$s : U \to Y$$ such that $$\mu \circ s = id\vert_U$$. Show that this forms a sheaf. (For those who have heard of vector bundles, these are a good example.) This is motivation for the phrase "section of a sheaf".
2. (This exercise is for those who know what a topological group is. If you don't know what a topological group is, you might be able to guess.) Suppose that $$Y$$ is a topological group. Show that continuous maps to $$Y$$ form a sheaf of $$groups.$$

###### Exercise 2.2.H:
Suppose $$\pi : X \to Y$$ is a continuous map, and $$\FF$$ is a presheaf on $$X$$. Then define $$\pi_* \FF$$ by $$\pi_*\FF (V) := \FF( \pi^{-1}(V) )$$, where $$V$$ is an open subset of $$Y$$. Show that $$\pi_* \FF$$ is a presheaf on $$Y$$, and is a sheaf if $$\FF$$ is. This is called the $$\textbf{pushforward}$$ or $$\textbf{direct}\ \textbf{image}$$ of $$\FF$$. More precisely, $$\pi_* \FF$$ is called the $$\textbf{pushforward}\ \textbf{of}\ \FF \ \textbf{by}\ \pi$$.

###### Exercise 2.2.I:
Suppose $$\pi : X \to Y$$ is a continuous map, and $$\FF$$ is a sheaf of sets (or rings or $$A$$-modules) on $$X$$. If $$\pi(p) = q$$, describe the natural morphism of stalks $$(\pi_* \FF)_q \to \FF_p$$. (You can use the explicit definition of stalk using representatives, §2.2.4, or the universal property, §2.2.5. If you prefer one way, you should try the other).

###### Exercise 2.2.J:
If $$( X, \OO_X )$$ is a ringed space and $$\FF$$ is an $$\OO_X$$-module, describe how for each $$p \in X$$, $$\FF_p$$ is an $$\OO_{X, p}$$-module.

### Section 2.3: Morphisms of Presheaves and Sheaves

###### Exercise 2.3.A:
If $$\phi : \FF \to \GG$$ is a morphism of presheaves on $$X$$ and $$p \in X$$, describe an induced morphism of stalks $$\phi_p : \FF_p \to \GG_p$$. Translation: taking the stalk at $$p$$ induces a functor $$\Set_X \to \Set$$. (Your proof will extend in obvious ways. For example, if $$\phi$$ is a morphism of $$\OO_X$$-modules, then $$\phi_p$$ is a map of $$\OO_{X,p}$$-modules. )

###### Exercise 2.3.B:
Suppose $$\pi : X \to Y$$ is a continuous map of topological spaces (i.e. a morphism in the category of topological spaces). Show that the pushforward gives a functor $$\pi_* : \Set_X \to \Set_Y$$. Here $$\Set$$ can be replaced by other categories. (Watch out for some possible confusion: a presheaf is a functor, and presheaves form a category. It may be best to forget that presheaves are a functor for now.)

###### Exercise 2.3.C:
Suppose $$\FF$$ and $$\GG$$ are two sheaves of sets on $$X$$. (In fact, it will suffice that $$\FF$$ is a presheaf.) Let $$\Hom (\FF , \GG )$$ be the collection of data $$\Hom(\FF, \GG)(U) := \Mor (\FF\vert_U, \GG\vert_U )$$ (Recall the notation $$\FF\vert_U$$, the restriction of the sheaf to the open set $$U$$, Example 2.2.8.) Show that this is a sheaf of sets on $$X$$. (To avoid a common confusion: the right side does not say $$\Mor (\FF(U),\GG(U))$$.) This sheaf is called “sheaf Hom”. (Strictly speaking, we should reserve Hom for when we are in an additive category, so this should possibly be called “sheaf Mor”. But the terminology “sheaf Hom” is too established to uproot.) It will be clear from your construction that, like Hom, Hom is a contravariant functor in its first argument and a covariant func- tor in its second argument.

###### Exercise 2.3.D:
1. If $$\FF$$ is a sheaf of sets on $$X$$, then show that $$\Hom(\{p\},\FF) \cong \FF$$, where $$\{p\}$$ is the constant sheaf associated to the one element set $$\{p\}$$.
2. If $$\FF$$ is a sheaf of abelian groups on $$X$$, then show that $$\Hom_{Ab_X} (\underline{\Z}, \FF ) \cong \FF$$ (an isomorphism of sheaves of abelian groups).
3. If $$\FF$$ is an $$\OO_X$$-module, then show that $$\Hom_{\Mod{\OO_X}} (\OO_X, f\FF) \cong \FF$$ (an isomorphism of $$\OO_X$$-modules).
A key idea in (b) and (c) is that 1 “generates” (in some sense) $$\Z$$ (in (b)) and $$\OO_X$$ (in (c)).

###### Exercise 2.3.E:
Show that $$\ker_{\textrm{pre}} \phi$$ is a presheaf. (Hint: if $$U \hookrightarrow V$$, define the restriction maps by chasing the following diagram: $$\require{amscd} \begin{CD} 0 @>>> \ker_{\textrm{pre}} \phi (V) @>>> \FF(V) @>>> \GG(V) \\ @. @VV{\exists !}V @VV{\res{V}{U} }V @VV{ \res{V}{U} }V \\ 0 @>>> \ker_{\textrm{pre}} \phi (U) @>>> \FF(U) @>>> \GG(U) \end{CD}$$

###### Exercise 2.3.F:
Show that the presheaf cokernel satisfies the universal property of cokernels (Definition 1.6.3) in the category of presheaves.

###### Exercise 2.3.G:
Show (or observe) that for a topological space $$X$$ with open set $$U$$, $$\FF \mapsto \FF(U)$$ gives a functor from presheaves of abelian groups on $$X$$, $$Ab_X^{\textrm{pre}}$$ to abelian groups, $$Ab$$. Then show that this functor is exact.

###### Exercise 2.3.H:
Show that a sequence of presheaves $$0 \to \FF_1 \to \FF_2 \to \dots \to \FF_n \to 0$$ is exact if and only if $$0 \to \FF_1(U) \to \FF_2(U) \to \dots \to \FF_n(U) \to 0$$ is exact for all $$U$$.

###### Exercise 2.3.I:
Suppose that $$\phi : \FF \to \GG$$ is a morphism of sheaves. Show that the presheaf kernel $$\ker_{\textrm{pre}} \phi$$ is in fact a sheaf. Show that it satisfies the universal property of kernels (Definition 1.6.3). (Hint: the second question follows immediately from the fact that $$\ker_{\textrm{pre}} \phi$$ satisfies the universal property in the category of presheaves.)

###### Exercise 2.3.J:
Let $$X$$ be $$\C$$ with the classical topology, let $$\underline{\Z}$$ be the constant sheaf on $$X$$ associated to $$\Z$$, $$\OO_X$$ the sheaf of holomorphic functions, and $$\FF$$ the presheaf of functions admitting a holomorphic logarithm. Describe an exact sequence of presheaves on $$X$$: $$0 \to \underline{\Z } \to \OO_X \to \FF \to 0$$ where $$\underline{\Z} \to \OO_X$$ is the natural inclusion and $$\OO_X \to \FF$$ is given by $$f \mapsto \textrm{exp}(2\pi i f)$$. (Be sure to verify exactness.) Show that $$\FF$$ is not a sheaf. (Hint: $$\FF$$ does not satisfy the gluability axiom. The problem is that there are functions that don’t have a logarithm but locally have a logarithm.) This will come up again in Example 2.4.10.

### Section 2.4: Properties Determined at the Level of Stalks, and Sheafification

###### Exercise 2.4.A:
Prove that a section of a sheaf of sets is determined by its germs, i.e., the natural map $$\FF(U) \to \prod_{p \in U} \FF_p$$ is injective. Hint 1: you won’t use the gluability axiom, so this is true for separated presheaves. Hint 2: it is false for presheaves in general, see Exercise 2.4.F, so you will use the identity axiom. (Your proof will also apply to sheaves of groups, rings, etc. — to categories of “sets with additional structure”. The same is true of many exercises in this section.)

###### Exercise 2.4.B:
Show that $$\textrm{Supp}(s)$$ is a closed subset of $$X$$.

###### Exercise 2.4.C:
Prove that any choice of compatible germs for a sheaf of sets $$\FF$$ over $$U$$ is the image of a section of $$\FF$$ over $$U$$. (Hint: you will use gluability.)

###### Exercise 2.4.D:
If $$\phi_1$$ and $$\phi_2$$ are morphisms from a presheaf of sets $$\FF$$ to a sheaf of sets $$\GG$$ that induce the same maps on each stalk, show that $$\phi_1 = \phi_2$$. Hint: consider the following diagram. $$\require{amscd} \begin{CD} \FF(U) @>>> \GG(U) \\ @VVV @VVV \\ \prod_{p \in U} \FF_p @>>> \prod_{p \in U} \GG_p \end{CD}$$

###### Exercise 2.4.E:
Show that a morphism of sheaves of sets is an isomorphism if and only if it induces an isomorphism of all stalks. Hint: Use (2.4.4.1). Once you have injectivity, show surjectivity, perhaps using Exercise 2.4.C, or gluability in some other way; this is more subtle.

###### Exercise 2.4.F:
1. Show that Exercise 2.4.A is false for general presheaves.
2. Show that Exercise 2.4.D is false for general presheaves.
3. Show that Exercise 2.4.E is false for general presheaves.
(General hint for finding counterexamples of this sort: consider a 2-point space with the discrete topology.)

###### Exercise 2.4.G:
Show that sheafification is unique up to unique isomorphism, assuming it exists. Show that if $$\FF$$ is a sheaf, then the sheafification is $$\textrm{id} : \FF \to \FF$$. (This should be second nature by now.)

###### Exercise 2.4.H:
Assume for now that sheafification exists. Use the universal property to show that for any morphism of presheaves $$\phi : \FF \to \GG$$, we get a natural induced morphism of sheaves $$\phi_{sh} : \FF^{sh} \to \GG^{sh}$$. Show that sheafification is a functor from presheaves on $$X$$ to sheaves on $$X$$.

###### Exercise 2.4.I:
Show that $$\FF^{sh}$$ (using the tautological restriction maps) forms a sheaf.

###### Exercise 2.4.J:
Describe a natural map of presheaves $$\textrm{sh} : \FF \to \FF^{sh}$$.

###### Exercise 2.4.K:
Show that the map sh satisfies the universal property of sheafification (Definition 2.4.6). (This is easier than you might fear.)

###### Exercise 2.4.L:
Show that the sheafification functor is left-adjoint to the forgetful functor from sheaves on $$X$$ to presheaves on $$X$$. This is not difficult — it is largely a restatement of the universal property. But it lets you use results from §1.6.12, and can "explain" why you don’t need to sheafify when taking kernel (why the presheaf kernel is already the sheaf kernel), and why you need to sheafify when taking cokernel and (soon, in Exercise 2.6.J) $$\otimes$$.

###### Exercise 2.4.M:
Show $$\FF \to \FF^{sh}$$ induces an isomorphism of stalks. (Possible hint: Use the concrete description of the stalks. Another possibility once you read Remark 2.7.3: judicious use of adjoints.)

###### Exercise 2.4.N:
Suppose $$\phi : \FF \to \GG$$ is a morphism of sheaves of sets on a topological space $$X$$. Show that the following are equivalent:
1. $$\phi$$ is a monomorphism in the category of sheaves.
2. $$\phi$$ is injective on the level of stalks: $$\phi_p : \FF_p \to \GG_p$$ is injective for all $$p \in X$$.
3. $$\phi$$ is injective on the level of open sets: $$\phi(U) : \FF(U) \to \GG(U)$$ is injective for all open $$U \subset X$$.
(Possible hints: for (b) implies (a), recall that morphisms are determined by stalks, Exercise 2.4.D. For (a) implies (c), use the "indicator sheaf" with one section over every open set contained in $$U$$, and no section over any other open set.) If these conditions hold, we say that $$\FF$$ is a subsheaf of $$\GG$$ (where the "inclusion" $$\phi$$ is sometimes left implicit).

###### Exercise 2.4.O:
Continuing the notation of the previous exercise, show that the following are equivalent.
1. $$\phi$$ is an epimorphism in the category of sheaves
2. $$\phi$$ is surjective on the level of stalks: $$\phi_p : \FF_p \to \GG_p$$ is surjective for all $$p \in X$$

###### Exercise 2.4.P:
Show that $$\textrm{exp} : \OO_X \to \OO^*_X$$ describes $$\OO_X^*$$ as a quotient sheaf of $$\OO_X$$. Find an open set on which this map is not surjective.

### Section 2.5: Recovering Sheaves from a "Sheaf on a Base"

###### Exercise 2.5.A:
Make this precise. How can you recover a sheaf $$\FF$$ from this partial information?

###### Exercise 2.5.B:
Verify that $$F(B) \to \FF(B)$$ is an isomorphism, likely by showing that it is injective and surjective (or else by describing the inverse map and verifying that it is indeed inverse). Possible hint: elements of $$\FF(B)$$ are determined by stalks, as are elements of $$F(B)$$.

###### Exercise 2.5.C:
Suppose $$\{ B_i \}$$ is a base for the topology of $$X$$. A morphism $$F \to G$$ of sheaves on the base is a collection of maps $$F(B_k) \to G(B_k)$$ such that the diagram $$\require{amscd} \begin{CD} F(B_i) @>>> G(B_i) \\ @V{\res{B_i}{B_j}}VV @VV{\res{B_i}{B_j}}V \\ F(B_j) @>>> G(B_j) \end{CD}$$ commutes for all $$B_j \hookrightarrow B_i$$.
1. Verify that a morphism of sheaves is determined by the induced morphism of sheaves on the base.
2. Show that a morphism of sheaves on the base gives a morphism of the induced sheaves. (Possible hint: compatible stalks.)

###### Exercise 2.5.D:
Suppose $$X = \bigcup U_i$$ is an open cover of $$X$$, and we have sheaves $$\FF_i$$ on $$U_i$$ along with isomorphisms $$\phi_{ij} : \FF_i\vert_{U_i \cap U_j} → \FF_j\vert_{ U_i \cap U_j}$$ (with $$\phi_{ii}$$ the identity) that agree on triple overlaps, i.e., $$\phi_{jk} \circ \phi_{ij} = \phi_{ik}$$ on $$U_i \cap U_j \cap Uk$$ (this is called the cocycle condition, for reasons we ignore). Show that these sheaves can be glued together into a sheaf $$\FF$$ on $$X$$ (unique up to unique isomorphism), such that $$\FF_i \cong \FF\vert_{U_i}$$, and the isomorphisms over $$U_i \cap U_j$$ are the obvious ones. (Thus we can "glue sheaves together", using limited patching information.) Warning: we are not assuming this is a finite cover, so you cannot use induction. For this reason this exercise can be perplexing. (You can use the ideas of this section to solve this problem, but you don’t necessarily need to. Hint: As the base, take those open sets contained in some $$U_i$$. Small observation: the hypothesis on $$\phi_{ii}$$ is extraneous, as it follows from the cocycle condition.)

###### Exercise 2.5.E:
Suppose a morphism of sheaves $$\FF \to \GG$$ on a base $$\{ B_i\}$$ is surjective for all $$B_i$$ (i.e., $$\FF(B_i) \to \GG(B_i)$$ is surjective for all $$i$$). Show that the corresponding morphism of sheaves (not on the base) is surjective (or more precisely: an epimorphism). The converse is not true, unlike the case for injectivity. This gives a useful sufficient criterion for “surjectivity”: a morphism of sheaves is an epimorphism (“surjective”) if it is surjective for sections on a base. You may enjoy trying this out with Example 2.4.10 (dealing with holomorphic functions in the classical topology on $$X = \C$$), showing that the exponential map $$\textrm{exp}: \OO_X → \OO_X^*$$ is surjective, using the base of contractible open sets.

### Section 2.6: Sheaves of Abelian Groups and $$\OO_X$$-Modules form Abelian Categories

###### Exercise 2.6.A:
Show that the stalk of the kernel is the kernel of the stalks: for all $$p \in X$$, there is a natural isomorphism $$( \ker (\FF \to \GG ) )_p \cong \ker (\FF_p \to \GG_p)$$

###### Exercise 2.6.B:
Show that the stalk of the cokernel is naturally isomorphic to the cokernel of the stalk.

###### Exercise 2.6.C:
Suppose $$\phi : \FF \to \GG$$ is a morphism of sheaves of abelian groups. Show that the image sheaf $$\im \phi$$ is the sheafification of the image presheaf. (You must use the definition of image in an abelian category. In fact, this gives the accepted definition of image sheaf for a morphism of sheaves of sets.) Show that the stalk of the image is the image of the stalk.

###### Exercise 2.6.D:
Show that taking the stalk of a sheaf of abelian groups is an exact functor. More precisely, if $$X$$ is a topological space and $$p \in X$$ is a point, show that taking the stalk at $$p$$ defines an exact functor $$Ab_X \to Ab$$.

###### Exercise 2.6.E:
Check that the exponential exact sequence (2.4.10.1) is exact.

###### Exercise 2.6.F:
Suppose $$U \subset X$$ is an open set, $$0 \to \FF \to \FF \to \mathscr{H}$$ is an exact sequence of sheaves of abelian groups. Show that $$\require{amscd} \begin{CD} 0 @>>> \FF(U) @>>> \GG(U) @>>> \mathscr{H}(U) \end{CD}$$ is exact. (You should do this "by hand", even if you realize there is a very fast proof using the left-exactness of the "forgetful" right adjoint to the sheafification functor.) Show that the section functor need not be exact: show that if $$0 \to \FF \to \GG \to \mathscr{H} \to 0$$ is an exact sequence of abelian groups, then $$\require{amscd} \begin{CD} 0 @>>> \FF(U) @>>> \GG(U) @>>> \mathscr{H}(U) @>>> 0 \end{CD}$$ need not be exact. (Hint: the exponential exact sequence (2.4.10.1). But feel free to make up a different example.)

###### Exercise 2.6.G:
Suppose $$0 \to \FF \to \GG \to \mathscr{H} \to 0$$ is an exact sequence of sheaves of abelian groups on $$X$$. If $$\pi : X \to Y$$ is a continuous map, show that $$\require{amscd} \begin{CD} 0 @>>> \pi_* \FF @>>> \pi_* \GG @>>> \pi_*\mathscr{H} \end{CD}$$ is exact. (The previous exercise, dealing with the left-exactness of the global section functor can be interpreted as a special case of this, in the case where $$Y$$ is a point.)

###### Exercise 2.6.H:
Suppose $$\FF$$ is a sheaf of abelian groups on a topological space $$X$$. Show that $$\mathcal{Hom}(\FF, \cdot)$$ is a left-exact covariant functor $$Ab_X \to Ab$$. Show that $$\mathcal{Hom}(\cdot, \FF)$$ is a left-exact contravariant functor $$Ab_X \to Ab$$.

###### Exercise 2.6.I:
Show that if $$( X, \OO_X )$$ is a ringed space, then $$\OO_X$$ form an abelian category. (There is a fair bit to check, but there aren’t many new ideas.)

###### Exercise 2.6.J:
1. Suppose $$\OO_X$$ is a sheaf of rings on $$X$$. Define (categorically) what we should mean by tensor product of two $$\OO_X$$-modules. Give an explicit construction, and show that it satisfies your categorical definition. Hint: take the "presheaf tensor product" — which needs to be defined — and sheafify. Note: $$\otimes_{\OO_X}$$ is often written $$\otimes$$ when the subscript is clear from the context. (An example showing sheafification is necessary will arise in Example 14.1.1.)
2. Show that the tensor product of stalks is the stalk of the tensor product. (If you can show this, you may be able to make sense of the phrase "colimits commute with tensor products".)

### Section 2.7: The Inverse Image Sheaf

###### Exercise 2.7.A:
Show that this defines a presheaf on $$X$$. Show that it needn’t form a sheaf. (Hint: map 2 points to 1 point.)

###### Exercise 2.7.B:
If $$\pi : X \to Y$$ is a continuous map, and $$\FF$$ is a sheaf on $$X$$ and $$\GG$$ is a sheaf on $$Y$$, describe a bijection $$\Mor_X( \pi^{-1} \GG, \FF ) \leftrightarrow \Mor_Y( \GG, \pi_* \FF )$$ Observe that your bijection is "natural" in the sense of the definition of adjoints (i.e., functorial in both $$\FF$$ and $$\GG$$ ). Thus Construction 2.7.2 satisfies the universal property of Definition 2.7.1. Possible hint: Show that both sides agree with the following third construction, which we denote $$\Mor_{YX} (\GG , \FF )$$. A collection of maps $$\phi_{VU} : \GG(V) → \FF(U)$$ (as $$U$$ runs through all open sets of $$X$$, and $$V$$ runs through all open sets of $$Y$$ containing $$\pi(U)$$) is said to be compatible if for all $$U' \subset U \subset X$$ and all open $$V' \subset V \subset Y$$ with $$\pi(U) \subset V$$, $$\pi(U') \subset V'$$, the diagram $$\require{amscd} \begin{CD} \GG(V) @>{ \phi_{VU}}>> \FF(U) \\ @V{ \res{V}{V'} }VV @VV{\res{U}{U'}}V \\ \GG(V') @>>{ \phi_{V'U'} }> \FF(U') \end{CD}$$ commutes. Define $$\Mor_{YX} ( \GG, \FF )$$ to be the set of all compatible collections $$\phi = \{\phi_{VU}\}$$.

###### Exercise 2.7.C:
Show that the stalks of $$\pi^{-1} \GG$$ are the same as the stalks of $$\GG$$. More precisely, if $$\pi(p) = q$$, describe a natural isomorphism $$\GG_q \cong (\pi^{-1}\GG)_p$$. (Possible hint: use the concrete description of the stalk, as a colimit. Recall that stalks are preserved by sheafification, Exercise 2.4.M. Alternatively, use adjointness.) This, along with the notion of compatible germs, may give you a simple way of thinking about (and perhaps visualizing) inverse image sheaves. (Those preferring the "espace étalé" or "space of sections" perspective, §2.2.11, can check that the pullback of the "space of sections" is the "space of sections" of the pullback.)

###### Exercise 2.7.D:
If $$U$$ is an open subset of $$Y$$, $$i: U \to Y$$ is the inclusion, and $$\GG$$ is a sheaf on $$Y$$, show that $$i^{-1} \GG$$ is naturally isomorphic to $$\GG\vert_U$$ (the restriction of $$\GG$$ to $$U$$, §2.2.8).

###### Exercise 2.7.E:
Show that $$\pi^{-1}$$ is an exact functor from sheaves of abelian groups on $$Y$$ to sheaves of abelian groups on $$X$$ (cf. Exercise 2.6.D). (Hint: exactness can be checked on stalks, and by Exercise 2.7.C, the stalks are the same.) Essentially the same argument will show that $$\pi^{-1}$$ is an exact functor from $$\OO_Y$$-modules (on $$Y$$) to $$(\pi^{-1}\OO_Y )$$-modules (on $$X$$), but don’t bother writing that down. (Remark for experts: $$\pi^{-1}$$ is a left adjoint, hence right-exact by abstract nonsense, as discussed in §1.6.12. Left-exactness holds because colimits of abelian groups over filtered index sets are exact, Exercise 1.6.K.)


text:
## § Crash course on DCPO: formalizing lambda calculus

In lambda calculus, we often see functions of the form $\lambda x \rightarrow x(x)$. We would like a way to associate a "natural" mathematical object to such a function. The most obvious choice for lambda calculus is to try to create a set $V$ of values which contains its own function space: $(V \rightarrow V) \subseteq V$. This seems to ask for a set whose cardinality is such that $|V|^|V| = |V|$, which is only possible if $|V| = 1$, ie $V$ is the trivial set $\{ * \}$. However, we know that lambda calculus has at least two types of functions: functions that terminate and those that don't terminate. Hence the trivial set is not a valid solution. However, there is a way out. The crucial insight is one that I shall explain by analogy:
• We can see that the cardinality of $\mathbb R$ is different from the cardinality of the space of functions over it, $\mathbb R \rightarrow \mathbb R$.
• However, "the set of all functions" isn't really something mathematicians consider. One would most likely consider "the set of all continuous functions" $\mathbb R \rightarrow \mathbb R$.
• Now note that a function that is continuous over the reals is determined by its values at the rationals . So, rather than giving me a continus function $f: \mathbb R \rightarrow \mathbb R$, you can give me a continuous function $f': \mathbb Q \rightarrow \mathbb R$ which I can Cauchy-complete, to get a function $\texttt{completion}(f') : \mathbb R \rightarrow \mathbb R = f$.
• Now, cardinality considerations tell us that:
$|\mathbb R^\mathbb Q| = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \cdot \aleph_0} = 2^\aleph_0 = |R|$
• We've won! We have a space $\mathbb R$ whose space of continuous functions $\mathbb R \rightarrow \mathbb R$ is isomorphic to $\mathbb R$.
• We bravely posit: all functions computed by lambda-calculus are continuous! Very well. This leaves us two questions to answer to answer: (1) over what space? (2) with what topology? The answers are (1) a space of partial orders (2) with the Scott topology

#### § Difference between DCPO theory and Domain theory

• A DCPO (directed-complete partial order) is an algebraic structure that can be satisfied by some partial orders. This definition ports 'continuity' to partial orders.
• A domain is an algebraic structure of even greater generality than a DCPO. This attempts to capture the fundamental notion of 'finitely approximable'.

#### § Posets, (least) upper bounds

• A partial order $(P, \leq)$ is a set equipped with a reflexive, transitive, relation $\leq$ such that $x \leq y$ and $y \leq x$ implies $x = y$.
• A subset $D \subseteq P$ is said to have an upper bound $u_D \in P$ iff for all $d \in D$, it is true that $d \leq u_D$.
• An upper bound is essentially a cone over the subset $D$ in the category $P$.
• A subset $D \subseteq P$ has a least upper bound $l_D$ iff (1) $l_D$ is an upper bound of $D$, and (2) for every upper bound $u_D$, it is true that $l_D \leq u_D$
• Least upper bounds are unique, since they are essentially limits of the set $D$ when $D$ is taken as a thin category

#### § Directed Sets

• A subset $D \subseteq P$ is said to be directed iff for every finite subset $S \subseteq D$, $S$ has a upper bound $d_S$ in $D$. That is, the set $D$ is closed under the upper bound of all of its subsets.
• Topologically, we can think of it as being closure , since the upper bound is sort of a "limit point" of the subset, and we are saying that $D$ has all of its limit points.
• Categorically, this means that $D \subseteq P$ taken as a subcategory of $P$ has cones over all finite subsets. (See that we do not ask for limits/least upper bounds over all finite subsets, only cones/upper bounds).
• We can think of the condition as saying that the information in $D$ is internally consistent: for any two facts, there is a third fact that "covers" them both.
• slogan: internal consistency begets an external infinite approximation.
• QUESTION: why not ask for countable limits as well?
• QUESTION: why upper bounds in $D$? why not external upper bounds in $P$?
• QUESTION: why only upper bounds in $D$? why not least upper bounds in $D$?
• ANSWER: I think the point is that as long as we ask for upper bounds, we can pushforward via a function $f$, since the image of a directed set will be directed.

#### § Directed Complete Partial Order ( DCPO)

• A poset is said to be directed complete iff every directed set $D \subseteq P$ has a least upper bound in $P$.
• Compare to chain complete, CCPO, where every chain has a LUB.
• QUESTION: why not postulate that the least upper bound must be in $D$?
• In a DCPO, for a directed set $D$, denote the upper bound by $\cup D$.

#### § Monotonicity and Continuity

• A function $f: P \to Q$ between posets is said to be monotone iff $p \leq p'$ implies that $f(p) \leq f(p')$.
• A function $f: P \to Q$ is continuous, iff for every directed set $D \subseteq P$, it is true that $f(\cup D) = \cup f(D)$.
• This has the subtle claim that the image of a directed set is directed.

#### § Monotone map

• A function from $P$ to $Q$ is said to be monotone if $p \leq p' \implies f(p) \leq f(p')$.
• Composition of monotone functions is monotone.
• The image of a chain wrt a monotone function is a chain.
• A monotone function need not preserve least upper bounds . Consider:
$f: 2^{\mathbb N} \rightarrow 2^{\mathbb N} f(S) \equiv \begin{cases} S & \text{S} is finite \\ S U \{ 0 \} &\text{S is infinite} \end{cases}$
This does not preserve least-upper-bounds. Consider the sequence of elements:
$A_1 = \{ 1\}, A_2 = \{1, 2\}, A_3 = \{1, 2, 3\}, \dots, A_n = \{1, 2, 3, \dots, n \}$
The union of all $A_i$ is $\mathbb N$. Each of these sets is finite. Hence $f(\{1 \}) = \{1 \}$, $f(\{1, 2 \}) = \{1, 2\}$ and so on. Therefore:
$f(\sqcup A_i) = f(\mathbb N) = \mathbb N \cup \{ 0 \}\\ \sqcup f(A_i) = \sqcup A_i = \mathbb N$

#### § Continuous function

• A function is continous if it is monotone and preserves all LUBs. This is only sensible as a definition on ccpos, because the equation defining it is: lub . f = f . lub, where lub: chain(P) \rightarrow P. However, for lubto always exist, we need P to be a CCPO. So, the definition of continuous only works for CCPOs.
• The composition of continuous functions of chain-complete partially ordered sets is continuous.

#### § Fixpoints of continuous functions

The least fixed point of a continous function $f: D \rightarrow D$ is:
$\texttt{FIX}(f) \equiv \texttt{lub}(\{ f^n(\bot) : n \geq 0 \})$

#### § $\leq$ as implication

We can think of $b \leq a$ as $b \implies a$. That is, $b$ has more information than $a$, and hence implies $a$.

#### § References

• Semantics with Applications: Hanne Riis Nielson, Flemming Nielson.