Clarify definitions of relation and 0-ary relation

2k Views Asked by At

From mathworld.wolfram.com:

A relation is any subset of a Cartesian product

But if so, then the null set is all of: 0-ary, 1-ary, 2-ary etc. Wouldn't it be better to define it as:

A relation is any non-empty subset of a Cartesian product

Second question, from this answer I understand that in set theory a 0-ary function is commonly taken to mean $\{ \emptyset \}$, also called a constant. If a 0-ary relation is a non-empty subset of some set $D^{0}$ ($D$ is the domain), isn't it right to say a 0-ary relation is also a constant? I haven't seen model theory texts include 0-ary relations, which makes sense as they're including 0-ary functions instead. To be technically the same as 0-ary functions (as they're defined in the linked answer), wouldn't we have to define relation as:

An n-ary relation is any non-empty subset of $D^{\{0,1,\dots,n-1\}}$

What do you think?

EDIT: I should add that you can still define the empty set to be a relation of arity 0. From the comments below it seems it's a matter of convenience more than technical correctness as to how relations are defined.

2

There are 2 best solutions below

1
On BEST ANSWER

I will try to put together the answers/comments so far, and explain my own source of confusion. I am a novice, so please feel free to correct my mistakes, I shall be grateful for the education :)

First, I should more clearly state my "alternate" definition of a relation:

  1. $\emptyset$ is a relation with arity 0
  2. Every element of $\mathcal{P}(D^n) \setminus \emptyset$ is a relation of arity n

The point was to clearly specify the arity of $\emptyset$. This definition exchanges convenience for that extra "clarity". Note: It still allows two 0-ary sets: $\emptyset$ by definition, and $\mathcal{P}(D^0)\setminus \emptyset = \{ \emptyset \}$. This was what @David was saying. This was just a technical exercise, not worth it in practice I realized.

Second, I was sloppy in reading this answer. It says $S^0$ is $\{ \emptyset \}$, but a 0-ary operator maps $S^0$ to an element in $S$, so a 0-ary operator is $\{ (\emptyset, a) \}$ where $a \in S$. This is what @mrp was saying. I suppose this can be extended to define a general 0-ary function on into any non-empty set $A$ as $\{ (\emptyset,a) \}$ for $a \in A$.

Third, because of my sloppiness, I assumed a 0-ary function is $\{ \emptyset \}$ rather than $\{ (\emptyset,a) \}$, equating a 0-ary relation to a 0-ary function.

Fourth, I considered the definition of a 0-ary relation outside the context of model theory, leading to above definition. Inside model theory of course, we separate syntax and semantics. I think what @NoahSchweber is saying is that if we call some symbol a 0-ary function, it is mapped to an object in the domain (hence, 0-ary function symbols are called constant symbols too), while if we call the same symbol a 0-ary relation it should be mapped to $\{ \emptyset \}$ or $ \emptyset$, rather than an object in the domain.

Fifth, I think that calling a 0-ary function a constant symbol is strictly incorrect. When we talk of a constant symbol, we usually have in mind something that maps to an object in the domain, let's say $a$ maps to $a^\mathfrak{M}$. But as we found above, a 0-ary function $a$ should actually map to $\{ (\emptyset, a^\mathfrak{M}) \}$, not $a^\mathfrak{M}$. So perhaps, Wilfrid Hodges' definition is right in this sense (pg. 2 of his big book "Model Theory"). He restricts function and relation symbols to arity $\geq$ 1, and defines constant symbols as a different entity.

Sixth, we could perhaps "simulate" sentential logic in first order logic using 0-ary relations. Namely, having symbols $\{ P_1, P_2, \ldots \}$ be 0-ary relation symbols, mapped to $\emptyset$ if we want them to be false, and to $\{ \emptyset \}$ if we want them to be true, based on @MauroAllegranza's answer. The language would consist of no other symbols. The reason is: $R(a_1, \ldots, a_n)$ is true if the n-tuple $(a_1^\mathfrak{M}, \ldots, a_n^\mathfrak{M}) \in R^\mathfrak{M}$. So, for a 0-ary relation symbol $P_1$, $P_1$ is true if the 0-tuple $\emptyset \in P_1^\mathfrak{M}$ which is true if $P_1$ maps to $\{ \emptyset \}$ and false otherwise. Wikipedia says this too:

Relations of valence 0 can be identified with propositional variables. For example, P, which can stand for any statement.

2
On

Your approach is adopted in Bruno Poizat, A Course in Model Theory: An Introduction to Contemporary Mathematical Logic (2000 - ed or 1985), page 32-33:

Note: In certain cases, it can be convenient to introduce $0$-ary relations. As a function from $X$ to $Y$ associates to every element of $X$ one and only one element of $Y$, there is always one function from $\emptyset$ to $E$, whether or not $E$ is empty. The graph of this function is $\emptyset$; in other words, there is one $0$-tuple of elements of $E$. Consequently, there are always two nullary relations with universe $E$, namely $\{ \emptyset \}$ and $\emptyset$; the first can be called the true, the second the false. In contrast, if $m > 0$, there are no $m$-tuples of elements of $\emptyset$, and therefore only one $m$-ary relation with universe $\emptyset$, which is $\emptyset$. (We have often said that $\emptyset$ is always a local isomorphism between two $m$-ary relations for $m > 0$.)

A nullary relation symbol is therefore interpreted in a structure either by the true or by the false. These nullary relations are not very interesting in and of themselves, but occur naturally as a calculation tool: If a formula in $n$ free variables represents an $n$-ary relation (the set of $n$-tuples that satisfy it), a statement represents a $0$-ary relation, either the true or the false.