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. nfnbiOLD
    49. nfnt
    50. nfn
    51. nfnd
    52. exanali
    53. 2exanali
    54. exancom
    55. exan
    56. alrimdh
    57. eximdh
    58. nexdh
    59. albidh
    60. exbidh
    61. exsimpl
    62. exsimpr
    63. 19.26
    64. 19.26-2
    65. 19.26-3an
    66. 19.29
    67. 19.29r
    68. 19.29r2
    69. 19.29x
    70. 19.35
    71. 19.35i
    72. 19.35ri
    73. 19.25
    74. 19.30
    75. 19.43
    76. 19.43OLD
    77. 19.33
    78. 19.33b
    79. 19.40
    80. 19.40-2
    81. 19.40b
    82. albiim
    83. 2albiim
    84. exintrbi
    85. exintr
    86. alsyl
    87. nfimd
    88. nfimt
    89. nfim
    90. nfand
    91. nf3and
    92. nfan
    93. nfnan
    94. nf3an
    95. nfbid
    96. nfbi
    97. nfor
    98. nf3or
    99. 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. alcomw
    38. hbn1fw
    39. hbn1w
    40. hba1w
    41. hbe1w
    42. hbalw
    43. 19.8aw
    44. exexw
    45. spaev
    46. cbvaev
    47. aevlem0
    48. aevlem
    49. aeveq
    50. aev
    51. aev2
    52. hbaev
    53. naev
    54. naev2
    55. 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. sbievw
    31. sbiedvw
    32. 2sbievw
    33. sbcom3vv
    34. sbievw2
    35. sbco2vv
    36. equsb3
    37. equsb3r
    38. equsb1v
    39. nsb
    40. 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
  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