[FOM] 201:Algebraic Treatment of First Order Notions

[Harvey Friedman]

We give algebraic definitions of the key semantic concepts in predicate
calculus - 

1. strictly definable relations and functions in a relational structure.
2. definable relations and functions in a relational structure.
3. elementary extensions.
4. elementary embeddings.
5. elementary equivalence.

Strict definability is the same as definability but without parameters.

Defining 2 from 1 and 4 from 3 are well known. Our way of defining 3 from 1
is simple, and implicit in the literature.

We could define 3,4 from 5, but any definition of 5 from 1 seems more
complicated than the definitions that appear here.

5 has been treated many years ago by Keisler and Shelah in terms of
ultrapowers. In contrast, this approach is no more set theoretic than
ordinary algebra, and works if we restrict only to countable structures.

It will suffice to consider only finite relational types. All structures
will have finite (relational) type.

We say that a relational structure M is finitely embeddable into a
relational structure M' if and only if every finite "restriction" of M is
isomorphic to a finite "restriction of M'.

Here the "restriction" of M to a set E may not be a structure, since the
functions in M may map some tuple from E to a value outside E. So for this
purpose, we identify the function components of these "restrictions" with
their graphs. Also, "restrictions" of M are required to contain all
constants of M.  

Let alpha and beta be finite relational types. We say that M is alpha,beta
implicit if and only if

i) M is of type (alpha,beta,gamma), for some gamma;
ii) for any M',M'' finitely embeddable into M, if M',M'' have the same alpha
part (in particular, the same domain), then M',M'' have the same beta part.

THEOREM 1. Let M be a relational structure of finite type alpha and R be a
multivariate relation on dom(M). Then R is strictly M definable if and only
if there is an expansion M* = (M,R,...) which is alpha,"R" implicit. The
corresponding statement holds for constants and functions.

THEOREM 2. Let M,M' be relational structures of the same finite type. Then M
is an elementary substructure of M' if and only if every strictly M
definable multivariate surjection from dom(M') onto dom(M') maps dom(M) onto
dom(M).

THEROEM 3. M,M' are elementary equivalent if and only if they are
respectively isomorphic to two elementary substructures of a common
structure.   

Theorems 2 and 3 are well known, and Theorem 1 is not hard to get through
adaptation of the literature (Beth definability). The novelty here - if any
- is the use of such information to give algebraic characterizations of
first order notions.

*********************************************

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 201st in a series of self contained numbered postings to
FOM covering a wide range of topics in f.o.m. The list of previous
numbered postings #1-149 can be found at
http://www.cs.nyu.edu/pipermail/fom/2003-May/006563.html  in the FOM
archives, 5/8/03 8:46AM. Previous ones counting from #150 are:

150:Finite obstruction/statistics  8:55AM  6/1/02
151:Finite forms by bounding  4:35AM  6/5/02
152:sin  10:35PM  6/8/02
153:Large cardinals as general algebra  1:21PM  6/17/02
154:Orderings on theories  5:28AM  6/25/02
155:A way out  8/13/02  6:56PM
156:Societies  8/13/02  6:56PM
157:Finite Societies  8/13/02  6:56PM
158:Sentential Reflection  3/31/03  12:17AM
159.Elemental Sentential Reflection  3/31/03  12:17AM
160.Similar Subclasses  3/31/03  12:17AM
161:Restrictions and Extensions  3/31/03  12:18AM
162:Two Quantifier Blocks  3/31/03  12:28PM
163:Ouch!  4/20/03  3:08AM
164:Foundations with (almost) no axioms, 4/22/0  5:31PM
165:Incompleteness Reformulated  4/29/03  1:42PM
166:Clean Godel Incompleteness  5/6/03  11:06AM
167:Incompleteness Reformulated/More  5/6/03  11:57AM
168:Incompleteness Reformulated/Again 5/8/03  12:30PM
169:New PA Independence  5:11PM  8:35PM
170:New Borel Independence  5/18/03  11:53PM
171:Coordinate Free Borel Statements  5/22/03  2:27PM
172:Ordered Fields/Countable DST/PD/Large Cardinals  5/34/03  1:55AM
173:Borel/DST/PD  5/25/03  2:11AM
174:Directly Honest Second Incompleteness  6/3/03  1:39PM
175:Maximal Principle/Hilbert's Program  6/8/03  11:59PM
176:Count Arithmetic  6/10/03  8:54AM
177:Strict Reverse Mathematics 1  6/10/03  8:27PM
178:Diophantine Shift Sequences  6/14/03  6:34PM
179:Polynomial Shift Sequences/Correction  6/15/03  2:24PM
180:Provable Functions of PA  6/16/03  12:42AM
181:Strict Reverse Mathematics 2:06/19/03  2:06AM
182:Ideas in Proof Checking 1  6/21/03 10:50PM
183:Ideas in Proof Checking 2  6/22/03  5:48PM
184:Ideas in Proof Checking 3  6/23/03  5:58PM
185:Ideas in Proof Checking 4  6/25/03  3:25AM
186:Grand Unification 1  7/2/03  10:39AM
187:Grand Unification 2 - saving human lives 7/2/03 10:39AM
188:Applications of Hilbert's 10-th 7/6/03  4:43AM
189:Some Model theoretic Pi-0-1 statements  9/25/03  11:04AM
190:Diagrammatic BRT 10/6/03  8:36PM
191:Boolean Roots 10/7/03  11:03 AM
192:Order Invariant Statement 10/27/03 10:05AM
193:Piecewise Linear Statement  11/2/03  4:42PM
194:PL Statement/clarification  11/2/03  8:10PM
195:The axiom of choice  11/3/03  1:11PM
196:Quantifier complexity in set theory  11/6/03  3:18AM
197:PL and primes 11/12/03  7:46AM
198:Strong Thematic Propositions 12/18/03 10:54AM
199:Radical Polynomial Behavior Theorems
200:Advances in Sentential Reflection 12/22/03 11:17PM

Harvey Friedman