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 us 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. sylgt
    14. sylg
    15. alrimih
    16. hbxfrbi
    17. alex
    18. exnal
    19. 2nalexn
    20. 2exnaln
    21. 2nexaln
    22. alimex
    23. aleximi
    24. alexbii
    25. exim
    26. eximi
    27. 2eximi
    28. eximii
    29. exa1
    30. 19.38
    31. 19.38a
    32. 19.38b
    33. imnang
    34. alinexa
    35. exnalimn
    36. alexn
    37. 2exnexn
    38. exbi
    39. exbii
    40. 2exbii
    41. 3exbii
    42. nfbiit
    43. nfbii
    44. nfxfr
    45. nfxfrd
    46. nfnbi
    47. nfnbiOLD
    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.36imvOLD
    38. 19.36iv
    39. 19.37imv
    40. 19.37iv
    41. 19.41v
    42. 19.41vv
    43. 19.41vvv
    44. 19.41vvvv
    45. 19.42v
    46. exdistr
    47. exdistrv
    48. 4exdistrv
    49. 19.42vv
    50. exdistr2
    51. 19.42vvv
    52. 3exdistr
    53. 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. alcomiw
    37. alcomiwOLD
    38. hbn1fw
    39. hbn1w
    40. hba1w
    41. hbe1w
    42. hbalw
    43. spaev
    44. cbvaev
    45. aevlem0
    46. aevlem
    47. aeveq
    48. aev
    49. aev2
    50. hbaev
    51. naev
    52. naev2
    53. 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. sbrimvlem
    30. sbrimvw
    31. sbievw
    32. sbiedvw
    33. 2sbievw
    34. sbcom3vv
    35. sbievw2
    36. sbco2vv
    37. equsb3
    38. equsb3r
    39. equsb1v
    40. nsb
    41. 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. elsb3
    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. elsb4
    8. elequ2g
  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