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)

3
votes
1answer
79 views

Independence of existence of inaccessible cardinals

Let $I$ be the formula which states that there exists strongly inaccessible cardinals. My question is regarding the proof of $ZFC\nvdash I$ appearing in Jech (part of theorem 12.12). He starts by ...
1
vote
1answer
89 views

On provability of Paris–Harrington theorem

It is said that the Paris–Harrington theorem is true, but not provable in Peano arithmetic. I want to ask: So how do they know that it is true if it has no proof? I cannot imagine someone knows ...
0
votes
1answer
40 views

What kind of proof system have Zalta used in “Basic Concepts in Modal Logic”?

I have read that text and I'm so interested in the proof theoretic style (as also claimed by Zalta that it is used in modern approaches to modal logic) in it: That is both more mathematically rigorous ...
0
votes
3answers
135 views

Proof that there are infinitely many prime numbers

I answered a question to prove that there are infinitely many prime numbers, but I'm not sure if my attempt is right. Can somebody help me to check if my attempt is right? I would like, if I am wrong, ...
0
votes
1answer
48 views

If $\models \neg \phi$, then $\models \phi^\circ$, where $\phi^\circ$ is the “semi-dual” of $\phi$

This is exercise 1.3.22 from Hinman's Fundamentals of Mathematical Logic. Let $\mathrm{Sent}_{\neg, \vee, \wedge}$ be the set of all sentences from propositional logic closed under negation, ...
1
vote
2answers
69 views

Can I do instantiation like this?

Suppose, if I have been given this: $\forall x \in A(P(x))$ and $\exists y \in A(Q(y))$. Now from $\forall x \in A(P(x))$ using universal instantiation, I get $P(c)$ where $c$ is an arbitrary element ...
2
votes
0answers
78 views

Injury-free proof of Cof being $\Sigma^0_3$-complete

How can I prove, without using priority argument, that Cof, the set of indices of cofinite c.e. sets, is $\Sigma^0_3$-complete? I know an injury-free proof of Rec being $\Sigma^0_3$-complete, where ...
0
votes
1answer
52 views

Order of quantifiers in prenex normal form

I was wondering while doing some transformation into prenex form whether there is a situation when it does matter in what order you pull out the quantifiers to the front. If you know a good example, ...
2
votes
1answer
59 views

Proof of derivability

I'm a beginner at mathematical logic and I've come across the following problem: Let $X, Y \subset \mathcal{F}$, where $\mathcal{F}$ is the set of all formulas, and assume that $X \cup \{ \lnot ...
0
votes
4answers
98 views

Having hard time understanding implies

$P \Rightarrow Q$ I am having hard time understanding the second and third rows in the truth table. Implies means use if than, but the third statement is confusing. $P$ : Tesla Model S is a fast ...
1
vote
2answers
161 views

Diagonalization Principle

Diagonalization principle has been used to prove stuff like set of all real numbers in the interval [0,1] is uncountable. How is this principle used in different areas of maths and computer science ...
0
votes
1answer
72 views

Winning strategy for graphs (Ehrenfeucht-Fraïssé games)

I'm stuck with a question: Proof that you can't express if a graph is cyclic in first-order logic. The definition of cyclic is that for every node there is a ...
1
vote
2answers
354 views

Build a 3 bit full adder using only XOR gate?

I don't know if this is the right place to ask this, but I'm trying to design the logic for a simple calculator and I was wondering how can you build/design a 3 bit full adder using only XOR (one or ...
3
votes
1answer
75 views

How - in a Kripke model - to define a world by modal formulas true only at them?

I'm currently using van Benthem's "Modal logic for open minds", ed. 2010. In page 16 (and later in exercises), he considers a model whose relations are shown by directed graphs (the so called process ...
2
votes
0answers
44 views

What the definition of validity of a formule in a possible Kripke-world in Modal Logic?

Basic question here but I cannot find the definition: Given a modal logic and a set of propositions $P$, a model $M=(W,R,V)$ where $W$ are possible worlds, $R$ an accesibility relation and $V$ a ...
4
votes
1answer
76 views

extending automorphisms in complete boolean algebras

Suppose $A$ is a complete subalgebra of a complete boolean algebra $B$. Suppose $f : A \to A$ is an automorphism. Then $f$ can be extended to an automorphism of $B$. I can see this using the fact ...
3
votes
1answer
26 views

Let $\Gamma$ be a $\kappa$-based monotone operator where $\kappa$ is regular. Then the closure ordinal of $\Gamma$ is $\kappa$.

A monotone operator $\Gamma: \mathcal{P}(A) \to \mathcal{P}(A)$ is an operator such that, if $X \subseteq Y \subseteq A$, then $\Gamma(X) \subseteq \Gamma(Y)$. A monotone operator is $\kappa$-based ...
0
votes
1answer
118 views

A few questions about a true but unprovable statement

Can someone explain to me what this comment means: If ZFC is not a sound theory, a true but unprovable statement may be refutable and therefore decidable. What is a sound theory? What is ...
1
vote
2answers
92 views

Is the replacement theorem true for conditionals?

I read about the replacement theorem in Kleene's intro to logic which is as follows: If $\vDash(A\sim B)$ then $\vDash(C_A\sim C_B)$ where $C_A$ is a formula containing formula $A$ and $C_B$ is ...
2
votes
1answer
32 views

Finding a unique relation $T$

This is one question I have been solving from Velleman's How to prove book: Suppose $R$ and $S$ are relations on a set $A$, and $S$ is an equivalence relation. We will say that $R$ is compatible ...
0
votes
0answers
21 views

How to get accuracy of prediction?

I am working on a project where there is a part, which is based on the confidence level (between 0 and 1). The confidence level here is for various situations finally going Yes or No. So, 0.9 ...
0
votes
1answer
118 views

propositional logic entailment proof

I have a question, I am doing this exercise but I am a bit lost, it is the following: Let $\Sigma = \{\phi_1,...,\phi_n\}$ and $\varphi$ a proposition. Show that $\Sigma \vDash\varphi \iff ...
1
vote
2answers
283 views

Is the converse of a false conditional always true as in the Truth Table?

Accroding to the Truth Table, If $p$ is TRUE, and $q$ is FALSE, then $p\implies q$ is FALSE. And the converse, $q \implies p$, is TRUE. If the conditional statement is "If two angles are ...
1
vote
1answer
70 views

Proof strategy/writing for change of variables

Claim: If $f(x)=g(x)$ for all $x$, then $f(x+c)=g(x+c)$ for all x. Proof (attempt): Set $u=x-c$, and substitute $x=u+c$. $f(x)=g(x)$ implies $f(u+c)=g(u+c)$ for all $u$. Because $u$ is a dummy ...
2
votes
2answers
72 views

Questions about definability of truth

Suppose i work in ZFC. Using the recursion theorem, i can define the the truth value of formuals in the language $\mathcal{L}$ of set theory (one predicate symbol $\in$), $Val_\mathcal{M}(\varphi)$, ...
0
votes
0answers
105 views

How to convert formulas to rectified prenex form?

I'm preparing to an exam and I haven't understood this question: Convert the following formulas into rectified prenex form: a) $F = (\forall x \exists y\, P(x, g(y, f(x))) \lor \neg Q(z)) ...
1
vote
0answers
75 views

Proof for this equivalent statement to $2^{\aleph_0}=2^{\aleph_1}$ ??

This statement is some kind o a weak form of diamond and I am looking for a proof for its equivalence to $2^{\aleph_0}=2^{\aleph_1}$. $2^{\aleph_0}=2^{\aleph_1}$ is equivalent to the following ...
0
votes
1answer
34 views

Equivalence and implication for two identical statements

I saw in a maths book the following statement: $x>y ⇒ 2x>2y$ I think it should be written like this: $x>y ⇔ 2x>2y$ Which of the two above statements is correct?
3
votes
1answer
221 views

Counting quantification and the cardinality of a set

A counting quantifier is a quantifier that denotes how many elements satisfy a predicate. I will use the notation $C_n x P[x]$ to denote that there are $n$ elements that satisfy $P$. I was thinking ...
1
vote
2answers
94 views

Playing with propositional truth-tables

The following is the truth-table describing the definitions which allow us to establish truth values to composite formulae or molecules, which is nothing new: I had an idea about playing with the ...
4
votes
2answers
427 views

Is this axiom self-contradicting?

I was on physics stackexchange and came across an unusual answer where it was stated that the axiom, $$\forall x ((x \in x) \land (x \notin x))$$ Creates an axiom system where "nothing" exists in ...
0
votes
2answers
72 views

Decidability of certain first-order statements

Is it possible to construct an algorithm that can formally prove any statement in some countable first-order theory except for exactly those which aren't provable in the theory? Why or why not? Edit: ...
1
vote
0answers
37 views

How can a structure for a formal language be defined? [duplicate]

I'm learning some stuff about formal languages and structures for them. However there's this thing I don't understand. How can we ever define/specify a structure for a language, if we do not yet have ...
1
vote
1answer
54 views

Genus and faces of a graph

I am trying to determine the genus of a simple, undirected, connected graph using Euler's formula. However, I'm having trouble computing the number of faces of this graph: I seem to be confused ...
1
vote
4answers
76 views

Counterexample to “$A \to B, A \to C$, therefore $B \to C$”

We have $A\to B$ and $A\to C$. I need counter-examples to: '$\therefore B\to C$'. More formally, disprove: $$ (A\to B)\land(A\to C)\to (B\to C)$$ I have $A$ is a blackbird, $B$ is 'is black', $C$ ...
2
votes
2answers
37 views

The equivalence between the statements

Statement 1: Suppose for sake of contradiction that there is no non-negative rational number $x$ for which $x^2 < 2 < (x+ \epsilon)^2 $ . Statement 2: This means that whenever $x$ is ...
2
votes
0answers
29 views

Multiple order axioms independence [duplicate]

Let $T$ be a theory, let $L$ be its language, let $A$ be its set of axioms and let $P_0 \in L$ be a property. $P_0$ could be : Consequence of $A$ The negation of a consequence of $A$ Independent of ...
0
votes
0answers
73 views

“there are infinitely many” with finitely many variables

I vaguely recall reading somewhere that one cannot say "there are infinitely may" using a formula with only finitely many variables. A bit more precisely, let $\mathcal L$ be the result of extending ...
6
votes
3answers
337 views

Plantinga's logical argument for mind-body dualism [closed]

Some may feel this is not appropriate for the mathematics stack exchange, but it is a question in logic, and I feel it is entirely a good fit. The following argument has been put forth by the ...
1
vote
1answer
108 views

Computer program to tell you

Are there any computer programs, where if you input the premises and the conclusion, it tells you whether the conclusion is true or false?
1
vote
2answers
48 views

difference between some terminologies in logics

$$1) \alpha_1,\alpha_2,\alpha_3.......\alpha_{k-2}, \alpha_{k-1}, \alpha_k\vdash\alpha $$ Is a valid sequesnt. $$2) \alpha_1,\alpha_2,\alpha_3.......\alpha_{k-2}, \alpha_{k-1}, ...
0
votes
0answers
34 views

Meaning of valid sequent in logics

If $$\alpha_1,\alpha_2,\alpha_3.......\alpha_{k-2}, \alpha_{k-1}, \alpha_k\vdash\alpha$$ Here $\alpha_i$ are premises and $\alpha$ is conclusion .If I prove that sequent is valid using given rules in ...
0
votes
1answer
59 views

Confused on 'using the laws of logic'

Use the laws of logic to show the following: $$(a) \quad(p\rightarrow r)\vee (q\rightarrow r) \equiv (p\wedge q)\rightarrow r$$ $$(b) \quad [\neg q\wedge (p\rightarrow q)]\rightarrow \neg ...
1
vote
1answer
35 views

Proof involving recursive enumerability

Consider the set $S = \{x : \phi^1_x(x) \ \ \text{is undefined/does not converge\} }$ This is supposed to be a set that is not recursively enumerable. How do we prove this? My thoughts so far: ...
2
votes
2answers
91 views

Can we treat logic mathematically without using logic?

I'm reading Kleene's introduction to logic and in the beginning he mentions something that I have thought about for a while. The question is how can we treat logic mathematically without using logic ...
2
votes
1answer
106 views

Why isn't this a valid formalization of , “Every farmer who owns a donkey beats it?”

Why isn't $\forall(f,d)[\mathrm{farmer?}(f) \land \mathrm{donkey?}(d) \land \mathrm{owns?}(f, d) \implies \mathrm{beats?}(f,d)]$ a valid formalization of, "Every farmer who owns a donkey beats it?" ...
0
votes
1answer
130 views

Proving unsatisfiability with propositional resolution

I'm having trouble understanding how to use the resolution rule to prove if a statement is satisfiable or unsatisfiable. I watched this course lecture on propositional resolution and unsatisfiability ...
4
votes
1answer
45 views

Total Turing reducibility

For $x, y\in 2^\omega$, say $x$ is totally reducible to $y$ - and write "$x\le_{Tot}y$" - if there is some Turing machine $\Phi_e$ which is total on every oracle (that is, $\Phi_e^z$ is total for all ...
-1
votes
1answer
98 views

How to reason with Equisatisfiability

I am having trouble reasoning about the equisatisfiability of statements. (In the following I'll use the notation where addition is OR, multiplication is AND, and overbar is NOT.) By exhaustive ...
1
vote
1answer
42 views

Let $\alpha\in \text{FORM}$. If $\beta \in Sub( \alpha) \implies \beta $ shows up in every formation chain of $\alpha$.

Warning: I'm translating from spanish so probably many terms may sound unfamiliar. Warning 2: I'm probably going to link this question from many others I ask so I don't copy and paste these ...