67
$\begingroup$

This question already has an answer here:

I am trying to understand what mathematics is really built up of. I thought mathematical logic was the foundation of everything. But from reading a book in mathematical logic, they use "="(equals-sign), functions and relations.

Now is the "=" taken as undefined? I have seen it been defined in terms of the identity relation.

But in order to talk about functions and relations you need set theory. However, set theory seems to be a part of mathematical logic.

Does this mean that (naive) set theory comes before sentential and predicate logic? Is (naive)set-theory at the absolute bottom, where we can define relations and functions and the eqality relation. And then comes sentential logic, and then predicate logic?

I am a little confused because when I took an introductory course, we had a little logic before set-theory. But now I see in another book on introduction to proofs that set-theory is in a chapter before logic. So what is at the bottom/start of mathematics, logic or set theory?, or is it circular at the bottom?

Can this be how it is at the bottom?

naive set-theory $\rightarrow$ sentential logic $\rightarrow $ predicate logic $\rightarrow$ axiomatic set-theory(ZFC) $\rightarrow$ mathematics

(But the problem with this explanation is that it seems that some naive-set theory proofs use logic...)

(The arrows are of course not "logical" arrows.)

simple explanation of the problem:

a book on logic uses at the start: functions, relations, sets, ordered pairs, "="

a book on set theory uses at the start: logical deductions like this: "$B \subseteq A$", means every element in B is in A, so if $C \subseteq B, B \subseteq A$, a proof can be "since every element in C is in B, and every element in B is in A, every element of C is in A: $C \subseteq A$". But this is first order logic? ($(c \rightarrow b \wedge b \rightarrow a)\rightarrow (c\rightarrow a)$).

Hence, both started from each other?

$\endgroup$

marked as duplicate by Asaf Karagila elementary-set-theory Jun 22 '15 at 18:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 20
    $\begingroup$ There are some concepts that must be taken as primitive. If you try to understand them in terms of other things then you will indeed end up going in circles. $\endgroup$ – Zhen Lin Jun 22 '15 at 8:45
  • 1
    $\begingroup$ @ZhenLin I understand, but is there somewhere explained what is taken for granted when creating mathematics. I know that "set" is probably taken for granted, but what about "=", it gets confusing because set theory seems to use logic, but logic seems to use set theory. Do you know anyplace where it is explained from the very start, precisely what is taken for a primitive concept?, or is this something that vary from book to book? $\endgroup$ – user119615 Jun 22 '15 at 8:52
  • 1
    $\begingroup$ Are you sure you will end up going in circles? This might be a philosophical point but I don't think the primitive notions refer to anything but themselves. There is no real example or property that can be used to define the very primitive notion "elementhood" in set theory. You cannot formalize that concept nor can you understand it through referring to other concepts, I think. $\endgroup$ – Leo Jun 22 '15 at 8:53
  • 4
    $\begingroup$ I'm afraid it's turtles all the way down. (Kidding!) $\endgroup$ – Ken Jun 22 '15 at 12:55
  • 2
    $\begingroup$ Some of the following posts might be of interest for you: How to avoid perceived circularity when defining a formal language?, An (apparently) vicious circle in logic, Don't the axioms of set theory implicitly assume numbers? Is it important to distinguish between meta-theory and theory? (And you can probably find a few more related posts both here and on MO.) $\endgroup$ – Martin Sleziak Jun 22 '15 at 16:28
35
$\begingroup$

What you are butting your head against here IMO is the fact that you need a meta-language at the beginning. Essentially at some point you have to agree with other people what your axioms and methods of derivation are and these concepts cannot be intrinsic to your model.

Usually I think we take axioms in propositional logic as understood, with the idea that they apply to purely abstract notions of sentences and symbols. You might somethimes see proofs of the basic axioms such as Modus Ponens in terms of a meta-language i.e. not inside the system of logic but rather outside of it.

There is a lot of philosophical fodder at this level since really you need some sort of understanding between different people (real language perhaps or possibly just shared brain structures which allow for some sort of inherent meta-deduction) to communicate the basic axioms.

There is some extra confusion in the way these subjects are usually taught since propositional logic will often be explained in terms of, for example, truth tables, which seem to already require having some methods for modeling in place. The actual fact IMO is that at the bottom there is a shared turtle of interhuman understanding which allows you to grasp what the axioms you define are supposed to mean and how to operate with them.

Anyhow that's my take on the matter.

$\endgroup$
  • $\begingroup$ I was going to write something similar. $\endgroup$ – Mark Bennet Jun 22 '15 at 9:07
  • 2
    $\begingroup$ I would be interested to read such a proof of Modus Ponens, would you happen to have a link to one? $\endgroup$ – nosyarg Jun 22 '15 at 10:54
  • $\begingroup$ @nosyarg to be perfectly honest I'm not sure I can produce the one I was thinking of. It was shown to me (quite a few years ago by now) in a lecture at uni. There is a truth table argument you can look at on the wikipedia page for Modus Ponens. $\endgroup$ – DRF Jun 22 '15 at 11:21
  • 2
    $\begingroup$ @DRF: That kind of argument can be classified as a model theoretic method. Namely you define boolean connectives in terms of a model. Clearly then every model of $P$ and $P \rightarrow Q$ is also a model of $Q$. However, truth tables themselves are defined using the English "if", and using the truth tables invoke a meta inference rule essentially equivalent to modus ponens, namely that for a given formula, when you know the subformulas have certain value and if the subformulas have certain values, then the formula has a certain value by the truth table, you know ... $\endgroup$ – user21820 Jun 22 '15 at 14:06
  • 1
    $\begingroup$ @AlexPritchard Hehe, thank you. I hoped someone would enjoy it. $\endgroup$ – DRF Jun 22 '15 at 15:08
28
$\begingroup$

Most set theories, such as ZFC, require an underlying knowledge of first-order logic formulas (as strings of symbols). This means that they require acceptance of facts of string manipulations (which is essentially equivalent to accepting arithmetic on natural numbers!) First-order logic does not require set theory, but if you want to prove something about first-order logic, you need some stronger framework, often called a meta theory/system. Set theory is one such stronger framework, but it is not the only possible one. One could also use a higher-order logic, or some form of type theory, both of which need not have anything to do with sets.

The circularity comes only if you say that you can justify the use of first-order logic or set theory or whatever other formal system by proving certain properties about them, because in most cases you would be using a stronger meta system to prove such meta theorems, which begs the question. However, if you use a weaker meta system to prove some meta theorems about stronger systems, then you might consider that justification more reasonable, and this is indeed done in the field called Reverse Mathematics.

Consistency of a formal system has always been the worry. If a formal system is inconsistent, then anything can be proven in it and so it becomes useless. One might hope that we can use a weaker system to prove that a stronger system is consistent, so that if we are convinced of the consistency of the weaker system, we can be convinced of the consistency of the stronger one. However, as Godel's incompleteness theorems show, this is impossible if we have arithmetic on the naturals.

So the issue dives straight into philosophy, because any proof in any formal system will already be a finite sequence of symbols from a finite alphabet of size at least two, so simply talking about a proof requires understanding finite sequences, which (almost) requires natural numbers to model. This means that any meta system powerful enough to talk about proofs and 'useful' enough for us to prove meta theorems in it (If you are a Platonist, you could have a formal system that simply has all truths as axioms. It is completely useless.) will be able to do something equivalent to arithmetic on the naturals and hence suffer from incompleteness.

There are two main parts to the 'circularity' in Mathematics. The first is the understanding of logic, including the conditional and equality. If you do not understand what "if" means, no one can explain it to you because any purported explanation will be circular. Likewise for "same". (There are many types of equality that philosophy talks about.) The second is the understanding of the arithmetic on the natural numbers including induction. This boils down to the understanding of "repeat". If you do not know the meaning of "repeat" or "again" or other forms, no explanation can pin it down.

Now there arises the interesting question of how we could learn these basic undefinable concepts in the first place. We do so because we have an innate ability to recognize similarity in function. When people use words in some ways consistently, we can (unconsciously) learn the functions of those words by seeing how they are used and abstracting out the similarities in the contexts, word order, grammatical structure and so on. So we learn the meaning of "same" and things like that automatically.

$\endgroup$
  • $\begingroup$ And by the way, if the real world is finite in space, time and energy, then there is no consistent interpretation of mathematical induction that would be true in the real world. Much of mathematics exists only in an ideal world, but some ideal worlds are useful as they model the real world in some ways. Unfortunately, ZFC does not model the real world well at all. $\endgroup$ – user21820 Jun 22 '15 at 10:28
  • 4
    $\begingroup$ @user119615: Almost all set theories including ZFC are based on logic because their very axioms require knowledge of first-order logic. But as I mentioned mathematics need not be based on set theories. It happens that modern mathematics is generally based on ZFC but in my opinion the real world is not modeled well by ZFC. To prove things about first-order logic you need something more only when it is too weak to express or derive what you want. Similarly, there are a lot of things that one can prove about ZFC by building a model of it within ZFC itself. $\endgroup$ – user21820 Jun 22 '15 at 11:50
  • 1
    $\begingroup$ @user119615: So it does not make sense to say that first-order logic can provide anything more to prove facts about ZFC that ZFC itself cannot, since ZFC already 'knows' first-order logic. What ZFC does not know is its own consistency, among other things. PA (the system consisting of the Peano Axioms) also cannot prove its own consistency, but ZFC proves the consistency of PA by explicitly axiomatizing a model for it. That is one reason set theorists study all sorts of stronger extensions of ZFC, many of which prove the consistency of ZFC (but cannot prove their own consistency). $\endgroup$ – user21820 Jun 22 '15 at 12:01
  • 1
    $\begingroup$ +1, you are absolutely right this dives straight into philosophy (and more specifically epistemology); it's frustrating how few mathematicians realize that. You may enjoy the following definition: sanity is the ability to recognize differences, similarities, and identities. $\endgroup$ – Wildcard Aug 25 '17 at 22:40
  • 1
    $\begingroup$ @EyalRoth that thought is actually entirely different from the comment I posted, and is neither similar nor the same. Weed is not productive of any increase in intelligence nor sanity, sorry to have to tell you. (But if you want to take it up further, ping me in chat.) $\endgroup$ – Wildcard Apr 8 at 18:15
5
$\begingroup$

On the bottom you have axioms (things that are assumed to be true) and definitions. In the case of set theory, these might be the axioms of ZFC and the definitions that explain them. PA or KP might be another possibility.

We will need another informal system (like English) to build the lowest axioms. But English is not a formal system. We can easily reach the paradox: The smallest ordinal which is not definable using [logic system] is definable using English. And it must necessarily exist, since there are only countably many definitions and uncountably many countable ordinals. Therefore English must stand on top of all formal systems, thus it can not be a formal system itself.


This is what I think to be reasonable axiomation and definition of logic (Yes, I just made this up). Comments on this are more than welcome.

Axiom 1. Any proposition $P$ has either value 0 or value 1.

Definition 1. $\neg P$ has value 1 if $P$ has value 0, $\neg P$ has value 0 if $P$ has value 1.

Definition 2,3,4,5,6. $P \wedge Q$, $P \vee Q$, $P \implies Q$, $P \iff Q$, $x \in S$. You know their definition.

Definition 7. The proposition $\forall x \in S: P(x)$ is true if P(x) is true for all $x \in S$.

Definition 8. The proposition $\exists x \in S: P(x)$ is true if P(x) is true for some $x \in S$.

Using this tools we can formulate the axioms of ZFC.

$\endgroup$
  • $\begingroup$ But in order to create that advanced set-theory, don't you use tools from mathematical logic? So you do have the axioms of set-theory, but do you also use the machinery of propositional logic when creating the set-theory?(And here comes the problem, if the answer is yes, have you not gone in a circle?) Since logic uses some set-theory. $\endgroup$ – user119615 Jun 22 '15 at 8:48
  • $\begingroup$ Also definitions and axioms need a bottom. In set-theory the primitives "set" and "belonging to a set". $\endgroup$ – drhab Jun 22 '15 at 8:52
  • $\begingroup$ @user119615 as pointed out by Zhen Lin: Yes, it's circular and no, this cannot be avoided. $\endgroup$ – Stefan Perko Jun 22 '15 at 8:52
  • $\begingroup$ Thank you, but is not P(x) a function here? I added something to my original question, do you think that holds, that we start with naive-set theory, then go to sentinel logic etc.? $\endgroup$ – user119615 Jun 22 '15 at 9:10
  • 2
    $\begingroup$ Your made up axioms, while seemingly reasonable, is actually too vague because you have not defined what is a proposition and how you can stick an $x$ into a proposition $P$. It is not easy to define even that! $\endgroup$ – user21820 Jun 22 '15 at 9:58
3
$\begingroup$

As already pointed out, this is indeed circular. The only thing you can do is pretend it is not.

A simple reason is for example: How are you going to explain what a proof is? Well, you might just a give a philosophical description, but I turns out that you can study proofs mathematically (as sequences of formulas satisfying some properties). If you believe, that is not circular, then you have to accept the "common sense" is always right by default or something like this. Giving a philosophical description is, I believe, just hiding the fact, that it's still circular.

But it turns out, this isn't a real issue. You've been doing math all your life and it somehow magically worked.

When we start to do math rigerously we start with our existing knowledge, let's call it "Math $0$", that is based on what we know from school and "common sense" and then inside of that formalize math again as a logical system "Math $1$". In a logic course we are just taking this more serious, than in introductery real analysis.

Concerning "$=$": In classical mathematics equality is defined in its predicate logic, as is $\in$ as some relation satisfiying some rules. (In other flavors of mathematics, I call them "structural" as opposed to "material", there is no "gobal" notion of equality and one works with equivalence relations in general (or sometimes appartness relations), but don't be confused by this, it's not important.)

Ah, and one more thing: "$=$" is usually not "literally" a relation as in: a subset of a cartesian product, we just like to think of it that way.

$\endgroup$
3
$\begingroup$

I remember when I faced this problem in my early days as a student. Here's a (hopefully) simple explanation, result of some year of studies.

One of the first thing to understand is that set theory is not just a family of axioms, it is a formal system that is specified by

  • a language, that is the set of well formed formulas
  • a set of axioms, that is a subset of the well formed formulas
  • a set of inference rules, that can be thought as (meta)operations on formulas that allow to build inductively the set of theorems for the theory.

To be fair one could also treat axioms as inference rules (with no hypothesis) and so regard set theory as a logic-system of its own. In order to present this system you don't need any notion of first-order logic (you don't need to know what is an interpretation or a model for a theory, you don't need to know what a theory is).

So shortly set theory is a logic by its own. In order to use this system (this logic) you don't need to know what first-order logic is. The only thing you need to know is how to use the inference rules to build recursively the theorem of the theory, or if you prefer, you need to know how to build proofs.

This situation is similar to arithmetics were you don't need to know equational logic (that is the logic underlying equational theories) to do calculuations, in order to arithmetics you can simply use the computational rules (which can be seen as inference rules) to do your calculuation (the proofs) in a mechanical way.

So from this perspective it should be clear that mathematical logic (intended as the study of formal systems) does not come first of set theory (when it is regarded as a foundational theory).

On the other hand mathematical logic is a mathematical theory of formal systems. It aims to study and to prove abstract properties of these formal systems, it doesn't simply use them. In order to develop a theory of this kind one can proceed in two possibile ways:

  • either giving an axiomatic theory of formal systems: that is a (meta) formal system whose language is able to express properties of the formal systems, whose axioms express basic properties that these systems should have and whose inference rules allows one to prove any statement that should hold for these formal systems
  • or defining what a formal system should be in a meta/foundational theory (for instance set theory) and then use the axioms and inference rules of the (meta)theory to prove, from the given definitions, the properties that these formal systems have.

Since our mind are really used to think in terms of collection and since set theory is (or at least should be) the formal theory of collection the second approach to mathematical logic is more appealing and with this choice mathematical logic in some sense become of second nature to set theory.

I hope this helps, if you need any clarification feel free to ask in the comments.

$\endgroup$
  • $\begingroup$ I see that you say that set-theory can be used as a foundation, but could you please look at the last part of my question, I updated it "a simple explanation of the problem". It seems that logic uses set-theory at the start, and set-theory uses logic at the start, can we say that they are intertwined at the bottom of mathematics? $\endgroup$ – user119615 Jun 22 '15 at 9:44
  • $\begingroup$ @user119615: No logic does not require set theory but what you learnt about logic was phrased in terms of set theory simply because that is the current favoured language of most modern mathematicians. $\endgroup$ – user21820 Jun 22 '15 at 10:24
  • $\begingroup$ @user119615 I've made edits to the answer, hoping it's more clear now. $\endgroup$ – Giorgio Mossa Jun 22 '15 at 14:49
1
$\begingroup$

Set theory is one of the branch of mathematical logic it clearly means not every mathematical logic can be explained by set theory.Mathematical logic is often divided into the fields of set theory, model theory, recursion theory, and proof theory. These areas share basic results on logic, particularly first-order logic, and definability.

One can easily say that at the bottom of mathematics lies elementary arithmetic which is the elementary part of number theory and mathematics in general.Although arithmetic and number theory is axiomized by peano axioms there is a problem with peano axioms The Peano axioms do not define what natural numbers are, they instead describe certain properties of natural numbers that can be used to reason about natural numbers.

You can refer to: https://en.wikipedia.org/wiki/Arithmetic

$\endgroup$
  • $\begingroup$ Number theory and arithmetic is axiomized by Peano Arithmetic (PA). $\endgroup$ – wythagoras Jun 22 '15 at 9:05
  • $\begingroup$ there is a problem with peano axioms The Peano axioms do not define what natural numbers are, they instead describe certain properties of natural numbers that can be used to reason about natural numbers. $\endgroup$ – Vadeem Jun 22 '15 at 9:14
  • $\begingroup$ Technically Peano's original axioms did sort of define the natural numbers if you have a strong enough meta-system, because there is only one model of second-order Peano Arithmetic. First-order PA has infinitely many models. If however you don't even allow different but isomorphic models, then yes, no axiomatization can uniquely define anything but only describe its properties as you said. $\endgroup$ – user21820 May 19 '16 at 6:14
1
$\begingroup$

It's turtles all the way down.*

In other words: there is nothing at the bottom of mathematics but philosophy. It's a set of rules we came up with because it seemed useful, but it has no absolute grounding in reality or the universe. It functions well in the "shared delusion" that is our understanding of the universe, but there is no way we could tell whether it actually connects to reality.

$\endgroup$
1
$\begingroup$

There are several ways to build up mathematics. One book may do it one way, another book will do it another.

All these methods suffer from the fact that you must start with normal human language for your first definitions. The author try to make their definitions as rigid as possible.

It is very important both for the writer and the reader to separate the informal language used to explain things and the formal language being defined!

The most common way is to first define a formal logic. This logic is defined without referring to set theory. This logic talks about "propositions" without saying anything about what these propositions are. There will be a few axioms and usually the rule of Modus Ponens.

The next level is set theory. This gives you some propositions to do logic about. There are more axioms describing sets and their members.

So, set theory is based on formal logic... in most text books.

Some books will present these two together since pure logic isn't very interesting without something to reason about.

$\endgroup$
  • $\begingroup$ I disagree, and you can see the full details in my answer. For a short example, you cannot define modus ponens without using something equivalent to modus ponens in your meta language. $\endgroup$ – user21820 Jun 22 '15 at 10:30
  • $\begingroup$ @user21820: After reading you answer, I deleted the part I think you disagreed with. You are right. $\endgroup$ – Stig Hemmer Jul 1 '15 at 20:31
  • $\begingroup$ Yup that's the main part of my disagreement. The closest we can get to having rigid definitions is by using syntactic rules for manipulating finite strings of symbols drawn from a finite alphabet. But unfortunately this presupposes that we all have the same understanding of finite strings. Also, (standard) finite strings are equivalent to the standard natural numbers. So we essentially need a common understanding of the natural numbers. But if it comes from (philosophical) induction from experience in the real world, we have a problem since the real world appears to be finite. $\endgroup$ – user21820 Jul 2 '15 at 5:35
  • $\begingroup$ By the way, I'm not sure exactly how you would go about defining what are well-formed formulas without set theory. Do you have a set/class of well-formed formulas? Or do you have an inductive definition? It is not impossible, but many mathematicians often don't even realize that their meta-system is more powerful as the formal system they are defining. If you use strings, you are already invoking the existence and properties of natural numbers. In my opinion, there is nothing wrong with that, as we (apparently) can't get started without strings of some sort! $\endgroup$ – user21820 Jul 2 '15 at 5:43
  • $\begingroup$ One alternative to set theory is type theory, which is in fact closer to how mathematicians actually work before formalizing their reasoning. For example, you could say something like "Let a string of symbols be called a formula iff ...", which would correspond to creating a new type called "formula". Some mathematicians might claim that they only work in ZFC, but that is not true because they still use the word "set" though there is no set of sets. Same for those who say they only work in MK set theory, since they use the word "proper class". =D $\endgroup$ – user21820 Jul 2 '15 at 5:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.