Writing a First-Order Language for a Basketball League

Question

Here is exercise 4 in chapter 1.2 of Leary and Kristiansen's A Friendly Introduction to Mathematical Logic:

You have been put in charge of drawing up the schedule for a basketball league. This league involves eight teams, each of which must play each of the other seven teams exactly two times: once at home and once on the road. Think of a reasonable language for this situation. What constants would you need? Do you need any relation symbols? Function symbols? It would be nice if your finished schedule did not have any team playing two games on the same day. Can you think of a way to state this using the formal symbols that you have chosen? Can you express the sentence which states that each team plays every other team exactly two times?

I think this has given me more trouble than it should have. I've let the variables in the language represent, and included functions $f_0(x), \ldots, f_{13}(x)$ such that $f_a(x)$ is the team that $x$ will play against in its $a$th match. This allows me to express (with an axiom schema so cumbersome I won't write it out) the proposition that each team plays each other exactly twice.

I've also introduced for each $m \in \mathbf{N}$ 14 predicates, $D_m^0, \ldots, D_m^{13}$, defined so that $D_m^n$ is true if $x$ plays its $n$th game on day $m$. In this way I can again, with a long axiom schema, express the proposition that no team plays more than one game per day.

But I think I've made matters more complicated than they need to be. Is there a simpler approach?

Answer 1

You could use qualitative relations that describe when certain general situations like "playing a game of some kind" happens. For example,

• $\mathsf{plays}(a,b,n)$ could mean "Team $a$ plays against Team $b$ during game $n$"
• $\mathsf {home(}a,n)$ could mean "Team $a$ plays a home game during game $n$"

Then you could define a constant set of teams $T = \{t_1,\ldots,t_8\}$.

You can build up to the condition "Every team plays against each other team exactly twice; once at home and once away" by breaking it into simpler components:

• The condition that everyone plays a game is: $\forall t \in T\;\;\; \exists u \in T, n\in N : \mathsf{plays}(t,u,n)$.
• The condition that every team plays against every other team is: $\forall t \neq u \in T, \exists n : \mathsf{plays}(t,u,n)$.

• The condition "$a$ plays against $b$, twice once home, once away" can be expressed in everyday language as: "There exist two games, $H$ and $A$. $H$ is a home game between $a$ and $b$, $A$ is an away game between $a$ and $b$. Any other home game between $a$ and $b$ must be game $H$. Similarly for $A$".

  $$f(a,b) \equiv \exists H,A :\\ \mathsf{plays}(a,b,H) \wedge \mathsf{plays}(a,b,A)\wedge \\ \mathsf{home}(a,H)\wedge \neg \mathsf{home}(a,A)\wedge \\ \forall G : \mathsf{plays}(a,b,G) \Rightarrow (G=H \;\vee\; G=A)$$

• Then the condition that this is true for all pairs of teams can be just: $$\forall a,b \in T \\ a \neq b \Rightarrow \exists H,A :\\ \mathsf{plays}(a,b,H) \wedge \mathsf{plays}(a,b,A)\wedge \\ \mathsf{home}(a,H)\wedge \neg \mathsf{home}(a,A)\wedge \\ \forall G : \mathsf{plays}(a,b,G) \Rightarrow (G=H \;\vee\; G=A)$$