0

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
    I don't see why it wouldn't be (and I'm fairly confident it is). For instance, you could setup a propositional statement such as $P(x) :=$ "y is not divisible by $x$". Then you could say that proving $y$ is prime is equivalent to proving the following statement: $\forall x\in \mathbb{N}, x > 1, x \neq y, P(x)$. Simply finding one instance that is false, is equivalent to disproving the statement (meaning that $y$ was composite and not prime). – Jared Jun 05 '18 at 05:10
  • 1
    You are correct. – JonathanZ Jun 05 '18 at 05:12
  • @JonathanZ I read that Wiki excerpt just now. It seems to use a finite domain, unless there's something I'm missing. I'm not familiar with model theory. –  Jun 05 '18 at 05:28
  • @Mike, the first three lines of that excerpt state the generalized laws (valid for any domain, finite or infinite). The model stuff is just used to show how the generalized laws "decay" into the finite ones by picking a specific (finite) domain to work in. I've added a full-on answer that hopefully deals with your questions more fully. – JonathanZ Jun 05 '18 at 16:53

1 Answers1

2

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.

JonathanZ
  • 10,615
  • 1
    The final goal is to develop an introductory course on classical logic. For this reason, I want to get my facts straight. As you say, the statement is intuitively true, but without explanation by axioms it's not a proof. I know how to prove the countably infinite statement using a Fitch-style proof, so I'll provide my readers with that proof instead. Thanks for your answer! –  Jun 05 '18 at 16:59
  • In the case of integers (countably infinite), you can use induction to prove the law. So I disagree with "begging the question", it's really an inductive argument (not made, but could easily be made and, I think, is implied). You can't make the same inductive argument over a continuous range. I'm not saying this answer is wrong (I firmly believe it's correct), but the first statement seems to be simply stating "yes you're correct". – Jared Jun 06 '18 at 07:43
  • The poster is in the difficult situation of giving an invalid proof of something that's true.So yes, my first statement was intended to establish that point. – JonathanZ Jun 06 '18 at 17:36
  • As for induction: Induction proves something to be true for all finite $n$, but does not prove it for $\mathbb{N}$ -- at least if we're talking about the basic type of induction we learn about first, and not transfinite induction, Consider the statement "The sum of $k$ many real numbers is always finite" which is true for all finite $k$ but not when $k$ is countably infinite. – JonathanZ Jun 06 '18 at 17:41
  • @JonathanZ I disagree because we can say that the sum of natural numbers up to $k$ is $\frac{k(k + 1)}{2}$ and this can be shown, through induction, to be true for all $k \in \mathbb{N}$. As for your example, but it is true that "The sum of $k$ many real numbers is finite" for all $k \in \mathbb{N}$ (and can be proved by induction). A value cannot be countably infinite--only a domain (of which the integers define that set). – Jared Jun 07 '18 at 05:51
  • I'm having a hard time seeing how what you're saying applies to the question at hand. To re-base the discussion I'll ask you: do you think that the original poster has proved (or can prove) $\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 $? And if so, how? – JonathanZ Jun 07 '18 at 06:19
  • @JonathanZ No, the OP did not prove it. How? You'd start with $p(n)$, that is $\neg \left(P(0) \wedge P(1) \wedge \dots \wedge P(n)\right) \iff \neg P(0) \vee \neg P(1) \vee \dots \vee \neg P(n)$. Then you show that this still holds for $p(n+1)$: $\neg \left(P(0) \wedge P(1) \wedge \dots \wedge P(n) \wedge P(n + 1)\right) \equiv \neg \left(P(0) \wedge P(1) \wedge \dots \wedge P(n)\right) \vee \neg P(n + 1)$ (by the normal, binary, DeMorgan's Laws). Then you can substitute the original RHS, thus if $p(n)$ is true, so too is $p(n + 1)$, i.e. true for all $n\in\mathbb{N}$. – Jared Jun 08 '18 at 05:26
  • 1
    A trailing "...." almost always indicates something that goes on infinitely. Being true for all finite $n \in \mathbb{N}$ is not the same thing as being true for countably infinite (i.e. $\mathbb{N}$-many). I'm not sure you get that distinction. – JonathanZ Jun 08 '18 at 15:59