Googology Wiki
Register
Advertisement
Googology Wiki

View full site to see MathJax equation

Addition is an elementary binary operation, written \(a + b\) (pronounced "\(a\) plus \(b\)"). It can be informally defined as the total number of objects when \(a\) objects are combined with \(b\) more. Formally, on finite real and cardinal numbers (but not on ordinals), it means the cardinality of a set formed by the union of two disjoint sets with cardinalities \(a\) and \(b\). \(a\) and \(b\) are called the summands, and \(a + b\) is called the sum.

On natural numbers, addition can be defined recursively using the successor function denoted by \(S(n)\):

\begin{eqnarray*} a+0 & = & a \\ a+S(b) & = & S(a+b) \end{eqnarray*}

In googology, it is the first hyper operator, and forms the basis of all following hyper operators.

Addition is commutative on \(\mathbb{N}\) and \(\mathbb{R}\): \(a + b = b + a\) for all natural or real values of \(a\) and \(b\). It is also associative, meaning that \((a + b) + c = a + (b + c)\). Repeated addition is called multiplication.

However, addition is not commutative on ordinals. For any limit ordinal \(\alpha\), \(1+\alpha = \alpha \neq \alpha+1\).

Zero is the additive identity, meaning that \(0 + n = n\) for all \(n\).

In other notations[]

Notation Representation
Up-arrow notation \(a \uparrow^{-1} b\)
Fast-growing hierarchy \(f_0^b(a)\)
Hardy hierarchy \(H_{b}(a)\)
Slow-growing hierarchy \(g_{\omega+b}(a)\)

Dependency of properties on arithmetics[]

When we work in ZFC, properties of addition such as commutativity and associativity hold. However, in Robinson arithmetic, the commutativity does not necessarily hold. The statement \(\forall a,b \in \mathbb{N} : a + b = b + a\) is independent of Robinson arithmetic.

Turing machine code[]

Given input of form (string of a 1's)+(string of b 1's) it outputs string of a+b 1's.

0 1 _ r 1
0 + _ r halt
1 1 * r 1
1 + + r 2
2 1 * r 2
2 _ 1 l 3
3 1 * l 3
3 + * l 3
3 _ * r 0

Time Complexity[]

Called \(a\) and \(b\) \((a, b \geq 0 | a, b \in N)\) as the length of the first and the second 1's, \(T(a,b)\) as the function that return how many steps are used in a Turing Machine.

\(T(a,b) = 2a^2 + 2ab + 3a + 1\)

Space Complexity[]

\(S(a,b)\) is how much cell has been maximally used during the process of compute

\(S(a,b) = a + b + 1\)

Symbols used[]

  • 1
  • +
  • _

See also[]

Advertisement