First-order logic without sets?

[jordi]

I have been trying to study first-order logic to have a sound basis on mathematical language. The main target is to have a clear path: I start with first-order logic (the language), then I go and study set theory, which is in fact a series of axioms (ie, a series of statements of the language), and then, from set theory, the whole mathematics can be deduced from that.

However, I have found a problem I did not expect to find. When I read set theory books, they mostly do not state clearly the laws of the first-order logic (or they do it in a too simple way; but it is OK, they are books on set theory, not on logic).

But I was expecting that when I started reading books on first-order logic, these books would be only about logic and the language. However, to my surprise all books I have been checking up to now resort to the concept of sets (in an intuitive way, they do not define sets most of the time).

I even have read a comment on that in a pdf I have found in the web:

A Problem Course in
Mathematical Logic
Version 1.5
Volume I
Propositional and
First-Order Logic
Stefan Bilaniuk

where it states in the Appendix A, devoted to Set theory:

"The properly sceptical reader will note that setting up propositional
or first-order logic formally requires that we have some set theory in
hand, but formalizing set theory itself requires one to have first-order
logic."

So, it is not only my impression.

Is there some good book that studies first-order logic without resorting to set theory or any other more advanced mathematics, such that it can be used as the foundations to study set theory on a second step?

 

[jambaugh]

I suggest you start with references for "symbolic logic" which tends to de-emphasize set theory. (Although Venn diagrams are still used to model systems of logical propositions.)

You might also consider the distinction between sets and classes. Ultimately class theory is the same as first order logic since classes are defined not by elements but by the propositions which select instances. Thus it would seem to me one could define classes and first order logic together without being either circular or contradictory.

As to a good reference I can't help you there.

 

[poutsos.A]

I have been trying to study first-order logic to have a sound basis on mathematical language. The main target is to have a clear path: I start with first-order logic (the language), then I go and study set theory, which is in fact a series of axioms (ie, a series of statements of the language), and then, from set theory, the whole mathematics can be deduced from that.

However, I have found a problem I did not expect to find. When I read set theory books, they mostly do not state clearly the laws of the first-order logic (or they do it in a too simple way; but it is OK, they are books on set theory, not on logic).

But I was expecting that when I started reading books on first-order logic, these books would be only about logic and the language. However, to my surprise all books I have been checking up to now resort to the concept of sets (in an intuitive way, they do not define sets most of the time).

I even have read a comment on that in a pdf I have found in the web:

A Problem Course in
Mathematical Logic
Version 1.5
Volume I
Propositional and
First-Order Logic
Stefan Bilaniuk

where it states in the Appendix A, devoted to Set theory:

"The properly sceptical reader will note that setting up propositional
or first-order logic formally requires that we have some set theory in
hand, but formalizing set theory itself requires one to have first-order
logic."

So, it is not only my impression.

Is there some good book that studies first-order logic without resorting to set theory or any other more advanced mathematics, such that it can be used as the foundations to study set theory on a second step?

First order logic is the axiomatic (OR NOT) development of propositional and predicate calculus of 1st order ( =the quantification of the variables of the predicate ,or the operation symbols).2ND order is the quantification of the predicates.

First oder theories are the formal development (formal proofs) of any theories in mathematics ,including that of sets,using 1st order logic as the logical medium of the proofs

The interrelation between the concept of a set and 1st order theories or logic can be compared with that between of natural Nos and set theory or any other theories of that matter.

Can anyone state and develop any theory in mathematics without numbering the axioms??



You study 1st order logic to be able to give formal proofs of 1st order .

Formal proofs are an excellent instrument for checking any proof in all fields of mathematics ,provided the theory is expressed in 1st order logic.

In analysis for example you can have 1st order proofs,and 2nd order proofs ,depending the way you express the theory.

Everyone has his favorite book of 1st order ,mine is the book written by Angelo .Margaris(first order mathematical logic).Because it has couple of formal proofs ,emphasizing the practical use of 1st order logic ,and part of it is devoted to theoretical side of formal logic ( completeness ,consistency, Godel's theorem e.tc ,e.t.c)

If one learns logic without applying it to mathematics ,is like learning everything about cars and driving without ever getting into a car to drive it.

 

[jordi]

Thank you for the explanation. I agree with what you say. What I meant is many books on first order logic, in the first pages of the book, when they start explaining first order logic, they use set theory concepts. But I find this faulty, because for me, the "logical" path is: first order logic -> first order theories (like set theory or others). You cannot use set theory concepts when you are "defining" first order logic, it becomes circular.

For example, in Srivastava book (a course on mathematical logic), in page 3, I can read (sorry, I do not know how to write latex here, but I imagine that you can understand it):

A first-order language L consists of two types of symbols: logical
symbols and nonlogical symbols. Logical symbols consist of a sequence
of variables x0, x1, x2, . . .; logical connectives ¬ (negation) and ∨ (disjunction);
a logical quantifier ∃ (existential quantifier) and the equality
symbol =. We call the order in which variables x0, x1, x2, . . . are listed
the alphabetical order. These are common to all first-order languages.
Depending on the theory, nonlogical symbols of L consist of an (empty or
nonempty) set of constant symbols {ci : i ∈ I}; for each positive integer
n, a set of n-ary function symbols {fj : j ∈ Jn}; and a set of n-ary
relation symbols {pk : k ∈ Kn}.

Come on! how can you DEFINE a first-order language, with the definition including set theoretic concepts, which in fact will be later "defined" as a first order theory using first-order language!

 

[jordi]

The interrelation between the concept of a set and 1st order theories or logic can be compared with that between of natural Nos and set theory or any other theories of that matter.

Can anyone state and develop any theory in mathematics without numbering the axioms??

I do not agree with this statement. You do not need to number the axioms. The only thing you need is the concept of proposition. An axiom is a proposition. A list of axioms is a list of propositions. I do not need numbers for that. I only need to say: the axioms of the given theory are p, q, ... and whatever, where p, q, ... are the axioms. I do not need to say p is the axiom number 1, q is the axiom number 2, ...

Of course, I will be able to say so after I define the numbers. I can then go back and after I have introduced the concept of numbers say: I give now a new list of axioms, where p is the axiom 1, q is the axiom 2, ...

One could think that the my problem in the definition above is also only nomenclature. Probably one could restate the definition without using set theoretic concepts. But for example, in Srivastava book, in page 4, he writes:

The set of all terms of a language L is the smallest set T of expressions
of L that contains all variables and constant symbols and is closed under
the following operation (...)

Here he is using the concept of smallest set! this is not only nomenclature, this is already using some "advanced" theoretic concepts. But he does that when he still has not properly defined the language with which he could try and define the theory that describes what a smallest set is!

 

[Hurkyl]

It gets worse: how are you going to develop first-order logic without first assuming first-order logic?

I think you're essentially running up against the regress problem from philosophy.

 

[jordi]

Mmm ... I do not think this is a problem to me (even though I understand some could think about it to be a problem). I see first-order logic as something "given" (even though I know there are other kinds of logic, but I do not care: I want to proceed with first-order logic, which is MY logic).

I see first-order logic as something "polishing" the language. I do not think that just stating the rules of logic in writing (which is more or less what first-order logic is all about) is a serious problem.

There has to be somebody who has thought about this. Come on, it cannot be that mathematicians fall in such an easy trick as circular reasoning!

 

[tgrrl]

There is a whole slew of different ideas running around here, but I'll try to give my own interpretation on some of them.

First of all, you say that you want to study logic, then set theory, and then deduce the whole of mathematics from that. To be perfectly honest, this isn't really a practical way to go about studying math. While it's true that this can be done, it's really an exercise for logicians more than mathematicians. It's sort of like saying that you want to learn every word in a language, and every rule about how sentences are constructed before you go about speaking it. Mathematics does rely pretty exclusively on set theory, but I don't know that it's necessary to make that reliance wholly explicit.

Let me try to illustrate this idea with an allegory.

In an elementary course in mathematical logic, one studies deductions--the process of proving an idea straight from the axioms and some rules of inference. Now, it is true that every major theorem in a branch of mathematics can be deduced wholly from the axioms in a system using some rules of inference. But would you really want to prove, say, the fundamental theorem of calculus straight from a set of axioms about the real numbers? Certainly not! So why should one want to build up every major mathematical result purely from set theory if they really intend to use the math they're working with? If you're interested in this as a logical exercise, that's one thing. Otherwise, we just sort of accept that everything rests on top of set theory, and then go on producing more mathematics with that handy tool, without worrying about the hidden, underlying structure.

Moving onward, you go on to say that you're studying (or trying to study) first-order logic from set theory books. Now, if you really want a thorough introduction to logic, then I would suggest a course in logic. Logic is really not so simple as it seems. Certainly, the everyday rules of propositional logic that we use in proving theorems is fairly elementary (not without exception), but a true study in mathematical logic is extremely involved. Now, if you want to get grounded in enough logic to start doing higher math, then just find a text on the transition to advanced mathematics. The one I used as an undergraduate when preparing for higher math was titled, simply, "A Transition to Advanced Mathematics". There wasn't a lot of depth in the considerations of logic here--just truth tables, how to deal with implication, denial, quantifiers, double-implication, proofs by contradiction, direct proofs, etc. You prove basic things, e.g. that the sum of two even numbers is even, etc. This is generally the kind of grounding that one needs in logic in order to "do" math. But, of course, this kind of study is really useful for getting your intuition going. The deeper bits are for logicians; most of us just intuit that in order to prove AvB==>C, one needs to prove that A==>C and B==>C.

In any case, once you get a grounding in this kind of logic, then you could move on to studying set theory (which, by the way, is what you usually do in a transitional course, though, again, just enough set theory to have some power in math).

Now, as far as your comment that setting up a language in predicate logic requires some set theory notions, I would say that you're merely being tricked here. While it's true that the definition of a language that you've been using does make mention of set theory, you could always rewrite those definitions to omit any reference to sets. However, the author's probably just trying to make your life easier by leaving the set notation in. I mean, we all understand what it means, so it's just easier to read that way. But if you didn't want it, then why not just throw out all references to sets, and try rewriting those definitions? I'm sure you could do it. I think you're just demanding a more strict writing by the author. I applaud that you noticed the author's apparent lack of rigor, but I think it's more for convenience than a glaring oversight.

Don't get caught up in the haze of trying to reduce everything to logic, unless logic is what you plan to study. Trust me, I did this quite a bit as an undergrad, and it really held me back in other math courses. Of course, that's just what I think.

I'm interested in the discussion; what do you think?

 

[poutsos.A]

I do not agree with this statement. You do not need to number the axioms. The only thing you need is the concept of proposition. An axiom is a proposition. A list of axioms is a list of propositions. I do not need numbers for that. I only need to say: the axioms of the given theory are p, q, ... and whatever, where p, q, ... are the axioms. I do not need to say p is the axiom number 1, q is the axiom number 2, ...

Of course, I will be able to say so after I define the numbers. I can then go back and after I have introduced the concept of numbers say: I give now a new list of axioms, where p is the axiom 1, q is the axiom 2, ...

One could think that the my problem in the definition above is also only nomenclature. Probably one could restate the definition without using set theoretic concepts. But for example, in Srivastava book, in page 4, he writes:

The set of all terms of a language L is the smallest set T of expressions
of L that contains all variables and constant symbols and is closed under
the following operation (...)

Here he is using the concept of smallest set! this is not only nomenclature, this is already using some "advanced" theoretic concepts. But he does that when he still has not properly defined the language with which he could try and define the theory that describes what a smallest set is!

When you say p,q,r ...axioms this is numbering in its general sense.Numbering is a one to one correspondence.

How would you count your goats if you have never been in a school??

Coming now to the use of the concept of the set while developing 1st order logic,you must realize that,there are two languages to use.

1) The object or subject language.

2)The metalanguage

The object language consists of the well formed formulas ( formulas formed under certain rules) ,the axioms ,the theorems.

The metalanguage is the language with which we describe the object language.

In our case the metalanguage is the English language

So probably all those concepts : set ,Nos e.t.c are within the metalanguage and thus have nothing to do with 1st order logic itself

 

[poutsos.A]

It gets worse: how are you going to develop first-order logic without first assuming first-order logic?

I think you're essentially running up against the regress problem from philosophy.

You do not have to assume first order logic to develop first order logic.

In developing first order logic you have to assume only M.Ponens from the rules of inference and probably sometimes the rule of substitution

 

[poutsos.A]

Certainly, the everyday rules of propositional logic that we use in proving theorems is fairly elementary (not without exception)

In proving nearly every theorem in mathematics are not only the rules of propositional logic we use but those of the predicate calculus as well

Practically what we do ,in an ordinary mathematical proof,without realizing it is the elimination and introduction ,under certain rules,of the two quantification symbols:

$$\forall$$ , $$\exists$$,plus the use of the propositional logic.

In a formal mathematical proof one have to show and name those rules.

And as i mentioned before one uses a formal proof to check an ordinary mathematical proof.

In a formal proof there are no gaps or things to assume or imagine,everything is explicitly mentioned : axioms.theorems,definitions,rules of inference.

SO ONE writes down a proof and is not absolutely sure as to the validity of his proof.

What must he/she do??

Two people are arguing w.r.t the correctness of a certain proof .

What must they do??

You come across a lengthy proof with a lot of gaps and assumptions what must you do, so you will completely comprehend and then memorize it??

Many people are of the impression that formal proofs are very laborious and difficult to understand.

At the beginning yes they are.

But formal proofs are the ultimate weapon mathematicians have for a complete command of the whole of mathematics.
And to accomplish that one need to thoroughly understand first order logic

 

[Hurkyl]

I see first-order logic as something "given" (even though I know there are other kinds of logic, but I do not care: I want to proceed with first-order logic, which is MY logic).

Okay fine, first-order logic is a given. Now everything follows orderly from that. (The color is significant)

Using first-order logic, we can define the language of set theory, its axioms, and prove theorems, thus developing first-order set theory.

Now, we're probably interested in proving things about logic. Since we already have first-order set theory, we might as well define first-order logic in terms of that, to keep things simple.

Since we want to prove things about proving things in set theory, we will probably also wind up developing first-order set theory. And, we would probably prove some theorems about how theorems of first-order set theory are valid^* in first-order set theory.

*: This is light blue, because we used first-order set theory to define first-order logic, and so validity is a set theoretic notion. (Of course, validity is not a set theoretic notion)


Note that we cannot prove (nor can we prove) things about first-order logic; there just aren't any facilities to do so. Maybe a different sort of "given" logic could allow such recursion, but first-order logic does not.

We could make a metamathematical assumption that first-order logic = first-order logic, but we don't need to for the purposes of mathematics; it's good enough to be able to prove things about first-order logic and first-order set theory, and to prove things about first-order set theory.

(I don't think we have to push things further, either)

Come on, it cannot be that mathematicians fall in such an easy trick as circular reasoning!

Seriously -- read up on the regress problem before you criticize methods of dealing with it.

 

[jordi]

I do not think what I am asking is so complex as some of you are suggesting.

Let me use an allegory:

Most analysis books give the axioms of the real numbers. From these axioms, a few "known" results are derived rigorously. But later on, when the book uses some facts about real numbers, very often these results are not proved via the axioms of the real numbers, but are just "common sense".

One could argue: if in fact we finally just use "common sense", why do we need the axioms of the real numbers? We could get rid of them, and just use "common sense". We could, but most people prefer to have the "comfort" of knowing the axioms are there.

In the same way, I would like to have the "axioms" of logic (call it as you wish: inference rules, language, ...), to derive some of its consequences rigorously (which in fact we all know in "common sense" terms), to find some interesting results (incompleteness theorems, ...) and finally to gain the intuition that I could derive the whole of mathematics from that knowledge. But in the same way analysis books do not derive all results from real numbers rigorously, I would not like to derive all results in mathematics from logic. Only to know that I have the axioms and I could do so if I wished (in the same way I could do it with the axioms of the real numbers; please note that without
the axioms of real numbers, I could not do it).

It is strange to me that it is accepted that it is good to list the axioms of real numbers, but mathematicians do not need to list the "axioms of logic", when I believe it is more necessary the latter than the former.

 

[csprof2000]

Jordi:

I think you should carefully read what Hurkyl wrote if you're actually interested in knowing the answer to your question.

 

[jordi]

Okay fine, first-order logic is a given. Now everything follows orderly from that. (The color is significant)

Using first-order logic, we can define the language of set theory, its axioms, and prove theorems, thus developing first-order set theory.

Now, we're probably interested in proving things about logic. Since we already have first-order set theory, we might as well define first-order logic in terms of that, to keep things simple.

Since we want to prove things about proving things in set theory, we will probably also wind up developing first-order set theory. And, we would probably prove some theorems about how theorems of first-order set theory are valid^* in first-order set theory.

*: This is light blue, because we used first-order set theory to define first-order logic, and so validity is a set theoretic notion. (Of course, validity is not a set theoretic notion)


Note that we cannot prove (nor can we prove) things about first-order logic; there just aren't any facilities to do so. Maybe a different sort of "given" logic could allow such recursion, but first-order logic does not.

We could make a metamathematical assumption that first-order logic = first-order logic, but we don't need to for the purposes of mathematics; it's good enough to be able to prove things about first-order logic and first-order set theory, and to prove things about first-order set theory.

(I don't think we have to push things further, either)



Seriously -- read up on the regress problem before you criticize methods of dealing with it.

I want to thank you the time you have devoted to outlining your argument. But for me, the line that I do not agree with is:

Now, we're probably interested in proving things about logic. Since we already have first-order set theory, we might as well define first-order logic in terms of that, to keep things simple.

I do not want to prove things about logic. And definitely I do not want to define first-order logic in terms of first-order set theory. Always, irrespective of the colour, logic comes before set theory.

I understand logic as something that I do not need to "prove". I only want to make everything explicit. I want to prove the rest of mathematics (set theory and beyond) using logic. Logic does not need to be proved to me.

But this does not mean I do not want to formalize logic. I want logic formalized, and as Halmos said in Naive Set Theory: learn it and forget it.

 

[jordi]

My problem is with the statement:

it's good enough to be able to prove things about first-order logic and first-order set theory, and to prove things about first-order set theory.

I do not want to prove things about first-order logic and first-order set theory, I only want to prove things about first-order set theory.

I find extremely uncomfortable about proving things about first-order logic using first-order set theory. I think it is "unnatural".

 

[jordi]

My problem is with the statement:



I do not want to prove things about first-order logic and first-order set theory, I only want to prove things about first-order set theory.

I find extremely uncomfortable about proving things about first-order logic using first-order set theory. I think it is "unnatural".

To sum up: what I want, and I cannot find in books, is:

first-order logic => first-order set theory => all mathematics based on set theory

But never, never, find in the process:

first-order logic => first-order set theory => first-order logic

which is what I find in all books I have been checking up to now (well, in fact what I find is worse than that: I find first-order logic, but without the statement that first-order logic comes from the process first-order logic => first-order set theory => first-order logic, but just left as if first-order logic were the "original" and "true" logic, ie first-order logic, which of course it is not), and I find it extremely uncomfortable (and unnecessary ... I like Occam's razor) to live with.

 

[poutsos.A]

I do not think what I am asking is so complex as some of you are suggesting.

Let me use an allegory:

Most analysis books give the axioms of the real numbers. From these axioms, a few "known" results are derived rigorously. But later on, when the book uses some facts about real numbers, very often these results are not proved via the axioms of the real numbers, but are just "common sense".

One could argue: if in fact we finally just use "common sense", why do we need the axioms of the real numbers? We could get rid of them, and just use "common sense". We could, but most people prefer to have the "comfort" of knowing the axioms are there.

In the same way, I would like to have the "axioms" of logic (call it as you wish: inference rules, language, ...), to derive some of its consequences rigorously (which in fact we all know in "common sense" terms), to find some interesting results (incompleteness theorems, ...) and finally to gain the intuition that I could derive the whole of mathematics from that knowledge. But in the same way analysis books do not derive all results from real numbers rigorously, I would not like to derive all results in mathematics from logic. Only to know that I have the axioms and I could do so if I wished (in the same way I could do it with the axioms of the real numbers; please note that without
the axioms of real numbers, I could not do it).

It is strange to me that it is accepted that it is good to list the axioms of real numbers, but mathematicians do not need to list the "axioms of logic", when I believe it is more necessary the latter than the former.

The answer to you post is my post # 11,but you overlooked it ,or you did not read it.

As i said practically in the whole of mathematics we can have two kinds of proofs.


1)An ordinary mathematical proof.

2)A formal proof

Take for example the two well known simple theorems in real Nos:


$$ab=0\Longleftrightarrow a=0\vee b=0$$ for all a.bεR

$$a>0\Longrightarrow\frac{ 1}{a}>0$$ for all aεR

An ordinary mathematical proof for the first one is:

Let ab=0 and $$a\neq 0$$ ,then $$a\frac {1}{a} = 1$$ ,but also $$\frac {1}{a}(ab) = (\frac {1}{a} a)b= 1b=b =0$$.

And conversely a= 0 ===> ab=0 ,and also b = 0 ===> ba= ab=0 ,thus ab=0.

Also an ordinary mathematical proof for the 2nd theorem is:

Since a>0 ,then $$a\neq 0 \Longrightarrow \frac {1}{a}a = 1$$ ,and if 1/a is not greater than zero then 1/a is less or equal zero ,but in those cases $$a\frac {1}{a} =1\leq 0$$ which is not true ,hence

$$\frac {1}{a}>0$$.


One may ask now: Which are the laws of logic involved in the proofs of the two above theorems . Also the theorems ,definitions ,axioms??

The answer to that is:To find out you must give a formal proof .

Another question frequently asked (usually for more complicated proofs) is: Are the proofs given correct.

A more complicated proof in real analysis is:

Prove that for all ε>0 and any real No x ,there exist a rational No a such that |a-x|<ε.


Here even an ordinary mathematical proof is quite complicated .

But even so can we give a formal proof ?? The answer is YES

 

[jordi]

poutsos.A, I did not overlook it.

My point is that my wish is less ambitious than yours. I think you would like to have all mathematical proofs with a high level of rigorosity. This would imply rewriting milions and milions of pages of mathematical books. What I want is less ambitious: to have a single book (about 100 pages) where logic is presented cleanly, and without any use of further language that will later require the language of logic to be clearly defined.

I only need a few examples to get sufficiently convinced that logic is enough (eg, write all set theory in logic language). For further theories, I will probably not need to rewrite all of them to get convinced that "I could do it" if I wished.

But your point makes sense. I always thought it would be cool to have a program where I could list all axioms of a theory, build lemmas, and just "linking" graphically axioms and lemmas, together with logic statements, leave the program to verify if a stated theorem is correct or not.

I imagine this was not practical when there were no computers and everything had to be done with pen and paper, but with computers and graphics capabilities, this should not be a far away dream.

 

[MathematicalPhysicist]

I don't understand you Jordi, in first order logic (predicate logic) you need a model which is a set, even in category theory you see there the need to invoke the use of a set.

 

[jordi]

I do not understand you, loop quantum gravity, either.

Why would you NEED to use a set to describe logic? As a maximum, I can understand set theory language may be useful to describe logic in an easier way than if it were not used.

.

 

[csprof2000]

I think the real trouble is that at their most fundamental level, they're both really the same thing, just different ways of talking about it. If you split the two ways into "just logic" and "just set theory", you need to sort of define both in terms of the other.

For instance, let's take a very basic example. The language of propositional logic could be defined as follows:

1. a is in the language, if a is an atom.
2. (F OR G) is in the language, if F and G are in the language
3. (NOT F) is in the language, if F is in the language.
4. Nothing else is in the language.

As you can see, to even define the language of propositional logic requires ideas about something "being in" something else - a set-theoretic notion. Or we can try to define the set of things which belong to the "language" of Lp:

Lp = { x | x in {atoms} OR (x = (F OR G) AND F in Lp AND G in Lp) OR (x = (NOT F) AND F in Lp) }

The problem with that, obviously, is that we have assumed some propositional logic - that we know the meaning of OR and AND, which is equivalent to saying we know about OR and NOT, and so we assume that propositional logic exists before we've even defined the set which contains formulas in the language of propositional logic.

The only way I see around this is to take logic and set theory and combine them into a single "set logic" or something. The reason this isn't more commonplace is that (a) I'm sure that trying to do this is no mean feat, (b) it's sort of redundant in the sense that we already have its constituent parts, and (c) normally, the problems you're talking about aren't such a big deal.


I challenge you to think of ways in which you could describe a "super logic" or "super set theory" which incorporates both propositional logic and set theory. There are clear parallels - in a set <-> true, not in a set <-> false, OR <-> union, complement <-> NOT, etc. You'll have to define a couple of objects to work with, probably, or maybe just one (wouldn't be surprised). Throw that with a couple of rules (needless to say, you will want to make these quite general) and see what you get.

 

[jordi]

I disagree with the previous comment. I am sorry to say you are cheating, since you state your 1-4 statements using set theory language (it looks like as if "language" is a set and a (and other symbols) are elements of the set). But it is not necessary to do so at all. In fact, I believe most books do not do that, even though they may use later set theory concepts when explaining logic.

For example, Suppes uses the following language, equivalent to your 3 (all the others are similar):

"If P is a primitive formula, then -P is a primitive formula"

Definitely, this "is a" IS NOT the set theoretic "belongs to" (or what you call it, "is in"). It is the "natural" "is a", the "is a" for which I do not require a proof or definition.

In some way, and I know that this is more philosopy than mathematics, I believe logic "has real existence" (in the Plato sense), but set theory is only a (very useful) human construct. The parallels in a set <-> true are not parallels at all then, but just a copy in set theory from the "true" concept. Additionally, the parallel is not perfect: all statements are either true or false, but not any "element" is "in a set" (or not), or at least, one could say not always it makes sense to ask if an element is in a set or not.

 

[Hurkyl]

There isn't really a difference between "is a" and "is in". In fact, it is not uncommon to use the notation $x \in P$ as an alternative syntax for $P(x)$. (Here, P is a predicate, and x is a variable)

The point is that sets aren't supposed to correspond to statements -- they are supposed to correspond to predicates. In fact, that correspondence is essentally the entire definition of Cantor's naïve set theory. (And the paradoxes of Cantor's set theory were generally also paradoxes of pure logic)

If you check, in higher-order logic, all of the arithmetic operations and relations you need to do set theory (e.g. Cartesian products, power sets, subsets, unions, singletons, pairs) are defined for predicates.

Just to demonstrate, if P is a predicate, then its union is the predicate $\mathcal{U}_P$ defined by

$$\mathcal{U}_P(x) := \exists Q : P(Q) \wedge Q(x)$$

If we use the $\in$ notation to express the evaluation of a predicate, then this has the familiar form of the axiom of unions from Zermelo set theory:

$$x \in \mathcal{U}_P \Leftrightarrow \exists Q : Q \in P \wedge x \in Q$$

 

[jordi]

There isn't really a difference between "is a" and "is in". In fact, it is not uncommon to use the notation $x \in P$ as an alternative syntax for $P(x)$. (Here, P is a predicate, and x is a variable)

The point is that sets aren't supposed to correspond to statements -- they are supposed to correspond to predicates. In fact, that correspondence is essentally the entire definition of Cantor's naïve set theory. (And the paradoxes of Cantor's set theory were generally also paradoxes of pure logic)

If you check, in higher-order logic, all of the arithmetic operations and relations you need to do set theory (e.g. Cartesian products, power sets, subsets, unions, singletons, pairs) are defined for predicates.

Just to demonstrate, if P is a predicate, then its union is the predicate $\mathcal{U}_P$ defined by

$$\mathcal{U}_P(x) := \exists Q : P(Q) \wedge Q(x)$$

If we use the $\in$ notation to express the evaluation of a predicate, then this has the familiar form of the axiom of unions from Zermelo set theory:

$$x \in \mathcal{U}_P \Leftrightarrow \exists Q : Q \in P \wedge x \in Q$$

As I said before, there are some similarities between "is a" and "is in" (you outline them brilliantly) but they are not the same. Example: x "is in" {{a},{b}} is something perfectly valid, but I would never say x "is a" {{a},{b}}. They are different things.

For me, if p is a statement, it is completely basic to say if p is true or false. However, the "is in" is something derived, not "completely basic" if you understand what I mean.

As I said, this discussion is very philosophical, but for me it is very clear logic is "fundamental" (it exists by its own) and set theory a derived "human construct".

 

[Hurkyl]

As I said before, there are some similarities between "is a" and "is in" (you outline them brilliantly) but they are not the same. Example: x "is in" {{a},{b}} is something perfectly valid, but I would never say x "is a" {{a},{b}}.

But if I let T denote the type of object contained set, then you would say that {a} "is a" T.

They are different things.

They are equivalent things; switching between the two notions is a purely syntactic rewriting of notation that has no effect on semantics. i.e. it's two different ways of saying the same thing.

For me, if p is a statement, it is completely basic to say if p is true or false. However, the "is in" is something derived, not "completely basic" if you understand what I mean.

Don't think "statement". Think "predicate". The set R corresponds to the predicate "____ is a real number".

 

[Hurkyl]

Anyways, going back to the original topic... I'm confused as to why you have a problem. You want to take logic as given, and then study

logic ==> set theory ==> rest of mathematics

However, that's exactly what you see in typical presentations, is it not? Formal set theory textbooks would yield that first arrow, and the textbooks on other topics would deal with the second arrow on a case-by-case basis.

You say that you don't want to see

logic ==> set theory ==> logic

and it's easy to achieve that goal -- don't read any books on formal logic!

 

[jordi]

Anyways, going back to the original topic... I'm confused as to why you have a problem. You want to take logic as given, and then study

logic ==> set theory ==> rest of mathematics

However, that's exactly what you see in typical presentations, is it not? Formal set theory textbooks would yield that first arrow, and the textbooks on other topics would deal with the second arrow on a case-by-case basis.

You say that you don't want to see

logic ==> set theory ==> logic

and it's easy to achieve that goal -- don't read any books on formal logic!

If you could give me a good book where the implication


logic ==> set theory

is discussed, I would be happy and consider my initial question answered.

However, my first question comes from the fact I have still not found a book where the implication

logic ==> set theory

is worked out. Basically because of the fact they do not start with logic, but with logic (they define logic using set theoretic concepts).

I am sure there must be a book on logic which does not require any knowledge whatsoever of set theory and it is comprehensive, but after checking 3 or 4 books on logic, I still have not found one.

 

[jordi]

But if I let T denote the type of object contained set, then you would say that {a} "is a" T.

Yes, but the fact that you have to do something (eg, call T the type of object contained set), but you do not need to do it when you are talking about "is a", is an indication that both things are not exactly the same: they can be made to look like the same through your argument, but set theory is one step further than predicates, being a "man construction", while logic exists there "by its own".

 

[diotimajsh]

Hmmm. How much set theory do you want to rule out, jordi? If a system of logic uses the concepts of membership and quantification but doesn't start out with anything else set-theoretical, would that be too much?

WVO Quine had a 1937 paper, "New Foundations for Mathematical Logic", where he built up some other key notions for set theory from just the above two primitive notions plus the Scheffer stroke (logical NAND). It's kind of a revised (and very readable) version of something Russell and Whitehead did in Principia Mathematica. While Russell and Whitehead attempted to show how all of mathematics (as known at the time) could be derived from logical principles, Quine's paper shows how to get to the Principia's starting point from a somewhat more minimal set of assumptions. (Consequently, it's waaaaay shorter and much more to the point; and since it was written later than the Principia, it uses rather less obnoxious notation.)

"New Foundations" is on JSTOR, but I could email you a copy if you don't have access.


For something more modern though, what kind of logic textbooks have you been looking into? If you've been looking primarily at mathematical logic books, maybe you should try a philosophy-oriented logic book. Those tend to focus on intuitive logical principles first and then work toward set theory later.

(Unfortunately, I don't have any really great recommendations. I used Hurley's A Concise Introduction to Logic as an undergrad, I think, but I didn't really like it, and I can't remember whether it resorts to set theory for its definitions.)

 

[jordi]

Hmmm. How much set theory do you want to rule out, jordi? If a system of logic uses the concepts of membership and quantification but doesn't start out with anything else set-theoretical, would that be too much?

No, not at all: it would be exactly what I am looking for.

WVO Quine had a 1937 paper, "New Foundations for Mathematical Logic", where he built up some other key notions for set theory from just the above two primitive notions plus the Scheffer stroke (logical NAND). It's kind of a revised (and very readable) version of something Russell and Whitehead did in Principia Mathematica. While Russell and Whitehead attempted to show how all of mathematics (as known at the time) could be derived from logical principles, Quine's paper shows how to get to the Principia's starting point from a somewhat more minimal set of assumptions. (Consequently, it's waaaaay shorter and much more to the point; and since it was written later than the Principia, it uses rather less obnoxious notation.)

"New Foundations" is on JSTOR, but I could email you a copy if you don't have access.

I do not have access to JSTOR. Would it be too much abusing if I sent to you my email address via PM?

For something more modern though, what kind of logic textbooks have you been looking into? If you've been looking primarily at mathematical logic books, maybe you should try a philosophy-oriented logic book. Those tend to focus on intuitive logical principles first and then work toward set theory later.

(Unfortunately, I don't have any really great recommendations. I used Hurley's A Concise Introduction to Logic as an undergrad, I think, but I didn't really like it, and I can't remember whether it resorts to set theory for its definitions.)

I tend to be quite picky with the books I use, and the philosophy-oriented logic books (I have browsed some of them) are too verbose for me.

What I would like is a modern book, with the title "everything you need before starting with set theory" (ie, logic and language). But probably the Quine's paper would be enough.

 

[csprof2000]

jordi:

"X is a (blank)" is another way of saying "X belongs to the set of all (blank)".

Being something is a set-theoretic notion.

 

[jordi]

jordi:

"X is a (blank)" is another way of saying "X belongs to the set of all (blank)".

Being something is a set-theoretic notion.

False. Proof: let (blank) := set

"X is a set" is meaningful. "X belongs to the set of all sets" is not meaningful, because the set of all sets does not exist.

 

[jordi]

A second argument, more a philosophical one, is that "is a" is a basic concept. Instead, sets are a "secondary" concept, based on basic concepts.

 

[diotimajsh]

No, not at all: it would be exactly what I am looking for.

I do not have access to JSTOR. Would it be too much abusing if I sent to you my email address via PM?

Certainly not, go ahead.

So, glancing through this paper again, it turns out it does use somewhat more outdated notational conventions than I'd thought. Turns out the version I'm familiar with was re-released in a compilation of essays (Quine's From a Logical Point of View), and they must have updated the notation then.

I dunno, see what you make of it. Hopefully this older version is still useful to you. I find it a tad confusing to follow though.