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
0answers
16 views

Are the logical [equivalence] laws sound and adequate without de Morgan's law?

I need to say whether the system of logical laws made of: Double negation Commutative Associative Distributive Idempotent Implication Contradiction de Morgans Absorption Equivalence is sound and ...
0
votes
2answers
20 views

Correct Form of a Logical Statement

I ran across a problem which has stumped me involving existential quantifiers. Let U, our universe, be the set of all people. Let S(x) be the predicate "x is a student" and I(x) be the predicate "x is ...
1
vote
1answer
78 views

Why Does The Reflection Principle Fail For Infinitely Many Sentences?

I've read the proof that ZF cannot be finitely axiomatized via the reflection principle and the 2nd incompleteness theorem. Since ZF can be countably axiomatized, the finiteness requirement in the ...
-5
votes
0answers
47 views

Maths question . Please ans in detail. [on hold]

116 People participated in a knockout tennis tournament . the players are paired up in the first round, the winners of the first round are paired up in the second round, and so on till the final is ...
1
vote
0answers
20 views

Prove Ordering of Mixed Quantifiers

I'm trying to familiarize myself with some of the formal logic behind mathematical proofs, and I'm having trouble proving some things explicitly even though I have no trouble with them intuitively. ...
-1
votes
2answers
23 views

Proof structure validity: assume (a), (b), show (c). Then Permute.

I am given a collection of sets $\mathcal{E}$ and am trying to prove it is an elementary family. To show $\mathcal{E}$ is an elementary family I must show that it satisfies the following properties: ...
0
votes
1answer
22 views

Properties of transitive modal frames

I am working through Fitting and Mendelsohn's First Order Modal Logic and have come across the following exercise: Prove that a frame $\langle \mathcal{G}, \mathcal{R} \rangle$ is transitive if ...
0
votes
2answers
55 views

Goldbach Conjecture predicate form?

I am learning logic, and when I was taking a quiz one of the multiple choice questions was "Which of the following is an unsolved conjecture?" I picked the following answer because I thought it was ...
2
votes
3answers
62 views

How do set theory, and formal logic fit in together?

Im at that stage in my mathematical understanding where I kinda understand what set theory is and what first order logic is but dont really understand how they fit together to create Mathematics. I ...
5
votes
3answers
925 views

How can the axiom of choice be called “axiom” if it is false in Cohen's model?

From what I know, Cohen constructed a model that satisfies $ ZF\neg C $. But if such a model exists, how can AC be an axiom? Wouldn't it be a contradiction to the existence of the model? Only ...
1
vote
2answers
34 views

Orders with no anti-symmetry requirement?

A ordered/partially ordered set is required to satisfy the $x \leqslant y$ and $y \leqslant x$, $\implies x=y$ (antisymmetry) axiom. Are there any viable theories where this condition is weakened? ...
0
votes
3answers
75 views

Godel's Second Incompleteness and the Assumption of Consistency

As I understand it, Godel's Second Incompleteness Theorem states that given a theory $T$ that is any extension of Robinson Arithmetic, that if that theory is consistent then it cannot prove a given ...
8
votes
1answer
58 views

Is an infinite system of (linear) equations solvable if all finite subsystems are?

I was wondering about the following. Let $A$ be an abelian group, $a_i$ variables indexed with some arbitrary set $I$ and assume we have an infinite set $E$ of linear equations in finitely many ...
3
votes
0answers
28 views

Model-theoretic characterization of local modal correspondence

I've been reading van Benthem's dissertation (available on ILLC's website) on modal correspondence theory. In Section I.3, he develops a model-theoretic characterization of modal formulas having ...
3
votes
3answers
63 views

Prove that if $\mathcal{F} \subseteq \mathcal{G}$ then $\cup\mathcal{F} \subseteq \cup\mathcal{G}$

Suppose $\mathcal{F}$ and $\mathcal{G}$ are families of sets. Prove that if $\mathcal{F} \subseteq \mathcal{G}$ then $\cup\mathcal{F} \subseteq \cup\mathcal{G}$ My attempt: Given $\mathcal{F} ...
2
votes
1answer
66 views

Questions about Gödel, formal systems, propositional calculus and first order logic.

I've been reading Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid, and I'm loving it, though there are some things I don't quite understand yet. Propositional Calculus is a formal system, ...
1
vote
1answer
25 views

Is PA+ TM doesnt halts consistent?

Suppose there isnt a proof in PA whether some TM halts or not. Suppose further that TM doesnt halt and PA is consistent. Is PA+TM halts necesserely consistent? Is PA+TM doesnt halt necesserely ...
0
votes
1answer
19 views

choose from implication and logical and in write assertions in first-order logic

I am a student and I get confused in translating some sentence to logic assertion. For example: Joe does not have a lawyer, i.e. is not a customer of any lawyer. The right way to translate is: "For ...
-3
votes
0answers
45 views

Diagonal lemma logic [on hold]

The substitution formula sub( x,x,y) says y is the code of the formula obtained when in the formula whose code is x, the numeral for x is substituted for the free variable. Both x and y are free in ...
3
votes
0answers
41 views

$F[t]$ has undecidable positive existential theory in the language $\{+, \cdot , 0, 1, t\}$

Consider the ring $F[t, t^{-1}]$ (the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$). Theorem 1. Assume that the characteristic of $F$ is zero. Then the existentia theory ...
0
votes
3answers
85 views

Please Help me understand this proof

DOUBT What i didnot understand is from where it is written our new goal means there exists a... I didnot understand how there exists word popped up here and why the new givens are written as they ...
2
votes
2answers
57 views

How do I express logical connectives with Nand?

Really struggling to understand how to express all the connectives as Nand. I understand that p ^ q would be the opposite of p nand q, but I get stuck when trying to express p -> q and p v q in ...
1
vote
0answers
38 views

A mistaken proof of consistent choice?

Given a set of sets ${\cal A} = \{S_i\mid i\in {\cal B}\}$ and a binary relation $Con$ on $\bigcup {\cal A}$, a $Con$-choice on $\{S_i\mid {i\in F}\}, F\subseteq {\cal B},$ is a function $\epsilon\in ...
1
vote
1answer
79 views

Prove that “No one likes Reggae music” is the same as “Everyone does not like Reggae music”.

I interpreted this as a case of the extension of De Morgan's Law to quantifiers. https://en.wikipedia.org/wiki/De_Morgan%27s_laws#Extensions I know that similar questions have been asked before about ...
1
vote
1answer
31 views

How to represent the sentence “If everyone votes then the motion passes” with FOL

Should it be ∀x Votes(x) ⟹ Passes(Motion)? Probably not, because if none but 'John' votes, then using extended interpretation, ...
1
vote
1answer
22 views

Prove that if $\forall A \in \mathcal F (B\subseteq A)$ then $B \subseteq \bigcap \mathcal F $

This is Velleman's exercise 3.3.10. Suppose that $\mathcal F$ is a nonempty family of sets, B is a set, and $\forall A \in \mathcal F (B\subseteq A)$. Prove that $B \subseteq \bigcap \mathcal F $. My ...
0
votes
0answers
16 views

Clarification of conditional propositions [duplicate]

I am studying first order logic and we have been introduced to conditional propositions.$(p \Rightarrow q)\;$ The truth table for $p \Rightarrow q$ is this: ...
1
vote
2answers
96 views

Formula that's only satisfiable in infinite structures

What formula in first order logic can I write that's only satisfiable over infinite structures, over a dictionary without the = sign?
0
votes
3answers
69 views

Please help me understand the proof

Doubt In third line of the proof, why is Q $\rightarrow$ R ? Thanks
2
votes
1answer
65 views

What is the definition of a definable set of statements, and what is a constructive way to think of this regarding Tarski's Undefinability Theorem?

Logic and model theory are not my area so my thinking is probably off, but I am curious about this so please go ahead and set me straight. A definable set is one for which there is a formula that is ...
3
votes
0answers
93 views
+200

Algorithm to answer existential questions - Reduction

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 ...
2
votes
1answer
66 views

Meaning of “such that”

The use of the term "such that" 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 ...
3
votes
2answers
65 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 ...
2
votes
2answers
41 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 ...
2
votes
2answers
64 views

Order of statements in implication

The question is from Exercise 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
34 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
41 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 ...
-1
votes
2answers
66 views

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

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 ...
3
votes
2answers
64 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
43 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 ...
-3
votes
0answers
27 views

prove that ¬[P ∨ (L)→M |- M [closed]

prove that need help to prove that examples
1
vote
3answers
70 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 ...
0
votes
1answer
28 views

prove [(¬M∧R)∧Q |- Q∨T [closed]

prove [(¬M∧R→Q |- Q∨T really confused :(
-1
votes
1answer
35 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 ...
2
votes
2answers
47 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 ...
1
vote
0answers
68 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) = ...
4
votes
1answer
96 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$?
3
votes
4answers
120 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 ...
1
vote
3answers
76 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 ...
0
votes
1answer
25 views

Logic question and proportions [closed]

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