One-digit link

from Wikipedia, the free encyclopedia

A one- digit link (also unary or monadic link) is a link with only one operand in mathematics . A simple example of a one-digit combination is the unary minus to form the opposite of a number. One-digit links are usually viewed as functions on a given set . They are used in algebra , logic and computer science , among others .

definition

A one-digit link on a set is a self-mapping

.

The pair is then also called single-digit algebra or chain . The one-digit link is the associated structure mapping.

notation

One-digit links are noted in different ways.

  • The quotation as a function. This is the name commonly used in mathematics. The function sign precedes the argument to which the function is applied. For example: . If it is clear what the function sign and what the argument is, you can do without brackets. This is the case, for example, with the root function.
  • The prefix notation . This is actually nothing different from the function notation described above. The function sign precedes the argument. In some programming languages ​​this is done consistently. For example in Lisp .
  • The postfix notation . The function sign is behind the argument.
  • The use of diacritics .

Examples

Examples of single-digit links are:

  • (Negation, formation of the opposite number of a number ). This is an example of prefix notation.
  • ( Factorial of a natural number ). This is an example of Postfix notation.
  • ( Squaring a real number )
  • : If the set of complex numbers, the function is a one-digit combination of . The function value of is called. ( Conjugation of a complex number ). This is an example of the use of diacritical marks.

history

Richard Dedekind , in his paper from 1887 "What are and what should the numbers" examine quantities together with a self-mapping . So, using the language of this article, he is examining sets with a one-digit association. He calls a lot a system. A subset for which he calls a chain . is therefore complete compared to the operation . The crowd is itself a chain.

Perhaps Dedekind had the following idea when he chose the name chain. If you start at and apply the self-mapping over and over again , you get a track or chain.

In order to examine these chains he developed a considerable part of today's multilingual language. This is how he explains what intersection and union of sets is. Each subset is contained in a smallest sub-chain of . This is the substring of created by . The principle of complete induction now says: Together with the one-digit link, let it be a chain generated by the subset . To show that every element has a property , it must be shown:

  1. Every element from has this property.
  2. The set of all elements with the property is closed with respect to one another.

Up to this point there is no special property of the natural numbers.

He elegantly defines what an infinite amount is. A set is called infinite if there is an injective but not a surjective function . From the existence of an infinite set he then deduces the existence of the set of natural numbers with the operations . Peano took up this a short time later.

use

In algebra , one-digit links are often used when defining algebraic structures . A group is defined as a tuple consisting of a carrier set , a two-digit link , a one- element (this is a zero-digit link ) and a single-digit link that assigns the associated inverse element to a group element .

In logic , the negation of a statement is an important one-digit association.

In programming languages , a number of single-digit links are often provided as ready-made functions. Examples in the C programming language are:

Lower chains

  • A subset of the chain is called a sub-chain of if it is closed opposite . That is .
  • The intersection and union of sub-chains is a sub-chain.
  • Each subset is contained in a smallest subchain of , which contains. It is called the sub-chain created by and is referred to in this article with . For the substring created by this element is also written briefly instead of .
  • Is there in the chain such that , it is said: is generated by an element.

Morphisms

If there are chains with the structural mappings, then a map is called a morphism if it applies.

  • Identity is always a morphism.
  • If there are chains and morphisms, then there is a morphism.
One says the class of the chains together with the morphisms form a category. In the book by F. William Lawvere and Stephen H. Schanuel "Conceptual Mathematics" this is called the category of endomaps. In this article it will be referred to as the category of chains.
A morphism of chains

In the picture we have the chain and the structure map . In addition, the chain with the structure illustration . If you go one step further in the top line and then click over , you get the same thing as if you first translate with and then continue with . The pattern repeats itself from the pair onwards . You can see there is exactly one second morphism . And the morphism with .

  • Two chains are called isomorphic if there is a morphism that is bijective as a mapping. The inverse mapping is then also a morphism.

Dedekind's recursion theorem

Simply infinite amount

A chain with an injective is simply called infinite , if there is one with and it is . It is by generated. With these terms applies:

Theorem : The following statements are equivalent:
  1. There is a simplest infinite set.
  2. There is a chain and such that the Peano axioms are fulfilled. These are:
    1. .
    2. is injective.
    3. Every subset completed opposite , with is already the same .

Note: This formulation is mainly from Richard Dedekind. If you look under the term Peano axioms , they are a little different.

  • But 1. and 2. of the formulation there is called is a chain.
  • 3. stated in the wording there .
  • 4. states that is injective.
  • 5. the formulation there is our statement 3.

If you choose the above formulation, it is initially still completely unclear whether there are not essentially different simply infinite sets. For example, choose a rotation around a certain angle as the plane and as the structure mapping.

Recursion sentence

Sentence: (Dedekind recursion sentence 1887)
If the set is simply infinite, then:
For every chain and every there is exactly one morphism with .
Conclusion: Any two simply infinite chains are isomorphic. That is, there is isomorphism between the chains. They are especially equally powerful as sets.

Algebraic structure of natural numbers

The addition

One chooses a simply infinite set and calls it N. The structure map should be denoted by 1+. The generating element hot 0. Then can be defined with the Recursion Theorem: For every there is exactly one morphism with . Look at the drawing.

The number n is added to a

Basically, it's the addition of two numbers with the help of meter sticks. You put two meter sticks on top of each other and move the upper one by a. If you want to find out what is, read under b - where the green arrow points - on the lower meter stick.

The following theorem applies:

Sentence: The figure defined above has the following properties.

  1. For everyone is . So the image is the identity.
  2. For everyone is .
  3. For everyone is .
  4. The following applies to everyone : is , so is .

The symbol should remind of sum. And so the sentence becomes more familiar if we use the usual character and put it between the arguments.

Sentence: The figure has the following properties.

  1. For everyone is .
  2. For all is .
  3. For all is .
  4. The following applies to everyone : is , so is .

The second formulation has the advantage of familiarity. It has the disadvantage that it hides the freedoms that one still has. The first formulation applies to any simply infinite amount. Also on one with a completely different structure mapping.

In summary one says: is a commutative regular monoid

The multiplication

We now write the usual character between the arguments. So instead of . The image

makes a chain .
The multiplication by 2 is shown in an arrow diagram

Therefore there is exactly one morphism with . It is then . And it is . We see exactly what is naively meant by multiplying by a number . is added to itself. If we write for , then the following theorem applies:

Sentence:
  1. for everyone .
  2. for everyone .
  3. for everyone .
  4. for everyone .
  5. for everyone .
  6. for everyone .
  7. Is , so is or .

Properties 1) to 6) are summarized when one says is a commutative half-ring with a neutral element . This is the most important half-ring of all. These procedures can be continued and this is how exposure occurs . Note that the natural numbers were never used as cardinal numbers in the whole construction. It's the pure counting numbers. But not counting in the sense of counting the number of a set, but simply in the sense of reciting the numerals in an orderly manner.

See also

literature

  • Richard Dedekind: What are and what are the numbers . Vieweg, 1965.
  • Hartmut Ernst: Basic course in computer science . Springer, 2013, ISBN 978-3-322-91968-7 , pp. 266 .
  • Ulrich Knauer, Kolja Knauer: Discrete and Algebraic Structures - In Brief . Springer, 2015, ISBN 978-3-662-45177-9 , pp. 141 .
  • F. William Lawvere, Stephan H. Schanuel: Conceptual Mathematics A first introduction to categories . 2009, ISBN 978-0-521-71916-2 .

Individual evidence

  1. Richard Dedekind "What are and what are the numbers"
  2. See the book by F, William Lawvere, and Stephen H. Schanuel

Web links