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
54 views

Proving Russel paradox using Hilbert style deduction

On Wikipedia's entry for Formal Presentation of Russel's paradox, existential instantiation ("reusing the symbol y") is one of the two steps (the other being universal instantiation) employed to get ...
7
votes
4answers
137 views

$\forall$ is “distributiv”

Recently I stumbled upon an equivalence in analysis which is of the form $\forall x\varphi(x)\leftrightarrow\forall x\psi(x)$. This made me wonder if this is mabe equivalent to $\forall ...
1
vote
0answers
101 views

How powerful is PA+Con(PA)+Con(PA+Con(PA))… etc?

From what i remember from Godel encoding there was alot of freedom in how one chooses to expresses the statement Con(PA), my question is if one can classify all statements, or some subclass of all ...
7
votes
1answer
136 views

Do metatheoretic results carry between mutually interpretable theories?

If two theories A and B are mutually interpretable, in the sense of there existing a translation procedure from A to B and from B to A, does it follow that whatever metatheoretic results (e.g., ...
3
votes
2answers
148 views

Skolemization of a Formula

I have the following formula: forall x(p(x) <- exists y q(y,x)) What is the Skolemization of the above formula?
1
vote
1answer
178 views

Convert algebraic formula to CNF

Consider the following test: $$\sum_{i=1}^n{a_ib_ic_i} \overset{?}{=} q,\tag1$$ where $a_i, b_i, c_i \in \{-1, 0, 1\}$ and $q \in \{0, 1\}.$ Is it possible to rewrite [1] to conjunctive normal ...
-1
votes
1answer
30 views

Logic forumas ( Bracketing ) propositional logic

I'm revising for an exam and i seem to be getting the questions right for propositional logic creating formulas for English sentences. But, my bracketing seems to be wrong / misplaces most of the ...
7
votes
2answers
206 views

Plausibility argument for Zorn's Lemma

In "Mathematical Physics" by Robert Geroch, the following 'plausibility argument' is given for Zorn's Lemma [If every totally ordered subset of a partially ordered set $S$ is bounded above, $S$ has a ...
2
votes
4answers
1k views

Satisfiability Problem: Determining Which People To Invite

When planning a party you want to know whom to invite. Among the people you would like to invite are three touchy friends. You know that if Jasmine attends, she will become unhappy if Samir is ...
2
votes
3answers
114 views

Truth table logic

Can someone please show me how this works, i'm going out of my mind I know the truth tables for the individual AND, OR AND NOT but when it comes to them being combined my understanding is shattered ...
4
votes
6answers
211 views

Logic puzzle - problem 298, linked below

http://www.jstor.org/discover/10.4169/mathhorizons.21.2.30?uid=3739576&uid=2&uid=4&uid=3739256&sid=21103171332151 Paraphrased (not by OP) the problem from the above link is: Three ...
3
votes
1answer
70 views

Construction of a Kurtz random sequence that's not Martin-Löf random

How can one construct a Kurtz random sequence that's not Martin-Löf random? I'm also interested in the paper that included the first of such constructions. I suspect it was in Kurtz's dissertation, ...
2
votes
2answers
1k views

Abductive vs. inductive reasoning

To me, abductive reasoning and inductive reasoning are very very similar, in that they both go from the specific to the general and they are distinguished only through the examples which are provided ...
3
votes
1answer
163 views

Can equinumerosity by defined in monadic second-order logic?

Two properties (or concepts) $F$ and $G$ are said to be equinumerous if they have the same cardinality, i.e. if they can be put in one-to-one correspondence with each other. This can be very easily ...
3
votes
2answers
138 views

Textbook on Basics of Formal Systems

Whilst trying to learn more about logic I came across Smullyan's Theory of Formal Systems on Google Books. What I liked about the book was how clearly it managed to describe (on pages 3-5 in chapter ...
1
vote
1answer
53 views

Logic question- its about propositional logic and it asks for a valuation for statisfiability

I dont understand this question that comes from a past paper, so please any help is appreciated. The part that i dont understand is what does it mean (question 3) that it wants me to consider the ...
1
vote
1answer
218 views

Addition within lambda calculus

I've been reading "The Emperor's New Mind" by Roger Penrose. He briefly introduces lambda calculus (pp. 86-92) and gives this formula for addition: $A = \lambda fgxy.[((fx)(gx))y]$ This was my ...
0
votes
3answers
85 views

Inferential logic in a simple-life situation.

Here's a little situation I want math to resolve for me : If I study, I make the exam , If I do not play tennis, I study , I didn't make the exam Can I conclude that was playing tennis ? Trying ...
7
votes
8answers
606 views

Conditional Statements: “only if”

For some reason, be it some bad habit or something else, I can not understand why the statement "p only if q" would translate into p implies q. For instance, I have the statement "Samir will attend ...
2
votes
0answers
75 views

Check that constructed recursive function proves that set is recursive.

Let $\forall\exists$-formula be any formula that looks like $\forall x_1...\forall x_m$$\exists y_1...\exists y_n \phi$, where $x_1...x_m, y_1...y_n$ - variables, $m,n \ge 0$ , $\phi$ - unquantified. ...
2
votes
1answer
41 views

Dependence on parameters in propositional logic

Warning: my background is mostly in probability and analysis, and not in logic. When reading or writing a complex proposition, with long chains of "for all... there exists... for all...", I tend to ...
1
vote
1answer
67 views

Prove the elementary equivalence of the two models

There are two models $\mathfrak A$ and $\mathfrak B$ in class $K$. $\mathfrak A = <P(\omega), \subseteq>$ $\mathfrak B = <P(\omega), \supseteq>$ Is the $Th(K)$ of a full theory of ...
2
votes
2answers
277 views

Peano arithmetic with the second-order induction axiom

I am in the middle of my PhD and I am trying to reinforce my knowledge of mathematics by studying the foundations of Analysis. The first task is to get the bases of the natural numbers. So for this I ...
3
votes
2answers
49 views

Meaning of duplicated predicate quantifiers

What is the meaning of duplicated predicate quantifiers? Examples: $$ ∃x\ ∃x\ ∀x\ ∀x\ P(xy) \\ ∀y\ ∀x\ ∃x\ ∀x\ ∃x\ ∃y\ ∃x\ P(xy) \\ ∃y\ ∀y\ ∀x\ ∃x\ ∃y\ ∀y\ ∀x\ ∃x\ ∃x\ P(xy) $$
1
vote
1answer
78 views

How are moments used in crystallization population balance calculations?

For example in this paper http://konyvtar.uni-pannon.hu/hjic/HJIC35_07_17.pdf method of moments is used to describe crystal size and other parameters. Can somebody explain how to relate normal method ...
3
votes
1answer
112 views

A theorem of formal Number Theory, according to Kleene, IM (1952)

In S.C.Kleene, Introduction to Metamathematics (1952) , I've found difficulty with the proof of 148 (preliminary to least number principle) : $\vdash \exists y[y < x \land A(y) \land \forall z( ...
4
votes
4answers
733 views

If we accept a false statement, can we prove anything? [duplicate]

I think that the question is contained in the title. Suppose we begin from something that is false for example $1=0$. Is it possible using only $\Rightarrow$ (and of course $\lnot ,\wedge,\lor$) to ...
5
votes
1answer
268 views

Was Fermat's last theorem proved based on Peano's postulates?

Is the proof of Fermat's last theorem solely based on the Peano's postulates $+$ first order logic? Or it contains other axiomatic systems as well? What does it mean from foundations of math ...
2
votes
3answers
47 views

truth of a sentence to the linearly ordered set

Let Φ - sentence of signature σ = <≤> such that for any infinite linearly ordered set A satisfies A ⊨ F. Prove that there exists n ∈ N such that for every linearly ordered set B power greater than ...
2
votes
0answers
79 views

Lowering the power of infinite model

I need to prove that for every infinite model $\mathfrak A$ of signature $\sigma$ exists model $\mathfrak B$ with attributes: $\mathfrak A \equiv \mathfrak B$. $\parallel \mathfrak B \parallel = ...
1
vote
2answers
46 views

Statements about attributes of given function.

Let $HF(0) = \emptyset$. $HF(n+1) = P_\omega(HF(n))$, where $P_\omega(A)$ - set of all finite subsets of $A$, and $HF = \displaystyle\bigcup_{n\subset\omega}HF(n)$. Are those statements true? ...
2
votes
0answers
113 views

cut elimination for infinitary logic

Takeuti (1987, 223) derives a cut-elimination theorem for infinitary logic from the soundness-and-completeness theorems. However, is there a way to adapt the original Gentzen-style proof? The ...
2
votes
1answer
258 views

Diagonal lemma in Godel Incompleteness Theorem

In the proof, we start with a numbering of all formulas with one free variable $v$. The formula $sub(x,x,y)$ used in the diagonal lemma says: $y$ is the godel number of the formula obtained when the ...
6
votes
2answers
136 views

Can we find the average of three numbers in this way?

Let $f_n$ denote the "averaging" function $[0,1]^n \rightarrow [0,1]$ defined as follows. $$f_n(x_0,\cdots,x_{n-1}) = \frac{x_0 + \cdots + x_{n-1}}{n}$$ Then clearly, it is possible to express $f_4$ ...
1
vote
5answers
3k views

The translations of “unless” and “except” into symbolic logic.

The following two exercises come from Logic for Mathematicians by J.B. Rosser, chapter 2 section one page 17. I am not so sure how to interpret the words "unless" and "except". Notation: $\sim P$ ...
0
votes
1answer
94 views

Order type of standard models of arithmetic

The standard model of PA has order type $\omega$. By compactness PA has a model of order type $\omega+n$ for any $n$, since every finite subset of the following set of statements is provable: ...
3
votes
1answer
220 views

Good books for building number/math intuition

I'm wondering if there are some good book/textbooks that were designed with algebraic logic in mind (ie. building intuition rather than rote learning). As an example of what I mean, consider this ...
-1
votes
1answer
89 views

Propositional logic gates

I've literally been trying to figure out how to do these for the past few hours. It's becoming really annoying, tedious and just wasting my time. I understand all the symbols, and can do the basics ...
0
votes
1answer
44 views

Propositional logic formula checking

I'm answering a question about propositional logic formulas, and was hoping one of you guys could check over my answer. "Either the lift doors are open or the lift is moving and lift doors are ...
1
vote
2answers
116 views

position of atomic propositons in bi-conditionals

In implication position of $p$ and $q$ is important and can't be interchanged but I guess in case of bi-conditionals these two can be interchanged freely. I mean to say $p\to q$ and $q\to p$ will not ...
1
vote
0answers
107 views

Free variables and universal quantifier in FOL

I've answered to a previous question (@LMZ : Free variables in definitions, asked Dec,15) regarding the common mathematical practice, free variables are implicitly universally quantified. The ...
6
votes
1answer
210 views

Can we capture all domains of discouse in the predicate logic within categorical logic?

In the construction of the bounded quantifiers via adjoints in the fibered category of subsets over a set (see e.g. here on Wikipedia), is there any restriction on the sets - specifically regarding ...
2
votes
3answers
42 views

Clarification on the definition of logical conjunction

First of all, I have never studied Logic seriously before. I am reading this article on Wikipedia. The definition is the following: Logical conjunction is an operation on two logical values, ...
7
votes
1answer
325 views

Axiom of Choice - Type Theory (Proof)

Background In Intuitionistic Type Theory (p. 27-28), Martin Löf provides a proof of the axiom of choice that is constructively valid. This version is considerably weaker than the ordinary set theory ...
2
votes
4answers
212 views

Book suggestion on set theory/logic

Can anyone recommend good books/tutorials on set theory/logic with simple explanations for a person with no math background (nothing beyond arithmetic and basic algebra back in school)?
2
votes
2answers
214 views

Automatic theorem prover for proving simple theorems?

Is there a simple software that I could use to practice proving theorems in my course of mathematical logic? Basically what I need is ability to 1) define what axioms and laws I am allowed to use in ...
0
votes
1answer
489 views

mathematical if else statement [closed]

What would be the best way of writing the following if else statement: if((t + n) > 25) then c = (t + n) - 25 else c = (t + n) endif or the best way ...
1
vote
0answers
38 views

On the Legitimacy of Grossone [duplicate]

A paper describing grossone used to measure such things as the sierpinski carpet here:http://arxiv.org/abs/1203.3150 I'd like to discuss the legitimacy of grossone. What is the general consensus ...
14
votes
1answer
460 views

What underlies formal logic (or math, generally)?

I read a useful definition of the word understanding. I can't recall it verbatim, but the notion was that understanding is 'data compression': understanding happens when we learn one thing that ...
4
votes
2answers
136 views

Can the material implication ever be used as the main connective within the scope of an existential quantifier?

Can the material implication ever be used as the main connective within the scope of an existential quantifier? Usually, a conjunction is the main connective in sentences bound by an existential ...