Metamath Proof Explorer


Table of Contents - 1.4. Predicate calculus with equality: Tarski's system S2 (1 rule, 6 schemes)

Here we extend the language of wffs with predicate calculus, which allows to talk about individual objects in a domain of discourse (which for us will be the universe of all sets, so we call them "setvar variables") and make true/false statements about predicates, which are relationships between objects, such as whether or not two objects are equal. In addition, we introduce universal quantification ("for all", e.g., ax-4) in order to make statements about whether a wff holds for every object in the domain of discourse. Later we introduce existential quantification ("there exists", df-ex) which is defined in terms of universal quantification.

Our axioms are really axiom schemes, and our wff and setvar variables are metavariables ranging over expressions in an underlying "object language". This is explained here: mmset.html#axiomnote.

Our axiom system starts with the predicate calculus axiom schemes system S2 of Tarski defined in his 1965 paper, "A Simplified Formalization of Predicate Logic with Identity" [Tarski]. System S2 is defined in the last paragraph on p. 77, and repeated on p. 81 of [KalishMontague]. We do not include scheme B5 (our sp) of system S2 since [KalishMontague] shows it to be logically redundant (Lemma 9, p. 87, which we prove as Theorem spw below).

Theorem spw can be used to prove any instance of sp having mutually distinct setvar variables and no wff metavariables. However, it seems that sp in its general form cannot be derived from only Tarski's schemes. We do not include B5 i.e. sp as part of what we call "Tarski's system" because we want it to be the smallest set of axioms that is logically complete with no redundancies. We later prove sp as Theorem axc5 using the auxiliary axiom schemes that make our system metalogically complete.

Our version of Tarski's system S2 consists of propositional calculus (ax-mp, ax-1, ax-2, ax-3) plus ax-gen, ax-4, ax-5, ax-6, ax-7, ax-8, and ax-9. The last three are equality axioms that represent three sub-schemes of Tarski's scheme B8. Due to its side-condition ("where is an atomic formula and is obtained by replacing an occurrence of the variable by the variable "), we cannot represent his B8 directly without greatly complicating our scheme language, but the simpler schemes ax-7, ax-8, and ax-9 are sufficient for set theory and much easier to work with.

Tarski's system is exactly equivalent to the traditional axiom system in most logic textbooks but has the advantage of being easy to manipulate with a computer program, and its simpler metalogic (with no built-in notions of "free variable" and "proper substitution") is arguably easier for a non-logician human to follow step by step in a proof (where "follow" means being able to identify the substitutions that were made, without necessarily a higher-level understanding). In particular, it is logically complete in that it can derive all possible object-language theorems of predicate calculus with equality, i.e., the same theorems as the traditional system can derive.

However, for efficiency (and indeed a key feature that makes Metamath successful), our system is designed to derive reusable theorem schemes (rather than object-language theorems) from other schemes. From this "metalogical" point of view, Tarski's S2 is not complete. For example, we cannot derive scheme sp, even though (using spw) we can derive all instances of it that do not involve wff metavariables or bundled setvar variables. (Two setvar variables are "bundled" if they can be substituted with the same setvar variable, i.e., do not have a "$d" disjoint variable condition.) Later we will introduce auxiliary axiom schemes ax-10, ax-11, ax-12, and ax-13 that are metatheorems of Tarski's system (i.e. are logically redundant) but which give our system the property of "scheme completeness", allowing us to prove directly (instead of, say, by induction on formula length) all possible schemes that can be expressed in our language.

  1. Universal quantifier (continued); define "exists" and "not free"
    1. Existential quantifier
    2. Nonfreeness predicate
  2. Rule scheme ax-gen (Generalization)
    1. ax-gen
    2. gen2
    3. mpg
    4. mpgbi
    5. mpgbir
    6. nex
    7. nfth
    8. nfnth
    9. hbth
    10. nftru
    11. nffal
    12. sptruw
    13. altru
    14. alfal
  3. Axiom scheme ax-4 (Quantified Implication)
    1. ax-4
    2. alim
    3. alimi
    4. 2alimi
    5. ala1
    6. al2im
    7. al2imi
    8. alanimi
    9. alimdh
    10. albi
    11. albii
    12. 2albii
    13. 3albii
    14. sylgt
    15. sylg
    16. alrimih
    17. hbxfrbi
    18. alex
    19. exnal
    20. 2nalexn
    21. 2exnaln
    22. 2nexaln
    23. alimex
    24. aleximi
    25. alexbii
    26. exim
    27. eximi
    28. 2eximi
    29. eximii
    30. exa1
    31. 19.38
    32. 19.38a
    33. 19.38b
    34. imnang
    35. alinexa
    36. exnalimn
    37. alexn
    38. 2exnexn
    39. exbi
    40. exbii
    41. 2exbii
    42. 3exbii
    43. nfbiit
    44. nfbii
    45. nfxfr
    46. nfxfrd
    47. nfnbi
    48. nfnt
    49. nfn
    50. nfnd
    51. exanali
    52. 2exanali
    53. exancom
    54. exan
    55. alrimdh
    56. eximdh
    57. nexdh
    58. albidh
    59. exbidh
    60. exsimpl
    61. exsimpr
    62. 19.26
    63. 19.26-2
    64. 19.26-3an
    65. 19.29
    66. 19.29r
    67. 19.29r2
    68. 19.29x
    69. 19.35
    70. 19.35i
    71. 19.35ri
    72. 19.25
    73. 19.30
    74. 19.43
    75. 19.43OLD
    76. 19.33
    77. 19.33b
    78. 19.40
    79. 19.40-2
    80. 19.40b
    81. albiim
    82. 2albiim
    83. exintrbi
    84. exintr
    85. alsyl
    86. nfimd
    87. nfimt
    88. nfim
    89. nfand
    90. nf3and
    91. nfan
    92. nfnan
    93. nf3an
    94. nfbid
    95. nfbi
    96. nfor
    97. nf3or
    98. The empty domain of discourse
  4. Axiom scheme ax-5 (Distinctness) - first use of $d
    1. ax-5
    2. ax5d
    3. ax5e
    4. ax5ea
    5. nfv
    6. nfvd
    7. alimdv
    8. eximdv
    9. 2alimdv
    10. 2eximdv
    11. albidv
    12. exbidv
    13. nfbidv
    14. 2albidv
    15. 2exbidv
    16. 3exbidv
    17. 4exbidv
    18. alrimiv
    19. alrimivv
    20. alrimdv
    21. exlimiv
    22. exlimiiv
    23. exlimivv
    24. exlimdv
    25. exlimdvv
    26. exlimddv
    27. nexdv
    28. 2ax5
    29. stdpc5v
    30. 19.21v
    31. 19.32v
    32. 19.31v
    33. 19.23v
    34. 19.23vv
    35. pm11.53v
    36. 19.36imv
    37. 19.36iv
    38. 19.37imv
    39. 19.37iv
    40. 19.41v
    41. 19.41vv
    42. 19.41vvv
    43. 19.41vvvv
    44. 19.42v
    45. exdistr
    46. exdistrv
    47. 4exdistrv
    48. 19.42vv
    49. exdistr2
    50. 19.42vvv
    51. 3exdistr
    52. 4exdistr
  5. Equality predicate (continued)
    1. weq
    2. speimfw
    3. speimfwALT
    4. spimfw
    5. ax12i
  6. Axiom scheme ax-6 (Existence)
    1. ax-6
    2. ax6v
    3. ax6ev
    4. spimw
    5. spimew
    6. speiv
    7. speivw
    8. exgen
    9. extru
    10. 19.2
    11. 19.2d
    12. 19.8w
    13. spnfw
    14. spvw
    15. 19.3v
    16. 19.8v
    17. 19.9v
    18. 19.39
    19. 19.24
    20. 19.34
    21. 19.36v
    22. 19.12vvv
    23. 19.27v
    24. 19.28v
    25. 19.37v
    26. 19.44v
    27. 19.45v
    28. spimevw
    29. spimvw
    30. spvv
    31. spfalw
    32. chvarvv
    33. equs4v
    34. alequexv
    35. exsbim
    36. equsv
    37. equsalvw
    38. equsexvw
    39. cbvaliw
    40. cbvalivw
  7. Axiom scheme ax-7 (Equality)
    1. ax-7
    2. ax7v
    3. ax7v1
    4. ax7v2
    5. equid
    6. nfequid
    7. equcomiv
    8. ax6evr
    9. ax7
    10. equcomi
    11. equcom
    12. equcomd
    13. equcoms
    14. equtr
    15. equtrr
    16. equeuclr
    17. equeucl
    18. equequ1
    19. equequ2
    20. equtr2
    21. stdpc6
    22. equvinv
    23. equvinva
    24. equvelv
    25. ax13b
    26. spfw
    27. spw
    28. cbvalw
    29. cbvalvw
    30. cbvexvw
    31. cbvaldvaw
    32. cbvexdvaw
    33. cbval2vw
    34. cbvex2vw
    35. cbvex4vw
    36. alcomimw
    37. excomimw
    38. alcomw
    39. hbn1fw
    40. hbn1w
    41. hba1w
    42. hbe1w
    43. hbalw
    44. 19.8aw
    45. exexw
    46. spaev
    47. cbvaev
    48. aevlem0
    49. aevlem
    50. aeveq
    51. aev
    52. aev2
    53. hbaev
    54. naev
    55. naev2
    56. hbnaev
  8. Define proper substitution
    1. sbjust
    2. wsb
    3. df-sb
    4. sbt
    5. sbtru
    6. stdpc4
    7. sbtALT
    8. 2stdpc4
    9. sbi1
    10. spsbim
    11. spsbbi
    12. sbimi
    13. sb2imi
    14. sbbii
    15. 2sbbii
    16. sbimdv
    17. sbbidv
    18. sban
    19. sb3an
    20. spsbe
    21. sbequ
    22. sbequi
    23. sb6
    24. 2sb6
    25. sb1v
    26. sbv
    27. sbcom4
    28. pm11.07
    29. sbrimvw
    30. sbbiiev
    31. sbievw
    32. sbievwOLD
    33. sbiedvw
    34. 2sbievw
    35. sbcom3vv
    36. sbievw2
    37. sbco2vv
    38. cbvsbv
    39. sbco4lem
    40. sbco4
    41. equsb3
    42. equsb3r
    43. equsb1v
    44. nsb
    45. sbn1
  9. Membership predicate
    1. wcel
    2. wel
  10. Axiom scheme ax-8 (Left Equality for Binary Predicate)
    1. ax-8
    2. ax8v
    3. ax8v1
    4. ax8v2
    5. ax8
    6. elequ1
    7. elsb1
    8. cleljust
  11. Axiom scheme ax-9 (Right Equality for Binary Predicate)
    1. ax-9
    2. ax9v
    3. ax9v1
    4. ax9v2
    5. ax9
    6. elequ2
    7. elequ2g
    8. elsb2
    9. elequ12
    10. ru0
  12. Logical redundancy of ax-10 , ax-11 , ax-12 , ax-13
    1. ax6dgen
    2. ax10w
    3. ax11w
    4. ax11dgen
    5. ax12wlem
    6. ax12w
    7. ax12dgen
    8. ax12wdemo
    9. ax13w
    10. ax13dgen1
    11. ax13dgen2
    12. ax13dgen3
    13. ax13dgen4