0

At the beginning of Sipser's Theory of Computation we get the following two definitions:

A predicate or property is a function whose range is $\{TRUE, FALSE\}$. For example, let even be a property that is $TRUE$ if its input is an even number and $FALSE$ if its input is an odd number. Thus $even(4) = TRUE$ and $even(5) = FALSE$.

A property whose domain is a set of k-tuples $A \times \cdots \times A$ is called a relation, a k-ary relation, or a k-ary relation on $A$.

My question: isn't Sipser's definition of relation nonstandard here (I am used to the definition of a relation as any subset of of a Cartesian product of sets)? That is, he defines a relation as a very specific type of function (a function with a specific domain as a Cartesian product of a given set with itself $n$ times and a range of $\{T,F\}$). Is this a common definition in computability theory?

EE18
  • 1,211
  • It's not very nonstandard. Whenever we have a "background set" $X$, we can conflate subsets of $X$ with their characteristic functions. Similarly, we can conflate $n$-ary relations on $X$ with the corresponding characteristic function $X^n\rightarrow{TRUE,FALSE}$. Putting everything in terms of functions is somewhat convenient in computability theory, but it's really not much of a twist on the original. – Noah Schweber Feb 09 '24 at 18:12
  • It is essentially the same thing. – Vivaan Daga Feb 09 '24 at 18:12
  • Ah I think I see. You're saying that the usual definition of relation (a subset of a Cartesian product) is equivalent to the one given here (a function with range ${T,F}$) because of the bijection between a powerset and characteristic functions on the underlying set? @NoahSchweber – EE18 Feb 09 '24 at 18:20
  • @EE18 Yup, that's basically it. – Noah Schweber Feb 09 '24 at 18:53
  • Thank you! Happy to accept an answer to that effect as well if you'd like :) @NoahSchweber – EE18 Feb 09 '24 at 22:13

0 Answers0