2
$\begingroup$

Here are some properties of predicates that I found. $$1.\;¬(∀x)ϕ(x) ⇐⇒ (∃x)¬ϕ(x)$$ $$2.\; (∀x)(ϕ(x) ∧ ψ(x)) ⇐⇒ ((∀x)ϕ(x) ∧ (∀x)ψ(x))$$ $$3.\; (∃x)(ϕ(x) ∨ ψ(x)) ⇐⇒ ((∃x)ϕ(x) ∨ (∃x)ψ(x))$$ $$4.\; (∀x)(ϕ(x) ∨ (∀x)ψ(x)) =⇒ (∀x)(ϕ(x) ∨ ψ(x))$$ $$5.\; (∃x)(ϕ(x) ∧ ψ(x)) =⇒ ((∃x)ϕ(x) ∧ (∃x)ψ(x))$$ $$6.\; (∀x)(∀y)ϕ(x, y) ⇐⇒ (∀y)(∀x)ϕ(x, y)$$ $$7.\; (∃x)(∃y)ϕ(x, y) ⇐⇒ (∃y)(∃x)ϕ(x, y)$$ $$8.\; (∃x)(∀y)ϕ(x, y) =⇒ (∀y)(∃x)ϕ(x, y)$$

I have the following questions:

  • How would one go about proving these properties? Most of them "make sense", but this is not a valid argument. My background in formal logic (and set theory) is not large, so I will present here my thought process.
  • It "makes sense" that a predicate $\forall x (P(x))$ if and only if $\bigwedge_{x}P(x)=P(x_1) \land P(x_2) \land ...$, where $x$ loops through the domain of discourse. The same could be said about the existential quantifier, $\exists x (P(x))$ if and only if $\bigvee_{x}P(x)$. Can we take this as a definition? Is it rigurous to say that theese are definitions? How would we formalize this concept of "disjuncting" some possibly infinite number of elements in our domain of discourse.

Now I will do my best to prove the 8 properties mentioned above, assuming the so called definitions of the quantifiers (would gladly appreciate if someone elaborates this in detail). I will assume that the distributive laws and the associative/commutative laws and De Morgan's laws hold when working with an infinite number of propositions. If we were to have a finite number of propositions, one could prove the rules by doing a truth table. One could also make an argument that we can check that these rules still hold if there is a countable number of propositions (I do not think that this is a good idea because we first have to define set theory, then postulate the induction via Peano's postulates or any other way, possibly using Zermelo-Frankel axioms).

Having said that, I will attempt to prove the properties mentioned above(here the meaning of $p \iff q$ is that $p \leftrightarrow q$ is a tautology and the meaning of $p \implies q$ is that $p \to q$ is a tautology).

Proof for $1.$:
$$¬(∀x)ϕ(x) \overset{\text{definition}}{\iff} ¬ \bigwedge_x(\phi(x)) \overset{\text{De Morgan's Law}}{\iff} \bigvee_x(¬\phi(x)) \overset{\text{definition}}{\iff} (∃x)¬ϕ(x)$$

Proof for $2.$:
$$(∀x)(ϕ(x) ∧ ψ(x)) \overset{\text{definition}}{\iff} \bigwedge_x(ϕ(x) ∧ ψ(x)) \overset{\text{commutativity and associativity}}{\iff} \bigwedge_x(ϕ(x)) \land \bigwedge_x(ψ(x)) \overset{\text{definition}}{\iff} ((∀x)ϕ(x) ∧ (∀x)ψ(x))$$

Proof for $3.$: We could use the fact that $p \leftrightarrow q \iff (¬p) \leftrightarrow (¬q)$ and $2.$ The direct proof:
$$(∃x)(ϕ(x) ∨ ψ(x)) \overset{\text{definition}}{\iff} \bigvee_x(ϕ(x) ∨ ψ(x)) \overset{\text{commutativity and associativity}}{\iff} \bigvee_x(ϕ(x)) \lor \bigvee_x(ψ(x)) \overset{\text{definition}}{\iff} ((∃x)ϕ(x) ∨ (∃x)ψ(x))$$

Proof for $4.$:
$$((∀x)ϕ(x) ∨ (∀x)ψ(x)) \overset{\text{definition}}{\iff} \bigwedge_x(\phi(x)) \lor \bigwedge_x(\psi(x)) \overset{\text{distributivity}}{\iff} \bigwedge_x(\bigwedge_y(\phi(x) \lor \psi(y))) \overset{\text{distributivity(common factor)}}{\iff} \bigwedge_x(\phi(x) \lor (\bigwedge_y(\psi(y)))) \overset{\text{}}{\implies} \bigwedge_x(\phi(x) \lor \psi(x)) \overset{\text{definition}}{\iff} (∀x)(ϕ(x) ∨ ψ(x))$$

Proof for $5.$: We can deduce it from the contrapositive of $4.$.

Proof for $6.$:
$$(∀x)(∀y)ϕ(x, y) \overset{\text{definition}}{\iff} \bigwedge_x(\bigwedge_y(\phi(x, y))) \overset{\text{commutativity and associativity}}{\iff} \bigwedge_y(\bigwedge_x(\phi(x, y))) \overset{\text{definition}}{\iff} (∀y)(∀x)ϕ(x, y)$$

Proof for $7.$:This can also be deduced from the contrapositive of $6.$
$$(∃x)(∃y)ϕ(x, y) \overset{\text{definition}}{\iff} \bigvee_x(\bigvee_y(\phi(x, y))) \overset{\text{commutativity and associativity}}{\iff} \bigvee_y(\bigvee_x(\phi(x, y))) \overset{\text{definition}}{\iff} (∃y)(∃x)ϕ(x, y)$$

For $8.$: I have tried using the distributive property, but I could not find a general formula for distributing $\bigvee_x(\bigwedge_y(\phi(x, y)))$. If we could somehow generalize $5.$ such that "exists(conjunction) implies conjunction(exists)", namely $(∃x)(\bigwedge_y(\phi(x, y))) \implies \bigwedge_y((∃x)ϕ(x, y))$. But $8.$ is a generalization of $5.$, so this doesn't feel like a proof.

Are there also any other important properties like these for predicates? Moreover, if I have proved this for some arbitrary predicates $\phi$ and $\psi$, does that mean that $\forall \phi(6 \text{ holds })$, which would be second order logic? Again, I am not very experienced in formal logic and I would gladly appreciate any resource for me to learn this topic better(formal logic, higher order logic, etc). Thanks!

$\endgroup$
4
  • 1
    $\begingroup$ Eight formulas to be proved???? Maybe start with a couple of them... $\endgroup$ Commented Feb 21, 2023 at 10:38
  • 2
    $\begingroup$ Now you have 11 similar cases to be managed :-) $\endgroup$ Commented Feb 21, 2023 at 10:53
  • $\begingroup$ @MauroALLEGRANZA I have proved every formula from 1-7, and i have rewritten my question to better emphasize my point $\endgroup$ Commented Feb 21, 2023 at 20:00
  • 1
    $\begingroup$ @MauroALLEGRANZA also what is a proof system? I have looked it up on wikipedia and it says it is a a sort of a "system of axioms". Can't we just prove it assuming no axioms? Or let the set to be the empty set and use just the laws of logic? $\endgroup$ Commented Feb 21, 2023 at 21:37

1 Answer 1

1
+50
$\begingroup$

To work through this exercise, you need to have a clear idea what it means (or takes) to prove statements of the form $(\forall x) P(x)$, $\neg P$, etc. As a side note, I'd also say that it's a good idea to be explicit about the domain $D$ of any variable that you are quantifying over, because for example some implications that one might intuitively expect, like $(\forall x) P(x) \Rightarrow (\exists x) P(x)$, don't hold if the domain is empty, but do hold if the domain is nonempty [and sometimes it's hard to know these things in advance; for example, if the $D$ is the set of odd perfect numbers, then we don't know if $D$ is empty or nonempty].

To prove $\neg P$ under some set of assumptions $A$, show that the assumptions $A$ together with $P$ lead to a contradiction (falsity). For example, to show that

$$(\forall x \in D) \neg P(x) \Rightarrow \neg (\exists x \in D) P(x),$$

assume $(\exists x \in D) P(x)$ together with $(\forall x \in D) \neg P(x)$. The first means there is some element $x_0 \in D$ such that $P(x_0)$ is true. On the other hand, if $(\forall x \in D) \neg P(x)$, then $\neg P(x_1)$ is true for any $x_1 \in D$; in particular, $\neg P(x_0)$ is true. In that case we have that both $P(x_0)$ is true and $\neg P(x_0)$ is true, but we know that if $P(x_0)$ is true then $\neg P(x_0)$ is false, and there's your contradiction: the statement $\neg P(x_0)$ cannot be simultaneously true and false.

To prove $(\forall x \in D) P(x)$ under some set of assumptions $A$, let $x_0$ be a particular but arbitrary element of $D$, and then prove that $P(x_0)$ is true under the assumptions $A$. For example, let's prove that

$$\neg (\exists x \in D) P(x) \Rightarrow (\forall x \in D) \neg P(x).$$

So, let $x_0 \in D$ be an arbitrary element. We assume $\neg (\exists x \in D) P(x)$, and our goal is to prove $\neg P(x_0)$. Remembering what we said in the previous paragraph, it suffices to prove that the assumptions $P(x_0)$ and $\neg (\exists x \in D) P(x)$ together lead to a contradiction. But the assumption $P(x_0)$ witnesses the fact that $(\exists x \in D) P(x)$ is true [the latter means $P(x_1)$ is true for some $x_1 \in D$, but you see this by taking $x_1$ to be $x_0$!]. But this contradicts the other assumption that $\neg (\exists x \in D) P(x)$ is true, and now the proof is complete.

From the work above, you can now prove (1) [hint: define $P(x)$ to be $\neg \phi(x)$, and use double negation laws].

To prove $P \wedge Q$ under a set of assumptions $A$, prove separately that $P$ follows from $A$ and that $Q$ follows from $A$. So for the forward implication of (2), prove that $(\forall x \in D) (\phi(x) \wedge \psi(x))$ implies $(\forall x \in D) \phi(x)$ [and similarly with $\psi$ replacing $\phi$]. To prove

$$(\forall x \in D) (\phi(x) \wedge \psi(x)) \Rightarrow (\forall x \in D) \phi(x),$$

let $x_0$ be a particular but arbitrary element of $D$, and assume $(\forall x \in D) (\phi(x) \wedge \psi(x))$; our goal is to prove $\phi(x_0)$. But from the assumption $(\forall x \in D) (\phi(x) \wedge \psi(x))$, it follows that $\phi(x_1) \wedge \psi(x_1)$ for any $x_1 \in D$, in particular when $x_1 = x_0$. So the statement $\phi(x_0) \wedge \psi(x_0)$ is true. This forces $\phi(x_0)$ to be true, which is what we wanted.

To prove the reverse implication of (2), i.e., to prove

$$((\forall x \in D) \phi(x)) \wedge ((\forall x \in D) \psi(x)) \Rightarrow (\forall x \in D) (\phi(x) \wedge \psi(x)),$$

remember what we said about how to prove statements of the form $(\forall x \in D) P(x)$ from a set of assumptions $A$. I'm going to leave this one as an exercise.

(3) follows from (2) by invoking "$\neg \forall \equiv \exists \neg$" and/or "$\neg \exists \equiv \forall \neg$", which we have carried out above, together with De Morgan laws that govern the interaction between $\vee, \wedge$, and $\neg$. I'm going to leave this as an exercise as well.

In fact, the methods I have explained should enable you to prove (4) and (5) as well.

For (6), let $D$ be the domain of discourse for the variable $x$, and $E$ the domain for $y$. To prove

$$(\forall x \in D)(\forall y \in E) \phi(x, y) \Rightarrow (\forall y \in E)(\forall x \in D) \phi(x, y),$$

look at what we're trying to prove, and read it in the order in which the variables approve. According to the methods above, we let $y_0$ be a particular but arbitrary element of $E$, and under the assumption $(\forall x \in D)(\forall y \in E) \phi(x, y)$, we set out to show that $(\forall x \in D) \phi(x, y_0)$ follows. But again, by the same method, we now let $x_0$ be a particular but arbitrary element of $D$, and under the assumption $(\forall x \in D)(\forall y \in E) \phi(x, y)$, our goal is now to prove that $\phi(x_0, y_0)$ follows. But from that assumption, we know that $(\forall y \in E) \phi(x_1, y)$ holds for any element $x_1$ of $D$; in particular, $(\forall y \in E) \phi(x_0, y)$ holds. I'll let you take it from here.

(7) follows from (6) by invoking equivalences "$\neg \forall \equiv \exists \neg$" and/or "$\neg \exists \equiv \forall \neg$"; I'll let you take it from here.

The most interesting is (8), especially since the converse is false. But again, follow the methods above: to prove that $(\forall y \in E)(\exists x \in D) \phi(x, y)$ follows from the assumption, let $y_0$ be a particular but arbitrary element of $E$. The goal is to prove $(\exists x \in D) \phi(x, y_0)$ follows from the assumption. But if the assumption $(\exists x \in D)(\forall y \in E) \phi(x, y)$ holds, then there is some element $x_0 \in D$ such that $(\forall y \in E) \phi(x_0, y)$ holds. Hold that $x_0$ fixed. (For that $x_0$) it means that $\phi(x_0, y_1)$ holds for every $y_1 \in E$, in particular when $y_1 = y_0$, so $\phi(x_0, y_0)$ is true. But now that $x_0$ witnesses the truth of $(\exists x \in D)(\phi(x, y_0))$, and now we are done.

By the way, throughout there have been statements of type "let $x_0$ be a particular but arbitrary element of $D$...". At this point you might cry out, "Hang on! Suppose the domain $D$ were empty!" But that's okay. Remember that those statements were introduced as temporary assumptions in the course of proof. If that assumption doesn't hold (if there is no such $x_0$), then it means that the collection $Q$ of assumptions collectively is false. But if the assumption statement $Q$ is false, then we know from truth tables that $Q \Rightarrow R$ is automatically true, no matter what $R$ is, and so the implication will hold vacuously in that circumstance, anyway. Hence it is harmless to assume that we have in our hand some such $x_0$.

$\endgroup$
4
  • 1
    $\begingroup$ Hi, you seem to have missed the question about how to define universal and existential quantifiers. $\endgroup$
    – DiaRar
    Commented Jun 11, 2023 at 13:43
  • $\begingroup$ Hello! I am satisfied with the answer, but as @FurrySenko mentioned, what are the rigurous definition of $\forall$ and $\exists$? I do not think my "definitions" can be made rigurous if the domain of discourse is infinite(we can make an argument we don't know what infinite is without using set theory). The proof you presented is clear, however I would like that you detail the rigurous "definitions" of the existential and universal quantifiers. Thank you! $\endgroup$ Commented Jun 12, 2023 at 20:08
  • 1
    $\begingroup$ @Shthephathord23 I may give that as a separate answer, because the current answer is already long. As you surmise, the treatment of quantifiers can and should be given without recourse to infinitary formulas, but thinking of quantifiers in terms of infinitary conjunctions/disjunctions won't lead you seriously astray at the intuitive level, at least not for classical logic and mathematics. The trouble is, these things take time to explain properly. $\endgroup$
    – user43208
    Commented Jun 13, 2023 at 0:48
  • $\begingroup$ @user43208. The separate answer about the definitions of quantifiers would be gladly appreciated. $\endgroup$ Commented Jun 14, 2023 at 5:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .