Complement (association theory)

Complementary elements

In a restricted lattice (mathematics) an element is called a complement of if ${\displaystyle b}$ ${\displaystyle a}$

${\displaystyle a\wedge b=0}$ and ${\displaystyle a\vee b=1}$

applies.

A restricted lattice in which every element has (at least) one complement is called a complementary lattice .

In general there can be several complementary elements for one element. If the complement of is unambiguous, different terms are used: it is common for subsets , for applications in logic , for switching algebras . It applies ${\displaystyle a}$ ${\displaystyle a^{\complement }}$ ${\displaystyle \neg a}$ ${\displaystyle {\bar {a}}}$

${\displaystyle \neg 0=1,\neg 1=0}$.

In a distributive bounded lattice, each element can have at most one complement.
If a complement has, then also has a complement, namely ${\displaystyle a}$ ${\displaystyle \neg a}$ ${\displaystyle \neg a}$

${\displaystyle \neg \neg a=a}$.

A distributive complementary lattice is called a Boolean lattice or Boolean algebra .

→ Main article : Boolean algebra

Relative complements

The non-modular association is complementary: and are both complements of . It is not relative-complementary, because the interval has no complement. ${\displaystyle N_{5}}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle a}$
${\displaystyle [0,c]}$ ${\displaystyle b}$

If there are elements of a lattice, then the set is called the interval determined by a and b . The definition is identical to that of a closed interval on ordered sets and the same notation is used. ${\displaystyle a,b}$ ${\displaystyle \left\{x\in V\mid a\leq x\land x\leq b\right\}}$
${\displaystyle [a,b]}$

Are , then the relative complement of relative , if ${\displaystyle c,d\in [a,b]}$ ${\displaystyle d}$ ${\displaystyle c}$ ${\displaystyle [a,b]}$

${\displaystyle c\wedge d=a}$ and applies. ${\displaystyle c\vee d=b}$

Here, too, it applies that there can be several elements that are too complementary and that uniqueness follows from the distributive law. ${\displaystyle [a,b]}$ ${\displaystyle c}$

A lattice is called relatively complementary if there is a relative complement for every element in every interval.

A relatively complementary association is a complementary association if and only if it is restricted. Conversely, a complementary association need not be relatively complementary. However, a modular complementary lattice is relatively complementary.

Relative complements can be used to characterize distributive associations. A lattice is distributive if and only if every element has at most one relative complement in every interval.

Pseudo complements

Rules for pseudo-complements: and can occur ${\displaystyle a<\neg \neg a}$ ${\displaystyle \neg a\vee \neg b<\neg (a\wedge b)}$

Are two members of a federation, then called a greatest element for which applies a relative Pseudokomplement of respect . ${\displaystyle a,b}$ ${\displaystyle c}$ ${\displaystyle a\wedge c\leq b}$ ${\displaystyle a}$ ${\displaystyle b}$

A relative Pseudokomplement of respect is Pseudokomplement of . ${\displaystyle a}$ ${\displaystyle 0}$ ${\displaystyle a}$

A lattice in which there is a pseudo-complement for each element is called a pseudo-complementary lattice. ${\displaystyle a}$

The designation for pseudo complements is not uniform.

properties

If (relative) pseudo complements exist, then they are uniquely determined.

In a distributive association forms an ideal. Hence the existence of pseudo complements in finite distributive lattices is assured. The distributivity is essential: it is not pseudocomplementary. ${\displaystyle \{x\mid a\wedge x=0\}}$ ${\displaystyle M_{3}}$

For pseudo complements does not have to apply, even if the lattice is distributive. But it always is ${\displaystyle \neg \neg a=a}$

${\displaystyle a\leq \neg \neg a}$ and ${\displaystyle \neg \neg \neg a=\neg a}$

One of De Morgan's laws applies to pseudo complements :

${\displaystyle \neg (a\vee b)=\neg a\wedge \neg b}$

For the dual form only applies:

${\displaystyle \neg a\vee \neg b\leq \neg (a\wedge b)}$

A distributive relatively complementary lattice is called Heyting's algebra .

→ Main article : Heyting algebra

Orthocomplements

In a lattice, a function is called orthogonalization if it meets the following conditions: ${\displaystyle k\colon V\to V}$

• ${\displaystyle a\vee a^{k}=1}$ and ${\displaystyle a\wedge a^{k}=0}$
• ${\displaystyle (a^{k})^{k}=a}$
• ${\displaystyle a\leq b\implies b^{k}\leq a^{k}}$,

The lattice (with this illustration) is called the orthocomplementary lattice . is called the orthocomplement of (to this orthogonalization). ${\displaystyle \textstyle a^{k}}$ ${\displaystyle a}$

If there is a distributive complementary lattice , then the complement of is also its only possible orthocomplement. In general, however, one can also have several different orthogonalizations in a distributive lattice. ${\displaystyle V}$ ${\displaystyle a}$

Examples of orthocomplements

• If a Euclidean vector space and a sub-vector space , then the vectors which are to be orthogonal form a vector space . and are orthocomplements in the (modular) lattice of the subspaces of . ${\displaystyle V}$ ${\displaystyle U_{1}}$ ${\displaystyle U}$ ${\displaystyle U_{2}}$ ${\displaystyle U_{1}}$ ${\displaystyle U_{2}}$ ${\displaystyle V}$
• The example of the Euclidean vector spaces can be generalized to any vector spaces with an inner product . Various internal products deliver i. A. Various orthocomplements in the union of the subspaces of . ${\displaystyle V}$

These are typical examples that also led to the naming.

Examples of orthocomplements

This association allows 3 different orthogonalizations.

${\displaystyle T_{30}}$: The normal complement is the only possible orthocomplement. ${\displaystyle \textstyle a^{\complement }={\frac {30}{a}}}$

There is exactly one orthogonalization for this association.

There is no orthogonalization for . ${\displaystyle M_{3}}$

literature

• Gericke Helmuth: Theory of associations . 2nd Edition. BI, Mannheim 1967.
• Grätzer George: Lattice Theory. First concepts and distributive lattices . WHFreeman and Company, 1971, ISBN 978-0-486-47173-0 .

Individual evidence

1. ↑ This follows from the reduction rule
2. ↑ G. Grätzer, Lattice theory, p. 20. In H. Gericke, Theory of Associations, p. 72 the designation is introduced differently . ${\displaystyle b/a}$
3. ↑ G. Grätzer, Lattice theory, p. 96.
4. ↑ The idea of ​​proof is that in and in each case the reduction rule does not apply, cf. H. Gericke, Theory of Associations, p. 113f ${\displaystyle N_{5}}$ ${\displaystyle M_{5}}$
5. ↑ G. Grätzer uses a ^* for the pseudo complement and a * b for the relative pseudo complement (G. Grätzer, Lattice Theory: Foundation, p 99). Gericke uses a mirrored symbol for the designation. (H. Gericke, Theory of Associations, p. 119) Also or occur. ${\displaystyle \neg }$ ${\displaystyle a\rightarrow b}$ ${\displaystyle a\Rightarrow b}$
6. ↑ H. Gericke, Theory of Associations, p. 120 f. Because of these properties, pseudo-complements can be used to model intuitionist logic .
7. ↑ H. Gericke, Theory of Associations, p. 106; however, a clearer designation is used here for the function