Negation operator and quantifiers

logicpredicate-logic

Consider that statement: "There is math course that no first-year student taking." Let $A(y)$, $B(x)$ and $C(x, y)$ be the predicates "$y$ is a math course", "$x$ is a first-year student" and "$x$ is taking course $y$", respectively. Consider that the domain of $x$ and $y$ is the universe of all students and all the courses, respectively.

I know that "There is math course that no first-year student taking." can be expressed as $\exists y\forall x (A(y) \wedge (B(x) \rightarrow\neg C(x, y)))$.

Can this same statement be expressed as $\exists y\neg \exists x (A(y) \wedge B(x) \wedge C(x, y))$? I think that this makes sense but these to expressions are not equivalent after applying De Morgan's law.

Best Answer

"There is math course that no first-year student taking." Let $A(y)$, $B(x)$ and $C(x, y)$ be the predicates "$y$ is a math course", "$x$ is a first-year student" and "$x$ is taking course $y$", respectively.

Consider that the domain of $x$ and $y$ is the universe of all students and all the courses, respectively.

Notice, from the specific way that you've set up the predicates, that separate discourse domains are unnecessary (but harmless) here.

I know that "There is math course that no first-year student taking." can be expressed as $$\exists y\forall x (A(y) \wedge (B(x) \rightarrow\neg C(x, y))).\tag1$$ Can this same statement be expressed as $$\exists y\neg \exists x (A(y) \wedge B(x) \wedge C(x, y))\;?\tag2$$

Statement $(2)$ translates to “There is a course for which, for no student, the course is math and the student is in year 1 and taking it”. It is strictly weaker than statement $(1),$ i.e., $$(1)\implies(2),\\(2)\kern.6em\not\kern-.6em\implies(1).$$ For example, $(2)$ is automatically true if the institution offers a non-mathematics course.

Related Question