Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

0
votes
2answers
97 views

understanding provability and more about Löb's theorem

This question is an additional question for my previous question,one week ago. Link : understanding provability Fortunately, some persons kindly commented for my question. However, I think I still ...
5
votes
3answers
73 views

Consequence in Logic

For arbitrary formulas $A,B,C$ it holds that: $\{A,B\} \vDash C $ if $A \vDash (B \Rightarrow C)$ $(A \Rightarrow B) \vDash C$ if $A \vDash (B \Rightarrow C)$ $A \vDash C$ if $A \vDash (B ...
2
votes
2answers
171 views

Does the statement “There is an algorithm that solves …” make sense?

Let $P(a,b)$ be a class of well-defined problems depending on two parameters. That is, for each pair $(a,b)$ there is a unique solution to problem $P(a,b)$. For example, $a,b$ could be integers, and ...
5
votes
4answers
342 views

Counterexample for $(p\rightarrow q) \longleftrightarrow (!q \rightarrow\mathord !p) $

Is the statement $$(p\rightarrow q) \longleftrightarrow (!q \rightarrow \mathord!p) $$ always true? If it is not, provide a counterexample. Till now I cannot find a counterexample nor prove that ...
4
votes
1answer
111 views

Question regarding inexpressibility results over finite models using compactness and the Löwenheim–Skolem theorem

In the book Elements of finite model theory by Leonid Libkin, they show that the parity query for structures over an empty vocabulary is not first order definable. They do this by constructing two ...
2
votes
2answers
79 views

is this argument true?

i had a puzzle and used a logical argument to show a point but some says that my argument is wrong but i can't understand the reason they provide ! the puzzles says , Given four cards laid out on a ...
2
votes
2answers
105 views

How to know when to use $P(x)\wedge Q(x)$ and when to use $P(x)\to Q(x)$?

When translating English phrases to mathematical statements using logical quantifiers, I find that I'm having trouble knowing the difference between $P(x)\wedge Q(x)$ and $P(x)\to Q(x)$. For example: ...
7
votes
2answers
243 views

Monadic second order logic without constants, functions and equality

Leibniz's law of the identity of indiscernibles can be stated in monadic second order logic: $$\forall x\forall y (x=y \leftarrow \forall P (Px \leftrightarrow Py))$$ This law is true for standard ...
1
vote
1answer
104 views

Logic: Maximally consistent and validity

Assume that $\Gamma$ is a maximally consistent set of formulas of $\mathcal{L}$. Show that if $\varphi$ is a validity, then $\varphi \in \Gamma$. Can I check if what I am doing is sound, no pun ...
0
votes
1answer
102 views

Logic: Equivalence Relation

Let $\Gamma$ be a maximally consistent set of formulas of $\mathcal{L}$. For any two terms $\tau_1$ and $\tau_2$ of $\mathcal{L}$, define that $\tau_1 \cong_\Gamma \tau_2$ if and only if ...
2
votes
1answer
208 views

Linear order and well-order

The question is: A linear(or total) order (L,=<) is a well-order if and only if (1) for every infinite decreasing sequence x0 =< x1 =< x2 =< ... in L, there is an n such that for all ...
4
votes
1answer
62 views

Logic: Infinite $K$-sequences, and $n$-free problems

There are two problems which seem to be similar that I am stuck on. This is not homework for me but would very much like to understand what is going on. First problem is this: An infinite ...
2
votes
2answers
145 views

Logical errors in math deductions

Sometimes in mathematics we do this a lot: Suppose that to find a function $y_1(x)$ that satisfies some equation (any type of equation, differential or whatever..): $$F(y_1(x))=0$$ In order to find ...
1
vote
2answers
165 views

An alternative definition of a group?

Will the following definition of a group work as a basis for group theory: $\forall G,f,i,e (Group(G,f,i,e)\leftrightarrow f:G\times G\rightarrow G$ $\wedge i:G\rightarrow G$ $\wedge \forall ...
4
votes
1answer
142 views

The Permitting Method

Define the term late permitting in the following way: $C$ late permits an element $x$ to enter $A_{s+1}$ if for a fixed computable function $f$ with $f(n)>n$, there exists $y\leq x$ such that $y\in ...
1
vote
1answer
48 views

Missing one link in logic of basic unique factorization argument

From page 2 of The Prime Facts : from Euclid to AKS by Scott Aaronson : Thus P/A = R/K. But R is less than P, since it’s a remainder from dividing by P. Okay So P/A can’t be in lowest ...
2
votes
1answer
134 views

Propositional Logic Inductive Proof

I am working on a problem to prove, but I do not understand it completely. Where should I use inductive method? What is the base case? And so on. Here is my problem: A truth assignment $M$ is a ...
2
votes
1answer
82 views

How to deal with infinite continued fractions in formal language?

A continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number ...
1
vote
1answer
91 views

simple sets, cofinite sets, filters

Let $\mathcal S$ be the class of simple sets and $\mathcal C$ the class of cofinite sets. Prove that $\mathcal S\bigcup \mathcal C$ is a filter in $\mathcal E$. Definitions: An infinite set is ...
5
votes
3answers
221 views

What's the problem this logic

In Lewis Carroll's story "What the Tortoise Said to Achilles," the swiftfooted warrior has caught up with the plodding tortoise, defying Zeno's paradox in which any head start given to the tortoise ...
1
vote
3answers
135 views

How to Prove $((F \iff H) \iff ((\neg F \land \neg H) \lor (F \land H)))$

I am at a complete loss here... $(F \iff H)$ PREMISE ... $((\neg F \land \neg H) \lor (F \land H))$ GOAL I keep getting stuck in a loop of contradiction and not able to complete the proof. I can ...
5
votes
2answers
547 views

Is ZFC without Axiom of Infinity consistent?

The incompleteness theorem states that one cannot prove whether ZF or ZFC is consistent, but what about ZFC withouth Axiom of infinity? (Assuming the empty set exists) Furthermore, let $M$ be a ...
2
votes
1answer
93 views

A question about consistent axiomatizable extensions of PA

Given $T\supset PA$ to be consistent and axiomatizable, I've been told that when $G\subset T$ is finite, and $\phi$ is a universal sentence, then: ($\star$) $PA\vdash ...
2
votes
2answers
147 views

How to prove that $(A \lor B) \land (\lnot A \lor B) = B$

I know this is fairly basic, and I understand that it becomes $$ \begin{align} (A \land \lnot A) \lor B \\ F \lor B \\ B \end{align} $$ However, I can't work out how to prove that it becomes that ...
1
vote
1answer
60 views

Does the logic that proves the halting problem unsolvable also apply to series?

Would it be possible to apply the proof that the halting problem is unsolvable to a proof that a function $$Q(i)=\sum_{n=1}^\infty P(i)$$ where $$P(i)= \left\{ \begin{array}{c} n,\quad when \quad i ...
6
votes
1answer
185 views

Is Rosser's trick necessary?

A version of Gödel's first incompleteness theorem goes as follows: Any true, definably axiomatized theory $T$ in the language of arithmetic is incomplete. (by $T$ being true I mean ...
3
votes
1answer
102 views

If {P is provable} is provable, then P is provable?

This is simple question. If, sort-of-says, "X is provable" is provable, then, we can always predicate that X is provable? It means, for the theory ...
1
vote
2answers
54 views

Domain, Range, and Relation

Show that if R is a relation, then $\cup\cup R =(\operatorname{dom}R)\cup(\operatorname{ran}R)$. First, I don't know what $\cup\cup R$ means where $R$ is a relation. I want to know what is the ...
3
votes
4answers
138 views

If $b\mid ca$, then $b\mid a$. Is this true?

My proof: We want to show $b\mid a$ i.e. $a = bn$ for some integer $n$. Since $b\mid ca$, $ca = bm$ for some integer $m$. Substituting for $a$ gives us $c(bn) = bm \Rightarrow b(cn) = bm\dots$ After ...
1
vote
2answers
239 views

Hard proof concerning the periodicity of trigonometrical functions. Is that a challenge or just trivial

i want to know if exist or if you can develop or give me ideas of a proof to show that the least number for which sine is periodic is $2\pi$ $$\neg \{\exists n\in \mathbb{R} \wedge n < 2\pi: ...
4
votes
3answers
167 views

False(ified) Axioms

Don't really know how to title this one. I'm working on a real analysis question that says: In one sentence write down the reason why $(1=2)\land (2=3)\to (1=3)$ (and similar substitutions) don't ...
5
votes
1answer
104 views

undecidability of the structure $(\omega,+,2^n)$

Is the structure $(\omega,+,2^n)$ undecidable? There is no easy way to define multiplication using a formula.
1
vote
0answers
74 views

An extension of Löb's theorem

This question is an extension question of previous one. link: Löb's theorem and provability Now, there is three sentences, P, Q and R. sort-of-says, they are like following. P: P, Q ...
0
votes
2answers
280 views

Propositional logic “equivalent to” using union, intersection and negation

In the Maths book, "implies to" is described as $A\rightarrow$B equals to $\lnot\ A \lor B $ How can I represent $A \Leftrightarrow B$ in the same way?
1
vote
2answers
281 views

Example of a logic where a proof by contradiction does not imply a direct proof.

It makes sense that for any logic that has axioms, an inference rule and a statement you want to prove P, you can take a direct proof of P and turn it into a proof by contradiction (you have already ...
1
vote
0answers
125 views

How should I prove $\Box (\Box p \rightarrow q) \vee \Box (\Box q \rightarrow \Box p)$ using KT45.

How am I supposed to prove the same using natural deduction? I started my proof with a LEM $$\Box (\Box p \rightarrow \Box q) \vee \neg \Box (\Box p \rightarrow \Box q)$$ I split the LEM via $\vee$ ...
17
votes
5answers
1k views

Is 1+1 =2 a theorem?

A theorem is defined to be a mathematical statement that is proven to be true. The statement $1+1=2$ has definitely been proven in the history of mankind (Russel and Whitehead had once proven it in ...
6
votes
5answers
382 views

Why do we prefer classical logic over non-classical logic?

In classical logic, we have paradoxes like paradoxes of material implication. If non-classical logic like relevance logic fixes those problems, why do we still continue to use classical logic?
6
votes
2answers
491 views

intersection of the empty set and vacuous truth

Let $\mathbb S = \varnothing$. Then from the definition: $ \bigcap \mathbb S = \left\{{x: \forall X \in \mathbb S: x \in X}\right\}$ Consider any $x \in \mathbb U$. Then as $\mathbb ...
1
vote
1answer
122 views

What's a non-standard model of Tarskian Euclidean geometry?

Tarski's axioms (see here: http://en.wikipedia.org/wiki/Tarski%27s_axioms) are a first-order axiomatization of Euclidean Geometry. Now, I believe the standard model for the axioms is the real number ...
3
votes
1answer
40 views

Which diophantine polynomials generate these diophantine sets?

Via Matiyasevich's Theorem, it is easy to prove that the following sets are diophantine: $\{k\}$ $\{0, 1, \dots, k-1, k+1, k+2, \dots \}$ $\{0, 1, \dots, k\}$ $\{k+1, k+2, \dots\}$ Number 1 is ...
4
votes
2answers
393 views

Why is propositional logic not Turing complete?

According to 1 (probably not the most relevant source), propositional logic is not Turing complete. Aren't all computations in computers performed using logic gates, which can be represented as ...
4
votes
2answers
62 views

Finding truth of logic statement

I'm attempting to evaluate the truth of the following statement: ∃a∀b((a < b) → (a^2 < b^2)), where a and b are real numbers. I have tested multiple values (whole numbers and fractions) and ...
2
votes
1answer
64 views

Interpreting one theory into another

Just a question about interpretations which I'm not sure of: Say we have two theories $T_0$ and $T_1$. Then an interpretation $I$ of $T_0$ into $T_1$ is an interpretation $I$ of the language $L_0$ ...
4
votes
1answer
89 views

Recovering an object from its category

Consider the category of groups (but the question arises for any category of mathematical object, basically). It is easy to read off what the automorphism group of a group is or what its cardinality ...
3
votes
0answers
86 views

Constructing an incomplete ordered field satisfying the nested interval property

Motivated by a problematic exercise in an analysis textbook, I decided to search for an example of an ordered field which satisfies the nested interval property yet fails to be complete. I first ...
6
votes
1answer
346 views

What are $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$?

Sometimes reading on wikipedia or in this site (and in very different context like topology, arithmetic and logic) I have found these symbols $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$. They are ...
1
vote
1answer
120 views

understanding provability

I am still confused about provability. . . Let a statement P is, sort-of-says like this. P: ( "X is provable" ∧ "P is provable" ) If ( X is provable ∧ P is provable ) is provable → (P is ...
4
votes
2answers
326 views

Why is it impossible to define multiplication in Presburger arithmetic?

Peano arithmetic defines multiplication recursivly as: $$\begin{gather}a\cdot0=a\\a\cdot S(b)=a+(a\cdot b)\end{gather}$$ Why is this not possible in Presburger arithmetic?
1
vote
1answer
305 views

SHOW that there are infinitely many equivalence classes of formulas

Let $\mathcal{Q}$ denote the additive group of rational numbers, i.e. the structure $\left<\mathbb{Q}; +; 0\right>$. Let $\mathcal{L}$ be the language of $\mathcal{Q}$ and let $T$ be the ...