How do we assure ourselves when defining an operation that it does not lead to contradictions? For example 0! := 1. I understand the practicality of why it is defined this way, but I am wary of what could happen if another such operation is created and defined in a way that leads to future contradictions that were not considered. This often happens when people come up with definitions for division by zero. How do we know it doesn’t happen with other definitions?

Note that I'm not asking about the consistency of our axioms for N or anything like that, but about definitions built upon those axioms.

  • 3
    Formally speaking, a definition cannot be inconsistent. What it might do is make certain universal theorems we have proved about the operation before we extended it no longer true. – spaceisdarkgreen Oct 19 at 19:44
  • 1
    Too much C or Java with their use != for $\neq$ – badjohn Oct 19 at 22:44
  • @badjohn, when i wrote 0! := 1 I did not mean != as NOT EQUALS in programming. The expression is meant to be read "Zero factorial is defined to be 1". The symbol := is used to say that the equality is by definition – Erdös Oct 20 at 21:00
  • I know. I was responding to a comment which seems to have gone. – badjohn Oct 20 at 21:23

A definition like that can't lead to a contradiction since it is just a definition: the meaning you've assigned to the symbols "$0!$".

A definition might lead to a problem with some rules of arithmetic you like. For example, if you chose to define $x^0 = 0$ instead of $1$ then the identlty $$ x^{a+b}= x^ax^b $$ would fail sometimes. So it would be a bad definition, but not a contradiction.

All the usual suggestions for how to define division by $0$ break some identity in ordinary arithmetic, which is why we don't use any of them.

Defining $0! = 1$ preserves the identity $$ n! = n(n-1)! $$ No other definition would do that.

  • 2
    It also preserves $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ when $k \in \{0, n\}$. – Peter Taylor Oct 20 at 8:40

Certain types of definitions can lead to contradictions. It is up to the person proposing the definition to show that this can't happen. Look up well-defined.

It depends what you mean by a definition. A definition such as $$ P \mathrel{:=} \{ i \in \Bbb{N} \mid \mbox{$i$ is prime}\} $$ where the defining property of $P$ simply states that it is equal to something that already exists is completely unproblematic. But in addition to explicit definitions like this, we often use various kinds of implicit definition. A recursive definition such as: $$ \begin{align*} 0! &= 1 \\ (n+1)! & = n! \times (n + 1) \end{align*} $$ is a fairly explicit form of implicit definition that can be shown to be consistent using the recursion theorem as discussed in Marcel's answer.

A recursive "definition" (of a function $f : \Bbb{N} \to \Bbb{N}$) such as $$ \begin{align*} f(0) &= 1 \\ f(n+1) & = f(n+2) \end{align*} $$

would be considered undefined in programming languages, but from a mathematical perspective it is just a loose definition (i.e., an implicit definition that does not uniquely determine the defined object): it says that $f(0) = 1$ and $f(i) = f(j)$ for $i, j > 0$ and this system of equations has many solutions. If we had instead:

$$ \begin{align*} f(0) &= 1 \\ f(n+1) & = 2(f(n+2)+1) \end{align*} $$

and still required $f : \Bbb{N} \to \Bbb{N}$, then this "recursive" definition would be inconsistent, i.e., there are no solutions and asserting the existence of such an $f$ would lead to a contradiction (do you see why?).

Another form of implicit definition would be to define the function $\exp : \Bbb{R} \to \Bbb{R}$ as the solution of the following system of equations:

$$ \begin{align*} \exp(0) &= 1 \\ \exp'(x) &= \exp(x) \end{align*} $$

Here an explicit construction of a witness (say using a power series) shows that the definition is consistent (and a simple argument using properties of the derivative shows that the definition characterises $\exp$, i.e., the equations have only one solution).

In general, there are many forms of implicit definition. To show that it is consistent to take a property $\phi(X)$ to be the defining property of a new object $X$, you have to prove $\exists x\phi(x)$. You will probably also want to prove that the existence is unique, i.e., $\forall x\forall y(\phi(x) \land \phi(y) \Rightarrow x = y)$, unless you really did intend your definition to be loose. If you are lucky, then something like the recursion theorem or the theory of differential equations will help with these proofs.

  • I don't see why $f(0) = 1\;;\;f(n+1) = 2(f(n+2)+1)$ leads to a contradiction: it's perfectly compatible with $f(n) = 3\cdot 2^{-n} - 2$. – Peter Taylor Oct 20 at 8:44
  • @PeterTaylor I suppose Rob still assumes that $f$ has domain and codomain $\mathbb N$, as it has above. No function with codomain the natural numbers satisfies those equations. – tomsmeding Oct 20 at 10:36
  • @tomsmeding: that was indeed my intention. I have stated it explicitly now. – Rob Arthan Oct 20 at 11:58

A recursively defined function like the factorial function is well-defined by the recursion theorem, which can be proved by induction:

https://math.stackexchange.com/a/46760/29892

Henkin has a great article on recursion available here:

https://www.jstor.org/stable/2308975

About $0^0$,

A polynomial, in general is written as

$$a_0+a_1x+...a_nx^n=\sum_{i=0}^na_ix^i$$

To be consistant, one will put $0^0=1$, to get the constant term $a_0$.

but

If you compute $$\lim_{x\to+\infty}(e^{-x})^\frac{-1}{\ln(x)}$$

it gives $0^0=+\infty$.

There are actually two different kinds of "definitions" in mathematics, arising from two separate mechanisms: $ \def\nn{\mathbb{N}} $

  1. Definition by existential instantiation: When we have an axiom or a deduced sentence asserting the existence of some object, namely "$\exists x\ ( P(x) )$" where $P$ is some predicate, we can instantiate it and name a reference to it, by saying "Let $c$ be such that $P(c)$.". This is far more general than you might think. For example when we define a function $f : \nn \to \nn$ such that $f(0) = 0$ and $f(n+1) = 2f(n)+1$ for every $n \in \nn$, we are invoking a theorem that says "$\exists f : \nn \to \nn\ ( f(0) = 0 \land \forall n\in\nn\ ( f(n+1) = 2f(n)+1 ) )$". Don't laugh! This is not necessarily a trivial theorem, depending on our choice of foundational system for mathematics. The bottom line is, such definitions are only valid if we can prove the existential statement that guarantees the existence of the object that we are giving a name to.

  2. Definitorial expansion: In some foundational systems, we cannot use the above kind of definition, simply because we cannot prove the required existential statement. For example in ZF set theory one can prove that there is no set $S$ whose members are exactly the sets that are not members of themselves. Namely, we can prove $\neg \exists S\ \forall x\ ( x \in S\ \Leftrightarrow \neg x \in x )$. However, we still can define a predicate $R$ where $R(S) \overset{def}\equiv \forall x\ ( x \in S\ \Leftrightarrow \neg x \in x )$ for every set $S$. $R$ is not a set, but we can still talk about sets that satisfy $R$. For example, $R(\{\})$ because the empty-set is not a member of itself. This notion of definition can itself be formally defined as described in this post, and more details about the issue with Russel's paradox can be found in this post. This is also more common than you might think. For example in ZFC set theory, there is no function that maps every set to its cardinality, and so the cardinality notation in "$\#(S)$" or "$|S|$" cannot be defined using the first type of definition. But it can be defined via this type of definition. Similarly, when you define the diameter $diam(G)$ of every finite graph $G$, note that actually $diam$ is not a function in ZFC set theory, because there is no set of all finite graphs! But the notion of "finite graph" and $diam$ are both definable via definitorial expansion, and we can use $diam$ on any finite graph. Things get a bit messy with higher-order things like the family of functions on finite graphs. That cannot even be defined via definitorial expansion, but we can often 'cheat' by using suitable concrete representative. For example we can define even by mere existential instantiation the family of all functions on graphs whose vertices are a subset of $\nn$.

We can show (as a fact about classical logic) that both these two mechanisms will not cause contradiction that did not already exist without it. For existential instantiation, if one can obtain a contradiction from instantiating an existential statement, then the correct judgement would be that the existential statement itself was invalidly assumed/deduced, and not the instantiation step. For definitorial expansion, it yields a conservative extension over the original system, meaning that every statement in the original language can be proven in the expanded system (i.e. with definitorial expansion) can already be proven in the original system.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.