Open Systems: A Double Categorical Perspective (Part 3)

23 January, 2021

Back to Kenny Courser’s thesis:

• Kenny Courser, Open Systems: A Double Categorical Perspective, Ph.D. thesis, U. C. Riverside, 2020.

Last time I explained the problems with decorated cospans as a framework for dealing with open systems. I vaguely hinted that Kenny’s thesis presents two solutions to these problems: so-called ‘structured cospans’, and a new improved approach to decorated cospans. Now let me explain these!

You may wonder why I’m returning to this now, after three months of silence. The reason is that Kenny, Christina Vasilakopolou, and I just finished a paper that continues this story:

• John Baez, Kenny Courser and Christina Vasilakopoulou, Structured versus decorated cospans.

We showed that under certain conditions, structured and decorated cospans are equivalent. So, I’m excited about this stuff again.

Last time I explained Fong’s theorem about decorated cospans:

Fong’s Theorem. Suppose \mathsf{A} is a category with finite colimits, and make \mathsf{A} into a symmetric monoidal category with its coproduct as the tensor product. Suppose F\colon (\mathsf{A},+) \to (\mathsf{Set},\times) is a symmetric lax monoidal functor. Define an F-decorated cospan to be a cospan

in \mathsf{A} together with an element x\in F(N) called a decoration. Then there is a symmetric monoidal category with

• objects of \mathsf{A} as objects,
• isomorphism classes of F-decorated cospans as morphisms.

The theorem is true, but it doesn’t apply to all the examples we wanted it to. The problem is that it’s ‘not categorified enough’. It’s fine if we want to decorate the apex N of our cospan with some extra structure: we do this by choosing an element of some set F(N). But in practice, we often want to decorate N with some extra stuff, which means choosing an object of a category F(N). So we should really use not a functor

F\colon (\mathsf{A},+) \to (\mathsf{Set},\times)

but something like a functor

F\colon (\mathsf{A},+) \to (\mathbf{Cat},\times)

What do I mean by ‘something like a functor?’ Well, \mathbf{Cat} is not just a category but a 2-category: it has categories as objects, functors as morphisms, but also natural transformations as 2-morphisms. The natural notion of ‘something like a functor’ from a category to a 2-category is called a pseudofunctor. And just as we can define symmetric lax monoidal functor, we can define a symmetric lax monoidal pseudofunctor.

All these nuances really matter when we’re studying open graphs, as we were last time!

Here we want the feet of our structured cospan to be finite sets and the apex to be a finite graph. So, we have \mathsf{A} = \mathsf{FinSet} and for any N \in \mathsf{FinSet} we want F(N) to be the set, or category, of finite graphs having N as their set of nodes.

I explained last time all the disasters that ensue when you try to let F(N) be the set of finite graphs having N as its set of nodes. You can try, but you will pay dearly for it! You can struggle and fight, like Hercules trying to chop all the heads off the Hydra, but you still can’t get a symmetric lax monoidal functor

F\colon (\mathsf{A},+) \to (\mathsf{Set},\times)

that sends any finite set N to the set of graphs having N as their set of nodes.

But there is a perfectly nice category F(N) of all finite graphs having N as their set of nodes. And you can get a symmetric lax monoidal pseudofunctor

F\colon (\mathsf{A},+) \to (\mathbf{Cat},\times)

that sends any any finite set to the category of finite graphs having it as nodes. So you should stop fighting and go with the flow.

Kenny, Christina and I proved an enhanced version of Fong’s theorem that works starting from this more general kind of F. And instead of just giving you a symmetric monoidal category, this theorem gives you a symmetric monoidal double category.

In fact, that is something you should have wanted already, even with Fong’s original hypotheses! The clue is that Fong’s theorem uses isomorphism classes of decorated cospans, which suggests we’d get something better if we used decorated cospans themselves. Kenny tackled this a while ago, getting a version of Fong’s theorem that produces a symmetric monoidal double category, and another version that produces a symmetric monoidal bicategory:

• Kenny Courser, A bicategory of decorated cospans, Theory and Applications of Categories 32 (2017), 995–1027.

Over the years we’ve realized that the double category is better, because it contains more information and is easier to work with. So, in our new improved approach to decorated cospans, we go straight for the jugular and get a double category. And here’s how it works:

Theorem. Suppose \mathsf{A} is a category with finite colimits, and make \mathsf{A} into a symmetric monoidal category with its coproduct as the tensor product. Suppose F\colon (\mathsf{A},+) \to (\mathbf{Cat},\times) is a symmetric lax monoidal pseudofunctor. Then there is a symmetric monoidal double category F\mathbb{C}\mathbf{sp} in which

• an object is an object of \mathsf{A}
• a vertical morphism is a morphism in \mathsf{A}
• a horizontal morphism is an F-decorated cospan, meaning a cospan in \mathsf{A} together with a decoration:


• a 2-morphism is a map of decorated cospans, meaning a commutative diagram in \mathsf{A}:

together with a morphism \tau \colon F(h)(x) \to x', the map of decorations.

We call F\mathbb{C}\mathbf{sp} a decorated cospan double category. And as our paper explains, this idea lets us fix all the broken attempted applications of Fong’s original decorated cospan categories!

All this is just what any category theorist worth their salt would try, in order to fix the original problems with decorated cospans. It turns out that proving the theorem above is not so easy, mainly because the definition of ‘symmetric monoidal double category’ is rather complex. But if you accept the theorem—including the details of how you get the symmetric monoidal structure on the double category, which I have spared you here—then it doesn’t really matter much that the proof takes work.

Next time I’ll tell you about the other way to fix the original decorated cospan formalism: structured cospans. When these work, they are often easier to use.


Part 1: an overview of Courser’s thesis and related papers.

Part 2: problems with the original decorated cospans.

Part 3: the new improved decorated cospans.


US Environmental Policy (Part 3)

21 January, 2021

It’s begun! When it comes to global warming we’re in a race for time, and the US has spent the last four years with its ankles zip-tied together. On his first day in office, the new president of the US signed this executive order:

ACCEPTANCE ON BEHALF OF THE UNITED STATES OF AMERICA

I, Joseph R. Biden Jr., President of the United States of America, having seen and considered the Paris Agreement, done at Paris on December 12, 2015, do hereby accept the said Agreement and every article and clause thereof on behalf of the United States of America.

Done at Washington this 20th day of January, 2021.

JOSEPH R. BIDEN JR.

He also signed this order connected to the climate crisis and other environmental issues:

Executive order on protecting public health and the environment and restoring science to tackle the climate crisis.

It undoes many actions of the previous president.

• It revokes previous executive orders so as to:

  • reduce methane emissions in the oil and gas sector,
  • establish new fuel economy standards,
  • establish new efficiency standards for buildings, and
  • restore protection to a number of park lands and undersea protected areas (“national monuments”).

• It instantly puts a temporary halt to leasing lands in the Arctic National Wildlife Refuge for the purposes of oil and gas drilling, so this program can be reviewed.

• It prevents offshore oil and gas drilling in certain Arctic waters and the Bering Sea.

• It revokes the permit for the Keystone XL pipeline.

• It revives the Interagency Working Group on the Social Cost of Greenhouse Gases, to properly account for the full cost of these emissions.

• It revokes many other executive orders listed in section 7 below.

Here are the details:

By the authority vested in me as President by the Constitution and the laws of the United States of America, it is hereby ordered as follows:

Section 1. Policy. Our Nation has an abiding commitment to empower our workers and communities; promote and protect our public health and the environment; and conserve our national treasures and monuments, places that secure our national memory. Where the Federal Government has failed to meet that commitment in the past, it must advance environmental justice. In carrying out this charge, the Federal Government must be guided by the best science and be protected by processes that ensure the integrity of Federal decision-making. It is, therefore, the policy of my Administration to listen to the science; to improve public health and protect our environment; to ensure access to clean air and water; to limit exposure to dangerous chemicals and pesticides; to hold polluters accountable, including those who disproportionately harm communities of color and low-income communities; to reduce greenhouse gas emissions; to bolster resilience to the impacts of climate change; to restore and expand our national treasures and monuments; and to prioritize both environmental justice and the creation of the well-paying union jobs necessary to deliver on these goals.

To that end, this order directs all executive departments and agencies (agencies) to immediately review and, as appropriate and consistent with applicable law, take action to address the promulgation of Federal regulations and other actions during the last 4 years that conflict with these important national objectives, and to immediately commence work to confront the climate crisis.

Sec. 2. Immediate Review of Agency Actions Taken Between January 20, 2017, and January 20, 2021. (a) The heads of all agencies shall immediately review all existing regulations, orders, guidance documents, policies, and any other similar agency actions (agency actions) promulgated, issued, or adopted between January 20, 2017, and January 20, 2021, that are or may be inconsistent with, or present obstacles to, the policy set forth in section 1 of this order. For any such actions identified by the agencies, the heads of agencies shall, as appropriate and consistent with applicable law, consider suspending, revising, or rescinding the agency actions. In addition, for the agency actions in the 4 categories set forth in subsections (i) through (iv) of this section, the head of the relevant agency, as appropriate and consistent with applicable law, shall consider publishing for notice and comment a proposed rule suspending, revising, or rescinding the agency action within the time frame specified.

(i)    Reducing Methane Emissions in the Oil and Gas Sector:  “Oil and Natural Gas Sector: Emission Standards for New, Reconstructed, and Modified Sources Reconsideration,” 85 Fed. Reg. 57398 (September 15, 2020), by September 2021. 

(ii)   Establishing Ambitious, Job-Creating Fuel Economy Standards:  “The Safer Affordable Fuel-Efficient (SAFE) Vehicles Rule Part One: One National Program,” 84 Fed. Reg. 51310 (September 27, 2019), by April 2021; and “The Safer Affordable Fuel-Efficient (SAFE) Vehicles Rule for Model Years 2021–2026 Passenger Cars and Light Trucks,” 85 Fed. Reg. 24174 (April 30, 2020), by July 2021.  In considering whether to propose suspending, revising, or rescinding the latter rule, the agency should consider the views of representatives from labor unions, States, and industry.

(iii)  Job-Creating Appliance- and Building-Efficiency Standards:  “Energy Conservation Program for Appliance Standards: Procedures for Use in New or Revised Energy Conservation Standards and Test Procedures for Consumer Products and Commercial/Industrial Equipment,” 85 Fed. Reg. 8626 (February 14, 2020), with major revisions proposed by March 2021 and any remaining revisions proposed by June 2021; “Energy Conservation Program for Appliance Standards: Procedures for Evaluating Statutory Factors for Use in New or Revised Energy Conservation Standards,” 85 Fed. Reg. 50937 (August 19, 2020), with major revisions proposed by March 2021 and any remaining revisions proposed by June 2021; “Final Determination Regarding Energy Efficiency Improvements in the 2018 International Energy Conservation Code (IECC),” 84 Fed. Reg. 67435 (December 10, 2019), by May 2021; “Final Determination Regarding Energy Efficiency Improvements in ANSI/ASHRAE/IES Standard 90.1-2016: Energy Standard for Buildings, Except Low-Rise Residential Buildings,” 83 Fed. Reg. 8463 (February 27, 2018), by May 2021.

(iv)   Protecting Our Air from Harmful Pollution:  “National Emission Standards for Hazardous Air Pollutants: Coal- and Oil-Fired Electric Utility Steam Generating Units—Reconsideration of Supplemental Finding and Residual Risk and Technology Review,” 85 Fed. Reg. 31286 (May 22, 2020), by August 2021; “Increasing Consistency and Transparency in Considering Benefits and Costs in the Clean Air Act Rulemaking Process,” 85 Fed. Reg. 84130 (December 23, 2020), as soon as possible; “Strengthening Transparency in Pivotal Science Underlying Significant Regulatory Actions and Influential Scientific Information,” 86 Fed. Reg. 469 (January 6, 2021), as soon as possible.

(b)  Within 30 days of the date of this order, heads of agencies shall submit to the Director of the Office of Management and Budget (OMB) a preliminary list of any actions being considered pursuant to section (2)(a) of this order that would be completed by December 31, 2021, and that would be subject to OMB review.  Within 90 days of the date of this order, heads of agencies shall submit to the Director of OMB an updated list of any actions being considered pursuant to section (2)(a) of this order that would be completed by December 31, 2025, and that would be subject to OMB review.  At the time of submission to the Director of OMB, heads of agencies shall also send each list to the National Climate Advisor.  In addition, and at the same time, heads of agencies shall send to the National Climate Advisor a list of additional actions being considered pursuant to section (2)(a) of this order that would not be subject to OMB review.

(c)  Heads of agencies shall, as appropriate and consistent with applicable law, consider whether to take any additional agency actions to fully enforce the policy set forth in section 1 of this order.  With respect to the Administrator of the Environmental Protection Agency, the following specific actions should be considered:

(i)   proposing new regulations to establish comprehensive standards of performance and emission guidelines for methane and volatile organic compound emissions from existing operations in the oil and gas sector, including the exploration and production, transmission, processing, and storage segments, by September 2021; and

(ii)  proposing a Federal Implementation Plan in accordance with the Environmental Protection Agency’s “Findings of Failure To Submit State Implementation Plan Revisions in Response to the 2016 Oil and Natural Gas Industry Control Techniques Guidelines for the 2008 Ozone National Ambient Air Quality Standards (NAAQS) and for States in the Ozone Transport Region,” 85 Fed. Reg. 72963 (November 16, 2020), for California, Connecticut, New York, Pennsylvania, and Texas by January 2022. 

(d)  The Attorney General may, as appropriate and consistent with applicable law, provide notice of this order and any actions taken pursuant to section 2(a) of this order to any court with jurisdiction over pending litigation related to those agency actions identified pursuant to section (2)(a) of this order, and may, in his discretion, request that the court stay or otherwise dispose of litigation, or seek other appropriate relief consistent with this order, until the completion of the processes described in this order.

(e)  In carrying out the actions directed in this section, heads of agencies shall seek input from the public and stakeholders, including State local, Tribal, and territorial officials, scientists, labor unions, environmental advocates, and environmental justice organizations.

Sec. 3. Restoring National Monuments. (a) The Secretary of the Interior, as appropriate and consistent with applicable law, including the Antiquities Act, 54 U.S.C. 320301 et seq., shall, in consultation with the Attorney General, the Secretaries of Agriculture and Commerce, the Chair of the Council on Environmental Quality, and Tribal governments, conduct a review of the monument boundaries and conditions that were established by Proclamation 9681 of December 4, 2017 (Modifying the Bears Ears National Monument); Proclamation 9682 of December 4, 2017 (Modifying the Grand Staircase-Escalante National Monument); and Proclamation 10049 of June 5, 2020 (Modifying the Northeast Canyons and Seamounts Marine National Monument), to determine whether restoration of the monument boundaries and conditions that existed as of January 20, 2017, would be appropriate.

(b)  Within 60 days of the date of this order, the Secretary of the Interior shall submit a report to the President summarizing the findings of the review conducted pursuant to subsection (a), which shall include recommendations for such Presidential actions or other actions consistent with law as the Secretary may consider appropriate to carry out the policy set forth in section 1 of this order.

(c)  The Attorney General may, as appropriate and consistent with applicable law, provide notice of this order to any court with jurisdiction over pending litigation related to the Grand Staircase-Escalante, Bears Ears, and Northeast Canyons and Seamounts Marine National Monuments, and may, in his discretion, request that the court stay the litigation or otherwise delay further litigation, or seek other appropriate relief consistent with this order, pending the completion of the actions described in subsection (a) of this section.

Sec. 4. Arctic Refuge. (a) In light of the alleged legal deficiencies underlying the program, including the inadequacy of the environmental review required by the National Environmental Policy Act, the Secretary of the Interior shall, as appropriate and consistent with applicable law, place a temporary moratorium on all activities of the Federal Government relating to the implementation of the Coastal Plain Oil and Gas Leasing Program, as established by the Record of Decision signed August 17, 2020, in the Arctic National Wildlife Refuge. The Secretary shall review the program and, as appropriate and consistent with applicable law, conduct a new, comprehensive analysis of the potential environmental impacts of the oil and gas program.

(b)  In Executive Order 13754 of December 9, 2016 (Northern Bering Sea Climate Resilience), and in the Presidential Memorandum of December 20, 2016 (Withdrawal of Certain Portions of the United States Arctic Outer Continental Shelf From Mineral Leasing), President Obama withdrew areas in Arctic waters and the Bering Sea from oil and gas drilling and established the Northern Bering Sea Climate Resilience Area.  Subsequently, the order was revoked and the memorandum was amended in Executive Order 13795 of April 28, 2017 (Implementing an America-First Offshore Energy Strategy).  Pursuant to section 12(a) of the Outer Continental Shelf Lands Act, 43 U.S.C. 1341(a), Executive Order 13754 and the Presidential Memorandum of December 20, 2016, are hereby reinstated in their original form, thereby restoring the original withdrawal of certain offshore areas in Arctic waters and the Bering Sea from oil and gas drilling.

(c)  The Attorney General may, as appropriate and consistent with applicable law, provide notice of this order to any court with jurisdiction over pending litigation related to the Coastal Plain Oil and Gas Leasing Program in the Arctic National Wildlife Refuge and other related programs, and may, in his discretion, request that the court stay the litigation or otherwise delay further litigation, or seek other appropriate relief consistent with this order, pending the completion of the actions described in subsection (a) of this section.

Sec. 5. Accounting for the Benefits of Reducing Climate Pollution. (a) It is essential that agencies capture the full costs of greenhouse gas emissions as accurately as possible, including by taking global damages into account. Doing so facilitates sound decision-making, recognizes the breadth of climate impacts, and supports the international leadership of the United States on climate issues. The “social cost of carbon” (SCC), “social cost of nitrous oxide” (SCN), and “social cost of methane” (SCM) are estimates of the monetized damages associated with incremental increases in greenhouse gas emissions. They are intended to include changes in net agricultural productivity, human health, property damage from increased flood risk, and the value of ecosystem services. An accurate social cost is essential for agencies to accurately determine the social benefits of reducing greenhouse gas emissions when conducting cost-benefit analyses of regulatory and other actions.

(b)  There is hereby established an Interagency Working Group on the Social Cost of Greenhouse Gases (the “Working Group”).  The Chair of the Council of Economic Advisers, Director of OMB, and Director of the Office of Science and Technology Policy  shall serve as Co-Chairs of the Working Group. 

(i)    Membership.  The Working Group shall also include the following other officers, or their designees:  the Secretary of the Treasury; the Secretary of the Interior; the Secretary of Agriculture; the Secretary of Commerce; the Secretary of Health and Human Services; the Secretary of Transportation; the Secretary of Energy; the Chair of the Council on Environmental Quality; the Administrator of the Environmental Protection Agency; the Assistant to the President and National Climate Advisor; and the Assistant to the President for Economic Policy and Director of the National Economic Council.

(ii)   Mission and Work.  The Working Group shall, as appropriate and consistent with applicable law: 

(A)  publish an interim SCC, SCN, and SCM within 30 days of the date of this order, which agencies shall use when monetizing the value of changes in greenhouse gas emissions resulting from regulations and other relevant agency actions until final values are published;

(B)  publish a final SCC, SCN, and SCM by no later than January 2022;

(C)  provide recommendations to the President, by no later than September 1, 2021, regarding areas of decision-making, budgeting, and procurement by the Federal Government where the SCC, SCN, and SCM should be applied; 

(D)  provide recommendations, by no later than June 1, 2022, regarding a process for reviewing, and, as appropriate, updating, the SCC, SCN, and SCM to ensure that these costs are based on the best available economics and science; and

(E)  provide recommendations, to be published with the final SCC, SCN, and SCM under subparagraph (A) if feasible, and in any event by no later than June 1, 2022, to revise methodologies for calculating the SCC, SCN, and SCM, to the extent that current methodologies do not adequately take account of climate risk, environmental justice, and intergenerational equity.

(iii)  Methodology.  In carrying out its activities, the Working Group shall consider the recommendations of the National Academies of Science, Engineering, and Medicine as reported in Valuing Climate Damages: Updating Estimation of the Social Cost of Carbon Dioxide (2017) and other pertinent scientific literature; solicit public comment; engage with the public and stakeholders; seek the advice of ethics experts; and ensure that the SCC, SCN, and SCM reflect the interests of future generations in avoiding threats posed by climate change.

Sec. 6. Revoking the March 2019 Permit for the Keystone XL Pipeline. (a) On March 29, 2019, the President granted to TransCanada Keystone Pipeline, L.P. a Presidential permit (the “Permit”) to construct, connect, operate, and maintain pipeline facilities at the international border of the United States and Canada (the “Keystone XL pipeline”), subject to express conditions and potential revocation in the President’s sole discretion. The Permit is hereby revoked in accordance with Article 1(1) of the Permit.

(b)  In 2015, following an exhaustive review, the Department of State and the President determined that approving the proposed Keystone XL pipeline would not serve the U.S. national interest.  That analysis, in addition to concluding that the significance of the proposed pipeline for our energy security and economy is limited, stressed that the United States must prioritize the development of a clean energy economy, which will in turn create good jobs.  The analysis further concluded that approval of the proposed pipeline would undermine U.S. climate leadership by undercutting the credibility and influence of the United States in urging other countries to take ambitious climate action.

(c)  Climate change has had a growing effect on the U.S. economy, with climate-related costs increasing over the last 4 years.  Extreme weather events and other climate-related effects have harmed the health, safety, and security of the American people and have increased the urgency for combatting climate change and accelerating the transition toward a clean energy economy.  The world must be put on a sustainable climate pathway to protect Americans and the domestic economy from harmful climate impacts, and to create well-paying union jobs as part of the climate solution. 

(d)  The Keystone XL pipeline disserves the U.S. national interest.  The United States and the world face a climate crisis.  That crisis must be met with action on a scale and at a speed commensurate with the need to avoid setting the world on a dangerous, potentially catastrophic, climate trajectory.  At home, we will combat the crisis with an ambitious plan to build back better, designed to both reduce harmful emissions and create good clean-energy jobs.  Our domestic efforts must go hand in hand with U.S. diplomatic engagement.  Because most greenhouse gas emissions originate beyond our borders, such engagement is more necessary and urgent than ever.  The United States must be in a position to exercise vigorous climate leadership in order to achieve a significant increase in global climate action and put the world on a sustainable climate pathway.  Leaving the Keystone XL pipeline permit in place would not be consistent with my Administration’s economic and climate imperatives.

Sec. 7. Other Revocations. (a) Executive Order 13766 of January 24, 2017 (Expediting Environmental Reviews and Approvals For High Priority Infrastructure Projects), Executive Order 13778 of February 28, 2017 (Restoring the Rule of Law, Federalism, and Economic Growth by Reviewing the “Waters of the United States” Rule), Executive Order 13783 of March 28, 2017 (Promoting Energy Independence and Economic Growth), Executive Order 13792 of April 26, 2017 (Review of Designations Under the Antiquities Act), Executive Order 13795 of April 28, 2017 (Implementing an America-First Offshore Energy Strategy), Executive Order 13868 of April 10, 2019 (Promoting Energy Infrastructure and Economic Growth), and Executive Order 13927 of June 4, 2020 (Accelerating the Nation’s Economic Recovery from the COVID-19 Emergency by Expediting Infrastructure Investments and Other Activities), are hereby revoked. Executive Order 13834 of May 17, 2018 (Efficient Federal Operations), is hereby revoked except for sections 6, 7, and 11.

(b)  Executive Order 13807 of August 15, 2017 (Establishing Discipline and Accountability in the Environmental Review and Permitting Process for Infrastructure Projects), is hereby revoked.  The Director of OMB and the Chair of the Council on Environmental Quality shall jointly consider whether to recommend that a replacement order be issued.

(c)  Executive Order 13920 of May 1, 2020 (Securing the United States Bulk-Power System), is hereby suspended for 90 days.  The Secretary of Energy and the Director of OMB shall jointly consider whether to recommend that a replacement order be issued.

(d)  The Presidential Memorandum of April 12, 2018 (Promoting Domestic Manufacturing and Job Creation Policies and Procedures Relating to Implementation of Air Quality Standards), the Presidential Memorandum of October 19, 2018 (Promoting the Reliable Supply and Delivery of Water in the West), and the Presidential Memorandum of February 19, 2020 (Developing and Delivering More Water Supplies in California), are hereby revoked. 

(e)  The Council on Environmental Quality shall rescind its draft guidance entitled, “Draft National Environmental Policy Act Guidance on Consideration of Greenhouse Gas Emissions,” 84 Fed. Reg. 30097 (June 26, 2019).  The Council, as appropriate and consistent with applicable law, shall review, revise, and update its final guidance entitled, “Final Guidance for Federal Departments and Agencies on Consideration of Greenhouse Gas Emissions and the Effects of Climate Change in National Environmental Policy Act Reviews,” 81 Fed. Reg. 51866 (August 5, 2016).

(f)  The Director of OMB and the heads of agencies shall promptly take steps to rescind any orders, rules, regulations, guidelines, or policies, or portions thereof, including, if necessary, by proposing such rescissions through notice-and-comment rulemaking, implementing or enforcing the Executive Orders, Presidential Memoranda, and draft guidance identified in this section, as appropriate and consistent with applicable law.

Sec. 8. General Provisions. (a) Nothing in this order shall be construed to impair or otherwise affect:

(i)   the authority granted by law to an executive department or agency, or the head thereof; or

(ii)  the functions of the Director of the Office of Management and Budget relating to budgetary, administrative, or legislative proposals.

(b)  This order shall be implemented in a manner consistent with applicable law and subject to the availability of appropriations.

(c)  This order is not intended to, and does not, create any right or benefit, substantive or procedural, enforceable at law or in equity by any party against the United States, its departments, agencies, or entities, its officers, employees, or agents, or any other person.

JOSEPH R. BIDEN JR.

THE WHITE HOUSE,
January 20, 2021.


Categories of Nets (Part 2)

20 January, 2021

guest post by Michael Shulman

Now that John gave an overview of the Petri nets paper that he and I have just written with Jade and Fabrizio, I want to dive a bit more into what we accomplish. The genesis of this paper was a paper written by Fabrizio and several other folks entitled Computational Petri Nets: Adjunctions Considered Harmful, which of course sounds to a category theorist like a challenge. Our paper, and particularly the notion of Σ-net and the adjunction in the middle column relating Σ-nets to symmetric strict monoidal categories, is an answer to that challenge.

Suppose you wanted to “freely” generate a symmetric monoidal category from some combinatorial data. What could that data be? In other words (for a category theorist at least), what sort of category \mathsf{C} appears in an adjunction \mathsf{C} \rightleftarrows \mathsf{SMC}? (By the way, all monoidal categories in this post will be strict, so I’m going to drop that adjective for conciseness.)

Perhaps the simplest choice is the same data that naturally generates a plain category, namely a directed graph. However, this is pretty limited in terms of what symmetric monoidal categories it can generate, since the generating morphisms will always only have single generating objects as their domain and codomain.

Another natural choice is the same data that naturally generates a multicategory, which might be called a “multigraph”: a set of objects together with, for every tuple of objects x_1,\dots,x_n and single object y, a set of arrows from (x_1,\dots,x_n) to y. In the generated symmetric monoidal category, such an arrow gives rise to a morphism x_1\otimes\cdots\otimes x_n \to y; thus we can now have multiple generating objects in the domains of generating morphisms, but not the codomains.

Of course, this suggests an even better solution: a set of objects, together with a set of arrows for every pair of tuples (x_1,\dots,x_m) and (y_1,\dots,y_n). I’d be tempted to call this a “polygraph”, since it also naturally generates a polycategory. But other folks got there first and called it a “tensor scheme” and also a “pre-net”. In the latter case, the objects are called “places” and the morphisms “transitions”. But whatever we call it, it allows us to generate free symmetric monoidal categories in which the domains and codomains of generating morphisms can both be arbitrary tensor products of generating objects. For those who like fancy higher-categorical machinery, it’s the notion of computad obtained from the monad for symmetric monoidal categories.

However, pre-nets are not without flaws. One of the most glaring, for people who actually want to compute with freely generated symmetric monoidal categories, is that there aren’t enough morphisms between them. For instance, suppose one pre-net N has three places x,y,z and a transition f:(x,x,y) \to z, while a second pre-net N' has three places x',y',z' and a transition f':(x',y',x') \to z'. Once we generate a symmetric monoidal category, then f can be composed with a symmetry x\otimes y \otimes x \cong x\otimes x\otimes y and similarly for f'; so the symmetric monoidal categories generated by N and N' are isomorphic. But there isn’t even a single map of pre-nets from N to N' or vice versa, because a map of pre-nets has to preserve the ordering on the inputs and outputs. This is weird and annoying for combinatorial data that’s supposed to present a symmetric monoidal category.

Another way of making essentially the same point is that just as the adjunction between SMCs and directed graphs factors through categories, and the adjunction between SMCs and multigraphs factors through multicategories, the adjunction between SMCs and pre-nets factors through non-symmetric monoidal categories. In other words, a pre-net is really better viewed as data for generating a non-symmetric monoidal category, which we can then freely add symmetries to.

By contrast, in the objects that we call “Petri nets”, the domain and codomain of each generating morphism are elements of the free commutative monoid on the set of places—as opposed to elements of the free monoid, which is what they are for a pre-net. Thus, the domain of f and f' above would be x+x+y and x+y+x respectively, which in a commutative monoid are equal (both are 2x+y). So the corresponding Petri nets of N and N' are indeed isomorphic. However, once we squash everything down in this way, we lose the ability to functorially generate a symmetric monoidal category; all we can generate is a commutative monoidal category where all the symmetries are identities.

At this point we’ve described the upper row and the left- and right-hand columns in John’s diagram:

What’s missing is a kind of net in the middle that corresponds to symmetric monoidal categories. To motivate the definition of Σ-net, consider how to solve the problem above of the “missing morphisms”. We want to send f:(x,x,y) \to z to a “permuted version” of f':(x',y',x') \to z'. For this to be implemented by an actual set-map, we need this “permuted version” to be present in the data of N' somehow. This suggests that the transitions should come with a permutation action like that of, say, a symmetric multicategory. Then inside N' we can actually act on f' by the transposition \tau = (2,3) \in S_3, yielding a new morphism \tau(f') : (x',x',y')\to z' which we can take to be the image of f. Of course, we can also act on f' by other permutations, and likewise on f; but since these permutation actions are part of the structure they must be preserved by the morphism, so sending f to \tau(f') uniquely determines where we have to send all these permutation images.

Now you can go back and look again at John’s definition of Σ-net: a set S, a groupoid T, and a discrete opfibration T \to P S \times P S ^{op}, where P denotes the free-symmetric-strict-monoidal-category functor \mathsf{Set} \to \mathsf{Cat}. Such a discrete opfibration is the same as a functor N \colon P S \times P S ^{op} \to \mathsf{Set}, and the objects of P S are the finite sequences of elements of S while its morphisms are permutations; thus this is precisely a pre-net (the action of the functor N on objects) with permutation actions as described above. I won’t get into the details of constructing the adjunction relating Σ-nets to symmetric monoidal categories; you can read the paper, or maybe I’ll blog about it later.

However, in solving the “missing morphisms” problem, we’ve introduced a new possibility. Suppose we act on f \colon (x,x,y) \to z by the transposition \sigma = (1,2) \in S_3 that switches the first two entries. We get another transition (x,x,y)\to z with the same domain and codomain as f; so it might equal f, or it might not! In other words, transitions in a Σ-net can have isotropy. If \sigma(f)=f, then when we generate a free symmetric monoidal category from our Σ-net, the corresponding morphism f:x\otimes x \otimes y \to z will have the property that when we compose it with the symmetry morphism x\otimes x\otimes y \cong x\otimes x\otimes y we get back f again. No symmetric monoidal category generated by a pre-net has this property; it’s more like the behavior of the commutative monoidal category generated by a Petri net, except that in the latter case the symmetry x\otimes x\otimes y \cong x\otimes x\otimes y itself is the identity, rather than just acting by the identity on f.

This suggests that Σ-nets can either “behave like pre-nets” or “behave like Petri nets”. This is made precise by the bottom row of adjunctions in the diagram. On one hand, we can map a pre-net to a Σ-net by freely generating the action of all permutations. This has a right adjoint that just forgets the permutation action (which actually has a further right adjoint, although that’s a bit weird). On the other hand, we can map a Petri net to a Σ-net by making all the permutations act as trivially as possible; this has a left adjoint that identifies each transition with all its permutation images. And these adjunctions commute with the three “free monoidal category” adjunctions in reasonable ways (see the paper for details).

The right adjoint mapping Petri nets into Σ-nets is fully faithful, so we really can say that Σ-nets “include” Petri nets. The left adjoint mapping pre-nets to Σ-nets is not fully faithful—it can’t possibly be, since the whole point of introducing Σ-nets was that pre-nets don’t have enough morphisms! But the full image of this functor is equivalent to a fourth kind of net: Kock’s whole-grain Petri nets. Kock’s approach to solving the problem of pre-nets is somewhat different, more analogous to the notion of “fat” symmetric monoidal category: he takes the domain and codomain of each transition to be a family of places indexed by a finite set. But his category turns out to be equivalent to the category of Σ-nets that are freely generated by some pre-net. (Kock actually proved this himself, as well as sketching the adjunction between Σ-nets and symmetric monoidal categories. He called Σ-nets “digraphical species”.)

So Σ-nets “include” both Petri nets and pre-nets, in an appropriate sense. The pre-nets (or, more precisely, whole-grain nets) are the Σ-nets with free permutation actions (trivial isotropy), while the Petri nets are the Σ-nets with trivial permutation actions (maximal isotropy). In Petri-net-ese, these correspond to the “individual token philosophy” and the “collective token philosophy”, respectively. (This makes it tempting to refer to the functors from Σ-nets to pre-nets and Petri nets as individuation and collectivization respectively.) But Σ-nets also allow us to mix and match the two philosophies, having some transitions with trivial isotropy, others with maximal isotropy, and still others with intermediate isotropy.

I like to think of Σ-nets as a Petri net analogue of orbifolds. Commutative-monoid-based Petri nets are like “coarse moduli spaces”, where we’ve quotiented by all symmetries but destroyed all the isotropy information; while whole-grain Petri nets are like manifolds, where we have no singularities but can only quotient by free actions. Pre-nets can then be thought of a “presentation” of a manifold, such as by a particular way of gluing coordinate patches together: useful in concrete examples, but not the “invariant” object we really want to study mathematically.


Part 1: three kinds of nets, and the kinds of monoidal categories they generate.

Part 2: what kind of net is best for generating symmetric monoidal categories?


Categories of Nets (Part 1)

17 January, 2021

I’ve been thinking about Petri nets a lot. Around 2010, I got excited about using them to describe chemical reactions, population dynamics and more, using ideas taken from quantum physics. Then I started working with my student Blake Pollard on ‘open’ Petri nets, which you can glue together to form larger Petri nets. Blake and I focused on their applications to chemistry, but later my student Jade Master and I applied them to computer science and brought in some new math. I was delighted when Evan Patterson and Micah Halter used all this math, along with ideas of Joachim Kock, to develop software for rapidly assembling models of COVID-19.

Now I’m happy to announce that Jade and I have teamed up with Fabrizio Genovese and Mike Shulman to straighten out a lot of mysteries concerning Petri nets and their variants:

• John Baez, Fabrizio Genovese, Jade Master and Mike Shulman, Categories of nets.

This paper is full of interesting ideas, but I’ll just tell you the basic framework.

A Petri net is a seemingly simple thing:

It consists of places (drawn as circles) and transitions (drawn as boxes), with directed edges called arcs from places to transitions and from transitions to places.

The idea is that when you use a Petri net, you put dots called tokens in the places, and then move them around using the transitions:

A Petri net is actually a way of describing a monoidal category. A way of putting a bunch of tokens in the places gives an object of this category, and a way of moving them around repeatedly (as above) gives a morphism.

The idea sounds straightforward enough. But it conceals some subtleties, which researchers have been struggling with for at least 30 years.

There are various ways to make the definition of Petri net precise. For example: is there a finite set of arcs from a given place to a given transition (and the other way around), or merely a natural number of arcs? If there is a finite set, is this set equipped with an ordering or not? Furthermore, what is a morphism between Petri nets?

Different answers are good for different purposes. In the so-called ‘individual token philosophy’, we allow a finite set of tokens in each place. In the ‘collective token philosophy’, we merely allow a natural number of tokens in each place. It’s like the difference between having 4 individual workers named John, Fabrizio, Jade and Mike where you can tell who did what, and having 4 anonymous workers: nameless drones.

Our goal was to sort this out all and make it crystal clear. We focus on 3 kinds of net, each of which naturally generates its own kind of monoidal category:

pre-nets, which generate free strict monoidal categories.

Σ-nets, which generate free symmetric strict monoidal categories.

Petri nets, which generate free commutative monoidal categories.

These three kinds of monoidal category differ in how ‘commutative’ they are:

• In a strict monoidal category we typically have x \otimes y \ne y \otimes x.

• In a strict symmetric monoidal category we have for each pair of objects a chosen isomorphism x \otimes y \cong y \otimes x.

• A commutative monoidal category is a symmetric strict monoidal category where the symmetry isomorphisms are all identities, so x \otimes y = y \otimes x.

So, we have a spectrum running from hardcore individualism, where two different things of the same type are never interchangeable… to hardcore collectivism, where two different things of the same type are so interchangeable that switching them counts as doing nothing at all! In the theory of Petri nets and their variants, the two extremes have been studied better than the middle.

You can summarize the story with this diagram:

There are three different categories of nets at bottom, and three diffferent categories of monoidal categories on top — all related by adjoint functors! Here the left adjoints point up the page — since different kinds of nets freely generate different kinds of monoidal categories — and also to the right, in the direction of increasing ‘commutativity’.

If you’re a category theorist you’ll recognize at least two of the three categories on top:

\mathsf{StrMC}, with strict monoidal categories as objects and strict monoidal functors as morphisms.

\mathsf{SSMC}, with symmetric strict monoidal categories as objects and strict symmetric monoidal functors as their morphisms.

\mathsf{CMC}, with commutative monoidal categories as objects and strict symmetric monoidal functors as morphisms. A commutative monoidal category is a symmetric strict monoidal category where the symmetry is the identity.

The categories of nets are probably less familiar. But they are simple enough. Here I’ll just describe their objects. The morphisms are fairly obvious, but read our paper for details.

\mathsf{PreNet}, with pre-nets as objects. A pre-net consists of a set S of places, a set T of transitions, and a function T \to S^\ast\times S^\ast, where S^\ast is the set of lists of elements of S.

\Sigma\mathsf{-net}, with Σ-nets as objects. A Σ-net consists of a set S, a groupoid T, and a discrete opfibration T \to P S \times P S^{\mathrm{op}}, where P S is the free symmetric strict monoidal category generated by a set of objects S and no generating morphisms.

\mathsf{Petri}, with Petri nets as objects. A Petri net, as we use the term, consists of a set S, a set T, and a function T \to \mathbb{N}[S] \times \mathbb{N}[S], where \mathbb{N}[S] is the set of multisets of elements of S.

What does this mean in practice?

• In a pre-net, each transition has an ordered list of places as ‘inputs’ and an ordered list of places as ‘outputs’. We cannot permute the inputs or outputs of a transition.

• In a Σ-net, each transition has an ordered list of places as inputs and an ordered list of places as outputs. However, permuting the entries of these lists gives a new transition with a new list of inputs and a new list of outputs!

• In a Petri net, each transition has a multiset of places as inputs and a multiset of places as outputs. A multiset is like an ‘unordered list’: entries can appear repeatedly, but the order makes no difference at all.

So, pre-nets are rigidly individualist. Petri nets are rigidly collectivist. And Σ-nets are flexible, including both extremes as special cases!

On the one hand, we can use the left adjoint functor

\mathsf{PreNet} \to \Sigma\mathsf{-net}

to freely generate Σ-nets from pre-nets. If we do this, we get Σ-nets such that permutations of inputs and outputs act freely on transitions. Joachim Kock has recently studied Σ-nets of this sort. He calls them whole-grain Petri nets, and he treats them as forming a category in their own right, but it’s also the full image of the above functor.

On the other hand, we can use the right adjoint functor

\mathsf{Petri} \to \Sigma\mathsf{-net}

to turn Petri nets into Σ-nets. If we do this, we get Σ-nets such that permutations of inputs and outputs act trivially on transitions: the permutations have no effect at all.

I’m not going to explain how we got any of the adjunctions in this diagram:

That’s where the interesting category theory comes in. Nor will I tell you about the various alternative mathematical viewpoints on Σ-nets… nor how we draw them. I also won’t explain our work on open nets and open categories of all the various kinds. I’m hoping Mike Shulman will say some more about what we’ve done. That’s why this blog article is optimistically titled “Part 1”.

But I hope you see the main point. There are three different kinds of things like Petri nets, each of which serves to freely generate a different kind of monoidal category. They’re all interesting, and a lot of confusion can be avoided if we don’t mix them up!


Part 1: three kinds of nets, and the kinds of monoidal categories they generate.

Part 2: what kind of net is best for generating symmetric monoidal categories?


This Week’s Finds (1–50)

12 January, 2021

Take a copy of this!

This Week’s Finds in Mathematical Physics (1-50), 242 pages.

These are the first 50 issues of This Week’s Finds of Mathematical Physics. This series has sometimes been called the world’s first blog, though it was originally posted on a “usenet newsgroup” called sci.physics.research — a form of communication that predated the world-wide web. I began writing this series as a way to talk about papers I was reading and writing, and in the first 50 issues I stuck closely to this format. These issues focus rather tightly on quantum gravity, topological quantum field theory, knot theory, and applications of n-categories to these subjects. There are, however, digressions into elliptic curves, Lie algebras, linear logic and various other topics.

Tim Hosgood kindly typeset all 300 issues of This Week’s Finds in 2020. They will be released in six installments of 50 issues each, for a total of about 2610 pages. I have edited the issues here to make the style a bit more uniform and also to change some references to preprints, technical reports, etc. into more useful arXiv links. This accounts for some anachronisms where I discuss a paper that only appeared on the arXiv later.

The process of editing could have gone on much longer; there are undoubtedly many mistakes remaining. If you find some, please contact me and I will try to fix them.

By the way, sci.physics.research is still alive and well, and you can use it on Google. But I can’t find the first issue of This Week’s Finds there — if you can find it, I’ll be grateful. I can only get back to the sixth issue. Take a look if you’re curious about usenet newsgroups! They were low-tech compared to what we have now, but they felt futuristic at the time, and we had some good conversations.



CP Violation

5 January, 2021

Here are two more open questions about physics. I have a question of my own at the end!

Why are the laws of physics not symmetrical when we switch left and right, or future and past, or matter and antimatter? Why do the laws of nature even violate “CP symmetry”? That is: why are the laws not symmetrical under the operation where we simultaneously switch matter and antimatter and switch left and right?

Violation of P symmetry, meaning the symmetry between left and right, is strongly visible in the Standard Model: for example, all directly observed neutrinos are “left-handed”. But violation of CP symmetry is subtler: in the Standard Model it appears solely in interactions between the Higgs boson and quarks or leptons. Technically, it occurs because the numbers in the Cabibbo–Kobayashi–Maskawa matrix and Pontecorvo–Maki–Nakagawa–Sakata matrix (discussed in the previous question) are not all real numbers. Interestingly, this is only possible when there are 3 or more generations of quarks and/or leptons: with 2 or fewer generations the matrix can always be made real.

Does the strong force violate CP symmetry? In the Standard Model it would be very natural to add a CP-violating term to the equations describing the strong force, proportional to a constant called the “θ angle”. But experiments say the magnitude of the θ angle is less than 2 × 10-10. Is this angle zero or not? Nobody knows. Why is it so small? This is called the “strong CP problem”. One possible solution, called the Peccei–Quinn mechanism, involves positing a new very light particle called the axion, which might also be a form of dark matter. But despite searches, nobody has found any axions.

• Wikipedia, CP Violation.

• Wikpedia, Strong CP Problem.

• Michael Beyer, editor, CP Violation in Particle, Nuclear, and Astrophysics, Springer, Berlin, 2008.

• I. Bigi, CP Violation — An Essential Mystery in Nature’s Grand Design.

It’s a theorem that quantum field theories are symmetrical under CPT: the combination of switching matter and antimatter, left and right, and future and past. Thus, a violation of CP implies a violation of time reversal symmetry. For more on this, see:

• R. G. Sachs, The Physics of Time Reversal, University of Chicago Press, Chicago, 1987.

What are the electric dipole moments of the electron and the neutron?

As of 2020, experiments show the electric dipole moment of the electron is less than 1.1 × 10-29 electron charge centimeters. According to the Standard Model it should have a very small nonzero value due to CP violation by virtual quarks, but various extensions of the Standard Model predict a larger dipole moment.

Also as of 2020, experiments show the neutron’s electric dipole is less than 1.8 × 10-26 e·cm. The Standard Model predicts a moment of about 10-31 e·cm, again due to CP violation by
virtual quarks, and again various other theories predict a larger moment.

Measuring these moments could give new information on physics beyond the Standard Model.

• Wikipedia, Electron Electric Dipole Moment.

• Wikipedia, Neutron Electric Dipole Moment.

• Maxim Pospelov and Adam Ritz, Electric Dipole Moments as Probes of New Physics.

Here’s my question. Do you know papers that actually calculate what the Standard Model predicts for the electric dipole moments of the electron and neutron?


Applied Category Theory 2021 — Adjoint School

2 January, 2021

Do you want to get involved in applied category theory? Are you willing to do a lot of work and learn a lot? Then this is for you:

Applied Category Theory 2021 — Adjoint School. Applications due Friday 29 January 2021. Organized by David Jaz Myers, Sophie Libkind, and Brendan Fong.

There are four projects to work on with great mentors. You can see descriptions of them below!

By the way, it’s not yet clear if there will be an in-person component to this school —but if there is, it will happen at the University of Cambridge. ACT2021 is being organized by Jamie Vicary, who teaches in the computer science department there.

Who should apply?

Anyone, from anywhere in the world, who is interested in applying category-theoretic methods to problems outside of pure mathematics. This is emphatically not restricted to math students, but one should be comfortable working with mathematics. Knowledge of basic category-theoretic language—the definition of monoidal category for example—is encouraged.

We will consider advanced undergraduates, PhD students, post-docs, as well as people working outside of academia. Members of groups which are underrepresented in the mathematics and computer science communities are especially encouraged to apply.

School overview

Participants are divided into four-person project teams. Each project is guided by a mentor and a TA. The Adjoint School has two main components: an Online Seminar that meets regularly between February and June, and an in-person Research Week in Cambridge, UK on July 5–9.

During the online seminar, we will read, discuss, and respond to papers chosen by the project mentors. Every other week, a pair of participants will present a paper which will be followed by a group discussion. Leading up to this presentation, study groups will meet to digest the reading in progress, and students will submit reading responses. After the presentation, the presenters will summarize the paper into a blog post for The n-Category Cafe.

The in-person research week will be held the week prior to the International Conference on Applied Category Theory and in the same location. During the week, participants work intensively with their research group under the guidance of their mentor. Projects from the Adjoint School will be presented during this conference. Both components of the school aim to develop a sense of belonging and camaraderie in students so that they can fully participate in the conference, for example by attending talks and chatting with other conference goers.

Projects to choose from

Here are the projects.

Topic: Categorical and computational aspects of C-sets

Mentors: James Fairbanks and Evan Patterson

Description: Applied category theory includes major threads of inquiry into monoidal categories and hypergraph categories for describing systems in terms of processes or networks of interacting components. Structured cospans are an important class of hypergraph categories. For example, Petri net-structured cospans are models of concurrent processes in chemistry, epidemiology, and computer science. When the structured cospans are given by C-sets (also known as co-presheaves), generic software can be implemented using the mathematics of functor categories. We will study mathematical and computational aspects of these categorical constructions, as well as applications to scientific computing.

Readings:

Structured cospans, Baez and Courser.

An algebra of open dynamical systems on the operad of wiring diagrams, Vagner, Spivak, and Lerman.

Topic: The ubiquity of enriched profunctor nuclei

Mentor: Simon Willerton

Description: In 1964, Isbell developed a nice universal embedding for metric spaces: the tight span. In 1966, Isbell developed a duality for presheaves. These are both closely related to enriched profunctor nuclei, but the connection wasn’t spotted for 40 years. Since then, many constructions in mathematics have been observed to be enriched profunctor nuclei too, such as the fuzzy/formal concept lattice, tropical convex hull, and the Legendre–Fenchel transform. We’ll explore the world of enriched profunctor nuclei, perhaps seeking out further useful examples.

Readings:

The Legendre–Fenchel transform from a category theoretic perspective, Willerton.

On the fuzzy concept complex (chapters 2-3), Elliot.

Topic: Double categories in applied category theory

Mentor: Simona Paoli

Description: Bicategories and double categories (and their symmetric monoidal versions) have recently featured in applied category theory: for instance, structured cospans and decorated cospans have been used to model several examples, such as electric circuits, Petri nets and chemical reaction networks.

An approach to bicategories and double categories is available in higher category theory through models that do not require a direct checking of the coherence axioms, such as the Segal-type models. We aim to revisit the structures used in applications in the light of these approaches, in the hope to facilitate the construction of new examples of interest in applications.

Readings:

Structured cospans, Baez and Courser.

A double categorical model of weak 2-categories, Paoli and Pronk.

and introductory chapters of:

Simplicial Methods for Higher Categories: Segal-type Models of Weak n-Categories, Paoli.

Topic: Extensions of coalgebraic dynamic logic

Mentors: Helle Hvid Hansen and Clemens Kupke

Description: Coalgebra is a branch of category theory in which different types of state-based systems are studied in a uniform framework, parametric in an endofunctor F:C → C that specifies the system type. Many of the systems that arise in computer science, including deterministic/nondeterministic/weighted/probabilistic automata, labelled transition systems, Markov chains, Kripke models and neighbourhood structures, can be modeled as F-coalgebras. Once we recognise that a class of systems are coalgebras, we obtain general coalgebraic notions of morphism, bisimulation, coinduction and observable behaviour.

Modal logics are well-known formalisms for specifying properties of state-based systems, and one of the central contributions of coalgebra has been to show that modal logics for coalgebras can be developed in the general parametric setting, and many results can be proved at the abstract level of coalgebras. This area is called coalgebraic modal logic.

In this project, we will focus on coalgebraic dynamic logic, a coalgebraic framework that encompasses Propositional Dynamic Logic (PDL) and Parikh’s Game Logic. The aim is to extend coalgebraic dynamic logic to system types with probabilities. As a concrete starting point, we aim to give a coalgebraic account of stochastic game logic, and apply the coalgebraic framework to prove new expressiveness and completeness results.

Participants in this project would ideally have some prior knowledge of modal logic and PDL, as well as some familiarity with monads.

Readings:

Parts of these:

Universal coalgebra: a theory of systems, Rutten.

Coalgebraic semantics of modal logics: an overview, Kupke and Pattinson.

Strong completeness of iteration-free coalgebraic dynamic logics, Hansen, Kupke, and Leale.


Cosmic Censorship

31 December, 2020

I seem to be getting pulled into the project of updating this FAQ:

Open questions in physics.

The more I look at it, the bigger the job gets. I started out rewriting the section on neutrinos, and now I’m doing the part on cosmic censorship. There are even bigger jobs to come. But it’s fun as long as I don’t try to do it all in one go!

Here’s the new section on cosmic censorship. If you have any questions or have other good resources to suggest, let me know.

Does Cosmic Censorship hold?  Roughly, is general relativity a deterministic theory—and when an object collapses under its own gravity, are the singularities that might develop guaranteed to be hidden behind an event horizon?

Proving a version of Cosmic Censorship is a matter of mathematical physics rather than physics per se, but doing so would increase our understanding of general relativity. There are actually at least two versions: Penrose formulated the “Strong Cosmic Censorship Conjecture” in 1986 and the “Weak Cosmic Censorship Hypothesis” in 1988. Very roughly, strong cosmic censorship asserts that under reasonable conditions general relativity is a deterministic theory, while weak cosmic censorship asserts that that any singularity produced by gravitational collapse is hidden behind an event horizon. Despite their names, strong cosmic censorship does not imply weak cosmic censorship.

In 1991, Preskill and Thorne made a bet against Hawking in which they claimed that weak cosmic censorship was false. Hawking conceded this bet in 1997 when a counterexample was found by Matthew Choptuik. This features finely-tuned infalling matter poised right on the brink of forming a black hole. It almost creates a region from which light cannot escape—but not quite. Instead, it creates a naked singularity!

Given the delicate nature of this construction, Hawking did not give up. Instead he made a new bet, which says that weak cosmic censorship holds “generically”—that is, except for very unusual conditions that require infinitely careful fine-tuning to set up. For an overview see:

• Robert Wald, Gravitational Collapse and Cosmic Censorship.

In 1999, Christodoulou proved that for spherically symmetric solutions of Einstein’s equation coupled to a massless scalar field, weak cosmic censorship holds generically. For a review of this and also Choptuik’s work, see:

• Carsten Gundlach, Critical Phenomena in Gravitational Collapse.

While spherical symmetry is a very restrictive assumption, this result is a good example of how, with plenty of work, we can make progress in rigorously settling the questions raised by general relativity.

What about strong cosmic censorship? In general relativity, for each choice of initial data—that is, each choice of the gravitational field and other fields at “time zero”—there is a region of spacetime whose properties are completely determined by this choice. The question is whether this region is always the whole universe. That is: does the present determine the whole future?

The answer is: not always! By carefully choosing the fields at time zero you can manufacture counterexamples. But Penrose, knowing this, claimed only that generically the fields at time zero determine the whole future of the universe.

In 2017, Mihalis Dafermos and Jonathan Luk showed that even this is false if you don’t demand that the fields stay smooth. But perhaps the conjecture can be saved if we require that:

• Kevin Hartnett, Mathematicians Disprove Conjecture Made to Save Black Holes.

• Oscar J.C. Dias, Harvey S. Reall and Jorge E. Santos, Strong Cosmic Censorship: Taking the Rough with the Smooth.


Solar Neutrinos

29 December, 2020

Over on the Category Theory Community Server, John van de Wetering asked me how many times a typical solar neutrino oscillates on its flight from the Sun to the Earth. I didn’t know, and I thought it would be fun to estimate this.

So let’s do it! Let’s do a rough calculation, and worry about details later. For those too lazy to even jump to the end, here are the results:

• A neutrino takes about 500 seconds to travel from the Sun to the Earth.

• Because a typical solar neutrino moving is moving close to the speed of light, time dilation affects it dramatically, and the time of travel from the Sun to the Earth experienced by the neutrino is much less: very roughly, 1/6 of a millisecond.

• There are different kinds of oscillation. If we keep track only of its slower oscillations, a typical solar neutrino oscillates roughly once for each 1250 meters of its flight through space.

• As it travels from Sun to Earth, this typical neutrino does about 120 million oscillations.

Let’s start at the beginning.

The Sun emits a lot of electron neutrinos. Most are produced from a reaction where two protons collide and one turns into a neutron, emitting a positron and an electron neutrino. The proton and neutron then stick together forming a ‘deuteron’, but let’s not worry about that.

More importantly, the energy of the neutrinos produced from these so-called pp reaction is at most 400 keV. That means 400,000 eV, where an eV or ‘electron volt’ is the energy an electron picks up as it falls through a potential of one volt. If you look at this chart:

you’ll see most solar neutrinos have a somewhat lower energy. Let’s say 300 keV.

By comparison to the rest mass of a neutrino, this is huge. Nobody knows neutrino masses very accurately—as we’ll see, people know more about differences of squares of the three neutrino masses. But a very rough estimate for the rest mass of the lightest neutrino might be 0.1 eV/c2. Here like particle physicists I’m measuring mass in units of energy divided by the speed of light squared. An eV, or electron volt, is the change in energy of an electron as it undergoes a one-volt change in potential.

This mass could be way off, say by a factor of 10 or more. But it’s good enough to show this: solar neutrinos are moving very close to the speed of light!

Remember, the energy of a moving particle, divided by its ‘mass energy’, the energy due to its mass, is

\displaystyle{ \frac{1}{\sqrt{1 - v^2/c^2}} }

Our solar neutrino, using our very rough guess about its mass, has

\displaystyle{ \frac{1}{\sqrt{1 - v^2/c^2}} \approx \frac{300 \textrm{keV}}{0.1 \textrm{eV}} = 3 \cdot 10^6 }

It has an energy 3 million times its rest energy! That gives

\displaystyle{  1 - v^2/c^2 \approx \frac{1}{9 \cdot 10^{12}} }

or

\displaystyle{  v^2/c^2 \approx 1 - \frac{1}{9 \cdot 10^{12}} }

or using a Taylor series trick

\displaystyle{  v/c \approx 1 - \frac{1}{18 \cdot 10^{12}} }

or if I didn’t push the wrong button on my calculator

v  \approx  0.99999999999994 \; c

This is ridiculously close to the speed of light.

It’s more useful to remember that our neutrino’s energy is roughly 3 million times what it would be at rest. And relativity says that due to time dilation, the passage of time experienced by this neutrino is slowed down by the same factor!

It takes 500 seconds for light to go from the Sun to the Earth. Our neutrino will take a tiny bit longer—the difference is not worth worrying about. But because of time dilation, the travel time ‘experienced by the neutrino’ will be

\displaystyle{ \frac{500 \; \textrm{sec}}{3 \cdot 10^6} \approx 1.67 \cdot 10^{-4} \; \textrm{sec} }

This figure is very rough, due to how poorly we know the neutrino’s mass, but it’s about a 1/6 of a millisecond.

Now let’s think about how the neutrino oscillates.

To keep things simple, let’s assume our electron neutrino gets out of the Sun without anything happening to it. What happens next?

There are three flavors of neutrino—and as it shoots through space, what started as an electron neutrino will ‘oscillate’ between all three flavors, like this:

Here black means electron neutrino, blue means muon neutrino and red means tau neutrino.

You’ll notice that both high-frequency and low-frequency oscillations are going on. This is because the three flavors of neutrino are nontrivial linear combinations of three ‘mass eigenstates’, each of which has a phase that oscillates at a different rate. Two of the mass eigenstates are very close in mass, and this small mass difference causes a small energy difference which causes the slower oscillation. The third mass eigenstate is farther away from the other two, so we also get a more rapid oscillation. As you can see, this is especially noticeable in how the neutrino flickers back and forth between being a muon and a tau neutrino.

But all this is a bit complicated, so let’s just focus on the slower oscillations. How many of those oscillations happen as our friend the neutrino wings its way from Sun to Earth?

To estimate this, let’s pretend there are only the two mass eigenstates that are very close in mass, and ignore the third. The two masses m_1 and m_2 are not actually known very accurately. What we know is

m_2^2 - m_1^2 \approx 0.000074 \; \textrm{eV}^2/c^4

The reason we know these differences in squares of mass is actually by doing measurements of neutrino oscillations: these differences actually determine the frequency of the neutrino oscillations! Let’s see why.

If something has energy E, quantum mechanics says its phase will oscillate over time like this:

\exp(-i t E / \hbar)

where \hbar is Planck’s constant and the minus sign is just an unfortunate convention. But all we detect is the absolute value of this, which is just 1: that doesn’t change. So to actually see oscillations we should think about something that can have two different energies E_1 and E_2. Then we need to think about things like

\exp(-i t E_1 / \hbar) - \exp(-i t E_2 / \hbar)

or other linear combinations of these two functions. But their difference illustrates the point nicely: we have

\exp(-i t E_1 / \hbar) - \exp(-i t E_2 / \hbar) =

\exp(-i t E_1) (1 - \exp(-it (E_2 - E_1)/\hbar)

and the absolute value of this changes with time! It’s

| 1 - \exp(-it (E_2 - E_1)/\hbar)|

and the takeaway message here is that it oscillates at a frequency depending on the energy difference,

\omega = (E_2 - E_1) / \hbar

So, if we have two kinds of neutrino, it’s the energy difference of the two mass eigenstates that determines how fast a superposition of these two will oscillate. It’s very similar to how when two piano strings are oscillating at almost but not quite the same frequency, you’ll hear ‘beats’ as they go in and out of phase—and the frequency of these beats depends on the difference of their piano strings’ frequencies.

So energy differences are what we care about. But how is energy related to mass? In units where the speed of light is 1, special relativity tells us this:

E^2 = m^2 + p^2

where m is mass and p is momentum. One of the mind-blowing moments of my early physics education was watching someone do a Taylor expansion for low momenta and getting this:

\displaystyle{ E = \sqrt{m^2 + p^2} \approx m + \frac{p^2}{2m} + \cdots }

It looks more impressive if you don’t set the speed of light c equal to 1:

\displaystyle{ E = \sqrt{m^2c^4 + p^2c^2} \approx mc^2 + \frac{p^2}{2m} + \cdots }

So we see that at low momenta the energy is Einstein’s famous E = mc^2 plus the kinetic energy p^2/2m famous from classical mechanics before relativity!

But all this is useless for our solar neutrino, which is ‘ultra-relativistic’: it’s moving almost at the speed of light! Now p^2 is much bigger than m^2, not smaller, in units where c = 1. So we should do a different Taylor expansion, where we treat m^2 as the small perturbation:

\displaystyle{ E = \sqrt{p^2 + m^2} \approx p + \frac{m^2}{2p} + \cdots }

Cute, eh? Everything is backwards from what I learned in school: we just switch m and p.

This shows us that if we have a neutrino with some large momentum p and it’s a linear combination of two different mass eigenstates with masses m_1 and m_2, it’ll be a blend of two energies:

\displaystyle{ E_1 = \sqrt{p^2 + m_1^2} \approx p + \frac{m_1^2}{2p} + \cdots }

and

\displaystyle{ E_2 = \sqrt{p^2 + m_2^2} \approx p + \frac{m_2^2}{2p} + \cdots }

So, the energy difference is

\displaystyle{E_2 - E_1 = \frac{1}{2 p} (m_2^2 - m_1^2) }

and this is what determines the rate at which the neutrino oscillates.

If we stop working in units where c = 1 we get

\displaystyle{E_2 - E_1 = \frac{c^3}{2 p} (m_2^2 - m_1^2) }

So, the frequency of oscillations is

\displaystyle{\omega = (E_2 - E_1) / \hbar = \frac{c^3}{2 \hbar p}  (m_2^2 - m_1^2) }

This frequency says how the relative phase rotates around in radians per second. But it’s more useful to think about radians per distance traveled; let’s call that k. Since our neutrino is moving at almost the speed of light, to get this we just divide by c.

\displaystyle{k = \frac{c^2}{2 \hbar p}  (m_2^2 - m_1^2) }

And because the neutrino is ultra-relativistic, its momentum almost obeys E = p c. Here E could be either E_1 or E_2; they’re so close the difference doesn’t matter here. So we get

\displaystyle{k = \frac{c^3}{2 \hbar E}  (m_2^2 - m_1^2) }

This is why people doing experiments with neutrino oscillations measure differences of squares of neutrino masses, not neutrino masses.

For our solar neutrino we’re assuming

E = 300 \; \mathrm{keV}

and remember

m_2^2 - m_1^2 \approx 0.000074 \; \textrm{eV}^2/c^4

Plugging these in we get

\displaystyle{k = \frac{1}{2 \hbar c} \frac{0.000074 \; \textrm{eV}}{300,000}  }

Now it gets annoying, and this is where I usually make mistakes. We use

c = 3 \cdot 10^8 \; \textrm{meter} / \textrm{second}

\hbar =  1.05 \cdot 10^{-34} \; \textrm{kilogram} \, \textrm{meter}^2 / \textrm{second}

\textrm{eV} = 1.60 \cdot 10^{-19} \; \textrm{kilogram} \, \textrm{meter}^2 / \textrm{second}^2

and get

\displaystyle{ k \approx \frac{1}{1600 \; \textrm{meter}} }

It’s funny how multiplying and dividing all these large and tiny numbers leaves us with something at the human scale!

But actually my computation was sloppy at one point. I warned you! I think it’s actually off by a factor of two. Wikipedia says right answer is

\displaystyle{k = \frac{c^3}{4 \hbar E}  (m_2^2 - m_1^2) }

and this gives

\displaystyle{ k \approx \frac{1}{3200 \; \textrm{meter}} }

So, the neutrino oscillates at a rate of about one radian every 3200 meters! And to get the wavelength of the oscillation we need to multiply by 2 \pi. So our solar neutrino makes a complete oscillation about once every 20 kilometers!

And the distance from the Earth to the Sun is 150 million kilometers. So, our neutrino oscillates about 7.5 million times on its trip here.

You should take all this with a grain of salt since I easily could have made some mistakes. If you find errors please let me know! I leave you with a puzzle:

Puzzle. Where does the missing factor of 2 come from?

I don’t think you need to know fancy physics to solve this. I think the mistake is visible in my calculations.


Neutrino Puzzles (Part 2)

26 December, 2020

Okay, I’ve drafted an update to my list of open questions in physics.

I eliminated a bunch of questions that seem to have been answered. It’s really remarkable how accelerator experiments in the last decade or so have settled questions in particle physics without discovering any new mysterious phenomena. The really big mysteries remain.

I have not gotten around to adding the new questions about black holes raised by LIGO. I have not gotten around to updating the sections on ultra-high energy cosmic rays or gamma ray bursters, both of which sorely need it. But I have updated the section on neutrinos!

Here’s the new version. I still need some more good new general reviews of neutrino experiments and theoretical questions. Do you know some?

What’s going on with neutrinos?  Why are all the 3 flavors of neutrino—called the electron neutrino, the muon neutrino and the tau neutrino—so much lighter than their partners, the electron, muon, and tau?  Why are the 3 flavors of neutrino so different from the 3 neutrino states that have a definite mass?  Could any of the observed neutrinos be their own antiparticles?  Do there exist right-handed neutrinos—that is, neutrinos that spin counterclockwise along their axis of motion even when moving very near the speed of light?  Do there exist other kinds of neutrinos, such as “sterile” neutrinos—that is, neutrinos that don’t interact directly with other particles via the weak (or electromagnetic or strong) force?

Starting in the 1990s, our understanding of neutrinos has dramatically improved, and the puzzle of why we see about 1/3 as many electron neutrinos coming from the sun as naively expected has pretty much been answered: the three different flavors of neutrino—electron, muon and tau—turn into each other, because these flavors are not the same as the three “mass eigenstates”, which have a definite mass.  But the wide variety of neutrino experiments over the last thirty years have opened up other puzzles.

For example, we don’t know the origin of neutrinos’ masses.  Do the observed left-handed neutrinos get their mass by coupling to the Higgs and a right-handed partner, the way the other quarks and leptons do?  This would require the existence of so-far-unseen right-handed neutrinos.  Do they get their mass by coupling to themselves?  This could happen if they are “Majorana fermions“: that is, their own antiparticles.  They could also get a mass in other, even more exciting ways, like the “seesaw mechanism“. This requires them to couple to a very massive right-handed particle, and could explain their very light masses.

Even what we’ve actually observed raises puzzles.  With many experiments going on, there are often “anomalies”, but many of these go away after more careful study.  Here’s a challenge that won’t just go away with better data: the 3×3 matrix relating the 3 flavors of neutrino to the 3 neutrino mass eigenstates, called the Pontecorvo–Maki–Nakagawa–Sakata matrix, is much further from the identity matrix than the analogous matrix for quarks, called the Cabibbo–Kobayashi–Maskawa matrix.  In simple terms, this means that each of the three flavors of neutrino is a big mix of different masses.  Nobody knows why these matrices take the values they do, or why they’re so different from each other.

For details, try:

The Neutrino Oscillation Industry.

• John Baez, Neutrinos and the Mysterious Pontevorco–Maki–Nakagawa–Sakata Matrix.

• Paul Langacker, Implications of Neutrino Mass.

• A. Baha Balantekin and Boris Kayser, On the Properties of Neutrinos.

• Salvador Centelles Chuliá, Rahul Srivastava and José W. F. Valle, Seesaw Roadmap to Neutrino Mass and Dark Matter.

The first of these has lots of links to the web pages of research groups doing experiments on neutrinos.  It’s indeed a big industry!