Questions about 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)

4
votes
1answer
147 views

The existential theory is undecidable

Lemma 1. For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and ...
1
vote
1answer
43 views

Proof of a classical Theorem of Martin-Löf on complexity dips for Kolmogorov complexity,

I have a question on the first Theorem from the article Complexity of Oscillations in Infinite Binary Sequences by P. Martin-Löf, which could be downloaded from the publisher or from here. Theorem ...
2
votes
1answer
87 views

(totally) (M,P)-generic forcing condition

We say a cardinal $\theta$ is sufficiently large for a forcing $Q$ if $\mathcal{P}(\mathcal{P}(Q)) \in H(\theta)$. And a set $M$ is a suitable model for $Q$ if $Q \in M$ and $M \prec H(\theta)$, $M$ ...
5
votes
2answers
120 views

Explicit construction of a nonmeasurable set, where only the proof of correctness uses choice?

By Solovay's theorem, assuming the existence of an inaccessible cardinal, the axiom of choice is necessary to prove the existence of nonmeasurable sets. In the past, I've thought that one consequence ...
2
votes
2answers
83 views

Why are some conditionals regarded false even if the antecedent is false?

In the Mendelson's logic book, there are 2 conditionals which Mendelson says they are regarded false even if their antecedent is false. One of them is the following: If this piece of iron is ...
3
votes
1answer
72 views

Is this a typo in Jech's Set Theory?

In Jech's Set Theory, p. 603 in the chapter about Proper Forcing, the proof of Theorem 31.7. In the second but last paragraph, the proof says By Theorem 8.27 (Menas), $\lbrace M \cap \lambda ...
0
votes
1answer
51 views

Max/Min to logical operator transformation and viceversa

I have some doubts in transforming conditions that involve max/min in logical operator condition and viceversa. In particular, should be (I put some examples, I would know if I'm right and the ...
2
votes
1answer
39 views

Real Closed Fields with Predicate for a Dense Subfield

Consider $M = (\mathbb{R};+,<, \times, 0, 1, K)$ where $K$ is a unary predicate which holds on $\mathbb{Q}$ (or any dense subfield of $\mathbb{R}$). Question: Is it true that the parametrically ...
1
vote
1answer
29 views

Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity

Denote by $C(n)$ the plain Kolmogorov complexity of $n$ and the length of a binary encoding of $n$ by $l(n)$, why do we have $$ C(n\mid l(n)) \ge C(n) - C(l(n))? $$ If I have a shortest program $p$ ...
2
votes
1answer
161 views

Is there a rule for uniform substitution of predicate symbols in FOL?

In a Hilbert-style axiomatization of first-order logic (FOL), there is a rule for variable substitution but I don't see any rule for substituting predicate symbols. Consider a theorem like: $\forall ...
2
votes
3answers
55 views

Prove that if $x \neq 0$, then if $ y = \frac{3x^2+2y}{x^2+2}$ then $y=3$

The problem is the following (Velleman's exercise 3.2.10): Suppose that $x$ and $y$ are real numbers. Prove that if $x \neq 0$, then if $ y = \frac{3x^2+2y}{x^2+2}$ then $y=3$. My approach so ...
1
vote
0answers
14 views

Each recursive approximating sequence for Kolmogorov complexity is not uniform

Denote the plain Kolmogorov complexity by $C(x)$. Let $\phi(t,x)$ be a recursive function and $\lim_{t\to\infty} \phi(t,x) = C(x)$ for all $x$. For each $t$ define $\psi_t(x) := \phi(t,x)$ for all ...
1
vote
2answers
39 views

Analyzing logical form of the statements

I have four statements given as exercises in the book: How to prove it. Sa : Alice and Bob are not both in the room. Sb : Alice and Bob are both not in the room. Sc : Either Alice or Bob is not ...
1
vote
0answers
19 views

Logical form of the statements

I have two statements taken from the book: How to prove it. S1 : We’ll have either a reading assignment or homework problems,but we won’t have both homework problems and a test. S2: You won’t go ...
0
votes
1answer
19 views

Propositional Logic - Conditional Proof

I'm confused doing one problem. The problem is to show that $$(P\vee Q \implies R) \implies (P\wedge Q \implies R)$$ using Rule C.P. What I have done so far: Assumed antecedent of the conclusion as ...
3
votes
1answer
36 views

Proving the Downward Löwenheim-Skolem using monotonic operators

This is another exercise from Kees Doets Basic Model Theory. Here's the idea. It's well known that the downward Löwenheim-Skolem theorem follows as an easy corollary of the following lemma using ...
6
votes
2answers
90 views

Law of Clavius explained

Law of Clavius states $ \sim P \Rightarrow P \vdash P$ And the only explanation I sort of understand is ...
2
votes
1answer
70 views

Different definitions of a valid argument?

I have some serious problems understanding what counts as a valid argument and what does not. I have read some different definitions of what a valid argument is: (Sorry if this post is missplaced, ...
2
votes
1answer
80 views

Help me solve this (∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px] first order logic (step by step)

This is a MCQ of a competitive exam(GATE) , defined below . I found many different -2 explanation in market books and many other sources , but there is conflict between each explanation , I found all ...
2
votes
0answers
15 views

Kolmogorov complexity of substring if string is divided according to rule

Denote the plain Kolmogorov complexity of a string $u$ by $C(u)$. Now let $u$ be a string of length $n$ with $C(u) \ge n - O(1)$ and suppose $u = u_1 \cdots u_{\log n}$, a subdivision of the ...
2
votes
2answers
33 views

find formula for $P\land Q$ using $\uparrow$

I am supposed to find a formula for $P \land Q$ using the logical connective $\uparrow$ $P \uparrow Q$ means that not both $P$ and $Q$ is true. I have already found that $P \lor Q \equiv (P\uparrow ...
3
votes
0answers
74 views

Reference request: fixed point and first-order logics

I'm looking for materials on the relationship between first-order and fixed-point logics, specifically on the condition for a formula in a fixed-point logic to have an equivalent first-order formula. ...
1
vote
0answers
31 views

On Kolmogorov complexity of first and last half of a string

Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy $C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$. Any ideas how to ...
1
vote
2answers
59 views

Inconsistent theory with uniformly long refutation?

I understand that there are theorems in PA that necessarily require "very long" proofs; cmp. [1]. On the other hand it seems interesting to think about Life in an inconsistent world. So is it ...
0
votes
2answers
34 views

Symbolic predicate logic “a variable belongs to naturals but bigger than two”

I have written a function and I would like to write at the end "where the variable $x$ belong to the naturals but bigger than $2$" but be translated into symbolic predicate logic. I am writing it as: ...
1
vote
3answers
243 views

Is there any commonality between Math induction and Logic induction?

Logic induction is reasoning by probability. Math induction seems to be related to just Natural numbers and used to prove a statement for every natural number. From these definitions there is no ...
0
votes
1answer
69 views

Existential quantifier axioms in Halmos' system, equivalence proof needed

I have to refer to page 21 of the book cited in the link below. There is a list of axioms Q1-Q5, and an assertion that they are equivalent to a shorter set, namely Q1, Q2 and Q6. I am trying to derive ...
2
votes
1answer
54 views

Implication in linear logic

Linear logic abandons the structural rules of weakening and contraction. I wanted to know whether we have $p ⊸ p$ in linear logic. Can anyone help?
-3
votes
1answer
37 views

Negate the following logic statements [closed]

Can anybody explain me how to negate the following statements correctly? a) All roses are either odorless or have spikes. b) $\forall x \in \mathbb{Z}: \exists y \in \mathbb{Z}: x+y=0$ c) $\forall ...
1
vote
1answer
50 views

Logical equivalence - Russell's Paradox

In 'How to Prove it' Velleman creates the following set: $R = \{A\in U| A \notin A \}$. This is, according to Velleman, equivalent to $\forall A \in U (A \notin A \iff A\in R) $. That is clear. ...
11
votes
1answer
142 views

Every non-increasing sequence of polynomial towers stabilizes — Finitary proof

In this question we are concerned only with positive integers $\mathbb N$ and other finitary objects that can be encoded using integers. A term function means a total computable function $\mathbb ...
1
vote
2answers
57 views

expressing inclusive OR using exclusive OR. [closed]

On page 5 of Hamilton`s mathematical logic book, it's been stated that we can express A or B or both using XOR, as also possible to express negation and conjunction using XOR. I couldn't find any ...
1
vote
0answers
82 views

Looking for this theorem by Devlin and Shelah

This is a theorem of Devlin and Shelah which I am looking for more details and also proof: $2^{\aleph_0}=2^{\aleph_1}$ is equivalent to the following statement: There is an $F:H(\aleph_1) ...
2
votes
3answers
66 views

Examples of logical possibility

According to Wikipedia, something is logically possible if it doesn't imply a contradiction. In that case, how could a mathematical statement be false but possible? Wouldn't a false statement be false ...
4
votes
3answers
96 views

Why can't you prove the law of the excluded middle in intuitionistic logic (for layman)?

I am learning about the difference between booleans and classical logics in Coq, and why logical propositions are sort of a superset of booleans: Why are logical connectives and booleans separate in ...
1
vote
1answer
46 views

About the cardinality of the set of all terms/formulas when $|L| > \aleph_0$

This may be a silly question; it was occasioned by exercise 17 of Doets Basic Model Theory book, in which he asks us to prove that, for an arbitrary language $L$, there are at most $|L| + \aleph_0$ ...
2
votes
1answer
48 views

Show that $(A ∩ B) ▵ C = (A ▵ C) ▵ (A \setminus B)$

I want to show the following equality (using logical connectives, not venn diagrams) Show that: $$(A ∩ B) ▵ C = (A ▵ C) ▵ (A \setminus B)$$ $A ▵ B$ is defined as: $(A ∪ B) \setminus (A ∩ B)$ My ...
1
vote
2answers
62 views

Cardinal Exponentiation Inequality

Let $\lambda, \kappa$ be infinite cardinals with $\lambda<\kappa$, what is known about $\kappa^\lambda$? specially in the case either $\kappa$ is regular. Or is there very little that can be ...
1
vote
1answer
45 views

An exercise on implication (proof and logic)

This question is derived from the book "How to think like a Mathematician" which does not have solutions to its questions. Following exercise is on implications: Suppose that students were told that ...
2
votes
0answers
64 views

Coding of a function f (relative to a ladder system $\overrightarrow{C}$)

Let $\overrightarrow{C}=\langle C_\delta \colon \delta \in \mbox{Lim}(\omega_1)\rangle$ be a ladder system on $\omega_1$. Let N $\subseteq M$ be countable subsets of $\gamma$ and $ \lbrace\omega_1, ...
4
votes
2answers
60 views

Stone-Čech compactification $\beta\mathbb{N}$ of the integers $\mathbb{N}$ with discrete topology has uncountably many points?

How do I show that the Stone-Čech compactification $\beta\mathbb{N}$ of the integers $\mathbb{N}$ with the discrete topology has uncountably many points? There is a hint that crux is to construct a ...
0
votes
0answers
27 views

Copying a line in a natural deduction proof

$p\land q \vdash (p\Rightarrow q) \land q$ $1. \ p \land q \ \ \ \text{assumption 0} \\ 2. \ q \ \ \ \ \land\text{-elimination 1} \\ 3. \ p\vdash q \\ \ \ \ \ 3.1. \ q \ \ \ \text{Copied from line ...
1
vote
0answers
26 views

Kolmogorov complexity, no description mechanism can improve on additively optimal/universal one infinitely often

In An Introduction to Kolmogorov Complexity and Its Applications explaining the notion of additively optimal or universal it is written: The key point is not that the universal description method ...
2
votes
0answers
41 views

Resources for learning fixed point logic

As the title says, I am looking for resources to learn some fixed point logic, especially partial fixed point logic. I have basic knowledge of propositional calculus and predicate logic, but sadly not ...
15
votes
3answers
970 views

Why do we show that structures aren't isomorphic by exhibiting a property not shared by one of them?

If someone asks me how to prove that two order structures $\langle A,\leq \rangle$ and $\langle B,\preceq \rangle$ are isomorphic I would immediately suggest: try to find a function $f:A\to B$ such ...
0
votes
2answers
18 views

Verifying the reasoning is true for the following deductive arguent

Identify the premises and conclusions of the following deductive arguments and analyze their logical forms. Do you think the reasoning is valid? Either John or Bill is telling the truth. Either Sam ...
0
votes
3answers
36 views

Combination Of Sets Question

I have a bit of an advanced combination problem that has left me stumped for a few days. Essentially my question is if you have n sets of items, and you can select a different number of items from ...
0
votes
0answers
23 views

Classification of commutative ring ideal closure operators?

First, some setup: So: given a commutative ring $R$, let $Ideals(R)$ be set of ideals of $R$ and let $IdealClosure(R)$ be the set of closure operations $cl: \mathcal{P}(R) \rightarrow Ideals(R)$. In ...
0
votes
3answers
105 views

Language that describes all real numbers

According to Wikipedia: Suppose that in a mathematical language $L$, it is possible to enumerate all of the defined numbers in $L$. Let this enumeration be defined by the function $G\colon W\to ...
1
vote
1answer
35 views

Conjunction Rule

I feel this is a basic question but it has been bugging me. Suppose I have the following derivation (in intuitionistic logic): $$(\wedge^{+})\frac{\Gamma_1 \vdash x=1 \hspace{1cm} \Gamma_2 \vdash ...