[FOM] Really Large Infinitary Languages
John Bell
jbell at uwo.ca
Fri Nov 21 07:38:49 EST 2014
Max Dickmann's book "Large Infinitary Languages" contains a discussion of proper class sized Infinitary languages.
-- John Bell
Sent from my iPad
> On Nov 20, 2014, at 6:30 PM, fom-request at cs.nyu.edu kwrote:
>
> Send FOM mailing list submissions to
> fom at cs.nyu.edu
>
> To subscribe or unsubscribe via the World Wide Web, visit
> http://www.cs.nyu.edu/mailman/listinfo/fom
> or, via email, send a message with subject or body 'help' to
> fom-request at cs.nyu.edu
>
> You can reach the person managing the list at
> fom-owner at cs.nyu.edu
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of FOM digest..."
>
>
> Today's Topics:
>
> 1. Really Large Infinitary Languages (Guillermo Badia)
> 2. 562: Perfectly Natural Review #1 (Harvey Friedman)
> 3. Re: Leibnizian principles (Robert Rynasiewicz)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Thu, 20 Nov 2014 17:35:32 +1300
> From: Guillermo Badia <guillebadia89 at gmail.com>
> To: fom <fom at cs.nyu.edu>
> Subject: [FOM] Really Large Infinitary Languages
> Message-ID:
> <CADtn9vDesbb5RDvJQD=HAst9EX-=3SpRV4+xOwaWnYi-d=fecQ at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
>
> Dear All,
> Are there any studies on languages with conjunctions and disjunctions
> of proper class size?
>
> Thanks in advance for any help you can offer me.
>
> Guille
>
>
> ------------------------------
>
> Message: 2
> Date: Wed, 19 Nov 2014 19:40:15 -0500
> From: Harvey Friedman <hmflogic at gmail.com>
> To: Foundations of Mathematics <fom at cs.nyu.edu>
> Subject: [FOM] 562: Perfectly Natural Review #1
> Message-ID:
> <CACWi-GUPQV__RpmziSv4nm-3_9LeNPSxCs=1Va90L8owXT2sdw at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
>
> THIS POSTING IS SELF CONTAINED
>
> There has been a lot of progress on CMI = Concrete Mathematical
> Incompleteness, which has been for some months within the territory of
> Perfectly Natural Concrete Mathematical Incompleteness.
>
> This is Part #1 of an abridged account of the entire picture as of
> now, and will not have the level of motivation and detail that the
> extended abstract will have on my website when it appears there.
>
> 1. Maximal Roots in Q[0,1]^k - Templates
> 2. Maximal Roots in Q[0,1]^k - Specifics
> 3. G-bases in Q^k
> 4. p,G-bases in Q^k
>
> 1. MAXIMAL ROOTS IN Q]0,1]^k - TEMPLATES
>
> We work with maximal roots in order invariant relations on Q[0,1]^k.
> The fuller version will also have entirely parallel developments using
> maximal squares and maximal cliques. A root of a binary relation on a
> set is a set such that any two elements lie in the relation. A maximal
> root is a root that is not a subset of any other root. Here relations
> are always binary.
>
> We begin with Perfectly Natural motivating Templates. For a specific
> independent statement, see Proposition 2.1.
>
> TEMPLATE A. Let F:Q[0,1]^k into Q[0,1]^k be order theoretic. Every
> order invariant relation on Q[0,1]^k has an F invariant maximal root.
>
> TEMPLATE B. Let E be an order theoretic equivalence relation on
> Q[0,1]^k. Every order invariant relation on Q[0,1]^k has an E
> invariant maximal root.
>
> TEMPLATE C. Let f:Q[0,1] into Q[0,1] be order theoretic. Every order
> invariant relation on Q[0,1]^k has an f invariant maximal root.
>
> Here Q[0,1] = Q intersect [0,1]. Order theoretic is the same as order
> invariant with constants (parameters). I.e., definable as a
> propositional combination of inequalities using only < and constants
> from Q. Let S containedin Q[0,1]. S is F invariant if and only if for
> all x in Q[0,1]^k, x in S iff Fx in S.S is E invariant if and only if
> for all E equivalent x,y, x in S iff y in S. S is f invariant if and
> only if for all x in Q[0,1]^k, x in S iff fx in S, where fx =
> (f(x_1),...,f(x_k)) in S.
>
> It is obvious that Templates A-C are Perfectly Natural motivators. For
> some, this may be yet more compelling when formulated analogously with
> maximal squares or with maximal cliques.
>
> See Theorem 1.6 for the implicit concreteness of these Templates.
>
> Although we have not yet been able to completely analyze these
> Templates, we present the following Perfectly Natural partial results.
>
> a. A Perfectly Natural sufficient condition for Templates A,C. The
> claim of sufficiency for A can be proved from large cardinals but not
> in ZFC.
> b. A Perfectly Natural sufficient condition for Template B. The claim
> of sufficiency for B can be proved from large cardinals but not in
> ZFC.
> c. The same Perfectly Natural sufficient conditions for the obvious
> multiple forms of Templates A,B,C, where we are given finite sequences
> of F's, E's, and f's. These claims of sufficiency can be proved from
> large cardinals but not in ZFC.
> d. a Perfectly Natural formulation of Templates A,B,C for isomorphism
> types of F's, E's, and f's. Here we can give a complete analysis of
> the resulting Templates. The correctness of the analysis can be proved
> from large cardinals but not in ZFC.
>
> We begin with a).
>
> DEFINITION 1.1. Let F:Q[0,1]^k into Q[0,1]^k. F is upward if and only
> if for all x in Q[0,1]^k, any coordinate moved by F is greater than
> any coordinate not moved by F. F is order preserving if and only if
> for all x in Q[0,1]^k, x and F(x)) are order equivalent.
>
> PROPOSITION 1.1. If Template A holds then F is order preserving.
> Template A holds if F is additionally upward and order preserving, If
> F is upward, then Template A holds for F if and only if F is order
> preserving.
>
> PROPOSITION 1.2. Template C holds if f is additionally upward.
>
> We now come to b).
>
> DEFINITION 1.2. Let E be an equivalence relation on Q[0,1]^k. E is
> upward if and only if finitely many rationals are moved somewhere by
> E, and every x_i smaller than all x_j moved somewhere by E is not
> moved by E from x.
>
> PROPOSITION 1.3. If Template B holds then E is order preserving.
> Template B holds if E is additionally upward and order preserving. If
> E is additionally upward, then Template A holds for F if and only if F
> is order preserving.
>
> Now for c).
>
> TEMPLATE D. Let F_1,...,F_r:Q[0,1]^k into Q[0,1]^k be order theoretic.
> Every order invariant relation on Q[0,1]^k has an F_1,...,F_r
> invariant maximal root.
>
> TEMPLATE E. Let E_1,...,E_r be order theoretic equivalence relations
> on Q[0,1]^k. Every order invariant relation on Q[0,1]^k has an
> E_1,...,E_r invariant maximal root.
>
> TEMPLATE F. Let f_1,...,f_r:Q[0,1] into Q[0,1] be order theoretic.
> Every order invariant relation on Q[0,1]^k has an f_1,...,f_r
> invariant maximal root.
>
> PROPOSITION 1.4. Template D holds if the F's are additionally upward,
> and order preserving, If the F's are upward, then Template D holds for
> the F's if and only if the F's are order preserving.
>
> PROPOSITION 1.5. Template E holds if the E's are additionally upward,
> and order preserving, If the E's are upward, then Template E holds for
> the E's if and only if the E's are order preserving.
>
> PROPOSITION 1.6. Template F holds if the f's are additionally upward.
>
> Now for d).
>
> DEFINITION 1.3. A,B containedin Q[0,1]^k are isomorphic if and only if
> (Q[0,1],<,A) and (Q[0,1],<,B) are isomorphic in the sense of model
> theory. Functions f:Q[0,1]^k into Q[0,1]^k are isomorphic if and only
> if their graphs are isomorphic subsets of Q[0,1]^k. Relations on
> Q[0,1]^k are isomorphic if and only if they are isomorphic subsets of
> Q[0,1]^2k. .
>
> THEOREM 1.7. (RCA_0). If f,g:Q[0,1]^k into Q[0,1]^k are isomorphic
> then f is order theoretic if and only if g is order theoretic. There
> is an effective criteria for determining whether two given order
> theoretic subsets of Q[0,1]^k are isomorphic.
>
> TEMPLATE G. Let F:Q[0,1]^k into Q[0,1]^k be order theoretic. For all
> F_1,...,F_r isomorphic to F, every order invariant relation on
> Q[0,1]^k has an F_1,...,F_r invariant maximal root.
>
> TEMPLATE H. Let E be an order theoretic equivalence relation on
> Q[0,1]^k. For all E_1,...,E_r isomorphic to E, every order invariant
> relation on Q[0,1]^k has an E_1,...,E_r invariant maximal root.
>
> TEMPLATE I. Let f:Q[0,1] into Q[0,1] be order theoretic. For all
> f_1,...,f_r isomorphic to f, every invariant relation on Q[0,1]^k has
> an f_1,...,f_r invariant maximal root, under the coordinate action.
>
> THEOREM 1.8. Every instance of Templates A-I, and Propositions 1.1-1.4
> are provably equivalent to Pi01 sentences over WKL_0, via Goedel's
> Completeness Theorem.
>
> THEOREM 1.9. Propositions 1.1 and 1.3-1.6 are provably equivalent to
> Con(SRP) over WKL_0. Proposition 1.2 is provable in WKL_0 + Con(SRP).
>
> THEOREM 1.10. Every instance of Templates G,H are provable in SRP or
> refutable in RCA_0. Every instance of Template I is provable in WKL_0
> + Con(SRP) or refutable in RCA_0.
>
> THEOREM 1.11. For each k there is an instance of Templates A,B,D,E,G,H
> that is provable in SRP but not in SRP[k]. So these Templates cannot
> be completely analyzed within any SRP[k]. There is an instance of
> Templates F,I that is provable in WKL_0 + Con(SRP) but not in SRP. So
> these Templates cannot be completely analyzed in SRP.
>
> Here SRP is the stationary Ramsey property hierarchy. This is the same
> as the subtle cardinal hierarchy and the ineffable cardinal hierarchy.
>
> There are more ambitious templates, involving rational piecewise
> linear functions, again with the important case of one-dimensional
> maps acting coordinatewise. There are a lot of open issues here
> amenable to attack.
>
> 2. MAXIMAL ROOTS IN Q[0,1]^k - SPECIFICS
>
> Here we give some Perfectly Natural cases of some of the Templates in
> section 1, which are provable using large cardinals but not in ZFC
> (assuming ZFC is consistent).
>
> Arguably the simplest example of this kind involves sections.
>
> DEFINITION 2.1. Let A,B containedin Q^k. The section of A at x is {y
> in Q^k-r: (x,y) in A}. Note that if r >= k then the section of A at x
> is the emptyset. A,B agree below p in Q if and only if for all x in
> Q^k with max(x) < p, x in A iff x in B. Let E containedin Q. E^r> is
> the set of all r tuples from E that are strictly decreasing. E^r>=,
> E^r<, E^r<= are defined analogously.
>
> PROPOSITION 2.1. Every order invariant relation on Q[0,1]^k has a
> maximal root whose sections at elements of {1,1/2,...,1/n}^r> agree
> below 1/n.
>
> There are a number of successive strenghenings of Proposition 2.1
> involving sections. The following is the strongest one that we
> consider.
>
> DEFINITION 2.2. Let E containedin Q. E^<=k is the set of all
> sequences from E of lengths 1,...,k. For x,y in Q^k, x*y is x
> concatenated with y. min(x) is the least coordinate of x.
>
> PROPOSITION 2.2. Every order invariant relation on Q[0,1]^k has a
> maximal root whose sections at any two order equivalent x,y in
> {1,1/2,...,1/n}^<=k agree below min(x*y).
>
> DEFINITION 2.3. Let E be a finite subset of Q[0,1]. The E-lift of x in
> Q[0,1]^k is obtained by replacing each x_i in E that is greater than
> all x_j notin E by the next greatest element of E; x if this does not
> exist.
>
> PROPOSITION 2.3. Let E be a finite subset of Q[0,1]. Every order
> invariant relation on Q[0,1]^k has an E-lift invariant maximal root.
>
> DEFINITION 2.4. Let E be a finite subset of Q[0,1]. x,y in Q[0,1]^k
> are E-related (are E-relatives) if and only if
> i. x,y are order equivalent.
> ii. the coordinates of x,y that are not in E are identical in
> identical positions, and smaller than the coordinates of x,y that are
> in E.
>
> PROPOSITION 2.4. Let E be a finite subset of Q[0,1]. Every order
> invariant relation on Q[0,1]^k has an E-related invariant maximal
> root.
>
> THEOREM 2.5. Propositions 2.1 - 2.4 are provably equivalent to Pi01
> sentences over WKL_0 via Goedel's Completeness Theorem.
>
> THEOREM 2.6. Propositions 2.1 - 2.4 are provably equivalent to
> Con(SRP) over WKL_0.
>
> 3. G-BASES IN Q^k
>
> DEFINITION 3.1. Let R be a relation on Q^k. x R reduces to y if and
> only if x R y and max(x) > max(y). S is R free if and only if S
> containedin Q^k and no element of S R reduces to any element of S. S
> is an R basis if and only if S is R free and every element of Q^k\S R
> reduces to some element of S.
>
> THEOREM 3.1. R = Q^2 has no basis.
>
> Here is a Perfectly Natural way to recover from Theorem 3.1. Instead
> of requiring that every element of Q^k\S reduces to some element of S,
> we require only that all tuples "built out of the elements of S"
> reduce to some element of S.
>
> DEFINITION 3.2. Let R be a relation on Q^k and G:Q^k into Q^k. A
> G-basis for R is an R free S such that every element of G[S]\S reduces
> to an element of S. More generally, let H:Q^kr into Q^k. An H-basis
> for R is a nonempty R free S such that every element of H[S^r]\S
> reduces to an element of S.
>
> THEOREM 3.2. Let H:Q^kr into Q^k be order theoretic. Every order
> invariant relation on Q^k has an H-basis.
>
> TEMPLATE J. Let F:Q^k into Q^k be order theoretic. For all order
> theoretic G:Q^k into Q^k, every order invariant relation on Q^k has a
> G-basis containing its F image.
>
> TEMPLATE K. Let E be an order theoretic equivalence relation on
> Q[0,1]^k. For all order theoretic G:Q^k into Q^k, every order
> invariant relation on Q^k has a G-basis containing its E image.
>
> TEMPLATE L. Let f:Q[0,1] into Q[0,1] be order theoretic. For all order
> theoretic G:Q^k into Q^k, every order invariant relation on Q^k has a
> G-basis containing its f image.
>
> We also have the variants with stronger conclusions.
>
> TEMPLATE M. Let F:Q^k into Q^k be order theoretic. For all order
> theoretic H:Q^kr into Q^k, every order invariant relation on Q^k has
> an H-basis containing its F image.
>
> TEMPLATE N. Let E be an order theoretic equivalence relation on
> Q[0,1]^k. For all order theoretic H:Q^kr into Q^k, every order
> invariant relation on Q^k has an H-basis containing its E image.
>
> TEMPLATE O. Let f:Q[0,1] into Q[0,1] be order theoretic. For all order
> theoretic H:Q^kr into Q^k, every order invariant relation on Q^k has
> an H-basis containing its f image.
>
> Here we know much more than we do in section 1. We can completely
> analyze Templates J-O, but only using large cardinals.
>
> THEOREM 3.3. Every instance of Templates J,K,M,N is either provable in
> SRP or refutable in RCA_0. Every instance of Templates L,O are either
> provable in WKL_0 + Con(SRP) or refutable in RCA_0. Assuming Con(SRP),
> Templates J,M are equivalent; K,N are equivalent; L,O are equivalent.
> In the first two claims, we cannot replace SRP by any fixed SRP[k].
>
> With relative bases we can go well beyond order theoretic invariance
> in Perfectly Natural ways. This allows us to give a particularly
> simple example of CMI.
>
> DEFINITION 3.3. The upper shift of x in Q^k is the result of adding 1
> to all nonnegative coordinates of x. The upper shift of S containedin
> Q^k is the set of upper shifts of the elements of S. A finite sequence
> of sets in various Q^k contains its upper shift if and only if each
> term contains its upper shift.
>
> PROPOSITION 3.4. For all order theoretic G:Q^k into Q^k, every order
> invariant relation on Q^k has a G-basis containing its upper shift.
>
> PROPOSITION 3.5. For all order theoretic H:Q^kr into Q^k, every order
> invariant relation on Q^k has an H-basis containing its upper shift.
>
> THEOREM 3.5. Propositions 3.4 and 3.5 are provably equivalent to
> Con(SRP) over WKL_0.
>
> TEMPLATE P. Let f:Q into Q be rational piecewise linear. For all order
> theoretic G:Q^k into Q^k, every order invariant relation on Q^k has a
> G-basis containing its f image.
>
> We also have the following multiple form.
>
> TEMPLATE Q. Let f_1,...,f_r:Q into Q be rational piecewise linear. For
> all order theoretic HG:Q^kr into Q^k, every order invariant relation
> on Q^k has an H-basis containing its f_1,...,f_r images.
>
> THEOREM 3.6. Every instance of Templates P,Q is either provable in
> WKL_0 + Con(SRP) or refutable in RCA_0.
>
> 4. p,G-BASES IN Q^k
>
> The p,G-bases of R, p >= 2, form a Perfectly Natural way of
> approximating the G-bases of R. pG-bases can be finite for any R,
> whereas this is not the case for G-bases.
>
> DEFINITION 4.1. Let R be a relation on Q^k, G:Q^k into Q^k, and p >=
> 2. A p,G-basis for R consists of nonempty sets A_1 containedin ...
> containedin A_p containedin Q^k, where A_p is R free and every element
> of G[A_i], i < p, reduces to an element of A_i+1.
>
> PROPOSITION 4.1. Let G:Q^k into Q^k be order theoretic. Every order
> invariant relation on Q^k has a finite 3,G-basis A containedin B
> containedin C, where C contains the upper shift of B.
>
> PROPOSITION 4.2. Let H:Q^kr into Q^k be order theoretic. Every order
> invariant relation on Q^k has a finite p,H-basis A_1 containedin ...
> containedin A_p, where each A_i+1 contains the upper shift of A_i.
>
> PROPOSITION 4.3. Let H:Q^kr into Q^k be order theoretic. Every order
> invariant relation on Q^k has a p,H-basis A_1 containedin ...
> containedin A_p, where each A_i contains its upper shift.
>
> Propositions 4.1 and 4.2 are explicitly Pi02. There is an obvious
> iterated exponential bounds on the cardinalities involved, and also
> the numerators and denominators involved so that they become
> explicitly Pi01. With Proposition 4.3, the sets generally have to be
> infinite, but they can have a combinatorial structure also leading to
> explicitly Pi01 forms.
>
> THEOREM 4.4. Propositions 4.1 and 4.2 are provably equivalent to
> Con(SRP) over EFA. Proposition 4.3 is provably equivalent to Con(SRP)
> over RCA_0.
>
> ************************************************************
> 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 562nd 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-527 can be found at the FOM posting
> http://www.cs.nyu.edu/pipermail/fom/2014-August/018092.html
>
> 528: More Perfect Pi01 8/16/14 5:19AM
> 529: Yet more Perfect Pi01 8/18/14 5:50AM
> 530: Friendlier Perfect Pi01
> 531: General Theory/Perfect Pi01 8/22/14 5:16PM
> 532: More General Theory/Perfect Pi01 8/23/14 7:32AM
> 533: Progress - General Theory/Perfect Pi01 8/25/14 1:17AM
> 534: Perfect Explicitly Pi01 8/27/14 10:40AM
> 535: Updated Perfect Explicitly Pi01 8/30/14 2:39PM
> 536: Pi01 Progress 9/1/14 11:31AM
> 537: Pi01/Flat Pics/Testing 9/6/14 12:49AM
> 538: Progress Pi01 9/6/14 11:31PM
> 539: Absolute Perfect Naturalness 9/7/14 9:00PM
> 540: SRM/Comparability 9/8/14 12:03AM
> 541: Master Templates 9/9/14 12:41AM
> 542: Templates/LC shadow 9/10/14 12:44AM
> 543: New Explicitly Pi01 9/10/14 11:17PM
> 544: Initial Maximality/HUGE 9/12/14 8:07PM
> 545: Set Theoretic Consistency/SRM/SRP 9/14/14 10:06PM
> 546: New Pi01/solving CH 9/26/14 12:05AM
> 547: Conservative Growth - Triples 9/29/14 11:34PM
> 548: New Explicitly Pi01 10/4/14 8:45PM
> 549: Conservative Growth - beyond triples 10/6/14 1:31AM
> 550: Foundational Methodology 1/Maximality 10/17/14 5:43AM
> 551: Foundational Methodology 2/Maximality 10/19/14 3:06AM
> 552: Foundational Methodology 3/Maximality 10/21/14 9:59AM
> 553: Foundational Methodology 4/Maximality 10/21/14 11:57AM
> 554: Foundational Methodology 5/Maximality 10/26/14 3:17AM
> 555: Foundational Methodology 6/Maximality 10/29/14 12:32PM
> 556: Flat Foundations 1 10/29/14 4:07PM
> 557: New Pi01 10/30/14 2:05PM
> 558: New Pi01/more 10/31/14 10:01PM
> 559: Foundational Methodology 7/Maximality 11/214 10:35PM
> 560: New Pi01/better 11/314 7:45PM
> 561: New Pi01/HUGE 11/5/14 3:34 PM
>
> Harvey Friedman
>
>
> ------------------------------
>
> Message: 3
> Date: Thu, 20 Nov 2014 12:31:26 -0500
> From: Robert Rynasiewicz <ryno at lorentz.phl.jhu.edu>
> To: Foundations of Mathematics <fom at cs.nyu.edu>
> Subject: Re: [FOM] Leibnizian principles
> Message-ID: <238E2C88-E900-4F10-8BBA-576130C0D808 at lorentz.phl.jhu.edu>
> Content-Type: text/plain; charset="windows-1252"
>
> This was an error in transcription. My apologies. The original reads ?without?. ?RR
>
>> On Sun 16.11.14, at 8:13 PM, Rob Arthan <rda at lemma-one.com> wrote:
>>
>>
>>> On 15 Nov 2014, at 02:05, Robert Rynasiewicz <ryno at lorentz.phl.jhu.edu <mailto:ryno at lorentz.phl.jhu.edu>> wrote:
>>>
>>> ?L?Espace est quelque chose d?uniforme absolument; & sans les choses y plac?es, un point de l?Espace ne differe absolument en rien d?un autre point d?Espace. [Space is Something absolutely Uniform; and with the Things placed in it, One Point of Space does not absolutely differ in any respect whatsoever from Another Point of Space.]?
>>
>> I have no comments to add on the philosophical issues, but ?sans? means ?without? not ?with?.
>>
>> Regards,
>>
>> Rob.
>> _______________________________________________
>> FOM mailing list
>> FOM at cs.nyu.edu
>> http://www.cs.nyu.edu/mailman/listinfo/fom
>
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: </pipermail/fom/attachments/20141120/9f5f398f/attachment.html>
>
> ------------------------------
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
>
> End of FOM Digest, Vol 143, Issue 17
> ************************************
More information about the FOM
mailing list