Logic – Is Any False Statement a Negation of a True Statement?

first-order-logiclogicpredicate-logicpropositional-calculus

  1. Consider the following example:

    What is the negation of this statement? $$\forall x{\in}\mathbb{R}\;\exists y{\in}\mathbb{R}\quad x+y\geq 0.\tag P$$

    I know that the standard answer is $$\exists x{\in}\mathbb{R}\;\forall y{\in}\mathbb{R}\quad x+y<0.\tag{¬P}$$

    But since we know that the first statement $P$ is true in mathematics, is it correct to say that any statement that is false is a negation of $P\,?$ For example, is $Q$ also a negation of $P\,?$ $$1<0\tag Q$$ Why or why not?

  2. Is any contradiction a negation of a tautology?

    For example, can I say that $$P \wedge \neg P$$ is a negation of $$Q\vee \neg Q\,?$$

Best Answer

  1. In classical logic, to negate a formula (including an open formula that has no definite truth value) means to logically flip its truth value.

  2. Therefore, these statements are equivalent:

    • $P$ and $Q$ are negations of each other;
    • regardless of interpretation, $P$ and $Q$ have opposite truth values;
    • $P↔Q$ is unsatisfiable;

    (A more pedantic definition of ‘negation’ than #1 considers $(¬A∨¬B)$ to be merely logically equivalent to the negation $¬(A∧B)$ of $(A∧B);$ in this case, change “$P$ and $Q$” in bullet 2 to “the truth-functional form of $P$ and $Q$”, and change “unsatisfiable” to “a contradiction”.)

  3. On the other hand, these statements are equivalent:

    • $P$ and $Q$ are logically equivalent;
    • regardless of interpretation, $P$ and $Q$ have the same truth value;
    • $P↔Q$ is valid, i.e., $P\equiv Q;$

  4. If statement $P$ is true in mathematics, then is any false statement in mathematics a negation of $P\,?$ For example, here, is $Q$ a negation of $P$? $$\forall x{\in}\mathbb{R}\;\exists y{\in}\mathbb{R}\quad x+y\geq 0.\tag P$$ $$1<0\tag Q$$

    Two formulae with opposite truth values (in a given interpretation) do not necessarily negate each other.

    For example, $(\forall x\;x^2\le0)$ and $(x=x)$ have opposite truth values in the universe $\mathbb R,$ but the same truth value in the universe of all imaginary numbers (that is, in this interpretation, the two formula are equivalent); so, they aren't mutual negations.

    And these two propositions have opposite truth values in some, but not all, interpretations: \begin{array}{cc|c@{}ccc@{}c} P&Q&&P&\rightarrow&Q&\\\hline 1&1&&1&\mathbf{1}&1&\\ 1&0&&1&\mathbf{0}&0&\\ 0&1&&0&\mathbf{1}&1&\\ 0&0&&0&\mathbf{1}&0& \end{array} \begin{array}{cc|c@{}ccc@{}cc@{}c@{}c} P&Q&&P&\rightarrow&&\lnot&Q&\\\hline 1&1&&1&\mathbf{0}&&0&1&&\\ 1&0&&1&\mathbf{1}&&1&0&&\\ 0&1&&0&\mathbf{1}&&0&1&&\\ 0&0&&0&\mathbf{1}&&1&0&& \end{array}

    In your example, in an interpretation in which the binary operation + is defined x+y := -3-|xy|, where subtraction & multiplication retain their standard meanings, sentences $P$ and $Q$ are equivalent to each other, even though in mathematics they have opposite truth values.

  5. Notice that negation preserves logical equivalence.

  6. By the definition in #1:

    • Negating a valid formula gives an unsatisfiable formula, and vice versa.
    • Negating an invalid formula gives a satisfiable formula, and vice versa.

    Examples:

    Observe that both $\big(\forall x\,P(x)\big)$ and its negation $\big(\exists x\,¬P(x)\big)$ are satisfiable and invalid: $(\forall x\;x^2\ge0)$ is true in the universe $\mathbb R$ but false in the universe of all imaginary numbers, while its negation $(\exists x\;x^2<0)$ is false in the universe $\mathbb R$ but true in the universe of all imaginary numbers.

    $(x=x)$ is valid and its negation $(x\ne x)$ is (not merely invalid but) unsatisfiable.

  7. Is any contradiction a negation of a tautology?

    Yes, by the definition in #1.

Related Question