FOM: 157:Finite societies
Harvey Friedman
friedman at mbi.math.ohio-state.edu
Tue Aug 13 18:56:09 EDT 2002
We continue from postings #155, #156.
FINITE SOCEITIES
A finite society (FS) is a system (S,L,W,A,k), where the following seven
conditions hold.
FS1. S is a nonempty finite set of people in the society.
FS2. L is a binary relation on S called the like relation. L(x,y) means
that x likes y.
FS3. W is the wealth function, which is a function from S onto some set
{1,2,...,n}. Thus 1,2,...,n are the n levels of wealth represented in the
society, from poorest to richest. Many people may have the same wealth.
FS4. A is the age function, which is a function from S onto some set
{1,2,...,m}. Thus 1,2,...,m are the m ages represented in the society, from
youngest to oldest. Many people may be of the same age.
FS5. There is somebody of any given age who is poorer than all older people.
FS6. Anybody who likes somebody richer likes somebody richer of the same age.
FS7. k is a nonnegative integer. There is a person of any given age and
wealth, who, among the people richer than themselves, likes exactly those
who bear some given elementary relation to some k richer people and some
given older people. Here by elementary relation, we mean one that is
defined using: and, or, not, likes, wealthier than, poorer than, (exactly)
as wealthy as.
This completes the definition of a finite society. Note that in FS7, the
age, wealth, k older people, and elementary relation are given in advance
of the choice of the postulated person. The k richer people are not given
in advance.
Here are some rationale.
Why do we use only specific older people in clause FS7? If we allow anyone,
then we would have a person of any level of wealth who likes exactly those
richer people that are not liked by that person. This is a contradiction if
there are at least two levels of wealth. If the society has at least two
ages, then there are at least two levels of wealth by FS5.
A person, in forming their likes of richer persons, will take into
consideration the likes of specific older persons and their wealth, and who
likes specific older persons and their wealth, rather than the likes of
specific persons of their age and younger and their wealth, and who likes
specific persons of their age and younger and their wealth. This is an
experience oriented society. Older people have been around longer and are
wiser.
Older people tend to be richer at the lower end of the wealth scale, as
indicated by FS5. This is again a consequence of the fact that older people
have been around longer and are wiser.
THEOREM 1. For any k,m, there is a finite society (S,L,W,A,k) with exactly
m ages.
Now consider the following condition.
alpha. Anyone who is one level richer than the poorest people of any given
age is among the youngest people.
This reflects the enormous birth rate, where there are so many more people
of the youngest age than of any other age.
It may seem bizarre to consider the wealth of people of the youngest age.
We can interpret S to be the society of people who are considered adults,
so that they legally own property and have well defined wealth.
ZC is Zermelo set theory with the axiom of choice. PRA is primitive
recursive arithmetic.
THEOREM 2. For any k,m, there is a finite society (S,L,W,A,k) with exactly
m ages satisfying condition alpha. This statement is provably equivalent to
the 1-consistency of ZC + {there exists V(omega times n)}_n, over PRA. In
particular, the statement is provable in ZC + (forall n)(V(omega times n)
exists) but not in ZC + {V(omega times n) exists}_n.
We now consider the following weak form of FS6.
FS6'. Anybody who likes somebody richer likes somebody richer of any
younger age.
If (S,L,W,A,k) satisfies FS1 - FS5, FS6', FS7, then we say that it is a
weak finite society.
THEOREM 3. For any k,m, there is a weak finite society (S,L,W,A,k) with
exactly m ages satisfying condition alpha. This statement is provably
equivalent to the consistency of ZC + {there exists V(omega times n}_n,
over PRA. In particular, the statement is provable in ZC + (forall
n)(V(omega times n) exists) but not in ZC + {V(omega times n) exists}_n.
We have not done the detailed work yet on just how small k needs to be in
the third claims of Theorems 2 and 3. Surely k = 5 is small enough, but
this might hold for k = 2.
We now consider finite societies with representatives. The idea is that the
representatives form a relatively small set of people in the society which
forms a microcosm of society. They can be polled much more easily than the
whole society, and might even be appropriate as a kind of ruling body like
the U.S. House of Representatives.
A finite society with representatives (FSR) is a system (S,L,W,A,R,k) where
FSR1. S is a nonempty finite set of people in the society.
FSR2. L is a binary relation on S called the like relation. L(x,y) means
that x likes y.
FSR3. W is the wealth function, which is a function from S onto some set
{1,2,...,n}. Thus 1,2,...,n are the n levels of wealth represented in the
society, from poorest to richest.
FSR4. A is the age function, which is a function from S onto some set
{1,2,...,m}. Thus 1,2,...,m are the m ages represented in the society, from
youngest to oldest.
FSR5. R is the set of representatives, which is a subset of S.
FRS6. There is an oldest person who is not of the same wealth as any
representative.
FSR7. There is a representative of any given age who is poorer than all
older people.
FSR8. Anybody who likes somebody richer likes somebody richer of the same age.
FSR9. Any representative who likes somebody richer likes a richer
representative of the same age.
FSR10. For any given person there is a person of the same age who likes the
representatives liked by the given person, and nobody else.
FSR11. For any given person there is a representative of the same age who
likes the same representatives.
FSR12. k is a nonnegative integer. There is a person (representative) of
any given age, and any given wealth (wealth of a representative), who,
among the persons richer than themselves, likes exactly those who bear some
given elementary relation with some k richer people, and some given older
persons (representatives). Here by elementary relation, we mean one that is
defined using: and, or, not, likes, wealthier than, poorer than, as wealthy
as.
This completes the definition of a finite society with representatives
(FSR). Note that we have given two forms of FSR12, the second through the
alternatives in parentheses.
Let WZC be weak Zermelo set theory with the axiom of choice, with bounded
separation instead of full separation.
PROPOSITION 4. For all k,m there exists a finite society with
representatives, (S,L,A,W,R,k), with exactly m ages.
THEOREM 5. Proposition 4 is provably equivalent to the 1-consistency of WZC
+ 'there exists a measurable cardinal', over PRA . In particular, the
statement is provable in ZC +'there exists a measurable cardinal' but not
in WZC + 'there exists a measurable cardinal'.
FSR8'. Anybody who likes somebody richer likes somebody richer of any
younger age.
If (S,L,W,A,R,k) satisfies FSR1 - FSR7, FSR8', FSR9, - FSR12, then we say
that it is a weak finite society with representatives.
PROPOSITION 6. For all k,m there exists a weak finite society with
representatives, (S,L,A,W,R,k), with exactly m ages.
THEOREM 7. Proposition 6 is provably equivalent to the consistency of WZC +
'there exists a measurable cardinal', over PRA. In particular, the
statement is provable in ZC + 'there exists a measurable cardinal' but not
in WZC + 'there exists a measurable cardinal'.
In Theorems 3 and 7 involving weak finite societies, we can give iterated
exponential bounds in k,m, on the number of people required.
*********************************************
I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 156th in a series of self contained postings to FOM covering
a wide range of topics in f.o.m. Previous ones counting from #100 are:
100:Boolean Relation Theory IV corrected 3/21/01 11:29AM
101:Turing Degrees/1 4/2/01 3:32AM
102: Turing Degrees/2 4/8/01 5:20PM
103:Hilbert's Program for Consistency Proofs/1 4/11/01 11:10AM
104:Turing Degrees/3 4/12/01 3:19PM
105:Turing Degrees/4 4/26/01 7:44PM
106.Degenerative Cloning 5/4/01 10:57AM
107:Automated Proof Checking 5/25/01 4:32AM
108:Finite Boolean Relation Theory 9/18/01 12:20PM
109:Natural Nonrecursive Sets 9/26/01 4:41PM
110:Communicating Minds I 12/19/01 1:27PM
111:Communicating Minds II 12/22/01 8:28AM
112:Communicating MInds III 12/23/01 8:11PM
113:Coloring Integers 12/31/01 12:42PM
114:Borel Functions on HC 1/1/02 1:38PM
115:Aspects of Coloring Integers 1/3/02 10:02PM
116:Communicating Minds IV 1/4/02 2:02AM
117:Discrepancy Theory 1/6/02 12:53AM
118:Discrepancy Theory/2 1/20/02 1:31PM
119:Discrepancy Theory/3 1/22.02 5:27PM
120:Discrepancy Theory/4 1/26/02 1:33PM
121:Discrepancy Theory/4-revised 1/31/02 11:34AM
122:Communicating Minds IV-revised 1/31/02 2:48PM
123:Divisibility 2/2/02 10:57PM
124:Disjoint Unions 2/18/02 7:51AM
125:Disjoint Unions/First Classifications 3/1/02 6:19AM
126:Correction 3/9/02 2:10AM
127:Combinatorial conditions/BRT 3/11/02 3:34AM
128:Finite BRT/Collapsing Triples 3/11/02 3:34AM
129:Finite BRT/Improvements 3/20/02 12:48AM
130:Finite BRT/More 3/21/02 4:32AM
131:Finite BRT/More/Correction 3/21/02 5:39PM
132: Finite BRT/cleaner 3/25/02 12:08AM
133:BRT/polynomials/affine maps 3/25/02 12:08AM
134:BRT/summation/polynomials 3/26/02 7:26PM
135:BRT/A Delta fA/A U. fA 3/27/02 5:45PM
136:BRT/A Delta fA/A U. fA/nicer 3/28/02 1:47AM
137:BRT/A Delta fA/A U. fA/beautification 3/28/02 4:30PM
138:BRT/A Delta fA/A U. fA/more beautification 3/28/02 5:35PM
139:BRT/A Delta fA/A U. fA/better 3/28/02 10:07PM
140:BRT/A Delta fA/A U. fA/yet better 3/29/02 10:12PM
141:BRT/A Delta fA/A U. fA/grammatical improvement 3/29/02 10:43PM
142:BRT/A Delta fA/A U. fA/progress 3/30/02 8:47PM
143:BRT/A Delta fA/A U. fA/major overhaul 5/2/02 2:22PM
144: BRT/A Delta fA/A U. fA/finesse 4/3/02 4:29AM
145:BRT/A U. B U. TB/simplification/new chapter 4/4/02 4:01AM
146:Large large cardinals 4/18/02 4:30AM
147:Another Way 7:21AM 4/22/02
148:Finite forms by relativization 2:55AM 5/15/02
149:Bad Typo 1:59PM 5/15/02
150:Finite obstruction/statisics 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
156:Societies 8/13/02
More information about the FOM
mailing list