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
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
177 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
219 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
126 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 $\...
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
181 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
2answers
55 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
115 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 ...
3
votes
3answers
339 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
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 ...
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
1answer
345 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
3answers
224 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
240 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
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
797 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
1answer
70 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
321 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
2answers
441 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 ))...
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
2answers
1k 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
2answers
150 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
100 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]}{\...
1
vote
1answer
120 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
51 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$ ...
1
vote
8answers
810 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 ...
14
votes
1answer
377 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
712 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
1answer
470 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\...
11
votes
4answers
636 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. ...
10
votes
3answers
917 views

Difference between proof of negation and proof by contradiction

I stumbled across this interesting article titled "Proof of negation and proof by contradiction" in which the author differentiates proof by contradiction and proof by negation and denounces an abuse ...
10
votes
1answer
846 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
2answers
773 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) \...
10
votes
6answers
410 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, ...
8
votes
1answer
171 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
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 ...
8
votes
3answers
291 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
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 ...
7
votes
1answer
230 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
5answers
490 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
3answers
581 views

Undecidable conjectures

Suppose we work with a conjecture saying that something is true for any natural $n$. For each $n$ there exists an algorithm of finite length allowing one to decide whether it is true or false for this ...
6
votes
2answers
282 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 ...
6
votes
1answer
254 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
1answer
175 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 ...
6
votes
2answers
296 views

Henkin vs. “Full” Semantics for Second-order Logic and Multi-Sorted First Order Interpretations

In this paper by Jeff Ketland, he notes: With Henkin semantics, the Completeness, Compactness and Löwenheim-Skolem Theorems all hold, because Henkin structures can be re-interpreted as many-sorted ...
6
votes
1answer
377 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
296 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 ...
5
votes
1answer
232 views

Jech's proof of Silver's Theorem on SCH

Jech's textbook proves Silver's Theorem–that if the Singular Cardinals Hypothesis holds for all singular cardinals of countable cofinality, then it holds for all singular cardinals–by breaking up the ...