Defining "definable"

134 Views Asked by At

I do not really know what definable is, so i tried to google it and found nothing special about it. So could help me with this example about definable relation so I could get an image of this topic. Consider this example

Prove that the binary function “least common multiple”, that receives two numbers x, y and returns z which is their “Least Common Multiple” (LCM) is definable. thank you

1

There are 1 best solutions below

2
On

'Definable' is relative to some language and interpretation.

When it comes to arithmetical relations like the ones you are working with, a standard language is the 'language of arithmetic' which uses the constant $0$, and the functions $s$ (the successor function), $+$, and $*$. Sometimes, the relation $<$ is added as well, though we could define that using the other symbols. Indeed, we say the relation $<$ is definable in the language of arithmetic exactly because the expression:

$\exists z \ x +s(z)= y$

is true (under the 'standard interpretation') if and only if $x$ is smaller than $y$

Now, to define some function, you can try seeing a $n$-place function as a $n+1$-place relation. For example, to define that first function $f(x,y)$ we can try to define a relation involving $x$, $y$, and $z$ such that that relation holds if and only if $z=f(x,y)$. So, you could do:

$$z= ((x*x)+(y*y))+((x+y)*(x+y))$$

(You really need all those parentheses, because logic has no idea of preference among functions. And you can't use exponents, since that is not part of the standard 'language of arithmetic'.)

P.s. There are rigorous mathematical definitions for what it means to define some relation or function, but I figured if you needed those your instructor or book would have given those to you, and most likely you just need some expression that 'intuitively' captures what you need to capture.