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

In Whitehead and Russell's PM, are homogenous relations the only ones that have relation numbers?

Given the definition of ordinal similarity: ✳151.01 $P \overline{smor} Q = \hat{S}\{ S\in 1\rightarrow 1. C‘Q=ConverseD‘S. P=S^;Q\}$ Df. $Q$ has to be homogeneous, otherwise $C‘Q$ is meaningless. ...
1
vote
1answer
23 views

Expressing statements in positive way

I have been working on this problem from Velleman's How to prove book: Negate these statements and then reexpress the results as equivalent positive ...
0
votes
2answers
18 views

Sorting out logic homework with a friend.

My friend and I were looking over my homework and he pointed out something that he thought was incorrect. I was to write sentances using logical connectives. The original sentance was: "To get ...
1
vote
0answers
21 views

Interpreting logical forms involving quantifiers

I have been trying to translate these two logical form into English statements without using any quantifier laws: (a) ∃x∀y ¬L(x,y) (b) ¬(∃x∀y L(x,y)) where ...
0
votes
1answer
277 views

Logical Symbol Statements True/False?

so I'm working through homework questions for proofs class and unsure if I'm correct in my interpretation. I would really appreciate feedback. The questions states: Write the full meaning in English ...
4
votes
2answers
73 views

Equivalence between temporal logic and notions of forcing

I have come across literature comparing modal logic to forcing (by Hamkins et al). Has anything similar been done showing equivalences between temporal logic and forcing? This would be interesting to ...
0
votes
1answer
59 views

Analog of modus ponens for semantics

To pose my question, I first must first quickly define a language, a model, semantics for such models, and a logical system called S4O. Consider a language $L$ with a set $PV$ of propositional ...
0
votes
2answers
55 views

Why does the author define these “logical notations” for set logic with “if then” and &?

In Section 1.1 of "Set Theory for Computer Science", the author defines $ \forall x \in X. P(x) $ and $ \exists x \in X.P(x) $ as shorthand for $ \forall x.(x \in X \Rightarrow P(x)) $ and $ \exists ...
3
votes
1answer
35 views

Truth Tables for Temporal Operators?

I would like to know whether we can construct truth tables for the following temporal operators in temporal logic as we do in propositional logic . ...
1
vote
0answers
100 views

Proving that a formula cannot be proven (has no formal proof) in a given deduction system

In my homework I was asked to prove that a deduction system for modal logic with $\rightarrow$, $\neg$ and $\square$, with 4 axioms and 2 inference rules (MP and a $\square$-generalization rule), is ...
2
votes
1answer
45 views

What does this negation on both sides of K mean: A = ¬ K ¬

What does this negation on both sides of K mean: (A = ¬K¬) ? I'm not sure if it's a typo, as there are some errors in this paper (Hong et al.). Hong, Zhi Ling, and Mei Hong Wu. "Constrained ...
0
votes
0answers
15 views

$P \Rightarrow Q$ and Skolem Functions [on hold]

We know if $P \Rightarrow Q$ (it means be true), Predicate Q is Weaker than P. which of the following is Weaker? F1 is a Skolem Function, and F2 is a Skolem constant. 1) $\exists y \forall x ...
1
vote
1answer
89 views

Is it interesting to consider satisfiability modulo theory in the context of modal logic?

Recently lot of work has been done considering satisfiability of formulas in specific theory (array theory, bit-vector theory). But I did not find any results about satisfiability modulo theory in ...
2
votes
2answers
76 views

Is there a modal operator which distributes over the implication?

Is there any notable modal operator $\Box$, so that if $P,Q$ are proposition $$\left(\Box(P\implies Q)\right)\Leftrightarrow\left(\Box P\implies \Box Q\right)$$
1
vote
2answers
60 views

The Entscheidungsproblem (decision problem) for modal logic

The Entscheidungsproblem is identified with the decision problem for first-order logic that is, the problem of algorithmically determining whether a first-order statement is universally valid. ...
7
votes
3answers
6k views

Difference or relation between Inference, Reasoning, Deduction, and Induction?

What is the precise difference or relation between these terms in logic: Inference, Reasoning, Deduction, and Induction?
1
vote
1answer
28 views

Proving that a propositional theory of any cardinality has an independent set of axioms

This is exercise 1.2.19 from Chang & Keisler's Model Theory, which has been giving me a headache for some time now. Let $\mathscr{S}$ be a given propositional language of any cardinality (i.e. ...
2
votes
1answer
49 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 ...
3
votes
2answers
104 views

Can one prove existence of incommensurables without the Pythagorean theorem?

Euclid's proof that the side and the diagonal of a square have no common measure, probably going back to Pythagoreans, reduces it to proving the irrationality of $\sqrt{2}$. This reduction uses the ...
2
votes
2answers
83 views

Example of a proof using the axiom of commensurability

I'm teaching our intro to proofs course (well, one of them) and one of the classic illustrations of an overturned "axiom" is the Greek axiom of commensurability, which stated in geometric terms the ...
2
votes
0answers
103 views

Is mathematics invented or discovered? [on hold]

A google search yields millions of results, most of which are made by laymen who have nothing to do with math and it's "just another article" for the authors, so I assume here with so much passion in ...
4
votes
3answers
159 views

Do the Kolmogorov's axioms permit speaking of frequencies of occurence in any meaningful sense?

It is frequently stated (in textbooks, on Wikipedia) that the "Law of large numbers" in mathematical probability theory is a statement about relative frequencies of occurrence of an event in a finite ...
4
votes
0answers
68 views

complete, finitely axiomatizable, theory with 3 countable models

Does it exist a complete, finitely axiomatizable, first-order theory $T$ with exactly 3 countable non-isomorphic models? A few relevant comments: There is a classical example of a complete theory ...
2
votes
2answers
91 views

Equivalence between middle excluded law and double negation elimination in Heyting algebra

It's well-know that in intuitionistic logic, middle excluded law and double negation elimination are equivalent. For example, in Johnstone - Topo theory, I read that, in a Heyting algebra, $p\vee\neg ...
3
votes
0answers
44 views

What is the most expressive logic such that presentations of algebraic structures “work”?

I feel like this is one of the best questions I've asked in a while. Hope you enjoy it. In my opinion, one of the most important ideas in modern algebra is the idea that we can present algebraic ...
1
vote
1answer
62 views

What actually constitutes a *definition* for a function?

I'm reading Enderton's text on logic trying to justify ( to myself ) the use of induction on recursively defined sets. This is of course used repeatedly in trying to prove results about well-formed ...
36
votes
11answers
9k views

Why is “the set of all sets” a paradox?

I've heard of some other paradoxes involving sets (ie, "the set of all sets that do not contain themselves") and I understand how paradoxes arise from them. But this one I do not understand. Why is ...
3
votes
2answers
69 views

Is it meaningless to say $M\prec N$ for two proper class models?

Kunen in page 88 of his "Set Theory" book says: ... For a specific given $\varphi$, the notion $M\prec_{\varphi}N$ (i.e. $\forall \overline{a}\in M~~~M\models \varphi ...
-4
votes
0answers
47 views

What is the pure essence of a definition of semantics? [on hold]

What is the very essence of the definition of semantics (and interpretation, structure, model) for a logician or for an algebraist? We all know the usual definitions. But is it not the essence of ...
-1
votes
2answers
25 views

One output for input of $n$-tuples using AND, OR, NOT

Let $B$ be set of $\{0,1\}$ and $B_n$ be the set of all strings of length $n$. How many functions can be constructed from $B_n$ to $B$ using logical operators like AND, OR, NOT. Help $\rightarrow$ ...
15
votes
8answers
1k views

Assumed True until proven False. The Curious Case of the Vacuous Truth

Given two statements, $P$ and $Q$, and the logical connective, $\implies$, the truth table for $P \implies Q$ is: $$\begin{array}{ c | c || c | } P & Q & P\Rightarrow Q \\ \hline \text T ...
0
votes
0answers
25 views

LUB property in a predicative logic

Is there a formulation of real analysis in a predicative logical system such that the LUB property is available? Here is a quote from http://en.wikipedia.org/wiki/Impredicativity : "Kleene uses the ...
4
votes
2answers
161 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 ...
3
votes
2answers
55 views

Checking understanding on proving uniqueness of identity and inverse elements of a group.

Sorry for such a trivial question, but just wanted to check my understanding. When proving a statement, for example, that the inverse of a group element is unique (in elementary group theory) one ...
-2
votes
1answer
35 views

Recurring Decimals [duplicate]

If: x = 0.999... 10x = 9.999... [Multiply by 10 on both sides] 9x = 9 [Subtract x, or 0.999... from both sides] x = 1 [Divide by 9 on both sides] Therefore, 0.999... = 1 Why is this? How is it ...
1
vote
2answers
218 views

brain teaser: Mr. Honest, Mr. Liar, and Mr. Drunk

There are 3 guys, Mr. Honest, that always give the truth answer; Mr. Liar, that always give the false answer; and Mr. Drunk, that gives a random number. Now: allow you to ask 3 questions, each to be ...
6
votes
4answers
265 views

A question regarding ❋166.44 in Whitehead & Russell's Principia Mathematica

In the first step of Dem, I wonder how $\Sigma ‘\times P^{;}Q$ is transformed into $\Sigma‘ \Sigma^;(P \overset{\downarrow}{.,})\dagger^; Q$. Thanks,
4
votes
1answer
149 views

How can be a set of partial isomorphisms defined from a n-back-and-forth system?

While studying partial Ebbinghaus-Flum's Mathematical Logic, I came across the partial isomorphism definition, as build upon an $n$-back-and-forth system. Consequently, the question I raise in the ...
0
votes
4answers
55 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 ...
2
votes
1answer
33 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 ...
4
votes
1answer
189 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 ...
5
votes
1answer
344 views

Krivine Machine

Can someone please point out online resources to learn about Krivine Machine? My professor briefly touched it while teaching a course in Computer logic. google did not turn up much except some papers ...
4
votes
1answer
60 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 ...
1
vote
1answer
98 views

Please help with translation of English to first order logic

In a certain work on mereology, Alfred Tarski claims that the third following statement is deducible from the previous two: The sum of a class is defined as follows: $y$ is the sum of a class ...
1
vote
1answer
55 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
140 views

How is the double negation translation similar to CPS in functional programming languages?

In Wikipedia's Double-negation translation article, I found that any formula in classical logic has its double negation as its intuitionist equivalent: It is also possible to define φN by ...
1
vote
1answer
62 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 ...
2
votes
0answers
26 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 ...
5
votes
1answer
214 views

Showing unique prime factorization in first-order logic?

Suppose I have the symbols $\{\neg, \rightarrow, =, <,\cdot, \leftrightarrow,\land, \lor \}$ and functions $Div(x,y)$ ($x$ divides $y$), $Prime(x)$ true if $x$ is a prime, and domain $\mathbb{N}$. ...
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 ...