Concept# Galois connection

Summary

In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the fundamental theorem of Galois theory about the correspondence between subgroups and subfields, discovered by the French mathematician Évariste Galois.
A Galois connection can also be defined on preordered sets or classes; this article presents the common case of posets.
The literature contains two closely related notions of "Galois connection". In this article, we will refer to them as (monotone) Galois connections and antitone Galois connections.
A Galois connection is rather weak compared to an order isomorphism between the involved posets, but every Galois connection gives rise to an isomorphism of certain sub-posets, as will be explained below.
The term Galois correspondence is sometimes used to mean a bijective Galois connection; this is s

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (6)

Loading

Loading

Loading

Related people

No results

Related units

No results

Related concepts (25)

Lattice (order)

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a uniqu

Complete lattice

In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is kno

Order theory

Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that

Related courses (3)

MATH-225: Topology

On étudie des notions de topologie générale: unions et quotients d'espaces topologiques; on approfondit les notions de revêtements et de groupe fondamental,et d'attachements de cellules et on démontre le Théorème de Seifert-van Kampen. Des exemples de surfaces illustrent les techniques de calcul.

CS-550: Formal verification

We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to use formal verification tools and explain the theory and the practice behind them.

MATH-215: Rings and fields

C'est un cours introductoire dans la théorie d'anneau et de corps.

Related lectures

Loading

Related lectures (10)

In this paper we study an asymptotically optimal tame tower over the field with p(2) elements introduced by Garcia-Stichtenoth. This tower is related with a modular tower, for which explicit equations were given by Elkies. We use this relation to investigate its Galois closure. Along the way, we obtain information about the structure of the Galois closure of X-0(p(n)) over X-0(p(r)), for integers 1 < r < n and prime p and the Galois closure of other modular towers (X-0(p(n)))n.

We use Masser's counting theorem to prove a lower bound for the canonical height in powers of elliptic curves. We also prove the Galois case of the elliptic Lehmer problem, combining Kummer theory and Masser's result with bounds on the rank and torsion of some groups of rational points on an elliptic curve.

Moran Feldman, Ashkan Norouzi Fard, Ola Nils Anders Svensson, Rico Zenklusen

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model that lies between the offline and streaming model, and study it under the aspect of one-way communication complexity. Our model captures the streaming setting (by considering a large number of players), and, in addition, two player approximation results for it translate into the robust setting. We present tight one-way communication complexity results for our model, which, due to the above-mentioned connections, have multiple implications in the data stream and robust setting. Even for just two players, a prior information-theoretic hardness result implies that no approximation factor above 1/2 can be achieved in our model, if only queries to feasible sets, i.e., sets respecting the cardinality constraint, are allowed. We show that the possibility of querying infeasible sets can actually be exploited to beat this bound, by presenting a tight 2/3-approximation taking exponential time, and an efficient 0.514-approximation. To the best of our knowledge, this is the first example where querying a submodular function on infeasible sets leads to provably better results. Through the above-mentioned link to the robust setting, both of these algorithms improve on the current state-of-the-art for robust submodular maximization, showing that approximation factors beyond 1/2 are possible. Moreover, exploiting the link of our model to streaming, we settle the approximability for streaming algorithms by presenting a tight 1/2 + epsilon hardness result, based on the construction of a new family of coverage functions. This improves on a prior 1 - 1/e + epsilon hardness and matches, up to an arbitrarily small margin, the best known approximation algorithm.