Movatterモバイル変換

[0]ホーム

Jump to content

Binary operation

Edit links

From Wikipedia, the free encyclopedia

Mathematical operation with two operands

Not to be confused withBitwise operation.

A binary operation $\circ$ is a rule for combining the arguments $x {\displaystyle x}$ and $y {\displaystyle y}$ to produce $x\circ y$

{\displaystyle \circ } — A binary operation $\circ$ is a rule for combining the arguments $x {\displaystyle x}$ and $y {\displaystyle y}$ to produce $x\circ y$

Inmathematics, abinary operation ordyadic operation is a rule for combining twoelements (calledoperands) to produce another element. More formally, a binary operation is anoperation ofarity two.

More specifically, abinary operation on aset is abinary function that maps everypair of elements of the set to an element of the set. Examples include the familiararithmetic operations likeaddition,subtraction,multiplication, set operations like union, complement, intersection. Other examples are readily found in different areas of mathematics, such asvector addition,matrix multiplication, andconjugation in groups.

A binary function that involves several sets is sometimes also called abinary operation. For example,scalar multiplication ofvector spaces takes a scalar and a vector to produce a vector, andscalar product takes two vectors to produce a scalar.

Binary operations are the keystone of moststructures that are studied inalgebra, in particular insemigroups,monoids,groups,rings,fields, andvector spaces.

Terminology

[edit]

More precisely, a binary operation on aset $S {\displaystyle S}$ is amapping of the elements of theCartesian product $S\times S$ to $S {\displaystyle S}$ :^[1]^[2]^[3]

\,f\colon S\times S\rightarrow S.

If $f {\displaystyle f}$ is not afunction but apartial function, then $f {\displaystyle f}$ is called apartial binary operation. For instance, division is a partial binary operation on the set of allreal numbers, because one cannotdivide by zero: ${\frac {a}{0}}$ is undefined for every real number $a {\displaystyle a}$ . In bothmodel theory and classicaluniversal algebra, binary operations are required to be defined on all elements of $S\times S$ . However,partial algebras^[4] generalizeuniversal algebras to allow partial operations.

Sometimes, especially incomputer science, the term binary operation is used for anybinary function.

Properties and examples

[edit]

Typical examples of binary operations are theaddition ( $+$ ) andmultiplication ( $\times$ ) ofnumbers andmatrices as well ascomposition of functions on a single set.For instance,

On the set of real numbers $\mathbb {R}$ , $f(a,b)=a+b$ is a binary operation since the sum of two real numbers is a real number.
On the set of natural numbers $\mathbb {N}$ , $f(a,b)=a+b$ is a binary operation since the sum of two natural numbers is a natural number. This is a different binary operation than the previous one since the sets are different.
On the set $M(2,\mathbb {R} )$ of $2\times 2$ matrices with real entries, $f(A,B)=A+B$ is a binary operation since the sum of two such matrices is a $2\times 2$ matrix.
On the set $M(2,\mathbb {R} )$ of $2\times 2$ matrices with real entries, $f(A,B)=AB$ is a binary operation since the product of two such matrices is a $2\times 2$ matrix.
For a given set $C {\displaystyle C}$ , let $S {\displaystyle S}$ be the set of all functions $h\colon C\rightarrow C$ . Define $f\colon S\times S\rightarrow S$ by $f(h_{1},h_{2})(c)=(h_{1}\circ h_{2})(c)=h_{1}(h_{2}(c))$ for all $c\in C$ , the composition of the two functions $h_{1}$ and $h_{2}$ in $S {\displaystyle S}$ . Then $f {\displaystyle f}$ is a binary operation since the composition of the two functions is again a function on the set $C {\displaystyle C}$ (that is, a member of $S {\displaystyle S}$ ).

Many binary operations of interest in both algebra and formal logic arecommutative, satisfying $f(a,b)=f(b,a)$ for all elements $a {\displaystyle a}$ and $b {\displaystyle b}$ in $S {\displaystyle S}$ , orassociative, satisfying $f(f(a,b),c)=f(a,f(b,c))$ for all $a {\displaystyle a}$ , $b {\displaystyle b}$ , and $c {\displaystyle c}$ in $S {\displaystyle S}$ . Many also haveidentity elements andinverse elements.

The first three examples above are commutative and all of the above examples are associative.

On the set of real numbers $\mathbb {R}$ ,subtraction, that is, $f(a,b)=a-b$ , is a binary operation which is not commutative since, in general, $a-b\neq b-a$ . It is also not associative, since, in general, $a-(b-c)\neq (a-b)-c$ ; for instance, $1-(2-3)=2$ but $(1-2)-3=-4$ .

On the set of natural numbers $\mathbb {N}$ , the binary operationexponentiation, $f(a,b)=a^{b}$ , is not commutative since, $a^{b}\neq b^{a}$ (cf.Equation x^y = y^x), and is also not associative since $f(f(a,b),c)\neq f(a,f(b,c))$ . For instance, with $a=2$ , $b=3$ , and $c=2$ , $f(2^{3},2)=f(8,2)=8^{2}=64$ , but $f(2,3^{2})=f(2,9)=2^{9}=512$ . By changing the set $\mathbb {N}$ to the set of integers $\mathbb {Z}$ , this binary operation becomes a partial binary operation since it is now undefined when $a=0$ and $b {\displaystyle b}$ is any negative integer. For either set, this operation has aright identity (which is $1 {\displaystyle 1}$ ) since $f(a,1)=a$ for all $a {\displaystyle a}$ in the set, which is not anidentity (two sided identity) since $f(1,b)\neq b$ in general.

Division ( $\div$ ), a partial binary operation on the set of real or rational numbers, is not commutative or associative.Tetration ( $\uparrow \uparrow$ ), as a binary operation on the natural numbers, is not commutative or associative and has no identity element.

Notation

[edit]

Binary operations are often written usinginfix notation such as $a\ast b$ , $a+b$ , $a\cdot b$ or (byjuxtaposition with no symbol) $a b {\displaystyle ab}$ rather than by functional notation of the form $f(a,b)$ . Powers are usually also written without operator, but with the second argument assuperscript.

Binary operations are sometimes written using prefix or postfix notation, both of which dispense with parentheses. They are also called, respectively,Polish notation $\ast ab$ andreverse Polish notation $ab\ast$ .

Binary operations as ternary relations

[edit]

A binary operation $f {\displaystyle f}$ on a set $S {\displaystyle S}$ may be viewed as aternary relation on $S {\displaystyle S}$ , that is, the set of triples $(a,b,f(a,b))$ in $S\times S\times S$ for all $a {\displaystyle a}$ and $b {\displaystyle b}$ in $S {\displaystyle S}$ .

Other binary operations

[edit]

For example,scalar multiplication inlinear algebra. Here $K {\displaystyle K}$ is afield and $S {\displaystyle S}$ is avector space over that field.

Also thedot product of two vectors maps $S\times S$ to $K {\displaystyle K}$ , where $K {\displaystyle K}$ is a field and $S {\displaystyle S}$ is a vector space over $K {\displaystyle K}$ . It depends on authors whether it is considered as a binary operation.

Notes

[edit]

^Rotman 1973, pg. 1
^Hardy & Walker 2002, pg. 176, Definition 67
^Fraleigh 1976, pg. 10
^George A. Grätzer (2008).Universal Algebra (2nd ed.). Springer Science & Business Media. Chapter 2. Partial algebras.ISBN 978-0-387-77487-9.

References

[edit]

Fraleigh, John B. (1976),A First Course in Abstract Algebra (2nd ed.), Reading: Addison-Wesley,ISBN 0-201-01984-1
Hall, Marshall Jr. (1959),The Theory of Groups, New York: Macmillan
Hardy, Darel W.;Walker, Carol L. (2002),Applied Algebra: Codes, Ciphers and Discrete Algorithms, Upper Saddle River, NJ: Prentice-Hall,ISBN 0-13-067464-8
Rotman, Joseph J. (1973),The Theory of Groups: An Introduction (2nd ed.), Boston: Allyn and Bacon

External links

[edit]

Weisstein, Eric W."Binary Operation".MathWorld.

v
t
e

Mathematical logic

General

Theorems
(list),
paradoxes

Logics

Traditional	Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram
Propositional	Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞
Predicate	First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus

Set theory

Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities
Types ofsets	Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann
Maps, cardinality	Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary
Theories	Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive