Does mathematics become circular at the bottom? What is at the bottom of mathematics? 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?
 A: 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. 
A: 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.
A: 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 (which is in fact a sociohistorical construct). 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.
I want to add a bit about the term "mathematics" itself. What we today call "mathematics" is a product of not just our observations of the world we live in, but also historical and social factors. If the world were different, we will not develop the same mathematics. But in the world we do live in, we cannot avoid the fact that there is no non-circular way to explain some fundamental aspects of the mathematics that we have developed, including equality and repetition and conditionals as I mentioned above, even though these are based on the real world. We can only explain them to another person via a shared experiential understanding of the real world.
A: 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.
A: 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.
A: 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.
A: 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
A: 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.
