Skip to main content

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).

Filter by
Sorted by
Tagged with
-1 votes
0 answers
23 views

Foundations of Math - Algebraic Logic

Has there been any recent work using algebraic logic as opposed to set theory or homotopy type theory for a foundation of mathematics?
2 votes
4 answers
1k views

Paradox in Prisoner's dilemma

I have come across a curious paradox concerning The Prisoner's Dilemma Suppose 4 things : prisoners A and B are rather stupid people and decide to use an artificial intelligence program to decide ...
0 votes
0 answers
24 views

Number of lattices over a finite set

I'm interested in finding a general formula for the number of lattices possible over a finite set $S$ as a function of the set's cardinality. For instance, how many lattices over $\{1, 2, 3\}$ are ...
-1 votes
2 answers
116 views

Is my understanding of the definition of a metric space correct?

The definition of metric space that I am using is as follows: Let $X$ be a nonempty set. A function $d:X\times X\to \Bbb R$ is said to be a metric or a distance function on $X$ if $d$ satisfies the ...
0 votes
0 answers
27 views

Is there a propositional proof system that is not known to be simulated by extended Frege?

As far as I know, it's not know yet whether any optimal propositional proof system exists. That means it's unknown whether extended Frege simulates every other propositional proof system. This leads ...
1 vote
2 answers
62 views

Proving the Negation of a Formula does not Require the Formula as an Assumption

The following lemma states that if we can prove negation of a Well Formed Formula (WFF) $\alpha$ by assuming the formula itself, then we can do it without such an assumption. Lemma. Let $\Sigma$ be a ...
3 votes
1 answer
60 views

Studying modal logic using category theory

When reading about modal logic, namely general frames and algebras, I've been seeing a lot of potential functors and/or universal properties. Like constructing an algebra with Boolean operators from a ...
1 vote
1 answer
70 views

A property of $\lt$ in Primitive recursive arithmetic

In Primitive recursive arithmetic (PRA), we can introduce $\lt$ by introducing its representing function $K_{\lt}$, where $K_{\lt}(x,y) =sg(x+1-y)$. Here "sg" and "-" are the ...
7 votes
1 answer
423 views
+250

Functional completeness over a structure

The set of propositional connectives $\{\wedge,\vee\}$ is of course not functionally complete; correspondingly, the logical vocabulary $\{\forall,\exists,=,\wedge,\vee\}$ is not sufficient for ...
-2 votes
2 answers
88 views

in definition of assigment, what's means 'except possibly a'?

in frist-order logic, part of assignments practice represent like this "if 𝜙is ∀𝛼𝜓, where 𝛼 is a variable, then ⊨vℳ 𝜙 iff for every assignment 𝑣' that agrees with 𝑣 on the values of every ...
0 votes
0 answers
39 views

First-Order Logic With Extensional Set Membership

It is common to sometimes present First-Order Logic with equality and sometimes without. Adding equality has some nice benefits, including the ability to talk about some number of things, e.g. $\...
-2 votes
2 answers
271 views

Can we modify the Peano axioms like this? [closed]

I am wondering if the following modifications of the Peano axioms result in a set of axioms equivalent to the Peano axioms, in the sense that any set of numbers satisfies these modified axioms if and ...
0 votes
1 answer
139 views

Negating "He will sink unless he swims" [closed]

I want to negate "He will sink unless he swims" using the formula $$\neg (P \Rightarrow Q) \equiv P \wedge (\neg Q).$$ But first, how do we write that statement as if-then statement?
5 votes
1 answer
127 views

Why do theories extending $0^\#$ have incomparable minimal transitive models?

This question says that the theory ZFC + $0^\#$ has incomparable minimal transitive models. It proves this as follows my emphasis): [F]or every c.e. $T⊢\text{ZFC\P}+0^\#$ having a model $M$ with $On^...
1 vote
0 answers
36 views

Is this restricted variant of predicate logic decidable, but expressive enough to be encoded by STLC ($\lambda \to$)?

As in the question, is it the case that a predicate calculus with these properties is decidable? n-ary predicates quantifiers finite domain of discourse impredicativity disallowed no function terms ...
0 votes
0 answers
34 views

Prove: Let α be a proposition containing only Boolean connectives ∧,∨. Then any assignment satisfying α must also satisfy f(α)

The question: Let f be a mapping that takes as input a Boolean proposition (no quantifiers) and outputs the same proposition but with all ∧ symbols replaced by ∨. For example: $$ f(x_1 ∧ (x_2 → ¬x_5) =...
0 votes
0 answers
75 views

If a contrapositive can be shown, then is a direct proof always possible?

If we can prove that $¬Y \implies ¬X,$ then is it always possible to prove that $X \implies Y$ without first proving that $¬Y \implies ¬X$ ? Motivation: when studying analysis, there are some problems/...
13 votes
5 answers
3k views

How do we define addition?

I've been trying to learn naive set theory through a YouTube series by 'The Bright Side of Mathematics'. So far, I've been able to understand successor maps and the definition of $\mathbb{N}_{0}$. I ...
1 vote
4 answers
153 views

Symbolising an following argument with two Therefore's

I am trying to translate the following argument to logic symbols to verify its validity using truth tables: If the supplier supplies the seeds, then if the seeds are sown on time, then the plants ...
2 votes
1 answer
379 views

What does Feferman-Vaught say $\textbf{exactly}$ about definable subsets of a direct product of two structures?

Below I reproduce a consequence of the Feferman-Vaught theorem, taken from Wilfrid Hodges' book Model Theory: Corollary 9.6.4: Let $L$ be a first-order language, let $A$ and $B$ be $L$-structures and ...
1 vote
1 answer
54 views

Proving "if Q is derivable from P, then all sentential interpretations of P->Q are true" from Suppes criterion I

Question. I have trouble understanding how Patrick Suppes in his "Introduction to logic" derives the important sentence (A2) from another two, (A1) and (CrI). Introduction. He uses criterion ...
-2 votes
0 answers
37 views

Marked numbers on a circle [closed]

On a circle, write all the numbers in ascending order from $1$ to $1000$, clockwise. Starting from $1$, colour in all the numbers in a clockwise direction $k$-th number ($1$, $k + 1$, $2k + 1$, ...). ...
-1 votes
0 answers
61 views

Incompleteness Proof Theory and Hypercomputation

Has anyone systematically studied how powerful hypercomputation can overcome "incompleteness proof theory"? For example: A deductive system for second-order logic in standard semantics with ...
2 votes
1 answer
112 views

Is a propositional function a proposition in propositional logic?

In mathematical logic, a proposition is defined as a declarative sentence that is either true or false, but not both. Two examples are '1 + 1 = 2' and 'Paris is the capital of France'. I have noticed ...
0 votes
1 answer
29 views

Confusion about Proving the Uniqueness of Linear Representation in N-ary Boolean function

$f\in B_n$ is called linear if $f(x_1,\cdots, x_n)=a_0+a_1x_1+\cdots+a_nx_n$ for suitable coefficients $a_0,\cdots, a_n\in \{0,1\}.$ Here $+$ denotes exclusive disjunction (addition modulo 2) and the ...
3 votes
3 answers
95 views

Help with proof in Gentzen-style Natural Deduction

For the life of me, I'm not able to show the following using Gentzen-style ND: $\neg \forall x \exists y Pxy \vdash \exists x \forall y \neg Pxy$ We may use all the usual rules: $\land$-I, $\land$-E, $...
8 votes
5 answers
2k views

A formal definition of a variable.

I am seeking a comprehensible yet formal definition of a varaible. I have already looked at the post What is the formal definition of a variable?, yet it is largely incomprehensible for someone who ...
0 votes
2 answers
78 views

Constructing a proposition in propositional logic which is a tautology if and only if ...

I'm trying to solve the following question: Let $A=\left \{ a_1,..,a_n \right \}$ be a finite set of arbitrary elements and $B_1,...,B_m$ subsets of A. Let $k\leq m$ be a natural number. Write a ...
0 votes
2 answers
105 views

Proof of Gödels first incompleteness theorem (as in Kunen)

On page 40 in Kunens "Set Theory An Introduction to Independence Proofs", we are given the following theorem: Gödel. If $\phi(x)$ is any formula with one free variable, $x$, then there is a ...
6 votes
1 answer
224 views

Definability of acyclic graphs

I think you should be able to encode the axioms of a directed, acyclic graph by introducing a strict partial order. Say E(a, b) represents there is an edge from a to b. We introduce a strict partial ...
3 votes
1 answer
76 views

What are other examples of $\aleph_1$-categorical theories?

In model theory, $\aleph_1$-categorical (first order) theories (in a countable language) are very important, and I am studying them at the moment. However, it seems that the only examples I can find ...
2 votes
1 answer
92 views

Confused about abstract models for axiomatic systems

I am studying axiomatic systems and I have a hard time understanding how one is supposed to come up with an "abstract" model for an axiomatic system. I will use the following example taken ...
2 votes
1 answer
173 views

Incompleteness Theorems for Limit-Computable Formal Systems

Godel’s First and Second Inconpleteness Theorems are about Peano Arithmetic, but their punchlines are respectively that “Any sufficiently expressive computable formal system cannot be complete and ...
5 votes
1 answer
97 views

What does consistency of $\frak c=\aleph_\alpha$ for any ordinal $\alpha$ without cofinality $\omega$ mean (ZFC)?

In this answer, Asaf Karagila says that it is consistent with ZFC that $\frak c=\aleph_\alpha$ for any ordinal $\alpha$ without cofinality $\omega$. It is not clear to me what exactly this means. If $\...
4 votes
1 answer
85 views

Why are extensions of countable models of ZFC better behaved than extensions of arbitrary models of ZFC?

This answer hints that certain kinds of extensions are only guaranteed to exist for countable models of ZFC. Why? One intuitive reason i can think of is that the metatheory might not have enough new ...
0 votes
0 answers
74 views

What is the correct translation of this Husserl's sentence in first order logic?

I found this Husserl's proposition in a book: The sum of the angles of a triangle is equal to the color red I'm not interested in the philosophical issue behind that sentence. I would just like to ...
3 votes
1 answer
577 views

Busy Beaver argument and Gödel's incompleteness theorem

By Gödel's incompleteness theorem, it should not be possible to prove the consistency of ZFC within ZFC (if it is consistent). It is well known that the Busy Beaver function is uncomputable, and that ...
1 vote
0 answers
82 views

Is the set of primitive recursive reals recursively enumerable?

Let's define a primitive recursive real as a real which is the output of a primitive recursive function (the function that computes its binary expansion for instance). The set of primitive recursive ...
2 votes
1 answer
43 views

Linear logic: Coherence space semantics for non-atomic formulas

In Jean-Yves Girard's "Between logic and quantic: a tract" (2004) the coherence space semantics of linear logic is explained. First, Girard introduces the notion of a carrier set $\mathbb{X}$...
-2 votes
0 answers
44 views

Natural Deduction Problem [closed]

This is the problem: $${(¬(¬((D↔B)↔A))),\\ ((C↔A)↔(C→D)),\\ ((C→D)∨(B∧A)) \\⊢\\ (((B∨B)↔C)→D)}$$ I'm used to use trees for the derivations, so if anyone can answer using that format would be better, ...
3 votes
1 answer
64 views

Proof-Theoretic Advantages to Using Only NANDs in Infinitary Logics

This question comes out of a question on Philosophy Stack Exchange, and a particular difference of opinion in regards to the initial question stated in 'Is there any major benefit to using NAND in ...
0 votes
2 answers
141 views

Logic behind uniqueness proof [closed]

The standard approach to proving uniqueness of an object, say A is to assume there are two objects A and B and show they are equal. Don't laugh, but I don't understand how this proves uniqueness. Can ...
15 votes
5 answers
5k views

"Predicate" vs. "Relation"

What's the difference between a predicate and a relation? I read the definition that an $n$-ary predicate on a set $X$ is a function $X^n\to \{\text{true}, \text{false}\}$ where $\{\text{true}, \text{...
0 votes
0 answers
77 views

statements that can be accepted by finitists.

"On the finitist view, the formula $\exists n P(n)$ is meaningful only when it is used as a statement specifying how to calculate an $n$ for which $P(n)$ is true". It is mentioned as above ...
1 vote
0 answers
79 views

Asking the experts in mathematical logic and set theory for survey articles to supplement the standard textbooks.....

I'm asking this question to the experts in mathematical logic and set theory.I'm a former graduate student in mathematics with an additional background in philosophy engaged in serious self study. I'...
0 votes
0 answers
51 views

Is my proof strategy legit?

I am working on a proof that I am finding quite challenging. While I think I have been able to prove one of the many intermediate steps of said proof, the final approach to show that particular step ...
9 votes
1 answer
204 views

Is there a noncomputable set whose noncomputability is hard to witness?

Belatedly, this notion has - unsurprisingly - been studied before; see Yamaguchi, Effective nonrecursiveness. Say that a function $f:\omega\rightarrow\omega$ is a noncomputability witness for a set $...
2 votes
0 answers
132 views

Why is the Axiom of Choice Necessary in ZFC

Within the framework of Zermelo-Fraenkel set theory with the Axiom of Choice $(ZFC)$, when we considered the method of constructing the set of natural numbers, we regarded it as the smallest inductive ...
0 votes
1 answer
91 views

Must both conditions of operator "OR ($\vee$)" be defined in mathematics? [closed]

I am in the process of writing an article and to explain my question, am providing to you a smaller instance of my wondering so that you can understand it, suppose that $A=\{0,1\}$ and that I define ...
2 votes
3 answers
293 views

Theorems & proof by contradiction

The following formula seems to be regarded as the essence of proof by contradiction: p → (q ∧ ~q) ⊢ ~p Or perhaps this one: ~p → (q ∧ ~q) ⊢ p If this is the case, what are the mathematical ...

1
2 3 4 5
566