Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

4
votes
5answers
181 views

Book about different kind of logic

I'm searching for a book that talks about different kind of logic ( esoteric and particular one too ) and their uses and differences. Does such a book exist?
4
votes
1answer
410 views

What is the Tarski–Grothendieck set theory about?

The wikipedia article on Tarski-Grothendieck set theory states: "[Tarski's axiom] also implies the existence of inaccessible cardinals, thanks to which the ontology of TG is much richer than that ...
4
votes
1answer
887 views

Independence of Axioms in an axiomatic system

How do we show that we are using independent axioms in an axiomatic systems i.e $A\rightarrow (B \rightarrow A)$ $(A\rightarrow (B\rightarrow C)) \rightarrow ((A\rightarrow B)\rightarrow ...
4
votes
3answers
774 views

Proof by contradiction and Incompleteness

Does Gödel's incompleteness theorem imply that proofs by contradiction don't work?
3
votes
2answers
11k views

Is an anti-symmetric and asymmetric relation the same? Are irreflexive and anti reflexive the same?

I don't understand the difference between an anti symmetric and asymmetric relation. From my understanding, it is asymmetric if there is not any element where: if (x,y) (y,x). But what if you have ...
3
votes
2answers
321 views

Logic and number theory books

I've recently decided to start preparing for uni, so I figured I need to learn logic and some number theory. I picked up Burton's Elementary Number Theory and wasn't quite comfortable with it, seemed ...
3
votes
2answers
886 views

Proving and understanding the Fixed point lemma (Diagonal Lemma) in Logic - used in proof of Godel's incompleteness theorem

http://en.wikipedia.org/wiki/Diagonal_lemma I am wondering about the proof of the "Fixed-Point Lemma" $\text{Mod } \Sigma$ is the class of all models of $ \Sigma$. $\text{Th Mod } \Sigma$ is the set ...
3
votes
3answers
277 views

what are first and second order logics? [duplicate]

The only knowledge I have on logic is due to a book I read a couple of years ago called Introduction to logic: and to the methodology of deductive sciences by Alfred Tarski. And in it he talks about ...
3
votes
1answer
248 views

Negation of a quantified statement

I would like to negate the following: $\exists x, \forall y, \forall z ((F(x,y) \land G(x,z)) \rightarrow H(y,z))$ Would the following proposed solution be correct? (1) First simplify what is in ...
3
votes
3answers
592 views

Factoring out universal quantifier in combination with an implication

I just began studying maths and so far everything made sense after tinkering around with it a little bit (e.g. $ \lnot(\forall x \in M : A(x)) = \exists x \in M : \lnot A(x) $ thinking "not all math ...
2
votes
1answer
653 views

How to prove $2+2=4$ using axioms of real number system?

How to prove $2+2=4$ using axioms of real number system? How do you make sense of the axioms for real number system when you cannot define the operations. You don't give an algorithm to calculate the ...
2
votes
1answer
231 views

$V_k$ being a model of ZFC whenever $k$ is strongly inaccessible

ZFC implies that the $V_k$ is a model of ZFC whenever $k$ is strongly inaccessible.. So if $k$ is weakly inaccessible, it can't be a model of ZFC? Why is it like this? And ZF implies that ...
2
votes
2answers
242 views

Propositional Calculus and “Lazy evaluation”?

I want to formalize a system, and currently I don't know, if I can use propositional calculus in my case. At first, I though that I need a simple conjunction. $A \wedge B$ However, there is a ...
1
vote
1answer
617 views

Gödel, Escher, Bach: $ b $ is a power of $ 10 $.

I’d like to verify if my formula correctly expresses that a number is a power of $ 10 $, using the $ \sf{TNT} $ language provided by Hofstadter in his famous book Gödel, Escher, Bach: An Eternal ...
16
votes
3answers
1k views

What are some examples of theories stronger than Presburger Arithmetic but weaker than Peano Arithmetic?

What are some examples of theories stronger than Presburger Arithmetic but weaker than Peano Arithmetic? Are all such theories decidable? If not, by what methods other than Gödelization can ...
11
votes
1answer
161 views

What's an Isomorphism?

I'm familiar with the definition (inverses and bijections, preserving operations) in the context of groups and vector spaces, the hoeomorphism of topological spaces, and have some feeling for the ...
11
votes
3answers
2k views

Is there an example for an undefinable number?

This question is motivated by a comment of Robert on the question Can any Real number be typed in a computer? : Can you "think of" an undefinable number? – Robert Israel I would like to ...
11
votes
4answers
2k views

What is the purpose of free variables in first order logic?

I understand the difference between free and bound variables, but what are free variables actually useful for? Can't you use quantifiers to express everything that you would want to express with both ...
11
votes
5answers
442 views

what is the definition of $=$?

what is the definition of $=$? Above is the question that I would like to be answered, below are some of my thoughts. I've been thinking about what it means to say $A = B$ I came to this from ...
10
votes
1answer
274 views

Is this a characterization of well-orders?

While grading some papers and thinking about a question related to well-orders (in particular, pointing a mistake in a solution), I came to think of a reasonable characterization for well-orders. I ...
10
votes
1answer
242 views

Independence results that cannot be established by forcing.

I read the Wikipedia article on Absoluteness recently and found mention of Shoenfield’s Absoluteness Theorem, which states that if $ \phi $ is any $ \Sigma^{1}_{2} $- or $ \Pi^{1}_{2} $-sentence of ...
8
votes
3answers
369 views

Is the “domain of discourse” in axiomatic set theory also a “set”?

The domain of discourse is defined by Wikipedia as the "set of entities over which certain variables of interest in some formal treatment may range." However, I believe we could not call the domain of ...
8
votes
1answer
1k views

Is “A and B imply C” equivalent to “For all A such that B, C”?

So I mostly study PDE, harmonic analysis, image processing, and so on, but for whatever reason I decided to be a TA for an undergraduate "introduction to proofs" course this semester. I suppose I ...
7
votes
2answers
208 views

The dense topology

The definition of the dense topology confuses me. If $C$ is a category and $X \in C$, a sieve $S$ on $X$ is a covering for the dense topology iff for every $f : Y \to X$ there is some morphism $g : Z ...
7
votes
3answers
538 views

Does a proof by contradiction always exist?

Good day, Usually, proofs by contradictions are the easier, and sometimes, even the only ones available. However, there are cases where the easiest proof is not the proof by contradiction. For ...
7
votes
1answer
329 views

Is it possible to formalize (higher) category theory as a one-sorted theory, just like we did with set theory?

Set theory is typically formalized as a one-sorted theory without urelements. Is it possible to do the same with category theory or higher category theory, formalizing the whole affair as a theory ...
7
votes
1answer
596 views

Why is quantified propositional logic not part of first-order logic?

If propositional logic is extended by quantifiers ($\forall$ and $\exists$) without adding functions and relations (or even objects and equality, i.e. we quantify over propositional-variables), the ...
7
votes
3answers
917 views

Why is Kunen inconsistency at the top of Cantor's upper attic?

Motivation: I have reproduced part of page 396 and 397 from Handbook of Mathematical Logic below: So if we start with a concept of number and play the game of naming the largest one, does Kunen ...
6
votes
1answer
148 views

When was contemporary logical notation established

When contemporary fundamental logical notation was established? I mean basic symbols as used nowadays $\iff\implies\land\lor\lnot\forall\exists\vdash\models$.
6
votes
1answer
98 views

Who first discovered that some R.E. sets are not recursive?

Who first discovered that some recursively enumerable sets are not recursive, or equivalently that some semidecidable sets are undecidable? And in what context? Was the earliest formulation of this ...
6
votes
2answers
531 views

Contraposition in intuitionistic logic?

I read that contraposition $\neg Q \rightarrow \neg P$ in intuitionistic logic is not generally equivalent to $P \rightarrow Q$. If this is right, in what case can this contraposition ...
6
votes
3answers
682 views

Give a proof that “p & ~p” implies “q”?

Context: This is not a textbook or homework problem. I was hoping you younger folks could help my tired old brain. "Everybody knows" a contradiction implies anything. What I'm looking for is a ...
6
votes
5answers
862 views

Proving Undecidability of first order logic without first proving it for arithmetic.

All text I have read prove the Undecidability of first order logic a bit as an afterthought and after having proved the incompleteness and Undecidability of (Peano) Arithmetic. This proof also ...
6
votes
1answer
424 views

distribution of categorical product (conjunction) over coproduct (disjunction)

In the classical and intuitionistic propositional calculi, it is straightforward, using natural deduction, to derive $((A \land C) \lor (B \land C))$ from $(A \lor B) \land C$: Assume $(A \lor B) ...
6
votes
1answer
398 views

Difference between elementary submodel and elementary substructure

This is a really "elementary" question, forgive the pun. What is the difference between an elementary submodel and an elementary substructure (in first-order Logic)? Sincere thanks for help.
6
votes
2answers
312 views

Is this a good way to explicate Skolem's Paradox?

Skolems Paradox shows an ostensible conflict between Cantor's Thoerem (CT) and the downward Löwenheim–Skolem Theorem (ST). CT: for any set $A$, the powerset of $A$, $P(A)$, has a strictly greater ...
6
votes
2answers
404 views

Puzzle: Can arithmetic be axiomatized with a single two-term relation?

Following my question about defining multiplication in terms of divisibility, can all of arithmetic be axiomatized with a single two-term relation? Asaf Karagila comments on my question that the ...
6
votes
3answers
708 views

Applications of descriptive set theory to mathematical logic?

The Wikipedia article Descriptive Set Theory asserts it has applications to logic, but gives no examples. Kechris' text Classical Descriptive Set Theory does not discuss logical applications, judging ...
5
votes
1answer
253 views

How far can we get without a foundation, using just first-order logic?

I think its interesting to ask how far we can get without committing to any particular foundations, using just first-order logic. For instance, we can prove theorems in this way about partially ...
5
votes
2answers
259 views

What are the main relationships between exclusive OR / logical biconditional?

Let $\mathbb{B} = \{0,1\}$ denote the Boolean domain. Its well known that both exclusive OR and logical biconditional make $\mathbb{B}$ into an Abelian group (in the former case the identity is $0$, ...
5
votes
2answers
3k views

Predicate vs function

In logic, what is the difference between a predicate and a function? To be specific, I am just interested in First Order Logic. Thanks!
5
votes
4answers
3k views

Prove that a set of connectives is inadequate

It is relatively easy to prove that a given set of connectives is adequate. It suffices to show that the standard connectives can be built from the given set. It is proven that the set $\{\lor, \land, ...
5
votes
3answers
2k views

Infinite processes riddle

A train with infinitely many seats, one for each rational number, stops in countably many villages, one for each positive integer, in increasing order, and then finally arrives at the city. At the ...
4
votes
1answer
69 views

Quantification over the set(?) of predicates

When learning set theory and logic, one fact that popped up a handful of times was that we did not quantify over predicates. To quote the notes I took in class on the axiom of unrestricted ...
4
votes
2answers
116 views

Why are maximal consistent sets essential to Henkin-proofs of Completeness?

As well-known, the Completeness theorem states that $$\Gamma \vDash \varphi \Rightarrow \Gamma \vdash \varphi$$ The proof we find in didactic textbooks are usually called "Henkin-proofs". Let ...
4
votes
2answers
110 views

Elementary equivalence of $\mathbb{Z}^{n}$

I have a question in model theory where I need to prove that $\mathbb{Z}^{n} \not\equiv \mathbb{Z}^{m}$ (= not elementarily equivalent) if $n\neq m$ in the language of groups $L = \{\circ ,^{-1},0 ...
4
votes
4answers
777 views

Which texts do you recommend to study universal algebra and lattice theory?

As I'm planning to study some algebraic logic (a lot of!), I found that some knowledge of universal algebra, lattice theory and boolean algebras is a must. I wonder if you have any recommendation to ...
4
votes
1answer
215 views

Defining new symbols (abbreviations) in first-order logic

In first order logic it is common (and just about necessary) to introduce new symbols which have been defined in terms of the "fundamental" symbols of a given theory. For instance, the signature of ...
4
votes
2answers
175 views

Reading on Mathematical Logic

I am looking for books to read, so as to dive into mathematical logical and related disciplines like set theory, model theory, and topos theory. I have a decent background in category theory and ...
4
votes
3answers
202 views

A terminology to analysts

When analysts say "$\epsilon$ (or whatever greek symbol) can be chosen arbitrary small", do they really just mean we can take $\epsilon = 0$ or $\epsilon \to 0$ later? When I asked myself this ...