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)

0
votes
2answers
138 views

Does axiom of foundation/regularity protect against Russell-like paradoxes?

In ZF set theory the axiom of regularity (also called axiom of foundation) says that: In all nonempty sets x there is an element y such that x∩y=∅ As I been told that the intention of the axiom ...
14
votes
1answer
360 views

Do you need the Axiom of Choice to assert that every real vector space has a norm?

Math people: This question is 95% answered (the first answer) at Does every $\mathbb{R},\mathbb{C}$ vector space have a norm? and Vector Spaces and AC . The questions, answers, and links found there ...
11
votes
4answers
1k 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
434 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 ...
9
votes
6answers
694 views

Books in foundations of mathematical logic

I'm a civil engineer that spends all of its free time (with the permission of my wife and my two children) studying set theory and mathematical logic. For instance, I've read and enjoyed "Axiomatic ...
9
votes
1answer
794 views

Picking from an Uncountable Set: Axiom of Choice?

Question: Given the real numbers as a set, does it require the (non-finite) Axiom of Choice to pick out an arbitrary single element? What about if we wanted to pick out an integer? What about if we ...
8
votes
1answer
140 views

Every elementary submodel of $H(\aleph_1)$ is transitive

I am trying to solve the first part of Exercise II.17.30 in Kunen's Foundations of Mathematics which asks: Prove that every $A \preccurlyeq H(\aleph_1)$ is transitive. Here we are working over ...
8
votes
2answers
933 views

Gromov-Hausdorff distance and the “set of all sets”

If $X$ and $Y$ are compact metric spaces, then the Gromov-Hausdorff distance, $d_{GH}(X,Y)$, describes how far $X$ and $Y$ are from being isometric. In the Wikipedia article on Gromov-Hausdorff ...
8
votes
2answers
7k views

What is the difference between a predicate and function?

I need to to understand the difference between predicates and functions in the context of Clasual Form Logic in order to define the Herbrand universe. If I have p(x) :- q(f(x)) would I be right in ...
7
votes
1answer
309 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
221 views

Does every nonempty definable finite set have a definable member?

Does every nonempty definable finite set $S$ have a definable member? EDIT: Here are a few ways to formalize the question, so you can pick your favorite and answer it. Assume whatever large ...
7
votes
3answers
837 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
275 views

What's an example of a number that is neither rational nor irrational?

Of course in regular logic, the answer is there aren't any. But in intuitionistic logic, there might be, as seen by this answer: http://math.stackexchange.com/a/1437130/49592. My question is, as per ...
6
votes
2answers
447 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
591 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
751 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
233 views

Why is bounded induction stronger than open induction?

It seems to me that any formula in the language of first-order arithmetic which has only bounded quantifiers can be written as a formula without any quantifiers. For instance, "There exists an n ...
6
votes
3answers
587 views

What's the problem this logic

In Lewis Carroll's story "What the Tortoise Said to Achilles," the swiftfooted warrior has caught up with the plodding tortoise, defying Zeno's paradox in which any head start given to the tortoise ...
6
votes
2answers
283 views

“Completeness modulo Godel sentences”?

So this has been bugging me for roughly four years. When I was an undergraduate, I attended a colloquium in which the speaker was a 'cheerleader' for AD (the axiom of determinacy- an alternative to ...
6
votes
3answers
664 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 ...
6
votes
5answers
485 views

Mathematician (non-logician) seeks reference for Gödel's incompleteness theorems

I would like to learn more about the proofs of Gödel's incompleteness theorems. I have read and am rereading Gödel's proof by Nagel, Newman, and Hofstadter. I like it very much, but I would like ...
6
votes
2answers
278 views

Ideas about Proofs

If there are two different proofs for one theorem, at some level are the two proofs the same, or can they be fundamentally different? In other words, if you have two proofs of a theorem, can one show ...
5
votes
1answer
74 views

Does $\mathrm{PA}^-$ prove all true literal sentences of basic arithmetic?

By "the literal sentences of basic arithmetic" let us mean sentences like $$3+4=7,\;\; 2\cdot 3 = 3\cdot 2, \;\;S(2)=3$$ where for example $3$ is shorthand for $S(S(S(0)).$ Note that some literal ...
5
votes
2answers
233 views

What holds in a deductively complete system?

I read an article which presented some system with axioms and inference rules (I don't know if that type of system have a term for in English). The article stated that the system is "deductively ...
5
votes
2answers
6k views

What is the difference between an axiom and a postulate?

I hear about axioms in set theory and postulates in geometry, but they seem like the same thing. Do they mean the same thing but then are used in different instances or what? Is one word more ...
5
votes
1answer
488 views

Difference between elementary logic and formal logic

In Kelley book on topology, in the appendix on elementary set theory, he says in the second paragraph, that "a working knowledge of elementary logic is assumed, but acquaintance with formal logic is ...
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
2answers
88 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
1answer
204 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
286 views

Natural numbers in Set Theory

We seem to accept the fact $(\omega,+,\times,<,0,1)^{V}$, where $V:=x=x$ is the set theoretic universe, properly reflects what is intuitively understood to be the set of natural numbers, i.e. we ...
4
votes
2answers
209 views

Formal definition of effective proof

I am someone who likes precise definitions for mathematical terminology. So, is there some text where there is a precise definition of an effective proof? The notion is vague to me.
4
votes
1answer
272 views

Some questions regarding Smullyan's proof of Compactness Theorem for propositional logic

According to Jeremy Avigad's description of Gödel's original argument (http://www.andrew.cmu.edu/user/avigad/Papers/goedel.pdf) the second step in the proof establish the following result : If a ...
4
votes
2answers
170 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
7answers
506 views

Can $P \implies Q$ be represented by $P \vee \lnot Q $?

Source: p 46, How to Prove It by Daniel Velleman Though the author writes $Q$ (the original apodosis) as 'You'll fail the course', for brevity I shorten $Q$ to 'You fail'. Let $P$ be the ...
4
votes
1answer
113 views

Is the set theory (ZF) a structure?

According to the definition, generally speaking, a structure $\langle A;R;F,C\rangle$ is such that $A$ is a non-empty set, $R$ is the set of relations, $F$ is the set of functions, and $C$ is a set of ...
4
votes
3answers
434 views

How to logically analyze the statement: “Nobody in the calculus class is smarter than everybody in the discrete math class.”

I am self-studying Daniel Velleman's "How to Prove It." In the exercises for section 2.1, for question # 1b, I got a different answer than he did (his answer is in the back of the book). I think ...
4
votes
1answer
325 views

System with infinite number of axioms

Assume we have a set of axioms $A_0$. There exists a statement that can be formulated with these axioms that cannot be proven to be true with this system. Assume we give such a statement axiomatic ...
4
votes
1answer
356 views

Is the formal semantics of first-order logic ambiguous?

When defining the semantics of propositional and particularly first-order logic, it has always made me uneasy when reading, for example: $$M \models A \lor B \quad\text{iff}\quad M \models A \text{ or ...
4
votes
4answers
2k views

The relation between logic and algebra.

What's the relation between logic and algebra? Can one be thought of as a special case of the other?
4
votes
3answers
368 views

Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows: build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
4
votes
3answers
710 views

First order logic.

In Artificial intelligence, I saw the following question and answer in website. Question: Politicians can fool some people all of the time, and they can fool all people some of the time, ...
4
votes
3answers
328 views

Prove: $ ((A \rightarrow B) \rightarrow A) \rightarrow A ) $

How could I derive the following proposition: $$ ((A \rightarrow B) \rightarrow A) \rightarrow A ) $$ using any of the following axioms: 1) $A→(B→A)$ 2) $(A→(B→C))→((A→B)→(A→C))$ 3) ...
4
votes
2answers
432 views

Turing's 1939 paper on ordinal logic

I am reading Turing's 1939 paper on ordinal logic ("Systems of Logic Based on Ordinals", A. M. Turing, Proc. London Math. Soc. ser. 2, 45 (1939), #1, 161-228, DOI: 10.1112/plms/s2-45.1.161.) ...
4
votes
3answers
3k views

Negation of Uniqueness Quantifier

Is there a negation of uniqueness quantifier? I need to negate an expression which includes a uniqueness quantifier.
4
votes
2answers
481 views

True, false, or meaningless?

Are the following two assertions always true, always false or meaningless? $\exists i \in \emptyset$ $\forall i \in \emptyset$ Because it seems that one encounters expressions of this kind fairly ...
4
votes
1answer
136 views

does the definition of model depend on a theory or just a signature?

Σ:signature T:Σ-theory For M:Σ-model which satisfies T, is it proper to name it “Σ,T-model” or “Σ-model satisfying T”? In comparison, in the context of Lawvere theories, any Lawvere theory L ...
3
votes
1answer
84 views

What properties are shared by isomorphic universal algebras?

There is a consensus, that "isomorphy" (the "is isomorphic to"-relation) is the right kind of sameness between universal algebras (say groups, (single-sorted) vector spaces, lattices, ...), because ...
3
votes
2answers
150 views

Ordinals - motivation and rigor at the same time

Can someone provide a description of ordinals within ZFC in a rigorous way that exhibits motivation? Every description or explanation I see in the literature or on the Internet is either too formal ...
3
votes
2answers
53 views

Set theory (containing Power Set) Need Help in a proof

I am confirming whether my proof is correct or not and need help. If $ A \subseteq 2^A , $ then $ 2^A \subseteq 2^{2^A} $ Proof: Given: $ \forall x ($ $ x\in A \rightarrow \exists S $ where $ ...