[FOM] 601: Finite Emulation Theory 1/perfect?
Harvey Friedman
hmflogic at gmail.com
Sat Aug 22 01:17:17 EDT 2015
THIS POSTING IS ENTIRELY SELF CONTAINED
the notion of EMULATION used here is slightly different than
CONTINUATION, and arguably as natural. Since our FINITE theory is now
moving to the positive integers, it turns out to be advantageous to
use Emulations rather than Continuations.
An emulation is the same as a continuation, except that we drop the
requirement that the original set be included.
Recall our perfect Propositions A,B,C of
http://www.cs.nyu.edu/pipermail/fom/2015-August/018876.html
PROPOSITION A. Every finite subset of Q^k|>n has a maximal nonnegative
continuation, where S[1,...,n]|>n = S[0,...,n-1]|>n.
PROPOSITION B. Every finite subset of Q^k|>n has a maximal nonnegative
r-continuation, where S[1,...,n]|>n = S[0,...,n-1]|>n.
PROPOSITION C. Every finite length tower of finite subsets of Q^k|>n
has a maximal nonnegative r-continuation tower, where each set
satisfies S[1,...,n]|>n = S[0,...,n-1]|>n.
We also have the analogous
PROPOSITION A'. Every finite subset of Q^k has a maximal nonnegative
emulation, where S[1,...,n]|>n = S[0,...,n-1]|>n.
PROPOSITION B'. Every finite subset of Q^k has a maximal nonnegative
r-emulation, where S[1,...,n]|>n = S[0,...,n-1]|>n.
PROPOSITION C'. Every finite length tower of finite subsets of Q^k has
a maximal nonnegative r-emulation tower, where each set satisfies
S[1,...,n]|>n = S[0,...,n-1]|>n.
All six are provably equivalent to Con(SRP) over WKL_0.
CORPORATE HIRING PRINCIPLES
We are building a company that is going to enter all marketplaces, so
we would like to do two things in the hiring process:
1. Make sure that any two hires are truly compatible.
2. Be as diverse as possible, incorporating a large mix of skill sets,
supporting a vast interactive productivity.
There is already a model company, much more specialized than ours, and
successfully developed over time, where any two hires are truly
compatible. We will use that existing company as a model for our
hiring. In particular, as we hire, we want to make sure that any two
hires of ours (together as a team of two) are similar to some two
hires from the model company. This will ensure that our hires can
truly work together, at least in pairs. I.e.,
1'. Any two hires, as a pair, are similar to some two hires, as a
pair, from the model company.
We can be as diverse as possible in this ambitious sense.
We consider a person UNACCEPTABLE if their being hired would cause a
violation of 1'.
So an ultimate kind of diversity is
2a. All of the people that we don't hire are unacceptable.
There is an even more ambitious kind of diversity. Consider a person
automatically STRONGLY UNACCEPTABLE if their being hired would cause a
violation of 1' with somebody younger than they are.
2b. All of the people that we don't hire are strongly unacceptable.
Whereas there are many ways we can conduct our hiring process to
achieve 1' and 2a, it is interesting to note that there is exactly one
way we can conduct our hiring process to achieve 1' and 2b.
HOWEVER, 1',2a and 1',2b are grossly impractical, as they generally
require an incredibly impractical amount of hiring.
INSTEAD, we naturally settle on a more realistic goal.
2c. Every list of three people not hired is similar (as a list) to a
list of three unacceptable people.
2d. Every list of three people not hired is similar (as a list) to a
list of three strongly unacceptable people.
1',2c and even 1',2d are much more realistic. They put a damper on our
most critical lost opportunities.
We now want to be more specific about some of the main features of our
hiring process. Each individual is profiled according to a tuple of
positive integers. We use a number of factors, which is the common
length of the attribute vectors. Obviously, various people are going
to generally have a mixture of low and high numbers in their attribute
vectors.
If there are a lot of very large numbers in certain crucial factors,
then the individual might be hired at a high managerial level.
However, we caution against a purely monotonic hiring process. The
company wants a complex mix of high and low attributes, to fill slots
at various compensation levels. For example, we have seen that if
someone is a top piano player AND a top programmer, then they may get
distracted too much from the important programming tasks, more so than
a fine but not top programmer who is not much of a musician. On the
other hand, top piano playing is a useful attribute for certain types
of hires, as quality of life at corporate meetings can be crucially
important for retention and morale.
There are certain preferred scores that historically are seen to be
important benchmarks for positions and rewards within the company.
Consequently, these numbers have a great influence on our hiring
practices and goals. Of course, the choice of these cutoff numbers is
somewhat arbitrary, but we have adhered to certain cutoff numbers
according to our historical hiring and operational experiences. These
benchmark numbers are not always large numbers, as there are many
positions available in the company at all kinds of compensation
levels, with all kinds of duties.
We can now be more specific about similarity used in 1'. For this
purpose, for judging the similarity of pairs of individuals, we look
at how their tuples of attributes compare numerically, factor by
factor (math: order equivalence of tuples of positive integers).
The benchmark numbers have proved so useful that we have incorporated
them in our goals 2c and 2d. Benchmark similarity strengthens
similarity in that not only do we look for numerical comparisons
between factors, but also how those numbers compare to the benchmark
numbers (math: benchmark numbers are the factorials) (math: benchmark
similarity is factorial order equivalence).
Thus we use similarity for 1' and benchmark similarity for 2c and 2d.
We are exploring the possibility of using various similarities for 1'
that incorporate some of the benchmarks, but that is yet to be worked
out.
So the revised goals are as follows.
2e. Every list of three people not hired is benchmark similar (as a
list) to a list of three unacceptable people.
2f. Every list of three people not hired is benchmark similar (as a
list) to a list of three strongly unacceptable people.
There is one other goal that we very much want to achieve.
3. Avoid lawsuits arising from negative hiring decisions.
The usual way lawsuits arise is when somebody has an attribute vector
with one or more numbers that are just a little bit less than a
benchmark number. They will complain that the number was arrived at
improperly, and that they would be over the benchmark if it was
redone. This is very expensive for the company, and sometimes they
even win in court.
Numbers falling just a little bit lower than any but the lowest
benchmark numbers (math: modestly large factorials minus 1, and I know
how to work the math with even upper 50% between two factorials) are
in general a headache for the company, even if it doesn't affect
hiring, because it affects the assignment of jobs and compensation.
So we would just like to completely avoid hiring anybody with any
numbers just a little bit lower than a benchmark number. We have found
that this seems desirable and feasible for all but the lower benchmark
numbers. Thus we have three aims, which we now put in final form:
1'. Any two hires, as a pair, are similar to some two hires, as a
pair, from the model company.
2e. Every list of three people not hired is benchmark similar (as a
list) to a list of three unacceptable people.
2f. Every list of three people not hired is benchmark similar (as a
list) to a list of three strongly unacceptable people.
3. Don't hire anybody with a number that is just a little bit below
all but the lowest benchmarks.
It would seem that 3 is too draconian, in that we are going to miss
critical opportunities that put requirements 2e or 2f in jeopardy. Are
these requirements compatible?
THE APPROPRIATE MATHEMATICAL MODEL THAT THIS DISCUSSION GENERATES SAYS
YES IF AND ONLY IF CON(SMAH).
SMAH = strongly Mahlo cardinals.
We will now fully present the mathematical model.
MATHEMATICAL MODEL
DEFINITION 1. Z+ is the set of all positive integers. We use
i,j,k,n,m,r,s,t for positive integers unless indicated otherwise. We
use x,y,z,u,v,w for tuples from Z+ unless indicated otherwise. x,y in
Z+^k are order equivalent if and only if for all 1 <= i,j <= k, x_i <
x_j iff y_i < y_j. Let S be a subset of Z+^k. S|<x (S|<=x) is the set
of all elements of S all of whose coordinates are <max(x) (<=max(x)).
For x_1,...,x_r in Z+^k, x_1*...*x_r is the concatenation of
x_1,...,x_r, which lies in Z+^kr. [n] = {1,...,n}.
DEFINITION 2. Let E containedin [n]^k. S is an emulation of E in [n]^k
if and only if S containedin [n]^k and every x*y, x,y in S, is order
equivalent to some z*w, z,w in S.
DEFINITION 3. Let S containedin [n]^k. The outsiders are the x in
[n]^k\S. The S/E rejects of S are the x in [n]^k such that S union {x}
is not an emulation of E. The S/E<= rejects are the x in [n]^k such
that S|<=x union {x} is not an emulation of E. The S/E< rejects are
the x in [n]^k such that S|<x union {x} is not an emulation of E.
Repetitions are allowed in lists.
THEOREM 1. Every subset of [n]^k has a maximal emulation in [n]^k,
where all outsiders are rejects. Every subset of [n]^k has a unique
maximal emulation in [n]^k, where all outsiders are strong rejects.
DEFINITION 4. x,y in Z+^k are factorial order equivalent if and only
if (x,1!,2!,3!,...) and (y,1!,2!,3!,...) are order equivalent. A list
of tuples omits t if and only if t is not a coordinate of any tuple in
the list.
PROPOSITION 2. Every E containedin [n!]^k has an emulation S in [n!]^k
where any list of three outsiders is factorial order equivalent to
some list of three S/E rejects omitting (8k)!-1.
PROPOSITION 3. Every E containedin [n!]^k has an emulation S in
[n!]^k, where any list of three outsiders is factorial order
equivalent to some list of three S/E<= rejects omitting (8k)!-1.
PROPOSITION 3. Every containedin [n!]^k has an emulation S in [n!]^k,
where any list of three outsiders is factorial order equivalent to
some list of three S/E< rejects omitting (8k)!-1.
As before, we can introduce parameters in the obvious way.
PROPOSITION 4. Every E containedin [n!]^k has an r-emulation S in
[n!]^k where any list of m outsiders is factorial order equivalent to
some list of m S/E rejects omitting (8krm)!-1.
PROPOSITION 5. Every containedin [n!]^k has an r-emulation S in
[n!]^k, where any list of m outsiders is factorial order equivalent to
some list of m S/E<= rejects omitting (8krm)!-1.
PROPOSITION 6. Every E containedin [n!]^k has an r-emulation S in
[n!]^k, where any list of m outsiders is factorial order equivalent to
some list of m S/E< rejects omitting (8krm)!-1.
THEOREM 7. Propositions 2-6 are provably equivalent to Con(SMAH) over EFA.
We can replace (8k)!-1 by {8k,...,n}!-1, and (8krm)!-1 by
{8krm,...,n}!-1, and obtain the same results.
************************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 601st 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-599 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2015-August/018887.html
600: Removing Deep Pathology 1 8/15/15 10:37PM
Harvey Friedman
More information about the FOM
mailing list