# Propositional logic without set theory

• Apr 5th 2010, 07:08 AM
farstar
Propositional logic without set theory
Hello, I am new in this forum.

I have a question regarding propositional logic: after having studied physics, now in my free time I am coming back a second time and I am trying to study mathematics properly, as a pleasure.

I want to start with logic, study well the "language of mathematics", and then proceed towards set theory and then to study properly analysis and other subjects of my interest (understanding quantum field theory correctly, at the mathematical level of rigor, is my target).

But I find a surprising problem: in all the books I am checking of logic (mathematical logic) they use the concept of a set beforehand, even though logic has to be the basis of a language for all mathematics, where even set theory has to be based on!

Of course, I understand that it is not the same axiomatic set theory than naive set theory. And talking about sets is not saying really anything, more than "the grouping of a few concepts", but it bothers me.

Even some books use concepts like "smallest set" without defining it.

And I am talking about "classic" books, like Mendelson, Hinman, Hedman or Shoenfield.

Could anybody give me a suggestion of a book on propositional logic that does not use set theory at all, but it gives a full preparation for axiomatic set theory? Ideally, I would like a modern book, because I like modern notation (I do not like old books, with cumbersome notations ... I know this should not be essential for a correct understanding, but it is the way I feel).

My plan is to study afterwards the book of Jech on Set Theory.
• Apr 5th 2010, 07:37 AM
MoeBlee
I think it's going to be hard to find a book that explicates mathematical logic (including propositional logic) without using the notion of a set.

At what level do you want a book on logic? Do you want one that mainly shows how to work IN the propositional (and then predicate) calculus, or do you want one that shows the major theorems ABOUT the propositional (and then predicate) calculus?

For working in the propositional (and then predicate) calculus, I highly recommend 'Logic: Techniques Of Formal Reasoning' by Kalish, Montague, and Mar. I have found this to be the best combination of rigor and common sense in a practical system for propositional (and then predicate) logic.

My advice would be first to learn a book such as I mentioned, using a common sense notion of 'set'. Then you can apply the predicate calculus to study set theory itself as a formal theory. Then you can use that formal set theory to go back and (this time) rigorously study mathematical logic within formal set theory, so that you you will be studying the formation of (and theorems about) such logic systems as in the Kalish/Montague/Mar as actual formal set theoretic results.

So you might have a plan something along these lines:

'Logic: Techniques Of Formal Reasoning' - Kalish, Montague, Mar
(This will give you all you need to work in the predicate calculus.)

'Elements Of Set Theory' - Enderton
and/or
'Axiomatic Set Theory' - Suppes
(This will give you the basic formal set theory you need to study mathematical logic within formal set theory.)

'A Mathematical Introduction To Logic' - Enderton
and/or
Hinman, Monk, etc.
(This will present mathematical logic in fairly informal set theory; but with the knowledge you'll have from previous study at this point, you'll see how such informal set theory can be formalized.)

'Set Theory' - Jech.
(As you mention that this book is for later, I agree. I wouldn't use this as a first book in set theory, since it's pretty advanced. Save it for after you've already learned basic formal set theory and mathematical logic.)
• Apr 5th 2010, 08:00 AM
farstar
Quote:

Originally Posted by MoeBlee
I think it's going to be hard to find a book that explicates mathematical logic (including propositional logic) without using the notion of a set.

At what level do you want a book on logic? Do you want one that mainly shows how to work IN the propositional (and then predicate) calculus, or do you want one that shows the major theorems ABOUT the propositional (and then predicate) calculus?

For working in the propositional (and then predicate) calculus, I highly recommend 'Logic: Techniques Of Formal Reasoning' by Kalish, Montague, and Mar. I have found this to be the best combination of rigor and common sense in a practical system for propositional (and then predicate) logic.

My advice would be first to learn a book such as I mentioned, using a common sense notion of 'set'. Then you can apply the predicate calculus to study set theory itself as a formal theory. Then you can use that formal set theory to go back and (this time) rigorously study mathematical logic within formal set theory, so that you you will be studying the formation of (and theorems about) such logic systems as in the Kalish/Montague/Mar as actual formal set theoretic results.

So you might have a plan something along these lines:

'Logic: Techniques Of Formal Reasoning' - Kalish, Montague, Mar
(This will give you all you need to work in the predicate calculus.)

'Elements Of Set Theory' - Enderton
and/or
'Axiomatic Set Theory' - Suppes
(This will give you the basic formal set theory you need to study mathematical logic within formal set theory.)

'A Mathematical Introduction To Logic' - Enderton
and/or
Hinman, Monk, etc.
(This will present mathematical logic in fairly informal set theory; but with the knowledge you'll have from previous study at this point, you'll see how such informal set theory can be formalized.)

'Set Theory' - Jech.
(As you mention that this book is for later, I agree. I wouldn't use this as a first book in set theory, since it's pretty advanced. Save it for after you've already learned basic formal set theory and mathematical logic.)

It will not be my first contact with set theory, though. I have already studied previously set theory, and after reading in diagonal Set Theory of Jech, I feel pretty confident I understand (or may understand with some effort) the first chapters of the book. Another thing are the final chapters, much more specialized.

I am grateful for your outline of study, but I really do not want to follow the path:

a bit of logic -> a bit of set theory -> rigorous logic (propositional and predicate) with naive set theory language -> rigorous set theory

I want to do:

rigorous logic without naive set theory at all (??? which book, this is my question) -> rigorous set theory (Jech)

I do not find any sense in having this kind of recurrence or circular arguments, when I am studying really the basis of mathematics. I am sure it can be done properly.
• Apr 5th 2010, 08:39 AM
MoeBlee
But my point is that I know of on one who can tell you how to break the circle.

You have to start first with someting that is informal. Either start with informal logic to study formal set theory or start with informal set theory to study formal logic.

The plain fact of the matter is that mathematical logic presupposes notions and principles about sets, while, circularly, forrmal set theory is in a particular logic (first order predicate calculus).

So what I am saying is since you have to start with something informal first, it makes sense to first informally learn the predicate calculus (by using some informal set theory), then formalize the set theory in the predicate calculus you learned, then go back to formalize the predicate calculus in the formal logic you learned.

There is just not a way to avoid either the circularity I just suggested or some other circularity.

And I think you'd be spinning your wheels trying to find a book that ADEQUATELY explicates logic without certain notions and principles about sets.

This subject of circularity is something I've thought about for a long time in a pedagogical sense.

Also, you described my plan as:

"a bit of logic -> a bit of set theory -> rigorous logic (propositional and predicate) with naive set theory language -> rigorous set theory"

That is not what I've suggested. What I've suggested:

a formalized predicate calculus (studied from the point of view of informal set theory) -> formal set theory (studied from the point of view of the previously formalized predicate calculus) -> formal mathematical logic, including formation of the formalized predicate calculus (studied from the point of view of formal set theory).

Thus, everything is eventually formalized and all results formally proven (both the logic and the set theory).

But I just don't know what book would adequately explicate logic without some notions and principles about sets (even if the book didn't mention sets, you'll find yourself still using notions and principles about sets in order to make the explanations in the book more rigorous).

In any case, a book such as 'Logic: Techniques Of Formal Reasoning' does an excellent job of presenting formal logic while presupposing precious little about sets. I don't think you'll find another GOOD logic book that presupposes as little about sets as does 'Logic: Techniques Of Formal Reasoning'.
• Apr 5th 2010, 09:18 AM
farstar
Quote:

Originally Posted by MoeBlee
But my point is that I know of on one who can tell you how to break the circle.

You have to start first with someting that is informal. Either start with informal logic to study formal set theory or start with informal set theory to study formal logic.

The plain fact of the matter is that mathematical logic presupposes notions and principles about sets, while, circularly, forrmal set theory is in a particular logic (first order predicate calculus).

So what I am saying is since you have to start with something informal first, it makes sense to first informally learn the predicate calculus (by using some informal set theory), then formalize the set theory in the predicate calculus you learned, then go back to formalize the predicate calculus in the formal logic you learned.

There is just not a way to avoid either the circularity I just suggested or some other circularity.

And I think you'd be spinning your wheels trying to find a book that ADEQUATELY explicates logic without certain notions and principles about sets.

This subject of circularity is something I've thought about for a long time in a pedagogical sense.

Also, you described my plan as:

"a bit of logic -> a bit of set theory -> rigorous logic (propositional and predicate) with naive set theory language -> rigorous set theory"

That is not what I've suggested. What I've suggested:

a formalized predicate calculus (studied from the point of view of informal set theory) -> formal set theory (studied from the point of view of the previously formalized predicate calculus) -> formal mathematical logic, including formation of the formalized predicate calculus (studied from the point of view of formal set theory).

Thus, everything is eventually formalized and all results formally proven (both the logic and the set theory).

But I just don't know what book would adequately explicate logic without some notions and principles about sets (even if the book didn't mention sets, you'll find yourself still using notions and principles about sets in order to make the explanations in the book more rigorous).

In any case, a book such as 'Logic: Techniques Of Formal Reasoning' does an excellent job of presenting formal logic while presupposing precious little about sets. I don't think you'll find another GOOD logic book that presupposes as little about sets as does 'Logic: Techniques Of Formal Reasoning'.

But I just cannot believe that mathematicians, that tend to be so precise with their language, accept to have this obvious circularity. I mean, first it is the language, and then set theory and everything else.

My path would be: logic without sets, enough to be able to write the axioms of ZFC (or any others); then develop axiomatic set theory; then reformulate the logic you have used initially with set theory; then finish logic with the power of sets, especially the most challenging parts (Gödel theorems, ...).

But I cannot understand one uses naive sets to define the basis of all mathematics.

I understand with set theory logic is simpler to explain, but come on, this circularity is so unaesthetic ...

I will try with what you suggest, but I am sure there are many mathematicians that have thought the same as I do, and there are shortcuts.

Thank you.
• Apr 5th 2010, 09:33 AM
MoeBlee
Quote:

Originally Posted by farstar
But I just cannot believe that mathematicians, that tend to be so precise with their language, accept to have this obvious circularity.

It's discussed in various places in the literature of philosophy of mathematics (I'd have to dig around to come up with an example though). It's famous that we have to start with SOME informal notions.

Formal logic is about symbols, formulas, sentences, proofs, theories, truth evaluations, validity, etc.

For example, what is a formula? It's a certain kind of string of symbols. Formally, what's a string? It's a finite sequence. Formally, what's a finite sequence. It's a function on a natural number. Formally, what's a function (let alone, formally, what's a natural number?)? A function is a many-one relation. Formally, what's a relation? A relation is a set of ordered pairs. Bam, there we are: SET.

What's an argument? It's a set of formulas (called the premises) and a formula (called the conclusion). Bam, there we are: SET.

How do we express the basic theorems about formal logic, such theorems as: unique readability, compactness, completeness, soundness, etc.? We express them through notions and principles about sets.

How do we even express the notion of formulas of formal languages? Through the notion of recursive (aka 'inductive') definitions. And how do we explicate recursive definition? Through notions and principles about sets.

You might want to consider that you have a presupposition about the subject that causes you to demand something that you might not even find, viz. a formalization of logic that doesn't involve sets. Sure, maybe you can find such a thing, but then if it doesn't involve sets it will have to involve some other basic notions and principles that are just as (if not more) in need itself of explication. The regress has to stop somewhere if it is not to be an infinite regress. You will find that overwhelmingly it is the case in mathematical logic that the regress stops with certain basic notions and principles about sets. Ask any logician.
• Apr 5th 2010, 09:42 AM
farstar

But I just find unaesthetic to use some concepts I will define rigorously later with the language I am defining right now.

Maybe it is just pedantic, but I would prefer a book telling me that a truth table is just "something" that assigns the value T or F, instead of a function with values in the set {T,F}.

I understand it is the same, and possibly the second explanation is simpler and more precise ... but I just cannot stand it.

Worse still, when some books use concepts like "the smallest set" or other semi-advanced concepts of set theory.

I believe it is pedantic what I am asking. I am sure it should not be very difficult just to translate those ideas from naive set theory into a language that (apparently) does not use set theory. But my sense of aestheticism does not allow me to accept it.

And this second time, I want to do it 100% right, whatever the cost.
• Apr 5th 2010, 10:08 AM
MoeBlee
Yes, I agree it should be done correctly, in pristine rigor.

But just look at my examples. You can see, notions and principles about sets are just so basic that it would be just a lot of rigmarole to try to formulate logic without notions and principles about sets.

So, since a few years ago I too wanted to do the subject correctly, with pristine rigor, I took the route I mentioned. In doing so, I have seen how to formalize in perfect rigor both set theory and mathematical logic. So I needed a formal logic to study set theory. But to formalize such a logic, I need some informal notions and principles to start with, and those are, virtually universally (and for good reason) taken by mathematicians and logicians to be basic notions and principles about sets.

Take just one example I gave: An argument. It's a set of premises and a conclusion. Why quibble about the word 'set' there? Sure, you can say it's a collection of premises, or a flock of premises, or a gaggle of premises, or whatever you like. But it boils down to the same notion: Set.

Now, as to your example about a truth table, sure, we can be fairly informal and call it an "assignment" or "table" or whatever. But I highly doubt that you'll find a GOOD explanation of predicate logic that avoids ALL notions and principles about sets. In that regard, I recommended a particular book I think you will find is as LITTLE invested in sets as can be found among good books on the subject of predicate logic.

/

By the way, though you might already know, the expression 'S is the smallest set having property such and such' means:

If any set X has the property such and such, then S is a subset of X.

Now, this is used, for example, in defining 'formula of the language'. The formulas of the language are precisely those that are members of the smallest set S that is closed under the formula making operations. I venture that any other way you express this will come out equivalent to what I just said. So why quibble about it? They're sets. Sets of symbols, etc. And sets of symbols closed under formula making operations. And a least such set of symbols closed under the formula making operations.