[FOM] 209:Faithful Representation in Set Theory with Atoms
Harvey Friedman
friedman at math.ohio-state.edu
Sat Jan 31 22:13:22 EST 2004
NOTE ON FAITHFUL REPRESENTATION IN SET THEORY WITH ATOMS
by
Harvey M. Friedman
Theoretical science depends on mathematical representations of
nonmathematical structures. I.e., various nonmathematical structures are
taken to be isomorphic to various mathematical structures.
Of course, any given nonmathematical structure is a simplification of the
relevant objective reality, as only certain features of objective reality
can be appropriately addressed by any theory.
Under usual choices of representations, there will be relationships between
the objects that are not physically significant, but instead are mere
artifacts of the choice of representation.
In this note, we show how a very straightforward extension of the usual
theory of sets to set theory with atoms provides a framework so that
"insignificant" relationships are entirely avoided in representations. I.e.,
how a very simple set theory with atoms supports faithful representation.
The same issue is already present within mathematics itself, where the
presence of such "insignificant" relationships is commonplace, and generally
ignored, as it causes little or no practical difficulties. From now on, we
will remain entirely within the mathematical context.
However, the issue of faithful representation (of isomorphism types of
structures) seems particularly relevant to well known approaches in the
philosophy of science, and to work in the foundations of science. In
particular, see [1].
As an illustrative example, suppose we say
"Consider the minimum dense linear ordering X with at least two elements in
which every nonempty set has a least upper bound and a greatest lower
bound".
More precisely,
"Consider the dense linear ordering X with at least two elements such that
i) every nonempty set has a least upper bound and a greatest lower bound;
ii) it is embeddable in every dense linear ordering with property i)".
It is well known that this expression defines a unique linear ordering X *up
to isomorphism*, which, up to isomorphism, is the linear ordering of the
extended real numbers R' = R union {-infinity,infinity}. The real numbers
are usually defined as Dedekind cuts, or equivalence classes of Cauchy
sequences.
However, it can be objected that such a representation of X carries much too
much information, not reflecting, e.g., the fact that there are exactly two
distinguished elements of X.
Why do we say that there are exactly two distinguished elements of X?
Because
i) for all x in X, if x is not an endpoint, then there is an automorphism of
X which does not fix x;
ii) every automorphism of X fixes both endpoints.
The representation of X by R' has many distinguished elements other than the
endpoints -infinity and infinity. For instance, 0,1,sqrt(2),e,pi, etc.
The essence of the matter is the enormous discrepancy between the following.
i) the automorphisms of R';
ii) the automorphisms of R' that extend to an automorphism of the entire
"universe".
There are many automorphisms of R', in fact continuumly many. However, we
claim that there is only one automorphism of R' that extends to an
automorphism of the entire "universe", in any reasonable sense. This one
automorphism is the identity.
For suppose h is an automorphism, and h(x) = y, x not= y. Then there is a
rational number q such that
q < x iff not q < y.
We now see how this problem is handled in set theory with atoms. We
introduce a formal system ZFCUA = Zermelo Frankel set theory with the axiom
of choice and unlimited atoms.
The language of ZFCUA consists of epilson,=, and the unary relation A for
"being an atom". A set is defined to be an object that is not an atom.
The axioms of ZFCUA are as follows.
1. Atoms. Every atom has no elements.
2. Extensionality for sets. Any two sets with the same elements are equal.
3. Pairing. There is a set consisting of any two given objects.
4. Union. There is a set consisting of all elements of elements of any given
set.
5. Separation. There is a set consisting of all elements of any given set
satisfying any given first order condition with object parameters.
6. Power set. There is a set consisting of all subSETS of any given set.
7. Infinity. There is a set containing the empty set, and closed under the
operation "union singleton".
8. Foundation. Every nonempty set has an epsilon least element.
9. Replacement. Suppose we are given a way of assigning a unique object to
any element of some given set, given by a formula with object parameters.
There is a set consisting of the objects so associated.
10. Choice. For any set of nonempty pairwise disjoint sets, there is a set
which has exactly one element in common with each of them.
11. Unlimited Atoms. There is no set consisting of all atoms.
We define a pure set as a set which is a subset of a transitive set that has
no elements which are atoms.
THEOREM 1. (Well known). ZFCUA and ZFC prove the same sentences whose
quantifiers range over the pure sets.
We now come to our main theorem. Informally, it tells us that we can prove
in ZFCUA that every structure has a faithful representation.
THEOREM 2. The following is provable in ZFCUA. Every structure M is
isomorphic to a structure M* whose domain is a set of atoms, such that every
automorphism of M* can be extended to a uniformly defined automorphism of
the universe of objects. More formally, there is a formula phi(x,y,z) in the
language of ZFCUA, with all free variables shown, such that the following is
provable in ZFCUA. Every structure M is isomorphic to a structure M* whose
domain is a set of atoms, such that for every automorphism h of M*,
phi(h,x,y) defines an automorphism of the universe of objects.
The proofs of Theorem 1 and 2 are straightforward using modern set theoretic
techniques, and can even be regarded as implicit in work of such logicians
as Frankel and Mostowski.
REFERENCE
[1] Pat Suppes, Representation and invariance of scientific structures, CSLI
publications, 2002.
*********************************************
I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 209th 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
201:Algebraic Treatment of First Order Notions 1/11/04 11:26PM
202:Proof(?) of Church's Thesis 1/12/04 2:41PM
203:Proof(?) of Church's Thesis - Restatement 1/13/04 12:23AM
204:Finite Extrapolation 1/18/04 8:18AM
205:First Order Extremal Clauses 1/18/04 2:25PM
206:On foundations of special relativistic kinematics 1 1/21/04 5:50PM
207:On foundations of special relativistic kinematics 2 1/26/04 12:18AM
208:On foundations of special relativistic kinematics 3 1/26/04 12:19AAM
Harvey Friedman
More information about the FOM
mailing list