Екінші реттік логика: Предикаттар бойынша квантификациялау мүмкіндігі

Кіріспе

Предикаттар бойынша сандық анықтамаға мүмкіндік беретін логика түрі. Логика мен математикада екінші реттік логика – бірінші реттік логиканың кеңейтілуі, ал ол өзі – еңбек логиканың кеңейтілуі болып табылады. Екінші реттік логика өз кезегінде жоғары реттік логика және типтер теориясымен кеңейтіледі. Бірінші реттік логика тек жеке элементтер (дискурс доменінің элементтері) бойынша өзгеретін айнымалыларды сандық анықтайды; екінші реттік логика, сонымен қатар, қатынастарды сандық анықтайды. Мысалы, екінші реттік сөйлемде кез келген формула P және кез келген жеке x үшін, Px дұрыс немесе Px емес дұрыс болады (бұл – шығарылған орта заңы). Екінші реттік логика жиындар, функциялар және басқа да айнымалылар бойынша сандық анықтаманы да қамтиды (төмендегі бөлімді қараңыз). Бірінші және екінші реттік логика екеуі де дискурс доменін (көбінесе жай ғана «домен» немесе «әмбебап жиын» деп аталады) пайдаланады. Домен – жеке элементтерді сандық анықтауға болатын жиын.

Синтаксис және фрагменттер

Екінші реттік логиканың синтаксисі, қандай өрнектердің дұрыс құрылған формулалар екенін көрсетеді. Бірінші реттік логиканың синтаксисіне қоса, екінші реттік логикада көптеген жаңа айнымалылар түрлері (кейде типтер деп аталады) бар. Олар: жеке тұлғалар жиыны бойынша өтетін айнымалылар түрі. Егер S осы түрдегі айнымалы болса және t бірінші реттік термин болса, онда t ∈ S (сондай-ақ S(t) немесе St деп жазылуы мүмкін, жақшаларды қысқарту үшін) – атомдық формула болады. Жеке тұлғалар жиынын домендегі унарлық қатынастар ретінде де қарастыруға болады. Кез келген k табиғи саны үшін жеке тұлғаларға қатысты барлық k-арлық қатынастарды қамтитын айнымалылар түрі бар. Егер R осындай k-арлық қатынас айнымалысы болса және t1, …, tk бірінші реттік терминдер болса, онда R(t1, …, tk) – атомдық формула болады. Кез келген k табиғи саны үшін доменнің k элементін қабылдап, доменнің бір элементін қайтаратын барлық функцияларға қатысты айнымалылар түрлері бар. Егер f осындай k-арлық функциясының айнымалысы болса және t1, …, tk бірінші реттік терминдер болса, онда f(t1, …, tk) – бірінші реттік термин болады. Дәл анықталған әрбір айнымалы үшін жалпы және/немесе экзистенциалдық кванторларды қолдану арқылы формулалар құруға болады. Осылайша, әр түрдегі айнымалылар үшін екі квантордың түрлері бар. Екінші реттік логикадағы теорема, бірінші реттік логикадағыдай, кез келген түрдегі еркін айнымалылары жоқ дұрыс құрылған формула болып табылады. Жоғарыдағы анықтамада функциялық айнымалыларды енгізуден бас тартуға болады (кейбір авторлар осылай жасайды), себебі n-арлық функциялық айнымалы n+1 арлық қатынас айнымалысымен және қатынастың n+1 аргументіндегі "нәтижесінің" бірегейлігін көрсететін тиісті формуламен бейнеленеді. (Шапиро 2000, 63-бет)

Монадалық екінші реттік логика (MSO) – екінші реттік логиканың шектеуі, онда тек унарлық қатынастар (яғни жиындар) бойынша квантификацияға рұқсат етіледі. Жоғарыда сипатталған қатынастардың теңдестігіне байланысты функциялар бойынша квантификацияға да рұқсат етілмейді. Бұл шектеулерсіз екінші реттік логика кейде монадтық нұсқадан ажырату үшін толық екінші реттік логика деп аталады. Монадалық екінші реттік логика, әсіресе, графтар теориясындағы алгоритмдік метатеорема – Курселл теоремасының аясында қолданылады. Толық шексіз екілік ағаштың (S2S) MSO теориясы шешіледі. Керісінше, кез келген шексіз жиынтыққа (немесе мысалы, (,+)-ға) қатысты толық екінші реттік логика нақты екінші реттік арифметиканы интерпретациялай алады. Бірінші реттік логикадағыдай, екінші реттік логика белгілі бір екінші реттік тілде логикалық емес символдарды қамтуы мүмкін. Алайда, олар құрайтын барлық терминдер бірінші реттік терминдер (бірінші реттік айнымалыны алмастыруға болатын) немесе екінші реттік терминдер (тиісті түрдегі екінші реттік айнымалыны алмастыруға болатын) болуы керек. Екінші реттік логикадағы формула, егер оның кванторлары (жалпы немесе экзистенциалдық болуы мүмкін) тек бірінші реттік айнымалыларға қатысты болса, бірінші реттік деп аталады (кейде ∨ немесе ∃ деп белгіленеді), бірақ екінші реттік еркін айнымалылары болуы мүмкін. Екінші реттік логиканың тек экзистенциалдық екінші реттік формулалардан тұратын фрагменті экзистенциалдық екінші реттік логика деп аталады және ESO, ∃SO немесе тіпті ∃SO деп қысқартылады. Формулалардың фрагменті дуалды түрде анықталады, оны әмбебап екінші реттік логика деп атайды. Кез келген k > 0 үшін өзара рекурсия арқылы экспрессивті фрагменттер анықталады: формасы бар φ, мұнда φ – формула, және ұқсас, формасы бар ψ, мұнда ψ – формула. (Екінші реттік арифметиканың ұқсас құрылымы үшін аналитикалық иерархияны қараңыз.)

Monadic second order logic (MSO) is a restriction of second order logic in which only quantification over unary relations (i. e. sets) is allowed. Quantification over functions, owing to the equivalence to relations as described above, is thus also not allowed. The second order logic without these restrictions is sometimes called full second order logic to distinguish it from the monadic version. Monadic second order logic is particularly used in the context of Courcelle's theorem, an algorithmic meta theorem in graph theory. The MSO theory of the complete infinite binary tree (S2S) is decidable. By contrast, full second order logic over any infinite set (or MSO logic over for example (,+)) can interpret the true second order arithmetic. Just as in first order logic, second order logic may include non logical symbols in a particular second order language. These are restricted, however, in that all terms that they form must be either first order terms (which can be substituted for a first order variable) or second order terms (which can be substituted for a second order variable of an appropriate sort). A formula in second order logic is said to be of first order (and sometimes denoted or ) if its quantifiers (which may be universal or existential) range only over variables of first order, although it may have free variables of second order. A (existential second order) formula is one additionally having some existential quantifiers over second order variables, i. e. , where is a first order formula. The fragment of second order logic consisting only of existential second order formulas is called existential second order logic and abbreviated as ESO, as , or even as ∃SO. The fragment of formulas is defined dually, it is called universal second order logic. More expressive fragments are defined for any k > 0 by mutual recursion: has the form , where is a formula, and similar, has the form , where is a formula. (See analytical hierarchy for the analogous construction of second order arithmetic.)

Семантика

Екінші реттік логиканың семантикасы әрбір сөйлемнің мағынасын белгілейді. Бірінші реттік логикадан өзгешелігі, ол тек бір стандартты семантикаға ие болса, екінші реттік логика үшін екі кең таралған семантика бар: стандартты семантика және Хенкин семантикасы. Осы семантикалардың екеуінде де бірінші реттік кванторлар мен логикалық байланыстар бірінші реттік логикадағыдай жұмыс істейді. Екі типтегі семантикада ғана екінші реттік айнымалылар бойынша кванторлардың ауқымы әртүрлі болады (Väänänen 2001). Стандартты семантика, сондай-ақ толық семантика деп аталатын, кванторлардың ауқымы тиісті типтегі барлық жиындықтарды немесе функцияларды қамтиды. Бірінші реттік айнымалылардың домені белгіленгеннен кейін, қалған кванторлардың мағынасы анықталады. Осы семантика екінші реттік логикаға экспрессивті күшін береді және осы мақаланың соңына дейін осы семантика қолданылады. Леон Хенкин (1950) екінші және жоғары реттік теориялар үшін балама семантиканы анықтады, онда жоғары реттік домендердің мағынасы, жиындықтар немесе функциялардың қасиеттерін түсіндіретін, типтер теориясына негізделген нақты аксиоматизациямен анықталады. Хенкин семантикасы – көп сортты бірінші реттік семантиканың бір түрі, онда стандартты семантикадағыдай семантика тек стандартты модельге ғана бекітілмейді, аксиомалардың модельдер класы бар. Хенкин семантикасындағы модель жоғары реттік домендердің интерпретациясы ретінде жиындықтар немесе функциялар жиынтығын ұсынады, бұл тиісті типтегі барлық жиындықтар немесе функциялардың кіші жиыны болуы мүмкін. Хенкин өз аксиоматизациясы үшін Гёдельдің толықтық теоремасы мен ықшамдық теоремасы, бірінші реттік логика үшін жарамды, Хенкин семантикасымен екінші реттік логикаға да қатысты екенін дәлелдеді. Сондай-ақ, Skolem–Löwenheim теоремалары Хенкин семантикасы үшін жарамды болғандықтан, Линдстрем теоремасы Хенкин модельдерінің жасырылған бірінші реттік модельдер екенін көрсетеді. Екінші реттік арифметика сияқты теориялар үшін жоғары реттік домендердің стандартты емес интерпретацияларының болуы Хенкин қолданған типтер теориясынан алынған нақты аксиоматизацияның кемшілігі ғана емес, сонымен қатар Гёдельдің толық еместік теоремасының қажетті салдары: Хенкин аксиомаларын стандартты интерпретацияны қамтамасыз ету үшін одан әрі толықтыру мүмкін емес. Хенкин семантикасы екінші реттік арифметиканы зерттеуде кеңінен қолданылады. Джоуко Вэнанен (2001) екінші реттік логика үшін Хенкин модельдері мен толық модельдердің арасындағы таңдау, жинақтар теориясының негізі ретінде ZFC мен V арасындағы таңдауға ұқсас екенін айтты: "Екінші реттік логика сияқты, математиканы V немесе ZFC арқылы аксиоматизациялауды таңдау мүмкін емес. Екі жағдайда да нәтиже бірдей, өйткені ZFC – V-ді математиканы аксиоматизациялауға жасалған ең жақсы әрекет".

The semantics of second order logic establish the meaning of each sentence. Unlike first order logic, which has only one standard semantics, there are two different semantics that are commonly used for second order logic: standard semantics and Henkin semantics. In each of these semantics, the interpretations of the first order quantifiers and the logical connectives are the same as in first order logic. Only the ranges of quantifiers over second order variables differ in the two types of semantics (Väänänen 2001). In standard semantics, also called full semantics, the quantifiers range over all sets or functions of the appropriate sort. Thus once the domain of the first order variables is established, the meaning of the remaining quantifiers is fixed. It is these semantics that give second order logic its expressive power, and they will be assumed for the remainder of this article. Leon Henkin (1950) defined an alternative kind of semantics for second order and higher order theories, in which the meaning of the higher order domains is partly determined by an explicit axiomatisation, drawing on type theory, of the properties of the sets or functions ranged over. Henkin semantics is a kind of many sorted first order semantics, where there are a class of models of the axioms, instead of the semantics being fixed to just the standard model as in the standard semantics. A model in Henkin semantics will provide a set of sets or set of functions as the interpretation of higher order domains, which may be a proper subset of all sets or functions of that sort. For his axiomatisation, Henkin proved that Gödel's completeness theorem and compactness theorem, which hold for first order logic, carry over to second order logic with Henkin semantics. Since also the Skolem–Löwenheim theorems hold for Henkin semantics, Lindström's theorem imports that Henkin models are just disguised first order models. For theories such as second order arithmetic, the existence of non standard interpretations of higher order domains isn't just a deficiency of the particular axiomatisation derived from type theory that Henkin used, but a necessary consequence of Gödel's incompleteness theorem: Henkin's axioms can't be supplemented further to ensure the standard interpretation is the only possible model. Henkin semantics are commonly used in the study of second order arithmetic. Jouko Väänänen (2001) argued that the choice between Henkin models and full models for second order logic is analogous to the choice between ZFC and V as a basis for set theory: "As with second order logic, we cannot really choose whether we axiomatize mathematics using V or ZFC. The result is the same in both cases, as ZFC is the best attempt so far to use V as an axiomatization of mathematics."

Экспрессивтік күш

Екінші реттік логика бірінші реттік логикадан гөрі көбірек экспрессивті. Мысалы, егер домен барлық нақты сандар жиыны болса, бірінші реттік логикада әр нақты санның қосымша кері санының бар екенін ∀x∃y (x + y = 0) деп жазып көрсетуге болады, бірақ нақты сандар жиындары үшін ең төменгі жоғарғы шек қасиетін растау үшін екінші реттік логика қажет, яғни нақты сандардың әрбір шектеулі, бос емес жиынының жоғарғы шегі болады. Егер домен барлық нақты сандар жиыны болса, келесі екінші реттік сөйлем (екі жолға бөлінген) ең төменгі жоғарғы шек қасиетін білдіреді: Бұл формула "әрбір , жиынтық А ." Бұл қасиетті қанағаттандыратын кез келген реттелген өріс нақты сандар өрісіне изоморфты екенін көрсетуге болады. Екінші жағынан, нақты сандарда дұрыс болатын бірінші реттік сөйлемдер жиыны компакттылық теоремасына сәйкес, кез келген үлкен модельдерге ие. Осылайша, ең төменгі жоғарғы шек қасиетін бірінші реттік логикадағы сөйлемдер жиыны арқылы білдіру мүмкін емес. (Шындығында, әрбір нақты жабық өріс нақты сандар сияқты бірдей қолтаңбадағы бірінші реттік сөйлемдерді қанағаттандырады.) Екінші реттік логикада "домен шекті" немесе "домен санаулы кардиналдылыққа ие" деген ресми сөйлемдерді жазуға болады. Домен шекті деп айту үшін, доменнен өзіне дейінгі әрбір сюръективті функция инъективті екенін білдіретін сөйлемді пайдаланыңыз. Домен санаулы кардиналдылыққа ие деп айту үшін, доменнің кез келген екі шексіз ішкі жиыны арасында биекция бар екенін білдіретін сөйлемді пайдаланыңыз. Бұл компакттылық теоремасы мен жоғары Ловенхайм-Сколем теоремасынан бірінші реттік логикада тиісінше шектілікті немесе санаулылықты сипаттау мүмкін емес екендігі көрінеді. Екінші реттік логиканың ESO сияқты кейбір фрагменттері бірінші реттік логикадан гөрі экспрессивті, бірақ толық екінші реттік логикадан кем экспрессивті. ESO сондай-ақ, сандық тәуелділіктердің сызықтық емес ретін қадағалауға мүмкіндік беретін бірінші реттік логиканың кейбір кеңейтімдерімен аударма эквиваленттілігін көрсетеді, мысалы, Хенкин сандықтарымен кеңейтілген бірінші реттік логика, Хинтика мен Сандудың тәуелсіздікке бейім логикасы және Вейненнің тәуелділік логикасы.

Second order logic is more expressive than first order logic. For example, if the domain is the set of all real numbers, one can assert in first order logic the existence of an additive inverse of each real number by writing ∀x ∃y (x + y = 0) but one needs second order logic to assert the least upper bound property for sets of real numbers, which states that every bounded, nonempty set of real numbers has a supremum. If the domain is the set of all real numbers, the following second order sentence (split over two lines) expresses the least upper bound property:

This formula is a direct formalization of "every , set A ." It can be shown that any ordered field that satisfies this property is isomorphic to the real number field. On the other hand, the set of first order sentences valid in the reals has arbitrarily large models due to the compactness theorem. Thus the least upper bound property cannot be expressed by any set of sentences in first order logic. (In fact, every real closed field satisfies the same first order sentences in the signature as the real numbers.) In second order logic, it is possible to write formal sentences that say "the domain is finite" or "the domain is of countable cardinality." To say that the domain is finite, use the sentence that says that every surjective function from the domain to itself is injective. To say that the domain has countable cardinality, use the sentence that says that there is a bijection between every two infinite subsets of the domain. It follows from the compactness theorem and the upward Löwenheim–Skolem theorem that it is not possible to characterize finiteness or countability, respectively, in first order logic. Certain fragments of second order logic like ESO are also more expressive than first order logic even though they are strictly less expressive than the full second order logic. ESO also enjoys translation equivalence with some extensions of first order logic that allow non linear ordering of quantifier dependencies, like first order logic extended with Henkin quantifiers, Hintikka and Sandu's independence friendly logic, and Väänänen's dependence logic.

Дедуктивті жүйелер

Логиканың дедуктивті жүйесі – формулалардың қай тізбектері жарамды дәлелдемелер құрайтынын анықтайтын, қорытынды шығару ережелері мен логикалық аксиомалар жиынтығы. Екінші реттік логика үшін бірнеше дедуктивті жүйе қолданылуы мүмкін, бірақ ешқайсысы да стандартты семантика үшін толық бола алмайды (төменде қараңыз). Бұл жүйелердің барлығы да дұрыс, яғни олармен дәлелдеуге болатын кез келген тұжырым тиісті семантикада логикалық жағынан дұрыс болады. Қолдануға болатын ең әлсіз дедуктивті жүйе – бірінші реттік логикаға арналған стандартты дедуктивті жүйе (мысалы, табиғи дедукция) екінші реттік терминдерді алмастыру ережелерімен толықтырылған нұсқасы. Бұл дедуктивті жүйе екінші реттік арифметиканы зерттеуде кеңінен қолданылады. Шапиро (1991) және Хенкин (1950) қарастырған дедуктивті жүйелер кеңейтілген бірінші реттік дедуктивті схемаға түсіністік аксиомалары мен таңдау аксиомаларын қосады. Бұл аксиомалар стандартты екінші реттік семантика үшін дұрыс. Олар Хенкин семантикасы үшін, түсіністік және таңдау аксиомаларын қанағаттандыратын Хенкин модельдерімен шектелгенде де дұрыс.

Бірінші реттік логикаға қайтаруға болмайтындық

Реал сандардың екінші реттік теориясын, толық екінші реттік семантикамен, төменде көрсетілгендей бірінші реттік теорияға келтіруге талпынуға болады. Бірінші, доменді барлық нақты сандар жиынынан екі реттелген доменге кеңейтіңіз, екінші ретте барлық нақты сандар жиындарын қамтиды. Тілге жаңа бинарлық предикат қосыңыз: мүшелік қатынасы. Содан кейін, бұрынғы екінші реттік сөйлемдер бірінші реттікке айналады, ал бұрынғы екінші реттік кванторлар екінші реттегі элементтер арасында өтеді. Бұл келтіруді бір реттелген теорияда элементтің сан немесе жиын екенін көрсететін униарлық предикаттарды қосу арқылы және доменді нақты сандар жиыны мен нақты сандардың қуаты жиыны деп қабылдау арқылы жасауға болады. Бірақ, доменге нақты сандардың барлық жиындары кіреді деп ескеріңіз. Бұл талапты бірінші реттік сөйлемге келтіру мүмкін емес, өйткені Лёвенхайм-Школем теоремасы оны көрсетеді. Бұл теорема, нақты сандардың санауға болатын шексіз кіші жиындарының бар екенін, олардың мүшелерін «ішкі сандар» деп атаймыз, сондай-ақ ішкі сандар жиындарының санауға болатын шексіз жиындарының бар екенін, олардың мүшелерін «ішкі жиындар» деп атаймыз, мұндай ішкі сандар мен ішкі жиындардан тұратын домен нақты сандар домені мен нақты сандар жиыны қанағаттандыратын дәл сол бірінші реттік сөйлемдерді қанағаттандырады. Атап айтқанда, ол былай дейтін ең төменгі жоғарғы шек аксиомасын қанағаттандырады: ішкі жоғарғы шегі бар әрбір бос емес ішкі жиынның ең төменгі ішкі жоғарғы шегі бар. Барлық ішкі сандар жиынының санаулылығы (олар тығыз реттелген жиынды құрайтынымен бірге) бұл жиынның толық ең төменгі жоғарғы шек аксиомасын қанағаттандырмайтынын білдіреді. Барлық ішкі жиындар жиынының санаулылығы оның барлық ішкі сандар жиынының барлық кіші жиындарының жиыны емес екенін білдіреді (өйткені Кантор теоремасы санаулы шексіз жиынның барлық кіші жиындарының жиыны санаусыз шексіз жиын екенін білдіреді). Бұл құрылым Сколемнің парадоксымен тығыз байланысты. Осылайша, нақты сандар мен нақты сандар жиындарының бірінші реттік теориясы көптеген модельдерге ие, олардың кейбіреулерін санауға болады. Дегенмен, нақты сандардың екінші реттік теориясының тек бір ғана моделі бар. Бұл классикалық теоремадан, тек бір ғана Архимедтік толық реттелген өріс бар екендігінен және Архимедтік толық реттелген өрістің барлық аксиомаларын екінші реттік логикада тұжырымдауға болатындығынан туындайды. Бұл нақты сандардың екінші реттік теориясын бірінші реттік теорияға келтіруге болмайтынын көрсетеді, себебі нақты сандардың екінші реттік теориясының тек бір ғана моделі бар, ал сәйкес бірінші реттік теорияның көптеген модельдері бар. Стандартты семантикасы бар екінші реттік логика бірінші реттік логикадан гөрі экспрессивтірек екенін көрсететін мысалдар бар. Континуум гипотезасы дұрыс болса, оның жалғыз моделі нақты сандар болатын және континуум гипотезасы дұрыс болмаса, оның моделі жоқ екінші реттік теория бар (Shapiro 2000, 105-бетке қараңыз). Бұл теория нақты сандарды толық Архимедтік реттелген өріс ретінде сипаттайтын шекті теориядан және доменнің бірінші санаусыз кардиналдылығына ие екенін көрсететін аксиомадан тұрады. Бұл мысал екінші реттік логикадағы сөйлемнің дұрыстығы туралы сұрақ өте күрделі екенін көрсетеді. Екінші реттік логиканың қосымша шектеулері келесі бөлімде сипатталған.

One might attempt to reduce the second order theory of the real numbers, with full second order semantics, to the first order theory in the following way. First expand the domain from the set of all real numbers to a two sorted domain, with the second sort containing all sets of real numbers. Add a new binary predicate to the language: the membership relation. Then sentences that were second order become first order, with the formerly second order quantifiers ranging over the second sort instead. This reduction can be attempted in a one sorted theory by adding unary predicates that tell whether an element is a number or a set, and taking the domain to be the union of the set of real numbers and the power set of the real numbers. But notice that the domain was asserted to include all sets of real numbers. That requirement cannot be reduced to a first order sentence, as the Löwenheim–Skolem theorem shows. That theorem implies that there is some countably infinite subset of the real numbers, whose members we will call internal numbers, and some countably infinite collection of sets of internal numbers, whose members we will call "internal sets", such that the domain consisting of internal numbers and internal sets satisfies exactly the same first order sentences as are satisfied by the domain of real numbers and sets of real numbers. In particular, it satisfies a sort of least upper bound axiom that says, in effect:

Every nonempty internal set that has an internal upper bound has a least internal upper bound. Countability of the set of all internal numbers (in conjunction with the fact that those form a densely ordered set) implies that that set does not satisfy the full least upper bound axiom. Countability of the set of all internal sets implies that it is not the set of all subsets of the set of all internal numbers (since Cantor's theorem implies that the set of all subsets of a countably infinite set is an uncountably infinite set). This construction is closely related to Skolem's paradox. Thus the first order theory of real numbers and sets of real numbers has many models, some of which are countable. The second order theory of the real numbers has only one model, however. This follows from the classical theorem that there is only one Archimedean complete ordered field, along with the fact that all the axioms of an Archimedean complete ordered field are expressible in second order logic. This shows that the second order theory of the real numbers cannot be reduced to a first order theory, in the sense that the second order theory of the real numbers has only one model but the corresponding first order theory has many models. There are more extreme examples showing that second order logic with standard semantics is more expressive than first order logic. There is a finite second order theory whose only model is the real numbers if the continuum hypothesis holds and that has no model if the continuum hypothesis does not hold (cf. Shapiro 2000, p. 105). This theory consists of a finite theory characterizing the real numbers as a complete Archimedean ordered field plus an axiom saying that the domain is of the first uncountable cardinality. This example illustrates that the question of whether a sentence in second order logic is consistent is extremely subtle. Additional limitations of second order logic are described in the next section.

Тарих және талас-тартыстар

Предикаттық логика математикалық қауымдастыққа К. С. Пирс арқылы енгізілді, ол екінші реттік логика терминін ойлап тапты және оның нотациясы қазіргі заманғы формаға (Путнам 1982) ең жақын. Дегенмен, бүгінде логиканы оқыған көптеген студенттер Пирстен бірнеше жыл бұрын өз еңбектерін жариялаған, бірақ Бертран Рассел мен Альфред Норт Уайтхед оларды танымал еткенге дейін аз танымал болған Фреге еңбектерімен көбірек таныс. Фреге объектілер мен қасиеттер мен жиындар бойынша сандық анықтаманы ажырату үшін әртүрлі айнымалыларды қолданды; бірақ ол өзін екі түрлі логиканы жасаушы деп санамады. Расселдің парадоксы ашылғаннан кейін оның жүйесінде бірдеңе дұрыс емес екені анықталды. Соңында логиктер Фреге логикасын түрлі жолдармен шектеуді тапты, қазір бірінші реттік логика деп аталатын бұл шектеу мәселені жойды: жиындар мен қасиеттерді бірінші реттік логикада ғана сандық анықтамаға жатқызуға болмайды. Логиканың қазіргі стандартты иерархиясы осы кезден бастау алады. Жинақтар теориясы бірінші реттік логика аппаратында аксиоматизацияланған жүйе ретінде тұжырымдалуы мүмкін екендігі анықталды (бірнеше толықтық түрлерінің құнымен, бірақ Расселдің парадоксынан кем емес нәрсе жоқ), және бұл жасалды (Зермело-Франкельдің жинақтар теориясын қараңыз), өйткені жинақтар математика үшін маңызды. Арифметика, мереология және басқа да көптеген қуатты логикалық теориялар бірінші реттік сандық анықтамадан басқа логикалық аппаратқа жүгінбей аксиоматикалық түрде тұжырымдалуы мүмкін, және бұл, Годель мен Сколемнің бірінші реттік логиканы қолдауымен бірге, екінші (немесе одан да жоғары) реттік логикадағы жұмыстың жалпы төмендеуіне әкелді. Бұл қарсылықты кейбір логиктер, ең белгілісі В. В. Куин белсенді түрде қолдады. Куин предикат тіліндегі Fx сияқты сөйлемдерде "x" айнымалы немесе объектіні білдіретін атау ретінде қарастырылуы керек және сондықтан оны "Барлық заттар үшін бұл жағдай..." деп сандық анықтамаға жатқызуға болады, ал "F" толық емес сөйлемнің қысқартылған түрі ретінде қарастырылуы керек, ол объектінің атауы емес (тіпті қасиет сияқты абстрактті объектінің де емес). Мысалы, бұл "...ит" дегенді білдіруі мүмкін. Бірақ мұндай нәрсені сандық анықтамаға жатқызудың мәні жоқ. (Бұл көзқарас Фрегенің концепт пен объектіні ажырату туралы аргументтерімен үйлеседі). Сондықтан предикатты айнымалы ретінде пайдалану – оның жеке айнымалылар ғана иеленуі тиіс атау орнын басуы. Бұл ойға Джордж Булос қарсы шықты. Соңғы жылдары екінші реттік логика қайта жанданды, Булос екінші реттік сандық анықтаманы бірінші реттік сандық анықтама сияқты объектілердің бірдей саласына сандық анықтама ретінде түсіндірді (Boolos 1984). Булос сонымен қатар "Кейбір сыншылар бір-бірін ғана бағалайды" және "Фианчеттоның кейбір адамдары қоймаға ешкіммен бірге кірмеді" сияқты сөйлемдердің бірінші реттік логикада берілмейтіндігіне назар аударды, ол оларды екінші реттік сандық анықтаманың толық күшімен ғана білдіруге болады деп санайды. Дегенмен, жалпыланған сандық және ішінара реттелген (немесе тармақталған) сандық анықтама белгілі бір кластағы берілмейтін сөйлемдерді білдіруге жеткілікті болуы мүмкін, және олар екінші реттік сандық анықтамаға жүгінбейді.

Predicate logic was introduced to the mathematical community by C. S. Peirce, who coined the term second order logic and whose notation is most similar to the modern form (Putnam 1982). However, today most students of logic are more familiar with the works of Frege, who published his work several years prior to Peirce but whose works remained less known until Bertrand Russell and Alfred North Whitehead made them famous. Frege used different variables to distinguish quantification over objects from quantification over properties and sets; but he did not see himself as doing two different kinds of logic. After the discovery of Russell's paradox it was realized that something was wrong with his system. Eventually logicians found that restricting Frege's logic in various ways—to what is now called first order logic—eliminated this problem: sets and properties cannot be quantified over in first order logic alone. The now standard hierarchy of orders of logics dates from this time. It was found that set theory could be formulated as an axiomatized system within the apparatus of first order logic (at the cost of several kinds of completeness, but nothing so bad as Russell's paradox), and this was done (see Zermelo–Fraenkel set theory), as sets are vital for mathematics. Arithmetic, mereology, and a variety of other powerful logical theories could be formulated axiomatically without appeal to any more logical apparatus than first order quantification, and this, along with Gödel and Skolem's adherence to first order logic, led to a general decline in work in second (or any higher) order logic. This rejection was actively advanced by some logicians, most notably W. V. Quine. Quine advanced the view that in predicate language sentences like Fx the "x" is to be thought of as a variable or name denoting an object and hence can be quantified over, as in "For all things, it is the case that . ." but the "F" is to be thought of as an abbreviation for an incomplete sentence, not the name of an object (not even of an abstract object like a property). For example, it might mean " . is a dog." But it makes no sense to think we can quantify over something like this. (Such a position is quite consistent with Frege's own arguments on the concept object distinction). So to use a predicate as a variable is to have it occupy the place of a name, which only individual variables should occupy. This reasoning has been rejected by George Boolos. In recent years second order logic has made something of a recovery, buoyed by Boolos' interpretation of second order quantification as plural quantification over the same domain of objects as first order quantification (Boolos 1984). Boolos furthermore points to the claimed nonfirstorderizability of sentences such as "Some critics admire only each other" and "Some of Fianchetto's men went into the warehouse unaccompanied by anyone else", which he argues can only be expressed by the full force of second order quantification. However, generalized quantification and partially ordered (or branching) quantification may suffice to express a certain class of purportedly nonfirstorderizable sentences as well and these do not appeal to second order quantification.