2차 논리

2차 논리의 문장 가 쓰여진 그라피티 (노이쾰른)

수리논리학에서 2차 논리(二次論理, 영어: second-order logic)는 임의의 다항 관계 및 다항 연산에 대한 변수 및 이에 대한 전칭·존재 기호를 사용할 수 있는 논리이다. 1차 논리에서 변수는 사용하는 모형의 원소만을 지칭하지만, 2차 논리에서는 모형 속의 임의의 부분 집합에 대하여 언급할 수 있다. 이에 따라 2차 논리는 1차 논리보다 더 다양한 개념들에 대하여 논할 수 있다. 그러나 2차 논리는 1차 논리와 달리 완전한 증명 체계를 갖지 못하며, 콤팩트성 정리뢰벤하임-스콜렘 정리와 같은 중요한 성질들이 성립하지 않는다.

정의

문법

2차 논리의 문법은 다음과 같은 기호들로 구성된다.

2차 논리의 변수(영어: variable)들은 다음과 같은 가산 무한 개의 종류(영어: sort)에 속한다.

  • 각 자연수 에 대하여, 항 연산 변수 .
    • 특히, 일 때, 1차 논리의 변수에 해당한다.
    • 사실, 인 연산 변수들은 생략할 수 있다.[1]:63 예를 들어, 와 같이 풀어 쓸 수 있다.
  • 각 자연수 에 대하여, 항 관계 변수 .
    • 특히, 일 때, 1차 논리 변수들의 집합에 해당한다.

변수 밖에도 다음과 같은 논리 기호들이 사용된다. (이들은 1차 논리와 같다.)

  • 전칭 기호 와 존재 기호
  • 등호
  • 명제 논리 기호 (논리곱), (논리합), (부정) 등
  • 괄호 및 반점
  • 주어진 항 연산 항 관계 . 예를 들어, 집합론의 언어는 하나의 2항 관계 를 갖는다. 다른 예로, 순서체의 언어는 2항 연산 , 1항 연산 , 0항 연산 , 그리고 2항 관계 를 갖는다.

2차 논리의 (영어: term)은 다음 문법을 따라야 한다.

  • 항 연산 변수 개의 항 에 대하여, 은 항이다. (편의상 일 때 괄호 를 생략하여 로 쓴다.)
  • 항 연산 개의 항 에 대하여, 은 항이다. (편의상 일 때 괄호 를 생략하여 로 쓴다.)

2차 논리의 논리식(영어: (well formed) formula)은 다음 문법을 따라야 한다.

  • 항 관계 변수 개의 항 에 대하여, 는 논리식이다.
  • 항 관계 개의 항 에 대하여, 는 논리식이다.
  • 두 항 , 에 대하여, 는 논리식이다.
  • 논리식 에 등장하는 항 자유 연산 변수 에 대하여, 는 논리식이다.
  • 논리식 에 등장하는 항 자유 관계 변수 에 대하여, 는 논리식이다.
  • 두 논리식 에 대하여, 에 대하여, 는 논리식이다.

여기서, 논리식 에 등장하는 연산 변수 또는 관계 변수 자유 변수(영어: free variable)라는 것은 가 포함되지 않는 것을 의미한다.

의미론

2차 논리의 의미론은 흔히 2차 논리의 모형으로 주어진다. 이 경우, 모형 가 주어졌을 때, 항 연산 변수는 위의 모든 (외적 관점에서의) 연산 의 값을 가질 수 있으며, 항 관계 변수는 위의 모든 (외적 관점에서의) 관계 의 값을 가질 수 있다. 특히, 1항 관계 변수는 의 모든 부분 집합의 값을 가질 수 있다. 반면, 1차 논리 모형에서는 (집합론의 언어를 사용할 경우, 추이적 모형의 경우) 1차 논리 언어로 정의 가능한 의 부분 집합만을 다룰 수 있다.

2차 논리의 경우, 위와 같은 표준적인 의미론 대신 헹킨 의미론(영어: Henkin semantics)을 사용할 수 있다. 헹킨 의미론에서는 각 변수 종류(영어: sort)가 다른 정의역(영어: domain)을 가질 수 있다. 헹킨 의미론을 사용할 경우 2차 논리는 사실상 1차 논리와 같아진다. 간혹 헹킨 의미론과 구별하기 위하여 전자를 표준 의미론(영어: standard semantics)이라고 하기도 한다.

성질

2차 논리의 증명 체계(영어: proof system)는 (순수한 논리 기호만 포함하는, 즉 변수 및 만을 포함하는) 2차 논리 명제에 대하여 증명을 제시하거나 또는 제시하지 않는 함수이다. 증명 체계가 증명을 제시하는 명제를 증명 가능 명제(영어: provable proposition)라고 한다. 여기서 "증명"이란 (주어진 알파벳에 대한) 일련의 문자열을 뜻한다.

괴델의 불완전성 정리에 따라, 2차 논리의 증명 체계는 다음 세 조건을 동시에 만족시킬 수 없다.

  • (정당성 영어: soundness) 증명 체계가 증명할 수 있는 모든 명제는 2차 논리의 모든 (표준) 모형에서 참이다.
  • (완전성 영어: completeness) 증명 체계는 2차 논리의 모든 (표준) 모형에서 참인 2차 논리 명제를 증명할 수 있다.
  • (유효성 영어: effectiveness) 증명들의 집합은 재귀적 집합이다. 즉, 주어진 문자열이 어떤 명제의 증명인지 여부를 항상 종료하는 알고리즘으로 판별할 수 있다.

반면, 1차 논리의 경우 위 세 조건을 만족시키는 증명 체계가 존재한다 (괴델의 완전성 정리).

2차 논리에서는 또한 콤팩트성 정리뢰벤하임-스콜렘 정리가 성립하지 않는다.

(위 성질들은 2차 논리의 표준 의미론에 대한 것이다. 헹킨 의미론을 사용하면 이는 1차 논리와 같은 성질들을 갖는다.)

역사

고틀로프 프레게는 1879년에 출판된 《개념 표기법》[2]에서 오늘날의 2차 논리와 유사한 논리 체계를 도입하였다.[3]:295 그러나 프레게는 1차 논리와 고차 논리를 구분하지 않았다. 이후 찰스 샌더스 퍼스가 1차 논리와 2차 논리를 구분하였으며, "2차 논리"라는 용어를 도입하였다.[3]:296

헹킨 의미론은 리언 앨버트 헹킨(영어: Leon Albert Henkin, 1921~2006)이 1950년에 도입하였다.[4]

2차 논리에 대하여 윌러드 밴 오먼 콰인은 (이솝 우화에 빗대어) “양의 탈을 쓴 집합론”(영어: set theory in sheep’s clothing)이라고 평하였다.[5]:66, Chapter 5 즉, 2차 논리로는 집합론에 해당하는 여러 개념들(멱집합 등)을 정의할 수 있으며, 또한 적절한 증명 이론을 제시할 수 없으므로, 1차 논리와 달리 2차 ‘논리’는 사실 논리가 아니라는 것이다.

반면, 조지 불로스(영어: George Boolos)[6]를 비롯한 다른 수리철학자들은[1][7][8][9][10] 콰인의 비판에 반대하여 2차 논리를 옹호하였다.

같이 보기

각주

  1. Shapiro, Stewart (2000). 《Foundations without foundationalism: a case for second-order logic》. Oxford Logic Guides (영어) 17. Oxford University Press. doi:10.1093/0198250290.001.0001. ISBN 978-0-19-825029-6. 
  2. Frege, Gottlob (1879). 《Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens》 (독일어). 할레: Verlag von Louis Nebert. 
  3. Putnam, Hilary (1982). “Peirce the logician”. 《Historia Mathematica》 (영어) 9 (3): 290–301. doi:10.1016/0315-0860(82)90123-9. ISSN 0315-0860. 
  4. Henkin, Leon Albert (1950). “Completeness in the theory of types”. 《Journal of Symbolic Logic》 (영어) 15 (2): 81–91. doi:10.2307/2266967. ISSN 0022-4812. JSTOR 2266967. 
  5. Quine, W. V. O. (1986년 6월). 《Philosophy of logic》 (영어) 2판. Harvard University Press. ISBN 978-067466563-7. 
  6. Boolos, George S. (1975년 9월). “On second-order logic”. 《The Journal of Philosophy》 (영어) 72 (16): 509–527. doi:10.2307/2025179. 
  7. Shapiro, Stewart (1999년 2월). “Do not claim too much: second-order logic and first-order logic”. 《Philosophia Mathematica》 (영어) 7 (1): 42–64. doi:10.1093/philmat/7.1.42. ISSN 0031-8019. 
  8. Shapiro, Stewart (2012년 10월). “Higher-order logic or set theory: a false dilemma”. 《Philosophia Mathematica》 (영어) 20 (3): 305–323. doi:10.1093/philmat/nks002. ISSN 0031-8019. 
  9. Väänänen, Jouko (2001). “Second-order logic and foundations of mathematics” (PDF). 《Bulletin of Symbolic Logic》 (영어) 7 (4): 504–520. doi:10.2307/2687796. JSTOR 2687796. 
  10. Bueno, Otávio (2010). “A defense of second-order logic” (PDF). 《Axiomathes》 (영어). doi:10.1007/s10516-010-9101-4. ISSN 1122-1151. 

외부 링크

Read other articles:

Presiden FilipinaPangulo ng PilipinasSegel / Cap Resmi KepresidenanBendera KepresidenanPetahanaBongbong Marcossejak 30 Juni 2022Pemerintah Filipina Sekretariat Presiden FilipinaGelarYang Mulia (His Excellency dalam Bahasa Inggris)JenisKepala Negara Kepala PemerintahanAnggotaKabinet Filipina Dewan Keamanan NasionalKediamanIstana MalacanangKantorManilaDitunjuk olehPemilihan langsungMasa jabatan6 Tahun,tidak dapat dipilih kembaliPendahuluGubernur Jenderal Perdana MenteriPejabat perdanaEmili...

 

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Januari 2023. Arum dalu Klasifikasi ilmiah Kerajaan: Plantae (tanpa takson): Angiosperma (tanpa takson): Eudikotil (tanpa takson): Asteridae Ordo: Solanales Famili: Solanaceae Genus: Cestrum Spesies: C. nocturnum Nama binomial Cestrum nocturnumL. Sinonim Refere...

 

Andrea Costa Informasi pribadiTanggal lahir 1 Februari 1986 (umur 38)Tempat lahir Reggio Emilia, ItaliaTinggi 1,82 m (5 ft 11+1⁄2 in)Posisi bermain BekInformasi klubKlub saat ini ParmaNomor 3Karier junior ReggianaKarier senior*Tahun Tim Tampil (Gol)2003–2004 Reggiana 16 (1)2005–2007 Bologna 43 (0)2008–2011 Reggina 88 (1)2014– Parma 0 (0) * Penampilan dan gol di klub senior hanya dihitung dari liga domestik Andrea Costa (lahir 1 Februari 1986) adalah seorang ...

Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon bantu kami mengembangkan artikel ini dengan cara menambahkan rujukan ke sumber tepercaya. Pernyataan tak bersumber bisa saja dipertentangkan dan dihapus.Cari sumber: Romulan – berita · surat kabar · buku · cendekiawan · JSTOR (23 Juli 2010) Romulan dalam TNG episode Balance of Terror Romulan adalah alien dalam dunia fiksional Star Trek. Romulan pertama kali muncul di seri...

 

تاريخ الأردنمعلومات عامةالمنطقة الأردن التأثيراتأحد جوانب الأردن تعديل - تعديل مصدري - تعديل ويكي بيانات جزء من سلسلة مقالات حولتاريخ الأردن ما قبل التاريخ عين غزال الغسولية التاريخ القديم شرق الأردن في العهد القديم عمون مؤاب إدوم الفترة الكلاسيكية الأنباط المقاطعة العر...

 

LGBTQ+ Pride Parade in Phoenix, Arizona For the defunct Major Indoor Soccer League team, see Phoenix Inferno. Marchers at 2017's Phoenix Pride Phoenix Pride (formerly known as Phoenix Pride March & Rally,[1] Desert Pride,[2] Arizona Central Pride,[2] and Phoenix Pride Festival[2]) is a parade and festival held each year in Phoenix, Arizona to celebrate the lesbian, gay, bisexual, and transgender (LGBT) people and their allies. Unlike other pride parades in ...

Gabriel Heinze Informasi pribadiNama lengkap Gabriel Iván Heinze[1][2]Tanggal lahir 19 April 1978 (umur 45)Tempat lahir Crespo, ArgentinaTinggi 1,78 m (5 ft 10 in)Posisi bermain BekInformasi klubKlub saat ini pensiunKarier senior*Tahun Tim Tampil (Gol)1996–1997 Newell's Old Boys 8 (0)1997–2001 Valladolid 54 (1)1998–1999 → Sporting CP (pinjaman) 5 (1)2001–2004 Paris Saint-Germain 99 (4)2004–2007 Manchester United 52 (1)2007–2009 Real Madrid 4...

 

French actress Marina HandsMarina Hands at the 2012 Deauville American Film FestivalBorn (1975-01-10) 10 January 1975 (age 49)Paris, FranceAlma materLondon Academy of Music and Dramatic ArtOccupationActressYears active1996–presentParent(s)Terry HandsLudmila Mikaël Marina Hands' voice from the BBC programme, The Film Programme, 17 August 2007[1] Marina Hands (born 10 January 1975) is a French stage and film actress. Hands is the daughter of British director Terry Hand...

 

Disambiguazione – Se stai cercando la parrocchia di Madeira, vedi Sao Vicente (Portogallo). Questa voce o sezione sull'argomento centri abitati del Portogallo non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Questa voce sugli argomenti centri abitati del Portogallo e Azzorre è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di W...

Questa voce sull'argomento stagioni delle società calcistiche italiane è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Voce principale: Taranto Football Club 1927. Unione Sportiva ArsenaltarantoStagione 1951-1952Sport calcio Squadra Arsenaltaranto Allenatore Bruno Arcari (1ª-13ª) Raffaele Costantino (14ª-34ª) Presidente Luigi Santilio Serie C2º posto nel girone D. Maggiori presenzeCampionato...

 

Logo Android TV Sebuah Android TV Android TV adalah sebuah versi sistem operasi Android Google yang telah dikonfigurasikan secara khusus untuk TV. Berbeda dengan sistem android seluler dengan layar penuh aplikasi atau widget seperti browser, cuaca, atau saham, layar awal TV Android lebih fokus untuk membantu dalam menemukan berbagai konten yang dapat Anda nikmati di TV.[1] Android TV sekarang juga dilengkapi dengan Google Assistant bawaan. Untuk mengaktifkan fitur ini yaitu dengan men...

 

Shannen Dohertydi dalam acara pemutaran perdana 90210, Malibu, California - 23 Agustus 2008PekerjaanAktris, SutradaraSuami/istriAshley Hamilton (1993 - 1994)Rick Salomon (2002 - 2003)Kurt Iswarienko (2011 - sekarang) Shannen Maria Doherty (lahir 12 April 1971) ialah seorang aktris dan juga seorang sutradara.[1] Shannen terkenal lewat perannya sebagai Brenda di serial Beverly Hills 90210,[2] Prue di serial Charmed,[3] dan juga film Heathers sebagai Heather.[4]&...

イスラームにおける結婚(イスラームにおけるけっこん)とは、二者の間で行われる法的な契約である。新郎新婦は自身の自由な意思で結婚に同意する。口頭または紙面での規則に従った拘束的な契約は、イスラームの結婚で不可欠だと考えられており、新郎と新婦の権利と責任の概要を示している[1]。イスラームにおける離婚は様々な形をとることができ、個�...

 

Kim Hong-doNama KoreaHangul김홍도 Hanja金弘道 Alih AksaraGim Hong-doMcCune–ReischauerKim Hongdo Kim Hong-do, (pseudonim: Danwon) (tanggal lahir tak diketahui, tahun 1745–meninggal tahun 1806), adalah seorang pelukis dari Dinasti Joseon.[1][2] Lukisan-lukisan karya Kim Hong-do menampilkan aktivitas dan kehidupan masyarakat Korea secara nyata pada masa akhir Dinasti Joseon.[1] Ia dianggap sebagai salah satu dari empat pelukis besar Korea.[3] Informasi n...

 

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)出典検索?: コルク – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL(2017年4月) コルクを打ち抜いて作った瓶の栓 コルク(木栓、�...

Thai Indians Ethnic group Thai IndiansIndian diaspora dressed in sari dancing at Dipavali Bangkok 2022Total populationIndian nationals65,000People of Indian descent465,000Regions with significant populationsBangkok · Pattaya · Chiang Mai · PhuketLanguagesThai · Tamil • English · Gujarati · Urdu · PunjabiReligionHinduism · Christianity · Buddhism ...

 

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2022. Gedung Stasiun Kereta Api Tanah Melayu adalah gedung serbaguna yang digunakan untuk keperluan perkeretaapian di Tanah Melayu. Fungsi gedung terbagi menjadi gedung stasiun, hotel dan kantor pejabat kepengurusan. Gedung ini merupakan gedung stasiun keret...

 

Mountain range in Colorado, United States Anthracite RangeAnthracite RangeHighest pointPeakAnthracite Range High PointElevation12,394 ft (3,778 m)[1][2]Prominence2,105 ft (642 m)[2]Coordinates38°48′52″N 107°08′40″W / 38.814526°N 107.144505°W / 38.814526; -107.144505[2]GeographyAnthracite Range CountryUnited StatesStateColoradoCountyGunnisonParent rangeWest Elk Mountains, Rocky Mountains The Anthracite...

Bangladeshi constitutional history This article is part of a series on thePolitics of the People's Republic of Bangladesh Constitution Amendments Law of Bangladesh Bangladesh Code Penal Code Human rights Article 70 Judicial review Government President: Mohammed Shahabuddin Prime Minister: Sheikh Hasina Cabinet: Hasina V Taxation Agencies Civil Service Local governments Parliament Speaker: Shirin Sharmin Chaudhury Leader of the House: Sheikh Hasina Leader of the Opposition: GM Quader Judiciary...

 

تحتاج هذه المقالة كاملةً أو أجزاءً منها لإعادة الكتابة حسبَ أسلوب ويكيبيديا. فضلًا، ساهم بإعادة كتابتها لتتوافق معه.تحوي هذه المقالة أو هذا القسم ترجمة آلية. فضلًا، ساهم في تدقيقها وتحسينها أو إزالتها لأنها تخالف سياسات ويكيبيديا. (نقاش) هذه المقالة بحاجة لصندوق معلومات. ف...