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
1answer
279 views

Model of Robinson Arithmetic but not Peano Arithmetic

I am curious how can structure of with linear successor function that do not admin induction looks like. In other words I would like to see structure of Peano Arithmetic without induction. I believe ...
4
votes
1answer
237 views

Beginner material for mathematical logic

I am looking for study and beginner material to study mathematical logic. I understand that it is a very broad topic but I would like to know what the best path there is to learning mathematical logic....
4
votes
1answer
72 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
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 ...
4
votes
1answer
229 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
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
330 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) $((¬B)→(&...
4
votes
1answer
209 views

Why every member of ${}^{*}\mathbb{R}$ is infinitely close to some member of ${}^{*}\mathbb{Q}$

Let $\mathbb{Q}$ be the set of rational numbers. Show that every member of ${}^{*}\mathbb{R}$ is infinitely close to some member of ${}^{*}\mathbb{Q}$. This is an exercise on page 180, A ...
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
179 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
1answer
348 views

Are proofs by contradiction just more powerful or just more convenient than other proofs?

One of my friends who got 100 % in logic told me, "when in doubt use contradiction". When I do proofs I personally find using contradiction a lot easier. Also, from the fact that a lot of famous ...
3
votes
2answers
187 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
1answer
633 views

Monotone self-dual boolean functions clone

It's said on Wikipedia page about Post's lattice that DM clone(all monotone self-dual functions) has majority function $(xy + xz + yz)$ as one of its bases. What is the proof of this fact?
3
votes
1answer
7k views

Boolean algebra operation precedence?

In my discrete mathematics class we wrote down the truth table for some Boolean functions and in that table they go in the following order: ¬, ∧, ∨, →, ~, ⊕, |, ↓ So, I assumed that this is the ...
3
votes
3answers
345 views

When and where the concept of valid logic formula was defined?

I was stimulated by a recent question about Gödel Completeness Theorem. All my citations are from Jean van Heijenoort (editor), From Frege to Gödel : A Source Book in Mathematical Logic (1967). ...
3
votes
2answers
181 views

Different models of ZF disagree on equality of explicit recursively enumerable sets

Assuming that ZF is consistent, are there two recursively enumerable sets defined by explicit enumerators that are the same in one model of ZF+Con(ZF) but different in another model of ZF+Con(ZF)? If ...
3
votes
2answers
56 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 $ ...
3
votes
1answer
226 views

Models of real numbers combined with Peano axioms

Suppose you take the axioms for a Dedekind-complete ordered field and weaken the Dedekind-completeness axiom to the corresponding weaker first-order axiom schema (e.g. replace the left and right sets ...
3
votes
1answer
119 views

Justification of ZFC without using Con(ZFC)?

I saw this post by Carl Mummert, which describes how one can 'see' the reasonableness of ZFC, via iterating the power-set operation starting from the empty set. However, this iterations proceed in ...
2
votes
2answers
151 views

substituting a variable in a formula (in logic)

What kind of mathematical object is this substitution(is it a function or what). We assuming set of variables exist.
2
votes
1answer
71 views

Prove this proposition concerning a theory with ∀∃-axiomatization part II.

This is a continuation of a problem I asked yesterday seen here: Prove this proposition concerning a theory with ∀∃-axiomatization The setting is reproduced below for easy reference. Setting A ...
2
votes
2answers
2k views

What does a condition being sufficient as well as necessary indicates?

I have a question in a book I am solving(Discrete Structures by Kolman, Busby & Ross). I am unable to make sense from the question. It is stated below, Show that k is odd is a necessary and ...
2
votes
1answer
123 views

$A⇒(B \lor C)$ and $[(A \Rightarrow B) \lor (A \Rightarrow C)]$

[(A⇒ B∨C)] ⇒ [A⇒(¬B⇒C)] ⇒[(A⇒¬B)⇒(A⇒C)] ⇒ [¬(A⇒¬B)∨(A⇒C)]⇒[(A∧B)∨(A⇒C)] [(A⇒B)∨(A⇒C)] is equivalent to A⇒(B∨C). Can I prove [(A∧B)∨(A⇒C)] ⇒ [A⇒(B V C)]? or is there problem in the proof above ...
2
votes
2answers
1k views

What is definability in First-Order Logic?

Can someone explain to me the definition of definability in first-order logic in simple terms and with an example? I would appreciate this. I just want to really understand this. Thank you. Here is ...
2
votes
8answers
820 views

Are the real numbers really uncountable?

Consider the following statement Every real number must have a definition in order to be discussed. What this statement doesn't specify is how that loose-specific that definition is. Some examples ...
2
votes
3answers
235 views

Recommendations for Intermediate Level Logics/Set Theory Books

I currently don't know what books I should read after having studied elementary logics/set theory, so I'd be glad if I can get some recommendations. My classes used the following two books for logics/...
2
votes
2answers
329 views

Example of a proof using the axiom of commensurability

I'm teaching our intro to proofs course (well, one of them) and one of the classic illustrations of an overturned "axiom" is the Greek axiom of commensurability, which stated in geometric terms the ...
2
votes
1answer
102 views

Quantifier-free induction and comparison with $\sqrt{2}$

I am trying to understand quantifier-free induction in the system called PRA - primitive recursive arithmetic which states the following: $$ \frac{ \varphi[0] \quad \varphi[n] \implies \varphi[Sn]}{\...
2
votes
1answer
350 views

Free boolean algebra

Consider the following definition: Let $X$ be a set and $e : X \mapsto A$ a mapping to a boolean algebra $A.$ We say that $A$ is free over $X$ (with respect to $e$) if for every mapping $f:X ...
2
votes
2answers
812 views

Are axioms and rules of inference interchangeable?

There is an equivalence between cellular automata and formal systems, you can code one into the other and vice versa. But in the the cellular automata (CA) the rules of inference are fixed and are ...
2
votes
3answers
2k views

What is the Conjunction Normal Form of a tautology?

I have a tautology and I need to write its CNF(Conjunction Normal Form). Since its a tautology CNF will not have any element. So ...
2
votes
2answers
244 views

Are non-standard models always not well-founded?

Are non-standard models of ZF set theory by definition always not well-founded? And it seems it is, because it must be. But then, Wikipedia says that when there is a set that is a standard model of ...
2
votes
2answers
444 views

prove $(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A)$ in Hilbert System

I'm looking for a way to prove : $$(A \rightarrow B) \rightarrow (\neg B \rightarrow \neg A)$$ From the axioms : A1) $(A) \rightarrow ( B \rightarrow A )$ A2) $(A \rightarrow ( B \rightarrow C ))...
1
vote
1answer
122 views

Reference request for the independence of $ \text{Con}(\mathsf{ZFC}) $.

Gödel’s Second Incompleteness Theorem says that if $ \mathsf{ZFC} $ is consistent, then $ \mathsf{ZFC} \nvdash \text{Con}(\mathsf{ZFC}) $, i.e., $ \text{Con}(\mathsf{ZFC}) $ is not provable in $ \...
1
vote
1answer
52 views

Infinite Spectrum Problem

Let us work in a class theory like NBG. For a given first order sentence $\phi$ define $\infty\text{-spectrum}(\phi)$ to be the class of all cardinal numbers $\kappa$ for which there is a model $M$ ...
14
votes
1answer
380 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 ...
12
votes
10answers
716 views

Quantifier Notation

What's the difference between $\forall \space x \space \exists \space y$ and $\exists \space y \space \forall \space x$ ? I don't believe they mean the same thing even though the quantifiers are ...
11
votes
4answers
637 views

Clarification of a remark of J. Steel on the independence of Goldbach from ZFC

On page 424 of the following paper: S. Feferman, Harvey M. Friedman, P. Maddy and John R. Steel, ``Does Mathematics Need New Axioms?'' The Bulletin of Symbolic Logic, Vol. 6, No. 4 (Dec., 2000), pp. ...
11
votes
1answer
471 views

Injective function and ultrafilters

An exercise left by my teacher let me think that the following statement is true: Let $\mathcal{U}$ be an ultrafilter on $\mathbb{N}$. Then every injective function $g:\mathbb{N}\rightarrow\...
10
votes
1answer
858 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 ...
10
votes
6answers
420 views

Why is “for all $x\in\varnothing$, $P(x)$” true, but “there exists $x\in\varnothing$ such that $P(x)$” false? [duplicate]

There exists an $X\in A$ such that $P(X)$. When $A$ is the empty set then this statement is false because there is nothing in $A$ that when plugged in for $X$, makes $P(X)$ come out True. However, ...
10
votes
2answers
779 views

Visualizing Concepts in Mathematical Logic

If you were forced to speculate or offer anecdotal evidence, how would you say excellent practicioners of mathematical logic coneptually grasp statements like: $$ \vdash ((P \rightarrow Q) \...
8
votes
1answer
385 views

$F[t]$ has undecidable positive existential theory in the language $\{+, \cdot , 0, 1, t\}$

Consider the ring $F[t, t^{-1}]$ (the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$). Theorem 1. Assume that the characteristic of $F$ is zero. Then the existential theory ...
8
votes
1answer
172 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
3answers
293 views

Why is the universal quantifier $\forall x \in A : P(x)$ defined as $\forall x (x \in A \implies P(x))$ using an implication?

And the same goes for the existential quantifier: $\exists x \in A : P(x) \; \Leftrightarrow \; \exists x (x \in A \wedge P(x))$. Why couldn’t it be: $\exists x \in A : P(x) \; \Leftrightarrow \; \...
8
votes
2answers
1k 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 ...
7
votes
1answer
266 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 <...
7
votes
1answer
231 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
1answer
1k views

Why are Hornsat, 3sat and 2sat not equivalent?

I have been reading a little bit about complexity theory recently, and I'm having a bit of a stumbling block. The horn satisfiability problem is solvable in linear time, but the boolean satisfiability ...
6
votes
1answer
176 views

Intuitionistic proof of $\neg\neg(\neg\neg P \rightarrow P)$

How do you prove $\neg\neg(\neg\neg P \rightarrow P)$ in intuitionistic logic? I know this statement to be intuitionistically provable because of Glivenko's theorem. However, I wish to prove it ...