7

Recently I stumbled upon an equivalence in analysis which is of the form $\forall x\varphi(x)\leftrightarrow\forall x\psi(x)$. This made me wonder if this is mabe equivalent to $\forall x(\varphi(x)\leftrightarrow\psi(x))$, i.e. if "$\forall$" is "distributiv" w.r.t. $\varphi$ and $\psi$.

My questions are:

  1. Does it even make sense to ask if $\forall x\varphi(x)\leftrightarrow\forall x\psi(x)$ is equivalent to $\forall x(\varphi(x)\leftrightarrow\psi(x))$, without specifying some " framework" within which this question has to be answered ? (Like for example the Hilbert system or in the sense of being true in all models ?)

  2. Is it the case that $\forall x\varphi(x)\leftrightarrow\forall x\psi(x)$ is indeed equivalent to $\forall x(\varphi(x)\leftrightarrow\psi(x))$ ?

*For those who want to know, how I arrived at this question:*$\varphi$ is the triangle inequality $$ \forall x,y\in\mathbb{R}:\ \left|x+y\right|\leqslant\left|x\right|+\left|y\right|\quad\quad\quad(1), $$ and $\psi$ the similar inequality $$ \forall x,y\in\mathbb{R}:\ \left|x-y\right|\leqslant\left|x\right|+\left|y\right|\quad\quad\quad(2), $$ and I wanted to show that $(1)$ and $(2)$ are equivalent. (The proof is short: If I know that $(1)$ is true, and want to prove $(2)$, I take some arbitrary $x,y\in\mathbb{R}$ and plug, $x,-y$ in $(1)$ and obtain that $(2)$ -- and similarly for the other implication.) This made me question, if $$ \forall x,y\in\mathbb{R}:\ \left|x+y\right|\leqslant\left|x\right|+\left|y\right|\ \longleftrightarrow\ \left|x-y\right|\leqslant\left|x\right|+\left|y\right| $$ also were true -- but I couldn't prove it using "usual mathematics", so I wondered this maybe is an instance of a general logical rule.

  • Obviously not, since you need for the pair $(x,y)$ on the left the pair $(x,-y)$ on the right. Replace the absolute value with any positive even function $0\le p(x)=p(-x)$ to make the claim less obvious. – Lutz Lehmann Dec 30 '13 at 18:33
  • @LutzL I don't understand, why is the fact that I need for the pair $(x,y)$ on the left a pair $(x,-y)$ on the right a negative answer to the second (I assume ?) question ? And why should I make the claim less obvious ? –  Dec 30 '13 at 20:54
  • You are claiming that for fixed x and y, $A(x,y)$ is equivalent to $B(x,y)$. But you are using that $B(x,y)$ is equivalent to $A(x,-y)$, that is, property $A$ for a different pair. Thus the second formulation does not work. – Lutz Lehmann Dec 30 '13 at 21:29

4 Answers4

6

Answering the first question, it doesn't make sense to formally ask anything without a formal theory. Informally it makes sense, everything does (or anything doesn't).

Answering the second question, with the standard 'meaning' for $\forall$ and $\to$ and given one-place predicates $\varphi$ and $\psi$ , it isn't true that $$\forall x\varphi(x)\leftrightarrow \forall x\psi (x)\iff \forall x(\varphi(x)\leftrightarrow \psi(x)).$$

As an example, in $\sf ZFC$, let $$\varphi(x): x\text{ is a real number and }x>0,$$ $$\psi(x): x\text{ is a real number and }x\text{ is invertible}.$$

Clearly $\forall x(\varphi(x)\leftrightarrow \psi(x))$ is false as there are negative invertible elements and $\forall x\varphi(x)\leftrightarrow \forall x\psi (x)$ is true because both $\forall x\varphi(x)$ and $\forall x\psi (x)$ are false.

Recall that $\leftrightarrow$ is expendable if you have $\neg$ and $\lor$. With this in mind one would suspect the equivalence couldn't possibly hold because of the non-distributivy of $\forall$ over $\lor$.

Git Gud
  • 31,356
1

It doesn't make sense to ask the question without any framework, but you're certainly working in some first-order predicate logic. It makes sense to ask whether the statements are logically equivalent.

They're not equivalent in this generality, however. You can check this by constructing an example structure where one statement holds but the other doesn't. If they were equivalent, they'd have to have the same truth value wherever you interpret them.

E.g.: Our structure will consist of 2 objects $\{A, B\}$, and we'll use two predicates $\phi$ and $\psi$ which we'll interpret so that

$\phi(A)$ is true

$\psi(A)$ is false

$\phi(B)$ is false

$\psi(B)$ is true

In this structure, $\forall x\phi(x)$ and $\forall x \psi(x)$ are false, so $\forall x \phi(x) \leftrightarrow \forall x \psi(x)$ is true, but $\forall x (\phi(x)\leftrightarrow \psi(x))$ is false.

As a side note, the implication does hold one way in general: if $\forall x (\phi(x)\leftrightarrow\psi(x))$, then $\forall x \phi(x) \leftrightarrow \forall x \psi(x)$. So, you can "distribute" it across, which makes it weaker, but you can't generally "factor it out".

matt
  • 2,125
  • Your last paragraph, concerning the implication that does hold in one direction, made me wonder: Can I prove for my analysis example from my question that $\forall(\phi(x)\leftrightarrow\psi(x))$ holds ? For the "distributed version of $\forall$" I have proved it there, but proving it for the "factored out" version seems not possible: Since for some fixed $a,b$, for example $a=1,b=2$, I can't prove that $|1+2|\leq|1|+|2|$ only using $|1-2|\leq|1|+|2|$ and logical inference rules [...] –  Dec 30 '13 at 21:10
  • [...] (although of course I can prove it "directly" - it is almost tautological - but that isn't the point I think, since I didn't use the "hypothesis" of the implication). –  Dec 30 '13 at 21:18
  • It holds for sort of trivial reasons in your example as you've noticed, which is why you find proving it strange. Here both $\phi$ and $\psi$ are always true because of the triangle inequality (a property of the absolute value function). You don't have to use the hypothesis in a proof of an implication. This just indicates that stuff in the theory (here, the triangle ineq for $||$) is sufficient and you didn't need the hypothesis. Both $\phi$ and $\psi$ are always equivalent to "true" here. This is in contrast to something like "for all integers n, n is equal to 1 or 3 mod 4 iff n is odd". – matt Dec 31 '13 at 03:55
  • I don't quite understand why "both $\phi$ and $\psi$ are always true". Do you mean "$\forall\phi$ and $\forall\psi$ are true" ? Also, since the proof of the "factored out" version only uses triangle inequality, which actually is the $\forall x \phi(x)$ formula, I'm proving $\forall x (\phi \rightarrow \psi)$ by using $\forall x\phi \rightarrow \forall x\psi$. Isn't that somehow strange ? I still can't seem to quite wrap my head around the proof of $\forall x (\phi \rightarrow \psi)$... –  Dec 31 '13 at 17:16
  • Yes, I mean that $\forall x, y \phi(x,y)$ and $\forall x,y \psi(x,y)$ are true for these $\phi, \psi$ over the reals. So, you can prove $\forall x,y (\phi(x,y) \leftrightarrow \psi(x,y))$ like this: "Let $x,y\in\mathbb{R}$. Both $\phi(x,y)$ and $\psi(x,y)$ are true by the triangle inequality (noting $|x-y|=|x+(-y)|$ if you'd like), so $\phi(x,y)\leftrightarrow\psi(x,y)$ is true. Hence $\forall x,y (\phi(x,y)\leftrightarrow\psi(x,y))$." This is a valid proof, but it's silly... – matt Dec 31 '13 at 17:48
  • You're actually proving $\forall x (\phi \rightarrow \psi)$ using only $\forall x \psi$, which is a theorem. You could use $\forall x \psi$ to prove $\forall x (P \rightarrow \psi)$ for any P. The hypothesis part is irrelevant since the conclusion is true in the theory already. – matt Dec 31 '13 at 17:50
  • For an analogy: it's like we're proving "for all x, x is red if and only if it is large" in a universe where all objects are large red balls. The proof wouldn't require any definition chasing to see how "red" and "large" relate to each other (and really, they may generally have nothing to do with each other), so it won't look like a math proof you're used to. You can simply observe that everything is red, and everything is large, so the $\leftrightarrow$ holds by just looking at $\leftrightarrow$'s truth table (it's true when both sides are true). – matt Dec 31 '13 at 17:58
1

You might want to look at Skolemization in which we move the all quatifiers to the left end of the expression owing to some of its distributive properties. the Even though what you said is false in general, a list of distributive laws which actually works can be found here (2.13 (d))

Blue Elephant
  • 61
0

This is a partial answer given for the sake of it. Hence why I've made it community wiki.

The following is constructed from a path of a tableau, which I could produce here if you like (but it will take a while).

Suppose $$\color{red}{(\forall x\varphi(x)\leftrightarrow \forall x\psi (x))}\leftrightarrow \color{blue}{\forall x(\varphi(x)\leftrightarrow \psi(x))}.$$ Then if $\color{red}{\neg (\forall x\varphi(x)\leftrightarrow \forall x\psi (x))}$ holds, then $\color{blue}{\neg \forall x(\varphi(x)\leftrightarrow \psi(x))}$ holds and so we can "instantiate" and say that there exists an $\color{blue}{a}$ such that $$\color{blue}{\neg (\varphi(a)\leftrightarrow \psi(a))}.$$ Assume $\color{blue}{\varphi(a)}$. Now $\color{blue}{\neg\psi(a)}$, but from $\color{red}{\neg (\forall x\varphi(x)\leftrightarrow \forall x\psi (x))}$, if we also assume $\color{red}{\neg\forall x\varphi(x)}$, we get $\color{red}{\forall x\psi(x)}$, giving $\color{red}{\psi(a)}$, a contradiction.

Shaun
  • 44,997
  • 1
    +1 for the colors :) But could you please explain, how you conclude from $\varphi(a)$ that $\neg \psi(a)$ holds (resp. how you get from the red equivalence and the other assumption that $\forall x \psi(x)$ has to hold) ? –  Dec 30 '13 at 20:49
  • Thank you. Think about when $A\leftrightarrow B$ is false. The above was produced using the method of analytic tableaux, explained in these lecture notes. – Shaun Dec 30 '13 at 21:19
  • [The Wikipedia article and the notes in their entirety are kind of overkill for your questions. Sorry. It should suffice to consider when $A\leftrightarrow B$ is false. Remember that $A\to B$ behaves like $(\neg A)\vee B$.] – Shaun Dec 30 '13 at 21:45
  • What do you mean by saying we instantiate? –  Oct 28 '17 at 01:11
  • I mean this, @Idonotknow. – Shaun Oct 28 '17 at 08:14