Negation operator and quantifiers

Question

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.

Answer 1

"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.

Answer 2

If you want to express in the second way note that

$$\forall x (A(y) \wedge (B(x) \rightarrow \neg C(x,y))) \equiv \neg(\exists x (\neg A(y) \vee (B(x) \wedge C(x,y)))).$$

As you said on your question the issue was with the application of the De Morgan’s Law. One should have $\neg A(y)$ and not $A(y)$.

Answer 3

The original statement: $$\exists y \forall x(A(y) \land (B(x) \to \lnot C(x,y)))$$

If we want to find something that is logically equivalent to it we can take the negation of this statement. Let's focus on the part where we have the implies: $$B(x) \to \lnot C(x,y) \\ \equiv \lnot B(x) \lor \lnot C(x,y) \\ \text{because of the logical equivalence: } p\to q \equiv \lnot p \lor q$$ Now we will "throw" the negation out front and get: $$\lnot ( \exists y \forall x(A(y) \land (\lnot B(x) \lor \lnot C(x,y)))) \\ \forall y \exists x\lnot (A(y) \land (\lnot B(x) \lor \lnot C(x,y))) \space \because \lnot \forall \equiv \exists \text{ and } \lnot \exists \equiv \forall \\ \forall y \exists x (\lnot A(y) \lor \lnot (\lnot B(x) \lor \lnot C(x,y))) \space \because \lnot \land \equiv \lor \\ \forall y \exists x (\lnot A(y) \lor \lnot \lnot B(x) \land \lnot \lnot C(x,y)) \space \because \lnot \lor\equiv \land \\ \boxed{\forall y \exists x (\lnot A(y) \lor B(x) \land C(x,y))} \space \because \text{Double Negation Law.}$$ Note: $\because$ means because.

Answer 4

The negation is that, for every course, at least one first year student is taking it. De Morgan's Law has nothing to do with it.

Here is formal proof using a form of natural deduction (screenshot from my proof checker)