Here is a photo of the board from the end of the lesson on nested quantifiers. Part of our discussion was a little rushed, so I wanted to recap here.

Recall that T(x,y) means that student x likes cuisine y. Recall also that the names x and y don’t matter…what matters is that the first entry is always a student and the second entry is always a cuisine. The exercise was to translate the propositions below into English sentences.

(a) \neg T(Juliano, Japanese) translates to “Juliano does not like Japanese food.”

(b) \exists x T(x, Korean) \wedge \forall x T(x, Mexican) translates to “There is a student who likes Korean food and all students like Mexican food.”

(c) \exists y (T(Shannon, y) \vee T(Jiayu, y)) translates to “There exits a cuisine that either Shannon or Jiayu (or both) like.”

(d) (x \neq z) \rightarrow \neg (T(x,y) \wedge T(z,y)))…let’s do this translation in a few steps:

  • T(x,y) \wedge T(z,y) translates to “Students x and z like cuisine y.”
  • \neg (T(x,y) \wedge T(z,y) translates to “It is not the case that students x and z like cuisine y,” which we can translate to “Either student x or student z does not like cuisine y.”
  • (x \neq z) \rightarrow \neg (T(x,y) \wedge T(z,y))) translates to “If x and z are different students, then either student x or student z does not like cuisine y.”
  • So far none of the statements are propositions, since we don’t know the values of the variables, but we can turn the last statement into a proposition by adding the quantifiers. \forall x \forall z \exists y ( (x \neq z) \rightarrow \neg (T(x,y) \wedge T(z,y))) translates to “For all students x and students z there exists a cuisine y such that if x and z are different students, then either student x or student z does not like cuisine y.” We can translate this into a more natural sentence in English by eliminating the variables: “For any pair of two distinct students, there is a cuisine that one of the students does not like.”

(e) \exists x \exists z \forall y (T(x,y) \leftrightarrow T(z,y))…again, let’s do this translation in a few steps:

  • T(x,y) \leftrightarrow T(z,y) translates to “Student x likes cuisine y if and only if student z likes cuisine y.”
  • Again, the above statement is not a proposition since we don’t know the values of the variables, but we can upgrade it to a proposition by adding the quantifiers. \exists x \exists z \forall y (T(x,y) \leftrightarrow T(z,y)) translates to “There exists a student x such that there exists a student z such that for all cuisines y, student x likes cuisine y if and only if student z likes cuisine y.” We can translate this into a more natural sentence in English: “There exits a pair of two students who like all the same cuisines as one another and don’t like all the same cuisines as one another.“

(f) \forall x \forall z \exists y (T(x,y) \leftrightarrow T(z,y))…let’s do this translation in a few steps:

  • T(x,y) \leftrightarrow T(z,y) is the same as in question (e)
  • This time the quantifiers will change the statement to: “For all students x and for all students z there exists a cuisine y such that student x likes cuisine y if and only if student z likes cuisine y.” Again, we translate this into a more natural sentence: “For all pairs of students there is a cuisine that they either both like or both do not like.”