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)

2
votes
1answer
69 views

How much set theory is necessary for serious logic?

I'm currently studying logic at my university and I have been trying to squeeze in as much set theory on the side as possible. Considering that I am spending quite a lot of time studying set theory ...
0
votes
4answers
49 views

Formulating a recursive definition

Let Σ(k) = 1 + 3 + 5 + ... + (2k+1) be the sum of all odd natural numbers from 1 up to and including (2k+1). Formulate a recursive definition for Σ including both the base case Σ(0) = 1 and a (k+1)th ...
1
vote
1answer
41 views

Equivalence between middle excluded law and double negation elimination.

It's well-know that in intuitionistic logic, middle excluded law and double negation elimination are equivalent. Let $p$ be a predicate; I proved that the implication $(p\vee\neg ...
1
vote
1answer
50 views

Contrapostive/Law of Excluded Middle

I remember that during my first proofs class the hardest thing I had accepting were the logic we had to learn, and it seems I still have questions about. So I was thinking about why when ...
1
vote
1answer
52 views

Countable Set & Formal Grammar

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary ...
1
vote
0answers
20 views

Does there exist a finite axiomatization of the quasi-algebraic theory of real matrix rings?

Some definitions. Let us take the signature of ring theory to consist of the function symbols $\{+,-,0,\cdot,1\}$ equipped with their usual airities, where the minus symbol represents a unary ...
1
vote
1answer
26 views

Suppose $R \sim_\omega R'$. Then for every $k$-tuple $a$ in $E$ and every natural number $p$, there is a $k$-tuple $b$ in $E'$ such that $a \sim_p b$

Sorry to bother you guys again with a Poizat question, but I'm struggling a little bit with the material (as it must be obvious) and I want to check if I got the main idea correctly or if I'm totally ...
-1
votes
0answers
42 views

Inference in First Order Logic [on hold]

Suppose we have $ E \bigwedge R \Rightarrow B$ $ E \Rightarrow R \bigvee P\bigvee L $ $ K \Rightarrow B$ $ \neg (L \bigwedge B ) $ $ P \Rightarrow \neg K $ which of them cannot inference from ...
4
votes
1answer
58 views

Elementary Model Theory

I'm working through section 4.3. on model theory from Dirk van Dalen's Logic and Structure (fifth ed.) and am struggling with van Dalen's sometimes sloppy way of presenting proofs. As usual let a ...
2
votes
1answer
53 views

Transfinite Cardinals and Expressive Power

Consider a language with a sufficiently rich lexicon such that, for every (finite and transfinite) cardinal K, it's possible to express the statement that there exist K-many objects. Two general ...
2
votes
1answer
31 views

Equality of sets of local isomorphisms between relations

I'm still working on the first pages of Poizat's A Course in Model Theory. I'll state the basic definitions again, in order to avoid referring back to an early question: Poizat defines an isomorphism ...
1
vote
2answers
56 views

About well formed formula

Axiom of specification is schema because it talks about definite condition(or wff) which use notion of finite but this again we define from sets. But in logic we defined wff using consept of tuple and ...
2
votes
1answer
37 views

Deciding between implication and conjunction

This is one of the solved problems in Velleman's How to prove book: Analyze the logical forms of the following statements: 1) John likes exactly one person. ...
0
votes
1answer
29 views

Two events depending on each other.

Person A goes to a party P only if person B goes, but B also only goes if A goes. Is this an uncertain statement or do they not go at all? I can think of two argumentations, of which the second is ...
0
votes
0answers
30 views

Extensions by recursive definitions

In the Wikipedia entry on Extension by definitions I learn that an explicit definition in the language of a theory $T$ yields a conservative extension $T'$ of $T$. I wonder if this eventually does ...
1
vote
1answer
80 views

Quantifier problems of equations in physics [closed]

Equations in physics are often written without quantifiers. For instance, from time to time we can see the equation $$E = mc^2$$ is casually written down. To assert that static energy equals mass ...
2
votes
0answers
35 views

Proposition into spoken language

Given: $\sim( p \leftrightarrow (q \vee r) )$ $p:$ It's raining $q:$ The sun is shining $r:$ There are clouds in the sky. Translate the proposition into spoken language. ...
-1
votes
0answers
50 views

Inner Models of ZFC which satisfy V=L [closed]

Let $M$ be an inner model of ZFC which satisfies the Axiom of Constructibilty ($V=L$). What is known about general form of such a model? Should it be similar to Godel's constructible universe ($L$) in ...
1
vote
1answer
51 views

Is it possible to iterate a function transfinite times?

Let $f:A\rightarrow A$ be a function. We can simply define $f\circ f$, $f\circ f\circ f$, etc., for each given natural number inductively. $f^{(0)}=id_A$ $\forall n\in\omega \qquad f^{(n+1)}=f\circ ...
1
vote
1answer
94 views

Miller's Construction, Partition Principle and Failure of Axiom of Choice

Partition Principle ($PP$) is the following statement: For all sets $a$, $b$ there is an injection $f:a\rightarrow b$ iff there is a surjection $g:b\rightarrow a$ It is known that $ZF\vdash ...
1
vote
3answers
78 views

Can we make illegitimate operations with $0$ legitimate by adding a few more axioms? [duplicate]

Just out of curiosity, can we make illegitimate operations with $0$, say, division by $0$ legitimate simply by imposing additional axioms? If so, then what consequences may follow? If the answer is ...
2
votes
4answers
74 views

Analyzing the logical form of “All married couples fight”

This is one of the example problems in Velleman's How to Prove book: Analyze the logical forms of the following statements. All married couples have ...
0
votes
1answer
37 views

complements of a powerset

I have a function $Q(n)=p(\{1,\ldots,n\})\setminus\{\{\}\}$ such that it won't have the empty set in it. Note, if you are going to change out my equations for Latex, I would greatly appreciate it ...
-2
votes
1answer
62 views

Inference in First Order Logic Problem [closed]

I read one logic note by Michle Sipser from MUT. I get stuck in inference. please help me in step by step inference? By using First order logic and Resolution Rules, and Proof by contradiction from ...
3
votes
5answers
141 views

Is $'' \sum_{n = 1}^{\infty} (-1)^n \; \text{is a real number}''$ an invalid statement or a false proposition?

So we're beginning an introductory logic course and my professor is giving examples for valid statements/ propositions - meaningful statements that are either true or false but not both. So he puts ...
4
votes
1answer
170 views

Replacing the “if $x ≤ y$, then $x + z ≤ y + z$” axiom in Reals.

How can I prove that we cannot (or maybe can) replace preservation of order under addition i.e. "If $x \leq y$, then $x + z \leq y + z$ with "if $0<x$ and $0<y$ , then $0<x+y$" in axioms ...
2
votes
0answers
45 views

On the back and forth conditions for a set of partial isomorphisms

I've recently begun reading Poizat's A Course in Model Theory and already in the first pages I had some doubts. One odd (not necessarily bad) thing is that he defines notions such as isomorphism only ...
1
vote
2answers
161 views

How many undecidable statements are there in ZFC?

There are several statements known to be undecidable in ZFC, with the continuum hypothesis probably being the most "popular" one. Is it known how many undecidable statements are there in ZFC? I.e. ...
7
votes
0answers
85 views

Does such a first-order theory exist? A question pertaining to transitive models of ZFC.

Assume a proper class of inaccessibles. Does there exist a first-order theory $T$ subject to the following conditions? $T$ admits an infinite model Whenever $M$ is a transitive model of ZFC with $T ...
-1
votes
1answer
42 views

looking at the alphabet ,the letters are numbered 1-26 ,

looking at the alphabet ,the letters are numbered 1-26 , such that 1 =one=15+14+5=34 (O=15, N=14, E =5 ) 2=two=20+23+15=58 (T=20, W=23, 0=15) 3=three =56 4=four=60 ...
1
vote
1answer
33 views

Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.
0
votes
2answers
43 views

Concluding Truth Value from Universe of Discourse

I have been working on the following problem from Velleman's How to Prove book: Are these statements true or false? The universe of discourse is the set of ...
3
votes
3answers
435 views

Idiomatic mathematical english statement for ∃x[P(x) ∧ ∀y(P(y) → y ≤ x)]

I have been working on problems from Velleman's How to Prove book and hit upon the following problem: Translate the following statements into idiomatic ...
-6
votes
1answer
40 views

Logical argument [closed]

Let A, B, and C be propositions. Let ∧ denote logical AND, let ∨ denote logical OR, and let ¬ denote logical NOT. Argue that if (𝐴∨𝐵) ∧(¬𝐵∨𝐶) is true, then (𝐴 ∨𝐶) must be true as well.
2
votes
2answers
68 views

Exercise about truth functions in J.R.Shoenfield's “mathematical logic”

The first exercise in Joseph R. Shoenfield's "mathematical logic" is: An n-ary truth function $H$ is definable in terms of the truth functions $H_1,\dots,H_k$ if $H$ has a definition ...
3
votes
3answers
83 views

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true … can I argue that?

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true ... can I argue that? I don't see how I can argue that $(A \vee C)$ must be true because can't we have $(T \vee T) ...
-2
votes
1answer
71 views

Single best example for mathematical reasoning [closed]

Please provide the best example to learn/teach mathematical reasoning. It is suggestible that the problem should contain at least 3 mathematical statements (not core mathematical but like Socrates ...
3
votes
0answers
59 views

Manifolds of Non-Standard Dimension

Can there exists (non-trivial) manifolds of non-standard dimensions? Certainly, there do exist manifolds of dimension $n$ for any $n \in \mathbb{N}$ (as well as manifolds of countably many ...
0
votes
3answers
103 views

Blue Eyes: A Logic Puzzle, has a puzzling solution (a.k.a. What does common knowledge have to do with it?)

In Blue eyes: a logic puzzle (specifically, the follow up questions), the most common answer is that it needs to be common knowledge that someone has blue eyes for all the blue-eyed people to leave. ...
3
votes
2answers
49 views

How to prove the following using direct proof

$[(\sim p \vee q) \wedge p ] \Rightarrow q $ What should be done next in order to apply direct proof to the example above? The following process has been already done but seemingly it's incorrect: ...
0
votes
1answer
22 views

FO-axiomatizable class?

I came across this question while preparing for my logic exam. Can this class be (finitely) axiomatizable, where the class contains all structures $\mathfrak{A} = (A, <, f)$, and for no $a \in A$ ...
0
votes
2answers
41 views

Questions regarding Universal Quantifiers

The question is to show that: $$\exists x:(P(x) \implies Q(x))\qquad\equiv\qquad\forall x:P(x) \implies \exists x:Q(x)$$ First I use double negation to get to the universal quantifier since it ...
0
votes
0answers
21 views

Connection between quantifier rank and Ehrenfeucht-Fraïssé Games

"Two $\tau$-structures $\mathfrak{A}, \mathfrak{B}$ are $m$-equivalent ($\mathfrak{A} \equiv_{m} \mathfrak{B}$) when... $\mathfrak{A} \models \psi$ iff $\mathfrak{B} \models \psi $ for all ...
3
votes
2answers
69 views

Proving $\vdash \exists x (x=c)$ for each term $c$.

I wish to prove that $\vdash \exists x (x=c)$ for each term $c$. It seems quite obvious that this would be the case, for $c$ is such an $x$, but creating a formal proof of this is escaping me. ...
0
votes
0answers
22 views

computational complexity theory(factorial)

I wanted to ask which class does factorial problems belongs to? there is the naive algorithm that solves the factorial factorial(n) = factorial(n-1) * n. but it is exponential in the length of the ...
0
votes
2answers
84 views

Understanding logical form of “Nobody in the calculus class is smarter than everybody in the discrete math class”

I'm self studying How to Prove book and have been working out the following problem in which I have to analyze it to logical form: Nobody in the calculus class ...
1
vote
2answers
46 views

Proving that $\sqrt{pq} \ne (p + q)/2$ implies $p \ne q$ using the contrapositive

Prove by the contrapositive method, that if $p$ and $q$ are positive real numbers with the property that $\sqrt{pq}$ is not equal to $(p+q)/2$, then $p$ is not equal to $q$. The proof is easy enough ...
0
votes
1answer
19 views

Analyzing Logical Forms involving quantifiers

I have been solving the following problem from How to Prove book: Analyze the logical forms of the following statement: Everyone likes Mary, except Mary ...
-2
votes
2answers
59 views

What's wrong with this induction based proof?

Claim: $\forall x \in \mathbb{R^+} ,$ $ x^n=1 $ $where$ $ n\in \mathbb{N}$ Proof by induction on n: Basis step: $\forall x \in \mathbb{R^+} ,$ $ x^0=1 $ Induction Step: Let this holds for all ...
5
votes
1answer
103 views

How much maths can we do in NF(U)?

I have recently become interested in non-standard set theories, particularly in NF and NFU and have been reading some things here and there. Of course, I don't know much about it and I'm still trying ...