2
$\begingroup$

In Paul Cohen's Set Theory and the Continuum Hypothesis (Page 71) there is a lemma with the assumption that $\exists x\, P(x)$. The ''proof'' there, uses the following argument:

Intuitively the lemma is obvious, since if $F$ is valid it holds for every set $S$ in which relations and constants corresponding to the formal language are defined and hence for the subset $$\{x|\,x \in S \land P(x)\}.$$ Thus $F_P$ is true in every model and hence is valid.

Where

If $F$ is a formula, then $F_P$ denotes the formula obtained from $F$ by adjoining to every variable $x$ the condition $P(x)$. That is in building $F_P$, each $\exists x\, B$ becomes $$\exists x\,[P(x) \land B]$$ and each $\forall x\, B$ becomes
$$\forall x\,[P(x) \rightarrow B].$$ We say $F_P$ is $F$ relativized to the condition $P(x)$.

Obviously, I must be missing something. But say that $F$ is the following statement $$\exists x\, \lnot P(x)$$ and it holds in some model $M$. That is $P(x)$ is true for some $x\in M$ and is false for some $x\in M$. Now for the subset $$B = \{x|\,x \in M \land P(x)\}$$ $F$ clearly fails and $F_P$ cannot be true.

What am I missing? Must $F$ be restricted to certain types of statements?


Christian Remling and Noah S. Explained that $F$ as defined above is not valid.

Still, I would like to get a better intuition of the lemma mentioned in Paul Cohen's book. So let's look at another example.

Assuming Peano axioms, say $F$ is $$\forall x \exists y\, x < y $$ is it considered valid?

If $F$ is valid, then if $P(x)$ is some property like $$x < 5$$ then $F_p$ becomes $$\forall x\, [x < 5 \rightarrow \exists y\, (y < 5 \land x < y)].$$ Which is clearly invalid considering $x=4$.

If $F$ is not valid, can someone give a ''non trivial'' example of a valid statement that includes $\forall$?

$\endgroup$
  • 1
    $\begingroup$ This is missing some context (what does "$\in>$" mean? what is the meaining of $F_P$?), but it seems your $F$ is not valid. $\endgroup$ – Noah Schweber Jun 18 '14 at 22:23
  • 1
    $\begingroup$ Yes, your $F$ is not "valid", which he defines on pg. 9 as a (propositional) tautology. Here it probably means valid in first-order logic (= a theorem of the theory with no non-logical axioms). $\endgroup$ – Christian Remling Jun 18 '14 at 22:25
  • 1
    $\begingroup$ You asked for a non-trivial example of a valid statement that includes $\forall$. Here's one that I think is non-trivial (despite its brevity), at least in the sense that many people have to think about it for a while before they see why it's valid: $\exists x\forall y\,(P(x)\implies P(y))$ $\endgroup$ – Andreas Blass Jun 20 '14 at 14:10
  • $\begingroup$ This is probably not the type of answer you were looking for (to your update), but anyway: first-order logic is undecidable, which could be interpreted as saying that there are lots of highly non-trivial valid sentences. $\endgroup$ – Christian Remling Jun 20 '14 at 20:26
3
$\begingroup$

A sentence is "valid" if it is true in every model, that is, if it is a tautology; in particular, "valid" is much stronger than "true" (or "true over here"). Your example sentence is not, in fact, valid.

One doesn't get to "assume" axioms when talking about validity - a sentence $\varphi$ in a relational$^*$ language $\Sigma$ is valid iff $M\models \varphi$ for every $\Sigma$-structure $M$; or, if you prefer syntactic descriptions, if $\{\}\vdash\varphi$.

A silly response to your last question is: "No, there are no nontrivial validities, since every valid sentence is in fact equivalent to "$\forall x(x=x)$." Of course, what you are asking for presumably is an example of a validity which is not obviously valid; Andreas has given one in the comments, but more generally note that the problem of deciding whether a sentence is valid is equivalent to the Halting problem, so while one might think of each individual validity as trivial, the collection of validities is far from trivial.


$^*$ Why "relational?" Well, arbitrary subsets of relational structures form relational structures, but if we have function symbols involved this won't be the case: $\{1\}$ is not a substructure of the group $\mathbb{Z}$, since it's not closed under the group operation. Usually this isn't too much of a restriction, since as Emil says we can replace function symbols with their graphs, but sometimes it can be problematic. In the case of set theory, though, everything is naturally relational already, so there's no difficulty.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

(This didn’t fit into a comment.) Concerning your edit: no, $F$ is still not valid, because you cannot “assume Peano axioms”. What is valid is an implication of the form $G\to F$, where $G$ is a conjunction of Peano axioms that are sufficient to derive $F$. Then the relativization $(G\to F)_P$ is indeed valid (but not very interesting, as $G_P$ will be contradictory), with one caveat: Cohen’s statement as written only applies to purely relational languages (which is fine for the intended application in set theory). You’d thus have to formulate Peano arithmetic in a language with predicate symbols for the graphs of $0,S,+,\cdot$, or alternatively, redefine the relativization as an implication whose premise states that the domain of $P$ is closed under all function symbols in sight.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.