Questions tagged [logic]
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 following tags as well, if they fit the question: (model-theory), (set-theory), (computability), and (proof-theory). This tag is not for logical puzzles, use (puzzle).
3,501
questions
7
votes
2
answers
141
views
Relation between primeness and co-primeness of integers
I wonder what this stunning formal analogy between the definitions of being co-prime (for two integers) and being prime (for one integer) might reveal – and how:
$\alpha, \beta$ are co-prime ...
- 18.2k
7
votes
1
answer
327
views
"All ultrafilters are principal" consistent with ZF?
In the article on ultrafilters, Wikipedia claims that
In ZF without the axiom of choice, it is possible that every ultrafilter is principal.{see p.316, [Halbeisen, L.J.] "Combinatorial Set Theory", ...
- 3,900
7
votes
2
answers
3k
views
Logical implication vs Tautological implication
I'm reading Enderton's logic book and have arrived to his deductive calculus for first order logic. After defining it, he presents the following theorem:
$\Gamma\vdash \varphi$ iff $\Gamma\cup \...
- 19.3k
7
votes
6
answers
988
views
Logical issues with the weak law of large numbers and its interpretation
In several probability textbooks I have found what amounts to the following argument:
Let A be an event in some probabilistic experiment. Let p=P(A) be the
probability of this event occurring in ...
7
votes
3
answers
3k
views
What books to use to start studying Mathematical Logic?
I want to study Mathematical Logic. One concept that confuses me, is that implication is equivalent to '-P or Q'. So, I want to start from the book where this idea first started; but I'm not looking ...
- 71
7
votes
4
answers
837
views
Show that $(p \to q) \lor (q \to p)$ is a tautology
I tried to prove that $(p \to q) \lor (q \to p)$ is a tautology.
I used $p$ and $¬q$ as conditions. (Premises 1 and 5)
I managed to get to a solution, but I'm not sure if it's right.
Can you please ...
- 71
7
votes
1
answer
4k
views
Are the quantifier negation rules in first-order logic derivable?
Question: Is is possible to derive $\ \vdash \sim\forall xP(x) \leftrightarrow\exists x \sim P(x) \ $ (or any other version of the quantifier negation rule) axiomatically?
Context: I tutor college ...
- 2,392
7
votes
1
answer
1k
views
Who first proved that the second-order theory of real numbers is categorical?
The second-order theory of real numbers is obtained by taking the axioms of ordered fields and adding a (Dedekind) completeness axiom, which states that every set which has an upper bound has a least ...
- 10.2k
7
votes
4
answers
5k
views
Recommendation on a rigorous and deep introductory logic textbook
In this post, I don't mean any word by its somewhat "mathematical or logical" meaning but just "literally".
It's been three years since I started "formal" mathematics, and now I'm familiar with set ...
- 126
7
votes
1
answer
177
views
Is there a two-variable polynomial capturing complex arithmetic?
My question is whether there is a polynomial in two variables which, in a precise sense, encodes the ring structure of $\mathbb{C}$:
Is there a two-variable complex polynomial $p(x,y)$ such that ...
- 246k
7
votes
1
answer
174
views
Can all relations be defined from symmetric relations?
I have a question about first-order structures over some set $D$. Suppose I have some set of relations $(R_i)_{i\in I}$ where $R_i\subseteq D^{n_i}$, $n_i\in \mathbb{N}$.
I would like to know if ...
- 1,297
7
votes
4
answers
1k
views
Is an argument valid if assuming its premises and conclusion leads to no contradiction?
To show that an argument is valid, why can we not assume that both its premises and conclusion are true then show that there's no contradiction?
Example:
If $x^2=4$ and $x\neq-2,$ then $x=2.$
Proof
...
- 177
7
votes
2
answers
1k
views
ZF Set Theory and Law of the Excluded Middle
I know that the law of the excluded middle is implied in ZFC set theory, since it is implied by the axiom of choice. Taking away the axiom of choice, does ZF set theory (with axioms as stated in the ...
- 253
7
votes
1
answer
899
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 ...
- 312
7
votes
1
answer
11k
views
Any functionally complete sets with XOR?
According to wikipedia, the set {^, ¬} is functionally complete. But is there any 2-set functionally complete set with XOR (e.g. (¬A) ⊕ A is always true).
I'm looking for a 2-set functionally ...
- 2,265
7
votes
4
answers
969
views
When do free variables occur? Why allow them? What is the intuition behind them?
In the formula $\forall y P(x,y)$, $x$ is free and $y$ is bound.
Why would one write such a formula?
Why are free variables allowed?
What is the intuition for allowing free variables?
- 421
7
votes
7
answers
6k
views
Is McGee's counterexample to Modus Ponens accepted by the mathematical community?
In the mid 1980's Vann McGee proposed a counterexample to Modus Ponens:
(a) If a Republicans will win the election, then if Reagan will not
win, Anderson will win. (b) A Republican will win the ...
- 3,400
7
votes
3
answers
2k
views
$\wedge,\cap$ and $\vee,\cup$ between Logic and Set Theory always interchangeable?
In "$\wedge,\cap,\times$ and $\vee,\cup,+$ are always interchangeable?"
It has been shown that arithmetic shouldn't be included. So the new modified question is:
The analogy of $\wedge,\cap$ and $\...
- 9,675
7
votes
1
answer
430
views
The order-type of models of Peano Arithmetic
Let $M$ be a non-standard model of Peano Arithmetic. It is well known, that $(M,<)$ has order type $\mathbb{N}+\xi\mathbb{Z}$, where $\xi$ is a dense, linear order without endpoints.
However not ...
- 1,441
7
votes
2
answers
294
views
A first order logic extended with binding terms like the familiar set descriptors $\{x:\varphi\}$
First order logic comes equipped with two kinds of terms:
Variable: those terms of the form $x$ for some variable $x$, of which there are infinite.
Function application: those terms of the form $f(...
- 11.4k
7
votes
5
answers
3k
views
True or false or not-defined statements
Is it correct to say that for a statement to be either true or false it has to be well defined?
For example: the statement
$$\frac{1}{0} = 1$$
is neither true nor false because the expression on the ...
- 43.6k
6
votes
2
answers
1k
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 ...
- 94.2k
6
votes
2
answers
563
views
Which second-order theories have a model?
A first-order theory has a model if and only if it's consistent.
If a second-order theory has a model then it's consistent, but the converse doesn't hold.
So I'm wondering if there's some condition, ...
- 16.3k
6
votes
3
answers
1k
views
What is the first order axiom characterizing a field having characteristic zero?
In this thread on the axioms of $\mathbb Q$ it's stated that a field having characteristic zero can be written down in first-order logic.
The definition in the logic lecture notes I work with (by ...
- 12.3k
6
votes
2
answers
330
views
Simple Failings of Axiom of Choice in Top
A common reply to the question "why should nonlogicians take note when using the Axiom of Choice (AC)" seems to be "AC fails in many categories, and we want to know that our results continue to hold ...
- 38.2k
6
votes
3
answers
1k
views
Contraposition and law of excluded middle
Does truth-equivalence of an $A \rightarrow B$ and contrapositive $\neg B \rightarrow \neg A$ rely on the law of excluded middle?
- 365
6
votes
2
answers
517
views
What exactly is a parameter in the sense of first-order logic?
What exactly is a parameter in the sense of first-order logic?
What "choices" are there for defining them formally?
My question is at least somewhat similar to this question, but is about ...
- 11.7k
6
votes
1
answer
475
views
Is weak forcing a semantic relation?
I'm vaguely recalling things from innumerable aeons ago:
A condition $p$ forces the negation $\sim\varphi$ of a sentence $\varphi$ precisely if no condition that extends $p$ forces $\varphi$. From ...
6
votes
4
answers
3k
views
Albert, Bernard and Cheryl popular question (Please comment on my theory)
Here is the problem, I think that there is one point that makes the question ambiguous, I think they should explicitly say the reason why Albert knows that Bernard does not know the date.
Case 1: The ...
- 106k
6
votes
2
answers
182
views
Are the two Or-Elims equivalent?
We have:
$\varphi \lor \psi, \neg \varphi \vdash \psi$
$\varphi \lor \psi, \varphi \to \chi, \psi \to \chi \vdash \chi$
Using $2$ and explosion (ex falso), one can prove $1$:
$\varphi \lor \psi$ [...
- 25.1k
6
votes
3
answers
1k
views
A proof of $(\forall x P(x)) \to A) \Rightarrow \exists x (P(x) \to A)$
I recently asked this question. In that question I presented a hand-waving proof as part of the question. There was some confusion as to the validity of my hand-waving proof. So I wanted to make it ...
- 288
6
votes
1
answer
1k
views
Miller's Construction, Partition Principle and Failure of Axiom of Choice
Partition Principle ($PP$) is the following statement:
For all sets $a$, $b$ there is an injection $f:a\rightarrow b$ iff there is a surjection $g:b\rightarrow a$
It is known that $ZF\vdash AC\...
user171016
6
votes
3
answers
2k
views
In what order are chained implications evaluated? (i.e. $a \implies b \implies c$)
Implication does not appear to be associative:
a b c | (a -> b) -> c | a -> (b -> c)
F T F | F | T
F F F | F | T
Is $a \...
- 596
6
votes
2
answers
7k
views
Questions on how to prove that a set of connectives is NOT functionally complete
In my textbook I am introduced to two ways to prove that a set of connectives is functionally incomplete. The first one is to prove that it has a property that not all truth functions do.
I am stuck ...
- 1,458
6
votes
1
answer
635
views
Construction of Ultrafilters
I've been doing a lot of work with ultrapowers and saturation recently. In particular, I am reading chapter 6 of Chang and Keisler as well as Keisler's paper on "Ultraproducts which are not saturated"....
- 6,363
6
votes
6
answers
243
views
Mathematical Logic unusual question
So a true or false question came in my quiz today. It went like this:-
If the moon is made out of chocolate then I am a purple dinosaur.
This is a p implies q statement but i cant really seem to ...
- 191
6
votes
1
answer
203
views
"$\Sigma_1^1$-Peano arithmetic" - does it pin down $\mathbb{N}$?
Let $\mathsf{PA}_{\Sigma^1_1}$ be the theory in second-order logic gotten by extending the usual first-order Peano axioms to include arbitrary $\Sigma^1_1$ formulas in the induction scheme. My ...
- 246k
6
votes
3
answers
2k
views
How to approach number guessing game(with a twist) algorithm?
I posted this on stackoverflow, but was advised to also post here. It's kind of a math/algo question so I think it's kind of stuck between both worlds of math and computer science. I believe this to ...
- 419
6
votes
3
answers
473
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 \; \...
- 1,062
6
votes
4
answers
706
views
Why isn't the equal sign part of the set theory language?
Many books define the language of set theory only based on $\in$.
What about the binary relation '$=$'? Why is it not mentioned as a symbol of the language? Yes, it is part of first-order logic, but ...
- 304
6
votes
3
answers
502
views
Do any authors systematically distinguish between 'theorems' (which have 'proofs') and mathematical 'beliefs' (which have 'evidence')?
I'm interested in understanding the logical structure of mathematics - I want to know how it all fits together. To this end, its interesting to ask whether any authors systematically distinguish ...
- 67.8k
6
votes
3
answers
765
views
A non-arithmetical set?
A set is called arithmetical if it can be defined by a first-order formula in Peano arithmetic. I first encountered these sets when exploring the arithmetical hierarchy in the context of ...
- 10.2k
6
votes
1
answer
371
views
What's wrong with this proof of ZF being inconsistent?
I'm studying (independently) mathematical logic and in investigating
self-referential statements I developed a result which I don't know
how to interpret. I'll use the notation from Enderton's "A
...
- 865
6
votes
4
answers
480
views
How does Hilbert's axiomatization relate to set theory?
I'm studying Hilbert's axiomatization of Euclidean geometry, and I'm trying to combine my current understanding into my knowledge on mathematical logic (not very much).
At the beginning of this ...
- 567
6
votes
3
answers
829
views
Completeness and Incompleteness
Through browsing questions asked in the past about Godel's completeness and imcompleteness theorems, I've come to see that the sense of completeness in both of the theorems are different. However, I ...
- 523
6
votes
1
answer
564
views
Understanding the meaning of $\forall,\exists$ rules in sequent calculus.
I'm stucking in understanding the usage and soundness of the rules for the quantifiers $\forall,\exists$ in sequent calculus.
$\forall-L$: $~~~~~\dfrac{\Gamma,\phi[t]\vdash \Delta}{\Gamma,\forall x\...
- 4,517
6
votes
2
answers
211
views
Problem with a basic lemma in Lambda Calculus
I have some serious problems with Lambda Calculus. In an introduction by Barendregt and Barendsen at page 11 there is the following lemma, whose proof I do not completely get.
$\mathbf{\lambda} \...
- 4,083
6
votes
2
answers
1k
views
Induction without integers (aka Structural Induction)
While composing the following question, I had an "ah-ha" moment. I still want to post the question along with my answer to show what I have learned. Any comments or additional answers will ...
- 2,176
6
votes
2
answers
1k
views
Are there logics without modus ponens?
The question doesn't go beyond the title.
And I don't mean logics that merely just don't have it as a primitive rule - I'm interested in logic where you can't actually use it.
I've searched around ...
- 12.3k
6
votes
1
answer
560
views
The Reals are not interpretable in the complex numbers
Let $L=\{+,\dot{},0,1\}$ be the language of fields. I wish to show that the reals ($N=(\mathbb{R},+,\dot{},0,1)$) are not interpretable in the structure $M = (\mathbb{C},+,\dot{},0,1)$.
I have the ...
user185596