3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why do you not want to consider empty relations? They're quite useful, and they don't cause any problems. $\endgroup$ – Noah Schweber Jan 13 '16 at 8:09
  • $\begingroup$ Well you could separately define a null set to be a relation too right (of arity 0)? This way it's arity is clear, but in the standard definition, its not. $\endgroup$ – NotGauss Jan 13 '16 at 8:12
  • $\begingroup$ I understand what you're saying. You believe that a relation should necessarily come along with information about the sets it relates. Bourbaki and some other authors share your concern. So instead of defining a binary relation between sets $E$ and $F$ as a subset $\Gamma$ of $E \times F$, they define it as a triple $(\Gamma, E, F)$. But others feel this formalism creates more problems than it solves. Nobody would do away with empty relations, however. If you had two relations $R$ and $S$, it wouldn't always be possible to consider the relation $R \cap S$. $\endgroup$ – David Jan 13 '16 at 8:17
  • 1
    $\begingroup$ A $0$-ary relation would be a relation that didn't depend on any variables. So it would have to be either always true or always false. Technically, a $0$-ary relation would be defined as a subset of the product of the empty collection of sets. This product is $\{\varnothing\}$. So there are two $0$-ary relations, namely $\varnothing$ and $\{\varnothing\}$. The first corresponds to "false" and the second to "true." $\endgroup$ – David Jan 13 '16 at 8:23
  • 1
    $\begingroup$ @NotGauss How would a 0-ary relation be a constant? Suppose my structure is the set of positive real numbers - what positive real number does either 0-ary relation correspond to? $\endgroup$ – Noah Schweber Jan 13 '16 at 8:39
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wow, finally a book that talks about this! Thanks for pointing it out. I'm writing an answer/summary of comments so far, and I think this will fit in well. $\endgroup$ – NotGauss Jan 13 '16 at 12:06
  • $\begingroup$ I added an answer. If you have time, perhaps you could read over it, and point out mistakes if any. Thanks! $\endgroup$ – NotGauss Jan 13 '16 at 15:09
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Since there are no errors pointed out so far, I am assuming this answer is correct. $\endgroup$ – NotGauss Jan 17 '16 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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