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)

0
votes
1answer
32 views

Meaning of such that.

The use of this term confuses me, I've seen this like $A=\{(x,y) :x,y\in\Bbb R\ \text{and } P(x,y) \}$ and $B=\{(x,y)\in \Bbb R^2:P(x,y)\}$ for some predicate $P$. Is there any difference between ...
2
votes
2answers
27 views

Testing whether Argument is valid or not

I am to determine if argument is valid by making truth table ATTEMPT Let W= Warning lights will come on P= Pressure is high R=Relief valve is clogged Then i have premises as W ...
3
votes
2answers
59 views

A simple expression to map $\mathbb N^*$ bijectively to $\mathbb N$

Let $\mathbb N = \{ 1,2,3,\ldots \}$, then by the well-known "Cantor"-Scheme we have $\mathbb N \times \mathbb N \cong \mathbb N$. But even nicer is that we can write this scheme $\varphi : \mathbb N ...
1
vote
1answer
37 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 ...
1
vote
1answer
30 views

Order of statements in implication

The question is from Excercise 13 of part 1.4 in Rosen's "Discrete Mathematics and Its Applications" (5th edition): "let M(x,y) be "x has sent y an e-mail message", where the universe of discourse ...
-1
votes
2answers
28 views

Boolean Algebra Problem ABCC'

Hi I just want to ask the answer of this Boolean Algebra problem.. $$ABCC' + B + A'B $$ How to simplify that one?
1
vote
1answer
40 views

Proof outline of a certain sentence (Introductory course on logic, proof writing et al.)

The exercise asks me to outline a direct proof that if $\mathbf A$ is a diagonal matrix, then $\mathbf A$ is invertible whenever all its diagonal entries are nonzero. To me this sounds like ...
6
votes
1answer
313 views

Elaboration of calculus in finitistic math

I was just curious if there were some approaches to prove major theorems of calculus in finitistic systems like PRA? I'm aware of some questions which were already considered, e.g. ...
0
votes
1answer
28 views
0
votes
1answer
57 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 ...
-1
votes
2answers
65 views

What is the formal negation of the statement “There is much X in Y”. [on hold]

What is the formal negation of the statement "There is much X in Y"? The answer to me is that "It is not the case that there is much X in Y" But I want a more useful negation. Can I say that its ...
1
vote
3answers
59 views

Distribution of universal quantifiers over implication

I want to prove that $∀x(φ(x)⟹ψ(x))$ implies $∀x(φ(x))⟹∀x(ψ(x))$. I read they are not equivalent, but I am not sure why. I tried the following: $∀x(φ(x)⟹ψ(x))$ $⟹[φ(a)⟹ψ(a)]$ is true. $⟹φ(a)$ is ...
3
votes
2answers
53 views

Are the quantifiers interchangeable?

In other words, is it true that $\forall x \; \exists y\;\phi(x, y) \iff \exists y\;\forall x \; \phi(x, y) $?
2
votes
1answer
34 views

what is essentially universal or existential?

In Lambda-Prolog , I see essentially universal quantifier or essentially existential quantifier such terms, I am confused. It seems the universal quantification of a variable in program or goal is ...
-1
votes
1answer
34 views

Solve the following proof : M |- M ∨ {[(Z∨S) ∧ (¬] → (C↔D)}

Solve the following proof : M |- M ∨ {[(Z∨SC↔D)} I try to proof above question with the following (F⋀Z)⋀ → (C↔D) 1 (F⋀Z)→C 2 F⋀Z 1⋀E 3 F 2⋀E really confused :( this ...
-3
votes
0answers
26 views
1
vote
0answers
57 views

Satisfiability/compactness theorem

I am trying to solve the following problem: Let $\mathcal{F}$ be a set of propositional formulas. Assume that for any valuation map $v$ there is some $F$ $\in$ $\mathcal{F}$ such that $v^*(F) = ...
0
votes
2answers
1k views

What is the purpose of implication in discrete mathematics?

I would be obliged if you can show me an example of a truth table for implication where there is a also a real life aspect to it. (i.e., where would someone use the scenario to make F->F = T and also ...
2
votes
2answers
39 views

Inference in Predicate Logic

I have stumbled upon the following reasoning, but I'm not sure if it's correct. Here it goes: Domain X $\forall x :\phi(x)⟹\gamma(x)$ Let $E\subseteq X⟹[\forall x\in E :\phi(x)⟹\gamma(x)]$ Suppose I ...
3
votes
4answers
117 views

Proving that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even.

Here is the proof: Let $a,b \in \mathbb{Z}$. Prove that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even. When working these problems, I do try to set them up logically. My ...
2
votes
1answer
114 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
1answer
65 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$ ...
2
votes
0answers
55 views
+50

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. ...
4
votes
1answer
83 views

If $\phi$ holds for all standard models of ZF and ZF proves this, then does ZF prove $\phi$?

I apologize if this is a nonsensical question. Suppose $\phi$ holds in all standard models of ZF. Suppose further that ZF proves this. Then does ZF prove $\phi$?
0
votes
2answers
38 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 ...
4
votes
1answer
102 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
3answers
170 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 ...
1
vote
3answers
71 views

Suppose $A\subseteq \mathscr P (A)$. Prove that $ \mathscr P (A)\subseteq \mathscr P ( \mathscr P (A))$

This is Velleman's exercise 3.3.4. Suppose $A\subseteq \mathscr P (A)$. Prove that $ \mathscr P (A)\subseteq \mathscr P ( \mathscr P (A))$. I started reexpressing the terms in their equivalent forms ...
2
votes
2answers
77 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 ...
2
votes
1answer
81 views

What does it mean to axiomatize a logic?

I'm sorry if this question is not clearly formulated: An axiomatization, or an axiomatic system, usually means a set of axioms (i.e. a theory). A formal theory is such a set of formulas in some formal ...
0
votes
1answer
25 views

Logic question and proportions [on hold]

there's something that have been bugging me. If we have quantities A, C, E And if we have quantities B, D, F And if we take the equimultiples G, H, K from A, C, E And if we take the equimultiples L, ...
5
votes
2answers
105 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
0answers
57 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 ...
2
votes
1answer
37 views

Prenex normal form of $\neg \big(\forall x \ P(x) \vee \forall x \ Q(x) \big)$

I have the statement $\neg \big(\forall x \ P(x) \vee \forall x \ Q(x) \big)$ and I have to write it in prenex normal form. First I use the second De Morgan law $\neg \big(\forall x \ P(x) \vee ...
-4
votes
0answers
42 views

Which one of the following well formed formula is a tautology?

Which one of the following well formed formula is a tautology? (a) $\forall x \, \exists y \, R(x, y) \equiv \exists y \, \forall x \,R(x, y)$ (b) $\left[\forall x \, \exists y \,(R(x, y) \implies ...
2
votes
3answers
50 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
1answer
27 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
32 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 ...
6
votes
2answers
88 views

Law of Clavius explained

Law of Clavius states $ \sim P \Rightarrow P \vdash P$ And the only explanation I sort of understand is ...
1
vote
0answers
12 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
36 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 ...
9
votes
1answer
118 views
+150

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
0answers
18 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 ...
2
votes
1answer
66 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
0answers
40 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 ...
3
votes
1answer
28 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 ...
2
votes
3answers
4k views

Proving/Disproving Product of two irrational number is irrational

I saw this question where I had to prove/disprove that: Ques. Product of two irrational number is irrational. I tried 'Proof by Contraposition'. Product of two irrational number is irrational. p ...
1
vote
1answer
62 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
31 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 ...