Is this proven by the generalized De Morgan's laws for propositional connectives?

99 Views Asked by At

I know the generalized De Morgan's laws say

$\begin{align*} \neg[P(0) \wedge P(1) \wedge \ldots \wedge P(n)] \Leftrightarrow \neg P(0) \vee \neg P(1) \vee \ldots \vee \neg P(n) \end{align*}$

for any finite $n$. And I can prove the above by induction. But I don't know if that's equivalent to

$\begin{align*} \neg [P(0) \wedge P(1) \wedge P(2) \wedge \ldots] \Leftrightarrow \neg P(0) \vee \neg P(1) \vee \neg P(2) \vee \ldots \end{align*}$

In particular, I want to know because I'm trying to decide if

$\begin{align*} \neg\forall x \in \mathbb{N}\ [P(x)] &\Leftrightarrow \neg[P(0) \wedge P(1) \wedge P(2) \wedge \ldots] \\ &\Leftrightarrow \neg P(0) \vee \neg P(1) \vee \neg P(2) \vee \ldots \\ &\Leftrightarrow \exists x \in \mathbb{N}\ [\neg P(x)]\end{align*}$

is a valid proof.

Edit: Fixed typo

1

There are 1 best solutions below

8
On BEST ANSWER

1) The generalization of DeMorgan's laws is valid. In fact, $$\neg\forall x P(x) \Leftrightarrow \exists x \neg P(x)$$ is valid in all domains, not just when quantifying over $\mathbb{N}$.

2) Your proof of the case $\mathbb{N}$ is a bit 'iffy'. What exactly the "..." means when someone writes $$P(0) \vee P(1) \vee P(2) \vee \ldots $$ isn't clear and is hard to make rigorous. And while it's great that you realize that there is a difference between something being true for all finite $n$ and something being true for $\mathbb{N}$, with your second "$\Leftrightarrow $" you took something you knew was true for all finite number of propositions and applied it to an infinite number. That's using the thing you were trying to prove in the proof itself, and isn't valid. (It's actually the original meaning of "begging the question".)

Unless they're trying to explore logic for its own sake most mathematicians take the generalized DeMorgan's laws as given and don't feel the need to prove them. If you let us know what your final goal is in asking this question we might be able to give you better advice on this.