Involution (mathematics)

From Wikipedia for FEVERv2
Jump to navigation Jump to search

For the archaic use of this term, see exponentiation. Involution (mathematics)_sentence_0

In mathematics, an involution, or an involutory function, is a function f that is its own inverse, Involution (mathematics)_sentence_1

Involution (mathematics)_description_list_0

  • f(f(x)) = xInvolution (mathematics)_item_0_0

for all x in the domain of f. Equivalently, applying f twice produces the original value. Involution (mathematics)_sentence_2

The term anti-involution refers to involutions based on antihomomorphisms (see § Quaternion algebra, groups, semigroups below) Involution (mathematics)_sentence_3

Involution (mathematics)_description_list_1

  • f(xy) = f(y) f(x)Involution (mathematics)_item_1_1

such that Involution (mathematics)_sentence_4

Involution (mathematics)_description_list_2

  • xy = f(f(xy)) = f( f(y) f(x) ) = f(f(x)) f(f(y)) = xy.Involution (mathematics)_item_2_2

General properties Involution (mathematics)_section_0

Any involution is a bijection. Involution (mathematics)_sentence_5

The identity map is a trivial example of an involution. Involution (mathematics)_sentence_6

Common examples in mathematics of nontrivial involutions include multiplication by −1 in arithmetic, the taking of reciprocals, complementation in set theory and complex conjugation. Involution (mathematics)_sentence_7

Other examples include circle inversion, rotation by a half-turn, and reciprocal ciphers such as the ROT13 transformation and the Beaufort polyalphabetic cipher. Involution (mathematics)_sentence_8

The number of involutions, including the identity involution, on a set with n = 0, 1, 2, ... elements is given by a recurrence relation found by Heinrich August Rothe in 1800: Involution (mathematics)_sentence_9

The first few terms of this sequence are 1, 1, 2, 4, 10, 26, 76, 232 (sequence in the OEIS); these numbers are called the telephone numbers, and they also count the number of Young tableaux with a given number of cells. Involution (mathematics)_sentence_10

The composition g ∘ f of two involutions f and g is an involution if and only if they commute: g ∘ f = f ∘ g. Involution (mathematics)_sentence_11

Every involution on an odd number of elements has at least one fixed point. Involution (mathematics)_sentence_12

More generally, for an involution on a finite set of elements, the number of elements and the number of fixed points have the same parity. Involution (mathematics)_sentence_13

Involution throughout the fields of mathematics Involution (mathematics)_section_1

Pre-calculus Involution (mathematics)_section_2

Basic examples of involutions are the functions: Involution (mathematics)_sentence_14

These are not the only pre-calculus involutions. Involution (mathematics)_sentence_15

Another one within the positive reals is: Involution (mathematics)_sentence_16

Other elementary involutions are useful in solving functional equations. Involution (mathematics)_sentence_17

Euclidean geometry Involution (mathematics)_section_3

A simple example of an involution of the three-dimensional Euclidean space is reflection through a plane. Involution (mathematics)_sentence_18

Performing a reflection twice brings a point back to its original coordinates. Involution (mathematics)_sentence_19

Another involution is reflection through the origin; not a reflection in the above sense, and so, a distinct example. Involution (mathematics)_sentence_20

These transformations are examples of affine involutions. Involution (mathematics)_sentence_21

Projective geometry Involution (mathematics)_section_4

An involution is a projectivity of period 2, that is, a projectivity that interchanges pairs of points. Involution (mathematics)_sentence_22

Involution (mathematics)_unordered_list_3

  • Any projectivity that interchanges two points is an involution.Involution (mathematics)_item_3_3
  • The three pairs of opposite sides of a complete quadrangle meet any line (not through a vertex) in three pairs of an involution. This theorem has been called Desargues's Involution Theorem. Its origins can be seen in Lemma IV of the lemmas to the Porisms of Euclid in Volume VII of the Collection of Pappus of Alexandria.Involution (mathematics)_item_3_4
  • If an involution has one fixed point, it has another, and consists of the correspondence between harmonic conjugates with respect to these two points. In this instance the involution is termed "hyperbolic", while if there are no fixed points it is "elliptic". In the context of projectivities, fixed points are called double points.Involution (mathematics)_item_3_5

Another type of involution occurring in projective geometry is a polarity which is a correlation of period 2. Involution (mathematics)_sentence_23

Linear algebra Involution (mathematics)_section_5

Further information: Involutory matrix Involution (mathematics)_sentence_24

For example, suppose that a basis for a vector space V is chosen, and that e1 and e2 are basis elements. Involution (mathematics)_sentence_25

There exists a linear transformation f which sends e1 to e2, and sends e2 to e1, and which is the identity on all other basis vectors. Involution (mathematics)_sentence_26

It can be checked that f(f(x)) = x for all x in V. That is, f is an involution of V. Involution (mathematics)_sentence_27

For a specific basis, any linear operator can be represented by a matrix T. Every matrix has a transpose, obtained by swapping rows for columns. Involution (mathematics)_sentence_28

This transposition is an involution on the set of matrices. Involution (mathematics)_sentence_29

The definition of involution extends readily to modules. Involution (mathematics)_sentence_30

Given a module M over a ring R, an R endomorphism f of M is called an involution if f  is the identity homomorphism on M. Involution (mathematics)_sentence_31

Involutions are related to idempotents; if 2 is invertible then they correspond in a one-to-one manner. Involution (mathematics)_sentence_32

Quaternion algebra, groups, semigroups Involution (mathematics)_section_6

An anti-involution does not obey the last axiom but instead Involution (mathematics)_sentence_33

This former law is sometimes called antidistributive. Involution (mathematics)_sentence_34

It also appears in groups as (xy) = yx. Involution (mathematics)_sentence_35

Taken as an axiom, it leads to the notion of semigroup with involution, of which there are natural examples that are not groups, for example square matrix multiplication (i.e. the full linear monoid) with transpose as the involution. Involution (mathematics)_sentence_36

Ring theory Involution (mathematics)_section_7

Further information: *-algebra Involution (mathematics)_sentence_37

In ring theory, the word involution is customarily taken to mean an antihomomorphism that is its own inverse function. Involution (mathematics)_sentence_38

Examples of involutions in common rings: Involution (mathematics)_sentence_39

Involution (mathematics)_unordered_list_4

Group theory Involution (mathematics)_section_8

In group theory, an element of a group is an involution if it has order 2; i.e. an involution is an element a such that a ≠ e and a = e, where e is the identity element. Involution (mathematics)_sentence_40

Originally, this definition agreed with the first definition above, since members of groups were always bijections from a set into itself; i.e., group was taken to mean permutation group. Involution (mathematics)_sentence_41

By the end of the 19th century, group was defined more broadly, and accordingly so was involution. Involution (mathematics)_sentence_42

A permutation is an involution precisely if it can be written as a product of one or more non-overlapping transpositions. Involution (mathematics)_sentence_43

The involutions of a group have a large impact on the group's structure. Involution (mathematics)_sentence_44

The study of involutions was instrumental in the classification of finite simple groups. Involution (mathematics)_sentence_45

An element x of a group G is called strongly real if there is an involution t with x = x (where x = t⋅x⋅t). Involution (mathematics)_sentence_46

Coxeter groups are groups generated by involutions with the relations determined only by relations given for pairs of the generating involutions. Involution (mathematics)_sentence_47

Coxeter groups can be used, among other things, to describe the possible regular polyhedra and their generalizations to higher dimensions. Involution (mathematics)_sentence_48

Mathematical logic Involution (mathematics)_section_9

The operation of complement in Boolean algebras is an involution. Involution (mathematics)_sentence_49

Accordingly, negation in classical logic satisfies the law of double negation: ¬¬A is equivalent to A. Involution (mathematics)_sentence_50

Generally in non-classical logics, negation that satisfies the law of double negation is called involutive. Involution (mathematics)_sentence_51

In algebraic semantics, such a negation is realized as an involution on the algebra of truth values. Involution (mathematics)_sentence_52

Examples of logics which have involutive negation are Kleene and Bochvar three-valued logics, Łukasiewicz many-valued logic, fuzzy logic IMTL, etc. Involutive negation is sometimes added as an additional connective to logics with non-involutive negation; this is usual, for example, in t-norm fuzzy logics. Involution (mathematics)_sentence_53

The involutiveness of negation is an important characterization property for logics and the corresponding varieties of algebras. Involution (mathematics)_sentence_54

For instance, involutive negation characterizes Boolean algebras among Heyting algebras. Involution (mathematics)_sentence_55

Correspondingly, classical Boolean logic arises by adding the law of double negation to intuitionistic logic. Involution (mathematics)_sentence_56

The same relationship holds also between MV-algebras and BL-algebras (and so correspondingly between Łukasiewicz logic and fuzzy logic BL), IMTL and MTL, and other pairs of important varieties of algebras (resp. corresponding logics). Involution (mathematics)_sentence_57

In the study of binary relations, every relation has a converse relation. Involution (mathematics)_sentence_58

Since the converse of the converse is the original relation, the conversion operation is an involution on the category of relations. Involution (mathematics)_sentence_59

Binary relations are ordered through inclusion. Involution (mathematics)_sentence_60

While this ordering is reversed with the complementation involution, it is preserved under conversion. Involution (mathematics)_sentence_61

Computer science Involution (mathematics)_section_10

The XOR bitwise operation with a given value for one parameter is an involution. Involution (mathematics)_sentence_62

XOR masks were once used to draw graphics on images in such a way that drawing them twice on the background reverts the background to its original state. Involution (mathematics)_sentence_63

The NOT bitwise operation is also an involution, and is a special case of the XOR operation where one parameter has all bits set to 1. Involution (mathematics)_sentence_64

Another example is a bit mask and shift function operating on color values stored as integers, say in the form RGB, that swaps R and B, resulting in the form BGR. Involution (mathematics)_sentence_65

f(f(RGB))=RGB, f(f(BGR))=BGR. Involution (mathematics)_sentence_66

The RC4 cryptographic cipher is an involution, as encryption and decryption operations use the same function. Involution (mathematics)_sentence_67

Practically all mechanical cipher machines implement a reciprocal cipher, an involution on each typed-in letter. Involution (mathematics)_sentence_68

Instead of designing two kinds of machines, one for encrypting and one for decrypting, all the machines can be identical and can be set up (keyed) the same way. Involution (mathematics)_sentence_69

See also Involution (mathematics)_section_11

Involution (mathematics)_unordered_list_5

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: (mathematics).