Galois connections link two ordered sets through paired functions, forming a powerful tool in lattice theory. They generalize to categories as , with lower adjoints preserving joins and upper adjoints preserving meets.
Closure and interior operators are closely related to Galois connections. Closure operators extend, preserve order, and are idempotent, while interior operators contract, preserve order, and are idempotent. Both have applications in formal concept analysis and data mining.
Galois Connections
Definition and Properties
Top images from around the web for Definition and Properties
GaloisGroupProperties | Wolfram Function Repository View original
Is this image relevant?
GaloisGroupProperties | Wolfram Function Repository View original
GaloisGroupProperties | Wolfram Function Repository View original
Is this image relevant?
GaloisGroupProperties | Wolfram Function Repository View original
Is this image relevant?
1 of 3
establishes a relationship between two partially ordered sets (posets) through a pair of monotone functions
Consists of two functions, typically denoted as f and g, that map between the posets in opposite directions
Satisfies the condition: for all elements x in the first poset and y in the second poset, f(x)≤y if and only if x≤g(y)
Adjoint functors generalize the concept of Galois connections to categories
Given two categories C and D, an adjunction between them consists of a pair of functors F:C→D and G:D→C
F is called the left adjoint and G is called the right adjoint
Lower adjoint (or left adjoint) preserves joins (least upper bounds) and maps elements to their largest possible image in the codomain
Formally, for a Galois connection (f,g) between posets P and Q, f is the lower adjoint if f(⋁X)=⋁f(X) for any subset X⊆P
Upper Adjoint and Residuated Mappings
Upper adjoint (or right adjoint) preserves meets (greatest lower bounds) and maps elements to their smallest possible image in the codomain
Formally, for a Galois connection (f,g) between posets P and Q, g is the upper adjoint if g(⋀Y)=⋀g(Y) for any subset Y⊆Q
Residuated mapping is a generalization of the upper adjoint in a Galois connection
Given a partially ordered set P and a Q, a function f:P→Q is residuated if there exists a function g:Q→P such that for all x∈P and y∈Q, f(x)≤y if and only if x≤g(y)
The function g is called the residual of f and is an upper adjoint
Closure and Interior Operators
Closure Operators
on a partially ordered set P is a function c:P→P that satisfies three properties:
Extensive: x≤c(x) for all x∈P
Monotone: if x≤y, then c(x)≤c(y) for all x,y∈P
Idempotent: c(c(x))=c(x) for all x∈P
Fixed points of a closure operator form a complete lattice
An element x∈P is a fixed point of c if c(x)=x
The set of all fixed points of c is denoted as Fix(c)
Interior Operators
on a partially ordered set P is a function i:P→P that satisfies three properties:
Contractive: i(x)≤x for all x∈P
Monotone: if x≤y, then i(x)≤i(y) for all x,y∈P
Idempotent: i(i(x))=i(x) for all x∈P
Closure and interior operators are dual notions
If c is a closure operator on P, then the function i(x)=⋁{y∈P∣c(y)≤x} is an interior operator on P
Conversely, if i is an interior operator on P, then the function c(x)=⋀{y∈P∣x≤i(y)} is a closure operator on P
Applications
Concept Lattices and Formal Concept Analysis
Concept lattices arise from the application of Galois connections to formal concept analysis (FCA)
FCA is a mathematical framework for analyzing the relationships between objects and their attributes
Starts with a formal context (G,M,I), where G is a set of objects, M is a set of attributes, and I⊆G×M is a binary relation indicating which objects have which attributes
Galois connection between the power sets of objects and attributes induces a concept lattice
For a formal context (G,M,I), define two functions f:2G→2M and g:2M→2G as follows:
f(A)={m∈M∣(g,m)∈I for all g∈A}
g(B)={g∈G∣(g,m)∈I for all m∈B}
The pair (f,g) forms a Galois connection between (2G,⊆) and (2M,⊇)
The fixed points of the composite functions f∘g and g∘f are called formal concepts and form a complete lattice, known as the concept lattice of the formal context
Concept lattices have applications in various domains, such as:
Knowledge representation and ontology engineering
Data mining and machine learning (e.g., association rule mining, clustering)