1
$\begingroup$

In an interpretation, are the domain and the subsets slated to go into the predicate letters, supposed to be well-defined sets? If the Axiom of Replacement is used to define a subset of the domain, using a formula, and this formula is undecidable for some $x$ in the domain, then I can't understand how a truth value can be assigned to the sentence "$x$ is in that subset" in the interpretation. I am very confused! Can anyone help?

  • 2
    http://mathoverflow.net/questions/72016/model-theory-confusion-closed2011-08-03
  • 2
    You should view the definition of model, and definition of truth in a model, as being like any other mathematical definition, in, say, group theory. And we can know what it *means* for a sentence to be true in a structure, even if we don't know *whether* the sentence is true in that structure. It is best not to drag formal set theory into the game. Model Theory is a field of mathematics like any other.2011-08-03
  • 0
    I would like to record a vote *against* closing. This, to me, appears to be a question about how model theory should be carried out inside an axiomatic set theory, which is a fair enough question. I'm no expert, but I suspect there may have been some confusion between theory and metatheory. I would certainly like to see a detailed answer from our resident set theorists.2011-08-04

2 Answers 2

3

I can't understand how a truth value can be assigned to the sentence "x is in that subset" in the interpretation.

A model $M$ of set theory will consist of a set $D_M$ (which is the domain of $M$) and a binary relation $E_M$ on $D_M$ (which is the interpretation of the $\in$ symbol) The truth of formulas is defined inductively via the T-schema:

  • For $a, b \in D_M$, the formula "$a \in b$" holds in $M$ if and only if $E_M(a,b)$ holds.

  • A formula $(\forall x)\phi(x)$ holds in $M$ if and only if for every $a \in D_M$, the formula $\phi(a)$ holds in $M$

  • A formula $(\exists x)\phi(x)$ holds in $M$ if and only if there is some $a \in D_M$ such that $\phi(a)$ holds in $M$.

  • The truth values of compound formulas $\phi \land \psi$, $\lnot \phi$, $\phi \to \psi$, and $\phi \lor \psi$ are determined from the truth values of $\phi$ and $\psi$ using truth tables.

One aspect of this definition is that, in the clauses for the quantifiers, no provision is made about effectiveness. Even if $D_M$ is countable, we may not have an algorithm that tells us whether $\phi(x)$ holds as a function of $x$ for a fixed $\phi$. But we know that either there is some $a \in D_M$ such that $\phi(a)$ holds, or else for every $a \in D_M$ the negation $\lnot \phi(a)$ holds. In other words the definition about truth values is solely about truth values, not about how we might come to determine truth values effectively.

0

In first order logic, predicate symbols are interpreted by arbitrary sets. For truth values, all we know is that a given formula is either true of false in a given structure. It may depend on set theory axioms, which of the two holds.

I'll give an example. Consider a structure ${\cal A}$ whose domain is ${\cal P}(\mathbb R)$ where a predicate symbol $p$ is interpreted as the set $\{A \subseteq \mathbb R : \aleph_0 < |A| < 2^{\aleph_0}\}$. Now the definition of $\cal A$ is not absolute, meaning that ${\cal A}$ is different in different models of set theory. In each model of set theory ${\cal A} \models \exists x p(x)$ has a definite value. However this values depends on whether CH holds in the given model.

In practice, however, set theoretic questions rarely arise in contemporary model theory. Most properties studied by model theorists do not depend on set theory axioms. It is best to approach model theory as any other branch of mathematics - with naive ideas about sets.

Edit I've changed $\mathbb N$, to $\mathbb R$, which obviously was incorrect.

  • 0
    Is it really possible to construct such a predicate $p$?2011-08-04
  • 0
    I mean, is there a first-order theory $T$, of which $\mathcal{A}$ is a model, such that there is a predicate $p$ which is *necessarily* interpreted as such a set?2011-08-04
  • 0
    The answer again depends on CH. If CH holds than $P = \{A \subseteq \mathbb R: \aleph_0 < |A| < 2^{\aleph_0}\} = \emptyset$. So $\lnot \exists x p(x)$ does the job. On the other hand, if CH does not hold, pick an element $A_0 \in P$ and let $P' = P \cup \{\mathbb R\} \setminus \{A_0\}$. Then ${\cal A} = \langle {\cal P}(\mathbb R), P \rangle$ is isomorphic to $\langle {\cal P}(\mathbb R), P' \rangle$. So there is no such theory.2011-08-04
  • 3
    @Zhen Lin: it is not possible to use a theory to ensure that the interpretation consists of particular sets. For example, using Henkin models, it is possible to construct a model of any consistent first-order theory such that domain of them model is any given countable set of objects.2011-08-04
  • 0
    @Carl: I think that Zhen wants a theory whose only model on $\cal P(\mathbb R)$ interprets $p$ as the set $\{A \subseteq \mathbb R: \aleph_0 < |A| < 2^{\aleph_0}\}$.2011-08-04
  • 0
    Hi There Thanks for showing an interest in my post. Are you saying that all formulas simply because of the way they are constructed must be TRUE or FALSE in any given INTERPRETATION.I can see that for a finite DOMAIN. For a COUNTABLE DOMAIN it should be true because you could test one element after another so that the process would either go on forever or HALT. Is that related to what you are saying?2011-08-04
  • 0
    I am saying that the function that assigns a truth value to a formula and an interpretation is well defined. This does not mean that ZFC or any other theory should decide what its values are for any particular formula and interpretation. Perhaps this analogy can help. Each Turing machine either halts or not. Now consider the Turing machine that tries to deduce $\bot$ from ZFC. If ZFC is consistent, then the machine will never halt. But ZFC can't show its own consistency, so it can't prove that the Turing machine will never halt. Thus ZFC does not decide whether our machine halts or not.2011-08-04
  • 0
    I was not refering to any theory last comment.Ifthe DOMAIN is given as finite set EXAMPLE Dis{ a,b,c,d,e,f,g,h } Ais{a,b} Bis {a,g} thenFOR ALL x : x in A implies x in B is FALSE. And that isa property of the structures given.Nothing to do with any axioms.Ifthe DOMAINis{1,2,3,...}Ais{xin D:there exists two consecutive primes greater than x }Andthe formula isFOR ALLx: x isinA Then if thatis aTRUE formula it mustbe inherentproperty of the positive integers.if it is FALSE must be same. BUILD SUBSETS ofthat TYPE UP INDUCTIVELY I can understand whya formula must beTRUEorFALSE otherwise not sure?2011-08-04
  • 0
    If there are infinitely many consecutive primes, then $\forall x A(x)$ is true, otherwise (i.e. if there are only finitely many consecutive primes), then $\forall x A(x)$ is false. So in both cases $\forall x A(x)$ is either true or false. You can substitute "if there are infinitely many primes" with "whatever bizarre condition you like". As a side note, please don't concatenate words to save characters, instead write two separate comments. Also, please use tex notation, it makes everybody's life much easier.2011-08-04
  • 0
    O.K. Thanks Levon. I,ll find out about tex notation.2011-08-04