1

I've the following exercise:

Determine if the following formula is satisfiable or valid:

$P(x_{0}) \rightarrow \forall x_{1}P(x_{1})$

I've no idea what $P$ means, no information is given and my first thought is that if we define $P(x_{0}) := \ x_{0} \wedge \neg x_{0}$ then the formula is satisfiable, but if $P(x_{0}) := x_{0} \doteq c$ where $c$ is a constant then this is not true in general.

So from my point of view the answer depends on $P$.

How do I solve it? What is my problem?

Community
  • 1
revylffadets
  • 25
  • I would read this as a formula in first-order logic, with unspecified predicate $P$ and variable terms $x_0,x_1$. To say whether it is "satisfiable or valid" suggests that on the one hand it might be true (provable in the predicate calulus) for some particular choice of $P$, and on the other hand it might hold for all choices of predicate $P$. So I think the dependence on choice of $P$ is the crux of the exercise. – hardmath May 26 '14 at 23:02
  • If you think that the possible values of $x_0$ are statements, then you should drop that idea; $x_0$ ranges over elements of a structure. If, on the other hand, you don't think that the possible values of $x_0$ are statements,then what do you mean by $x_0\land\neg x_0$? – Andreas Blass May 27 '14 at 00:01
  • Consider the case with the predicate $P$ interpreted as $... = 0$ and consider the domain $\mathbb N$ of natural numbers. The resulting formula : $x_0 = 0 \rightarrow \forall x_1 (x_1 = 0)$ is true in $\mathbb N$ ? Because, if we can found an interpretation in which the formula is not true, for sure it will not be valid (which means true in all interpretations). – Mauro ALLEGRANZA May 27 '14 at 06:20
  • It can also be stated in set notation as $$\forall U, X:[\exists a\in U \implies \exists b\in U:[b\in X \implies U\subset X]]$$ or equivalently... $$\forall U, X:[\exists a\in U \implies \exists b\in U:[b\notin X \lor U\subset X]]$$ – Dan Christensen May 27 '14 at 21:28

2 Answers2

2

$P$ is an arbitrary property. The sentence says that if $x_0$ has property $P$ then everything has property $P$. This is not universally true for all choices $P$ and $x_0$. But it is true for some choices of $P$ and $x_0$.

Rene Schipperus
  • 39,526
1

This is the drinker's paradox.

Edit: this was longer than I expected so I'll summarize: the statement is always satisfiable (there is always a choice of $x_0$ that makes it true no matter what $P$ is), but $x_0$ can be defined in a way to make the statement invalid. If $x_0$ is existentially quantified, then the statement is valid.

Consider 3 cases for $P$:

1) $P$ is universally false. Witness $x_0$ to be anything, the implication becomes: $$P(x_0) \rightarrow \forall x_1\,P(x_1)$$ $$\text{false} \rightarrow \text{false}$$ $$\text{true}$$

2) $P$ is universally true. Witness $x_0$ to be anything, the implication becomes:

$$P(x_0) \rightarrow \forall x_1\,P(x_1)$$ $$\text{true} \rightarrow \text{true}$$ $$\text{true}$$

3) $P$ is sometimes true and sometimes false. Witness $x_0$ to be a value that makes $P(x_0)$ false:

$$P(x_0) \rightarrow \forall x_1\,P(x_1)$$ $$\text{false} \rightarrow \text{false}$$ $$\text{true}$$

So you see, no matter the choice of $P$, the statement (let's call it $T$) is satisfiable. To make it a valid tautology, you have to consider$x_0$, is it already defined, or is it quantified:

1) $T$ can be invalid if $P$ is sometimes true and sometimes false: $$\begin{cases} \text{Define } x_0 \text{ as something that makes } P(x_0) = \text{true} \\ \text{Define } T \text{ as } P(x_0) \rightarrow \forall x_1\, P(x_1) \\ \end{cases} $$

2) $T$ can be valid if $P$ is sometimes true and sometimes false: $$\begin{cases} \text{Define } x_0 \text{ as something that makes } P(x_0) = \text{false} \\ \text{Define } T \text{ as } P(x_0) \rightarrow \forall x_1\, P(x_1) \\ \end{cases} $$

3) $T$ is valid if $P$ is always true or always false $$\begin{cases} \text{Define } x_0 \text{ as anything } \\ \text{Define } T \text{ as } P(x_0) \rightarrow \forall x_1\, P(x_1) \\ \end{cases} $$

4) $T$ is valid for any definition of $P$ if $T$ is existentially quantified: $$\begin{cases} \text{Define } T \text{ as } \exists x_0\,\bigg(P(x_0) \rightarrow \forall x_1\, P(x_1) \bigg)\\ \end{cases} $$

Some of the above statements are only true if the domain of discourse is non-empty. Most logics assume that the universe is not nonempty.

DanielV
  • 23,556