# First-order logic without sets?

1. Mar 7, 2009

### 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?

2. Mar 7, 2009

### 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.

3. Mar 11, 2009

### poutsos.A

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.

4. Mar 11, 2009

### 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!

5. Mar 11, 2009

### jordi

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!

6. Mar 11, 2009

### Hurkyl

Staff Emeritus
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.

7. Mar 11, 2009

### 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!

8. Mar 11, 2009

### 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?

9. Mar 11, 2009

### poutsos.A

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

10. Mar 11, 2009

### poutsos.A

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

11. Mar 11, 2009

### poutsos.A

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

12. Mar 11, 2009

### Hurkyl

Staff Emeritus
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. :tongue:

Last edited: Mar 11, 2009
13. Mar 12, 2009

### 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.

14. Mar 12, 2009

### csprof2000

Jordi:

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

15. Mar 12, 2009

### jordi

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:

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.

16. Mar 12, 2009

### 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".

17. Mar 12, 2009

### jordi

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.

18. Mar 13, 2009

### poutsos.A

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

19. Mar 13, 2009

### 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.

20. Mar 13, 2009

### 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.