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!
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$.