[Math] ny way to define arithmetical multiplication as other thing than repeated addition

arithmeticproducts

Is there any way to define arithmetical multiplication as other thing than repeated addition?
For example, how could you define $a\cdot b$ as other thing than $\underbrace{a+a+\cdots+a}_{b \text{-times}}$ or $\underbrace{b+b+\cdots+b}_{a \text{-times}}$?

Best Answer

Given two sets $A$ and $B$ of cardinality $a$ and $b$, respectively, the cardinality of the cartesian product $A\times B$ is called the product of $a$ and $b$, and is denoted by $a\cdot b$.

Update

When I wrote this answer I didn't have infinite sets in mind. I just wanted to convey a mental picture of multiplication that does not involve repeated addition.

Related Solutions

[Math] How to define addition through multiplication

The following is a partial answer for $\mathbb{N}$, and the usual notion of (first-order) definability, which is more restrictive than the notion you are implicitly using.

It is an old result of Mostowski that if $S$ is the set of true sentences of number theory that do not use addition, then $S$ is recursive. This is an analogue of the more famous result about the decidability of Presburger arithmetic. There we look at sentences that do not use multiplication.

If addition were definable from multiplication, then the set of true number theoretic sentences would be recursive. But we know that this is not the case.

Thus addition cannot be defined from multiplication in the restricted setting we have described.

Remark: Your definition of multiplication in terms of addition is not first-order. The issue is with the $\dots$, combined with "$b$ times." Replacing this with a more formal recurrence does not make it first-order.

[Math] How many number of multiplication/addition operations are there in a multiplication of two numbers of equal length

2) How did they find this "at-most $2n^2$" operations?

Lets consider the final addition part. For final addition, we are basically adding 4 numbers (results of multiplication by each digit). We can represent them like below (dashes and blank spaces replaced by 0's)

Now addition of $r_1$ and $r_2$ takes 7 basic opeartions.
Similarly addition of result of $(r_1+r_2)$ and $r_3$ takes 7 basic operations.
Similarly addition of result of $(r_1+r_2+r_3)$ and $r_4$ takes 7 basic operations.

A total of 21 operations for final addition. Here we are multiplying two small numbers. But if we would have multiplied $9999 \cdot 9999$ then final addition would be of 24 operations, i.e.
$$ r_1 - 00089991 + r_2 - 00899910 + r_3 - 08999100 + r_4 - 89991000 $$ 24 operations $= 2 n^2 - 2 n$ with $n = 4$ in our case.

(24 operations without considering carry overs. I am not sure if carry overs were also counted as additional opeartions by Tim Roughgarden)

Reference : https://people.mpi-inf.mpg.de/~mehlhorn/ftp/chapter2A-en.pdf

Best Answer

Related Solutions

[Math] How to define addition through multiplication

[Math] How many number of multiplication/addition operations are there in a multiplication of two numbers of equal length

Related Question