Definability | Logicians do it with Models

Archive for the ‘Definability’ Category

Hellman’s Second Definability Example

September 27, 2010

Tarski’s theorem shows that the set $\mathsf{Th} (\Omega)^\#$ of code numbers of sentences true in $\Omega$ is not definable. This has negative consequences for the prospects of aritmetically defining a truth predicate for arithmetic. Nevertheless, Tarski showed how to define truth in terms of satisfaction and by giving an inductive definition of satisfaction beginning with atomic sentences and on up with sentences of higher and higher complexity in terms of the satisfaction of their parts. While a stronger set theory or higher-order logic is still required to convert the inductive definition into an explicit one, Hellman investigates how Det-T and Det-R measure up against this weaker type of definability.

Addison’s theorem establishes that the class of arithmetically definable sets of numbers is itself not an arithmetically definable class of sets. This means that in the language, $\textup{L}$ , of arithmetic extended by a one place predicate $\textup{G}(x)$ , no formula $\textup{S}$ is true in $\Omega$ when $\textup{G}(x)$ is assigned a set $\textup{A}$ of numbers such that $\textup{A}$ is definable over $\Omega$ . The proof is involved and is clinched by contradiction on the existence of a generic arithmetical set (I may, or may not, get around to explaining what this is in the next post or so, since it involves explanation of the technique of forcing).

The example turns on this: Addison’s theorem shows that the predicate $\textup{DF}arith$ = ‘set of numbers definable in arithmetic’ is not inductively definable in arithmetic. Nevertheless, $\textup{DF}arith$ is determined by the primitive predicates of $\textup{L}$ . Set out the following: $\alpha$ is the set of standard $\omega$ -models of arithmetic. Now extend each model $m \in \alpha$ by adding the class $\textup{C}$ of all sets $\textup{X}$ of natural numbers from the domain of $m$ such that $\textup{X}$ is in the extension in $m$ of a formula $\textup{B}(x)$ of $\textup{L}$ with one free variable. Let $\alpha^{\textup{C}}$ be the class of $\alpha$ -structures extended in this way.

So, $\alpha^{\textup{C}}$ contains all the standard models of arithmetic that have standard interpretations of $\textup{DF}arith$ . This means that in $\alpha^{\textup{C}}$ -structures, $\textup{L}$ reference determines $\textup{DF}arith$ reference but within this same class of structures, $\textup{L} + \textup{G}(x)$ does not inductively define $\textup{DF}arith$ . In spite of this lack of definiability, Det-R still holds since (and this is all up to isomorphism) any two structures that assign the same interpretations to the primitives of $\textup{L}$ must also assign the same extension to the well-formed-formulas of $\textup{L}$ with only one free variable. So, up to isomorphism, the same sets of natural numbers are assigned to the distinguished elements of $\textup{C}$

The next example from Hellman is not mathematical, but from classical particle mechanics. After that I will go into Hellman’s clarification on the difference between the ontological and ideological status of attributes, properties and relations before moving into constructive work on the mental.

Posted in Definability, Supervenience and Determination | Leave a Comment »

“Physicalism” Concluding Summary

September 7, 2010

It took me a good while to get through this paper –more than I expected –but here we are.

What has Hellman accomplished?

First he showed us how to build the ontological principle of physical exhaustion, PE, $(\forall x)(\exists \alpha) (x \in \textup{R}(\alpha))$ . PE allows us to say that everything is exhausted by the physical without (embarrassingly) implying that everything is in the extension of a basic physical predicate.

Then he introduced the identity of physical indiscernables, IPI, and IPI’, $(\forall u)(\forall v)((\forall \phi) (\phi u \leftrightarrow \phi v) \rightarrow (u = v)$ and $(\forall \psi) (\forall u) (\forall v) (\exists \phi) (\psi u \wedge \lnot \psi v \rightarrow \phi u \wedge \lnot \phi v)$ , respectively. IPI says that if two objects have the same physical properties, then they are the same thing, while IPI’ says that no two objects are distinct with respect to a $\psi$ property without being distinct with respect to a $\phi$ property.

These three principles neither independently nor in conjunction imply or require reduction to the physical, but they are also too weak to express the physicalist thesis that physical phenomena determine all phenomena. He then turns his attention to principles of determination. In addition to PE and IPI/IPI’ Hellman introduces the determination of truth, Det-T: in $\alpha$ structures $\phi$ truth determines $\psi$ truth if, and only if, $(\forall m)(\forall m')((m, m' \in \alpha \wedge m \vert \equiv m' \vert \phi) \rightarrow m \vert \psi \equiv m' \vert \psi)$ , and Det-R: in $\alpha$ structures $\phi$ reference determines $\psi$ reference if, and only if, $(\forall m)(\forall m') ((m, m' \in \alpha \wedge m \vert \phi = m' \vert \phi) \rightarrow m \vert \psi = m' \vert \psi)$ .

Det-T says that once you have given a complete description of things in $\phi$ terms, there is only one correct way to describe them in $\psi$ terms. Det-R says that if two $\alpha$ structures agree in what they assign to the $\phi$ terms, then they agree on what they assign to the $\psi$ terms.

Given a notion of definability, Hellman is able to state the thesis of physical reduction, PE: in $\alpha$ structures, $\phi$ reduces $\psi$ , if, and only if, $(\forall \textup{P}(\textup{P} \in \psi \rightarrow \textup{P}$ is definable in terms of $\phi$ in $\alpha$ structures $)$ .

Given that assumptions about the mathematical-physical determination of all truths and, maybe, reference, are regulative principles of scientific theory construction –the assumption in general that all terms and all theories are reducible to mathematical-physical terms is probably false. Hellman’s physicalist materialism is instead composed of PE, DET-T and DET-R, with PE independent of PR and the determination principles.

Because there are non-standard models of the laws of science, our formal systems do not model scientific possibility in a way that permits the move from physical determination to physical reduction –thus Beth’s definibility theorem poses no threat to physicalist materialism. And any way you cut it, the link between theories as syntactic entities and reductionism doesn’t carry over to determination of reference, ruling out even accidental co-extensiveness between terms.

This sets up the theoretical background for an evaluation of the applications of physicalist materialism across disciplines and problems in philosophy of science, mind and social theory. In the next updates I will be covering Hellman’s 1977 “Physicalist Materialism” (Noûs) as well as giving a detailed, critical, evaluation of some of the anti-Materialist claims David Chamers makes in the early chapters of his book The Conscious Mind: In Search of a Fundamental Theory.

Posted in Definability, Physicalism, Reductionism, Supervenience and Determination | Leave a Comment »

Beth’s Definability Theorem

August 31, 2010

We’ll set this up in the most general way and later see how Hellman’s account in terms of $\phi$ and $\psi$ applies.

Letting $\textup{L}$ be a language with $p$ a $k$ -ary relation symbol not appearing in the relation-symbol set of $\textup{L}$ , $\textup{L}^{+}$ is the language that extends $\textup{L}$ and which includes $p$ . $\textup{T}^{+}$ is a theory in $\textup{L}^{+}$ .

We say that $p$ is explicitly definable if, and only if, there is an $\textup{L}$ formula $\theta$ with free variables $x_{0}\dots x_{k-1}$ such that $\textup{T}^{+} \models p x_{0}\dots x_{k-1} \leftrightarrow \theta$ . And we say that $p$ is implicitly definable if, and only if, for any $\textup{L}$ - structure $\mathfrak{A}$ and any $\textup{P}, \textup{Q} \subseteq \ \vert \mathfrak{A}\vert^{k}$ (i.e., the universe of the structure), if both $(\mathfrak{A}, \textup{P})$ , and $(\mathfrak{A}, \textup{Q})$ are models of $\textup{T}^{+}$ , then $\textup{P} = \textup{Q}$ .

Beth’s definability theorem says that if $\textup{L}$ a language with $p$ a $k$ -ary relation symbol not appearing in the relation-symbol set of $\textup{L}$ , $\textup{L}^{+}$ is the language that extends $\textup{L}$ and which includes $p$ and $\textup{T}^{+}$ is a theory in $\textup{L}^{+}$ , then $p$ is explicitly definable if, and only if, $p$ is implicitly definable.

To prove that explicit definability implies implicit definability is straightforward. Assume $\textup{T}^{+} \models p x_{0}\dots x_{k-1} \leftrightarrow \theta$ . Show for $\textup{P}, \textup{Q} \subseteq \ \vert \mathfrak{A}\vert^{k}$ , if $(\mathfrak{A}, \textup{P}), (\mathfrak{A}, \textup{Q}) \in \textup{M} od (\textup{T}^{+}) \rightarrow \textup{P} = \textup{Q}$ . Since we’re assuming $\textup{T}^{+} \models p x_{0}\dots x_{k-1} \leftrightarrow \theta$ , $\textup{P}$ is definable over $\mathfrak{A}$ (i.e., for $k$ -ary $p$ , $\textup{P} = \phi^{\mathfrak{A}}$ , for $\phi$ with $k$ free variables. Let $\phi = \theta$ . So $\textup{P} = \theta$ ; but $\textup{Q} \subseteq \ \vert \mathfrak{A}\vert^{k}$ and $(\mathfrak{A},\textup{Q})$ models $\textup{T}^{+}$ . So $\textup{P} = \theta^{\mathfrak{A}}$ $\square$ .

To prove that implicit definability implies explicit definability takes just a bit longer, but it’s simple; using the Compactness Theorem and the Craig Interpolation Theorem.

Next time I’ll turn to how Hellman deals with the problems posed by this theorem.

Posted in Beth's Theorem, Definability, Elementary Model Theory | Leave a Comment »

A Note on Definability

August 26, 2010

Since we’re talking about definability I wanted to say that in general, for any language $\textup{L}$ , any structure $\mathfrak{A}$ in $\textup{L}$ and any $\textup{L}$ -formula $\phi$ with $n$ free variables, $x_{0}, \dots, x_{n-1}$ , the $n$ -ary relation (or predicate, since predicates represent relations) over the universe $\textup{A}$ of $\mathfrak{A}$ , $\phi^{\mathfrak{A}} : = \{( a_{0}, \dots, a_{n-1}) \in \textup{A}^{n} : \models_\mathfrak{A}\phi [a_{0}, \dots, a_{n-1}\}$ , is the relation defined over $\mathfrak{A}$ by $\phi$ .

In Hellman’s terminology, $\phi^{\mathfrak{A}}$ is $\textup{A}$ , and he is saying that a predicate $\textup{P}$ is definable in a family of structures $\alpha$ if, and only if for every $\mathfrak{A}$ in $\alpha$ , $\textup{P} = \phi^{\mathfrak{A}}$ .

With the next update I’ll move into Hellman’s account of reducibility.

Posted in Definability, Physicalism | Leave a Comment »

φ-Definability in α structures

August 25, 2010

At the start of §2.2 Reduction and Determination, Hellman introduces the notion of definability:

An $n$ -place predicate $\textup{P}$ is definable in terms of a vocabulary $\phi$ in $\alpha$ structures if, and only if, there is a finite sentence $\textup{A}$ containing no nonlogical terms not in $\phi$ and with occurrences of $n$ distinct variables, $x_{1},\dots, x_{n}$ , such that every structure in $\alpha$ models $(\forall x_{1})\dots (\forall x_{n}) (\textup{P}x_{1} \dots x_{n} \leftrightarrow \textup{A})$ .

$\textup{P}$ is not just coextensive with a term in the $\phi$ vocabulary. What the claim of definability says is that there is a term, $\textup{A}$ , in the $\phi$ vocabulary such that the $n$ -place predicate $\textup{P}$ is coextensive with it in every structure in $\alpha$ .

Hellman notes that to say that a term is definable in a given vocabulary is not to say that the term is synonymous with a term in that vocabulary. While the notion of definability can be spelled out explicitly, the notion of synonymy cannot. Also, the coextensiveness at issue here involves definability of terms in $\phi$ terms over the structures in $\alpha$ and since each structure $\mathfrak{A}$ in $\alpha$ is a model of the laws of science, Hellman claims that definability is a kind of lawlike coextensiveness between terms terms.

From here, Hellman will go on to discuss reducibility that holds when all the terms in the vocabulary being reduced are definable in the reducing vocabulary.

Posted in Definability, Physicalism, Reductionism | Leave a Comment »

M	T	W	T	F	S	S
« Feb
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Logicians do it with Models

Archive for the ‘Definability’ Category

Hellman’s Second Definability Example

“Physicalism” Concluding Summary

Beth’s Definability Theorem

A Note on Definability

φ-Definability in α structures

Categories

Archives

Twitter

Mathematics and Philosophy Links

Follow “Logicians do it with Models”