# Logic: Functions and statements

What is the relationship between the concept of an equation (a statement) and the concept of a function (and the concept of morphisms in category theory)?

I'm going to use equations as the most important subclasses of statements. To take a seemingly trivial example, the equation (E1) 2*x = 5. This equation which could be rewritten as (E2) f(x) => 2*x -5, but E1 and E2 are technically not equivalent. With f(x)=> I mean, the statement is a function of x. For every x f(x) returns true or false, depending on the contents of f(x). The equation E1 can be true for values depending on x. The truth value is dependent on the value of x, i.e. E1 is a function which returns a bool, given a value of x. E2 returns a value. I haven't defined domain and co-domain. Say it is N. E2 is always true. So if I write (E3) f(x) = 2*x -5 and f(x)=0, E3 and E1 become equivalent. In other words, everything is a function, because equations are simply boolean functions. In (E2), f(x) could be seen as a placeholder for (E1). E2 says: there is an expression, which is an equation, which has the contents 2*x=5. In a programming language this could be all said much clearer. In python E1 would be: 2*x ==5 and E3: def f(x): return 2*x-5==0.

More generally, as I understand it, the approach of Russell/Wittgenstein was to reduce everything to statements. In category everything is reduced to functions (or morphisms in it's own parlance).

Edit: some further notes to clarify.

-
You say that the equation $2x=5$ ‘could be rewritten as’ $f(x)=2x-5$; this is absolutely false. $(E1)$ is a statement, something with a truth value, while $(E2)$ is an incomplete definition $-$ specifically, the definition of the function $f$ $-$ and as such has no truth value; they are completely different species of animal. – Brian M. Scott Nov 30 '12 at 11:25
I have rewritten the statement. However I don't see anything wrong with writing f(x) = 2x -5. This can be interpreted as saying: 2x -5 depends on x. Rather the traditional statement f(x) = 2x-5, should be written as f(x) := 2x-5, because it is a definition of a function, and not an equation. "=" acts as an assignment operator not as a comparison operator ("=="). This works obviously in most cases, because mathematicians can tell the difference between "=" and "==". This doesn't mean it's completely rigorous. – RParadox Nov 30 '12 at 11:36
I saw that you’d rewritten it; my objection still holds. I don’t agree that ‘$f(x)=2x-5$’ can be interpreted as saying that $2x-5$ depends on $x$. It has two possible interpretations: (1) an incomplete definition of $f$, and (2) an assertion that some previously defined function $f$ is the same as the function $2x-5$. The latter does make it a statement, but one that is unrelated to the statement $2x=5$. – Brian M. Scott Nov 30 '12 at 11:41
The relationship is that f(x) takes the value of 0 when the equation is true. In fact equations can be rewritten as A=B <=> A-B=0. define f(x)=A-B and let f(x)=0. There you go. – RParadox Dec 1 '12 at 22:24
No. Under interpretation (1) of my previous comment it’s meaningless to talk about the truth or falsity of $f(x)=2x-5$. Under interpretation (2) the statement ‘$f(x)=2x-5$ is true’ is meaningful but has nothing at all to do with the statement ‘$2x=5$’; rather, it’s equivalent to the statement ‘$f(x)-(2x-5)=0$’. – Brian M. Scott Dec 1 '12 at 22:33

Though not widely used for some reason, I have found the following definition to be useful. Given sets A and B, f is said to be a function mapping A to B iff:

$\forall x(x\in A\rightarrow f(x)\in B)$

Built into this notation is the fact that every element of A has unique image in B. By a simple substitution, we have:

$(f(a)=b \wedge f(a)=c)\rightarrow b=c$

As for morphisms in category theory, it's best not to think of them as functions (although they can be functions). Category theory is less like set theory (with its elements, sets and functions) and more like graph theory (with its nodes and directed arrows). The difference is that there may be any number of arrows (morphisms) between any pair of nodes (objects). Every node $x$ has an identity arrow with a source and target node at $x$. Composition of arrows is defined for any pair of arrows with compatible source and target nodes. And composition of arrows is associative.

-
Ok, great. Are equations or more generally relations, relations of graphs? For instance in computer science we evaluate A+B == C*D, by reducing each side to a boolean expression. – RParadox Dec 4 '12 at 8:37
You can use a 2D graph to show which values satisfy some relation between a pair of variables. Each point (dot or pixel) has an ordered pair of numbers associated with it. The graph of the equation $y=2x+3$ is a straight line. For each point on that line, the $x$ and $y$ co-ordinates are such that $y=2x+3$. The graph of the relation $y<2x+3$ is the region below the same line. For each point in that region, the co-ordinates are such that $y<2x+3$. In your equation here, you have 4 variables. It is true if and only if A+B has the same numerical value as C*D. – Dan Christensen Dec 4 '12 at 13:52

It is not a direct answer on the question, but Brian mostly answered that in the comment.

There are many possible ways of using the abstract arrows of categories to express sentences. I describe one of these:

In category theory originally one rather considers various structures and their morphisms, than simply functions.

Let us now fix an algebraic first order language: operation symbols $\mu,\nu,..$ of given arities, and a set of variables $x,y,...$. We can formally build terms out of these and then equations are the atomic formulas of the form $\tau(\vec x)=\sigma(\vec x)$ where $\tau,\sigma$ are terms containing variables within $\vec x=(x_1,..,x_n)$.

Now consider the category of algebraic structures of the given type. Then, for example, to the given equation $\tau(\vec x)=\sigma(\vec x)$ we can assign the canonical homomorphism from the free algebra on $\{x_1,..,x_n\}$ to its quotient by the given equation.

Or, another way, for any algebra $A$ and equation as above over the variables $x_1,..,x_n$, we can assign them the injection $$\{(a_1,..,a_n)\in A^n\mid \tau(\vec a)=\sigma(\vec a)\} \to A^n.$$

-
Interesting. This assumes it is possible to distinguish between a first order language and a second order language and that many of those loaded words, such as structures, functions, morphisms, free algebras, equation, etc. are always perfectly clear. – RParadox Nov 30 '12 at 12:05

Categories are diagrams of morphisms, a function is a morphism and an equation $f=g$ is a diagram with the following property. Take the two morphisms $f: A \rightarrow B$, $g: C \rightarrow D$ and the corresponding morphisms $h: A \rightarrow C$ and $i: B \rightarrow D$. $f=g \iff$ $g$ and $h$ are the identity. This is very easy to see in vector spaces: two vectors are equal if and only if they map every point A to the same point B. If any other vector maps C to D, and A is equal to C, B has to be equal to D. Or put more simple: any two vectors that are equal map to the same point from 0. Or: if A=A then A-A=0, so the inverse of every vector that is equal to A will retract A to zero (this requires the inverse though). For instance two triangles are equal for instance, if put above each other there is only one triangle left. To compare two triangles in this way requires an affine transformation.

In other words in category theory morphisms (functions) are more fundamental than equations and equations can be explained by the diagram given above. In the category of sets every relation is a subset of the cartesian product. Functions and equations are relations. To give another example in the category of programs, every side is evaluated as a tree to true or false or a simple expression. Both sides are the result of the function, call it eval() which maps every statement to a simple expression. In my example 2*x=5, 2*x is an expression which gets evaluated depending on x. If x is 3, 2*x is being evaulted as 6 and can be compared to 5.

-