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)

2
votes
0answers
32 views

Logic to identify the “minimal paths” in a directed (ordered) acyclic graph (DAG)

I am a reliability engineer and nowadays trying to write a code which analyse complex reliability block diagrams (RBD). (my profession is industrial eng.) RBD properties (valid always): directed ...
1
vote
1answer
657 views

consider the two statements “all rhombi are squares” and “no rhombi are squares” are these two statements negations of each other?

Explain your reasoning I think their negations but do not know how to explain it. I need help But I do know that: Every square is a rhombus, but every rhombus is not a square. A square must have all ...
2
votes
1answer
39 views

Intuitionistic Logic: introduction and elimination rules for the universal and existential quantifiers

Are the natural deduction introduction and elimination rules for the universal and existential quantifiers in Intuitionistic Logic the same as those for Classical Logic?
2
votes
1answer
25 views

Did I analyze the logical form of a statement well?

Analyze the logical forms of the following statements. You may use the symbols ∈, !∈, =, !=, ∧, ∨, →, ↔, ∀, and ∃ in your answers, but not ⊆, ⊆, P , ∩, ∪, \, {, }, or ¬. (Thus, you must write ...
5
votes
0answers
116 views

ZF and weakly inaccessible cardinals

This question should probably have been asked 3 years ago (perhaps it has and was removed for some reason?) In 2011, Alexander Kiselev claimed to have proved in ZF that there are no weakly ...
3
votes
2answers
40 views

Write $(p↔q)$ in DNF

I have the following formula: $(p↔q)$ and I have to write in DNF (disjunctive normal form) This is where I got so far: $(p↔q) = ((p→q)∧(q→p)) = ((¬p∨q)∧(¬q∨p))$ but here I got stuck. How ...
0
votes
1answer
52 views

Question about understanding an Interpretation definition in First Order Logic

I am trying to understand a definition within First Order Logic using interpretation. Below is the specific interpretation definition We define the truth value of a formula A in an interpretation I. ...
3
votes
1answer
75 views

Models of the successor function

I would like to ask a few questions about models of the succesor function (s(x)=x+1), intact that is a bit vague, consider $T_{S}$ to be the set of axioms given by; S1: $\forall xy[s(x)=s(y) ...
2
votes
1answer
100 views

A problem in the first-order predicate calculus.

So the teacher decided to make our life harder by giving us an extra-credit problem: Use the language of the first-order predicate calculus to express that in a group $ S $ of elements with a ...
1
vote
1answer
35 views

Every positive formula is satisifiable

We say that a propositional logical formula is positive if it does not include the negation connective ¬ anywhere in it (but it may still use ∧, ∨, ↔, →, and propositions). Show that all ...
1
vote
1answer
75 views

This sentence is false

"This sentence is false". Is this sentence true or false? My attempt: If this sentence were true, then what it says would be the truth , it implies that it is false which is a contradiction. if ...
5
votes
0answers
50 views

Deductive closure of sentence $\forall x \forall y F(x,y) \stackrel{.}{=} F(y,x)$ in language $\mathcal{L}$ is undecidable.

$\mathcal{L}$ is the language that contains a single binary function symbol $F$. In the earlier parts of this question, we were told to take the $\mathcal{L}$-structure $\mathcal{M}$ with universe ...
2
votes
2answers
73 views

Ordinals - motivation and rigor at the same time

Can someone provide a description of ordinals within ZFC in a rigorous way that exhibits motivation? Every description or explanation I see in the literature or on the Internet is either too formal ...
2
votes
0answers
37 views

Models and signatures for propositional logic

The following is a bit long, so I collected my questions at the end, but as this is the only opportunity I get for feedback I would appreciate it if anyone could also point out where I've gone astray ...
3
votes
2answers
103 views

Is there a more useful formulation of the frame condition for the McKinsey axiom?

I am looking for a Kripke frame condition corresponding to the McKinsey axiom M: $\Box\Diamond p \rightarrow \Diamond\Box p$. I read somewhere the following condition: "For every partitioning of the ...
1
vote
3answers
117 views

Definition of the mathematical proof

How do we define a mathematical proof? Is it a series of arguments? Is it a series of conclusions? Is it manipulation of formulas? Is it a mixture of laws of logic and axioms,theorems or ...
1
vote
3answers
53 views

Are cardinal numbers sets in ZFC?

Are cardinal numbers sets in ZFC, or just proper classes? If they are sets, what is their structure?
1
vote
1answer
35 views

Every complete axiomatizable theory is decidable

Enderton (in A Mathematical Introduction to Logic) gives the following theorems: Theorem $17$F : A set of expressions is decidable iff both it and its complement (relative to the set of all ...
1
vote
1answer
49 views

Mathematical Logic descending chains

I'm working on a mathematical logic question. Suppose $<$ belongs to $S$ and $\Phi \subseteq L_{0}^{S}$. Assume that for any $m \in \mathbb{N}$ there is a model $\mathfrak{A}$ of $\Phi$ such ...
1
vote
2answers
3k views

Is an anti-symmetric and asymmetric relation the same? Are irreflexive and anti reflexive the same?

I don't understand the difference between an anti symmetric and asymmetric relation. From my understanding, it is asymmetric if there is not any element where: if (x,y) (y,x). But what if you have ...
1
vote
2answers
28 views

Proving that a set with a quaternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{N\}$ of one logical connective is inadequate where $N$ is a quaternary connective that is defined as follows: $N(w,x,y,z)=((x\land y)\land(w\lor z))$ ...
1
vote
1answer
69 views

About the proof of a test for quantifier elimination.

I've been reading D. Marker's book on Model theory. In the part dealing with quantifier elimination there's a corollary I've been trying to prove without any luck: Corollary 3.1.6 Let $T$ be an ...
4
votes
0answers
90 views

Mathematical Thinking - How does it work? [closed]

Not only am I hoping you can answer my question, but perhaps refine my question itself. Unfortunately it is something I do not know how to ask, but I will give it my best attempt. Either I ask it, or ...
1
vote
0answers
49 views

Primitive recursivness of a function. How does the function work?

So, I need some help with an homework assignment. Firstly: understanding the following function: $h(x) = \prod_{m=0}^{f(x)} m*f(m)$ From my limited knowledge of the product of sequences my guess is ...
2
votes
1answer
41 views

$\mu-$recursive functions

In my book there is the following: Although the class of primitive recursive functions contains a great many functions of practical interest, it does not include all the Turing-computable or ...
6
votes
1answer
60 views

Distance between theorems

In automated proving one can define the best proof of a theorem as the one which minimizes the length of the proof. Given a set of known statements one could define the difficulty of a theorem as the ...
1
vote
1answer
57 views

Undecidable definition of pure function

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
0
votes
0answers
32 views

Church’s Thesis with regard to R-decidability and R-enumerability.

Church’s Thesis with regard to R-decidability and R-enumerability: If some set is enumerable/decidable, then there exists a program, i.e., a register machine, with respect to which the set is ...
1
vote
1answer
38 views

Translate proposition into formal language

Knowing that predicate $P(x)$ means '$x$ is a prime number' and $a/b$ denotes '$a$ is a divisor of $b$' express the following using logical operators, quantifiers, etc: 'number $z$ is a divisor of the ...
8
votes
6answers
2k views

How do the Properties of Relations work?

This is simply not clicking for me. I'm currently learning math during the summer vacation and I'm on the chapter for relations and functions. There are five properties for a relation: Reflexive - R ...
3
votes
2answers
33 views

Decidability of predicate calculus with equality only

I read in some books that propositional calculus is decidable (e.g. with truth tables), and predicate calculus is not decidable (as proved by Church and Turing). Unfortunately, I do not exactly ...
2
votes
2answers
47 views

Logical Implication Question

$A: \text{Humans are at most 12 feet tall}$ $B: \text{Humans are at most 9 feet tall}$ Neither implies the other. A contradicts B and B contradicts A. Am I correct?
2
votes
1answer
59 views

Argue that if a sentence has a proof, then it is a tautology

This is a corollary of the soundness theorem, which states that for a set of formulas $\Phi$ (of propositional logic) and a formula $\alpha$ : $$\Phi\vdash\alpha\Longrightarrow\Phi\vDash\alpha$$ What ...
9
votes
2answers
150 views

Can $T$, $T+A$, and $T+\neg A$ all have different consistency strengths?

Let $T$ be a consistent theory, and let $A$ be a statement in the same language. Consider the three theories $T$ $T+A$ $T+\neg A$ Is it possible for them to be pairwise distinct in consistency ...
2
votes
2answers
129 views

Study of all published works of Bertrand Russell on foundations of mathematics: Please recommend his works.

Study of all published works of Bertrand Russell on foundations of mathematics: Please recommend his works. I think Bertrand Russell was a special mind and I set a goal for myself to study all his ...
2
votes
1answer
27 views

Question regarding using the natural deduction system

I have the following: Premise: ((V → ¬W) ∧ (X → Y)) Premise: (¬W → Z) Premise: (V ∧ X) |- (Z ∧Y) The part I want to know is how do I go about separating ...
0
votes
1answer
22 views

Showing that calculus are (not) equivalent

Let $\mathcal{A} = \{ x,y \}$ be an alphabet. Consider the following rules for derivation: $R_1 : \begin{array}{c} \hline \epsilon \end{array},\\R_2: \begin{array}{c} z \\\hline zx \end{array},~ R_3: ...
9
votes
2answers
596 views

Who stole the axioms in Natural Deduction?

The study of Gentzen's sequent calculus give me the opportunity to propose some reflections about the concept of logical truth. I'll refer to the english edition of Gentzen's works : The collected ...
4
votes
3answers
144 views

A function defined for all inputs?

This might seem like a weird question, but is it actually possible to define a function for all possible inputs? By this, I really mean /all/ possible inputs, including numbers, true and false, sets, ...
2
votes
2answers
62 views

Soft question about logic and Banach-Tarski Paradox

I precise for the possible down voters that I'm not student in maths I'm learning chemistry, and my friend is learning litterature, and we were speaking about BT paradox, my friend discovers this ...
4
votes
2answers
83 views

Every theory eliminates quantifiers in an appropriate definitional expansion?

I need to prove that every theory eliminates quantifiers in an appropriate definitional expansion. For this, consider: let $T$ be a theory in language $L$. Consider the following expansion of the ...
2
votes
0answers
70 views

What are the connections between linear algebra and logic?

I was wondering whether someone could tell me what connections there are between linear algebra and first order or second order logic, whether it be the model theoretic or proof theoretic component of ...
1
vote
2answers
60 views

Deduction theorem in modal logic

I am looking for a semantic for deduction theorem in modal logic,I wanna find a semantic way to prove this theorem,but I wasn't successful.tnx for your help
2
votes
4answers
97 views

Logical puzzle. 3 Persons, each 2 statements, 1 lie, 1 true

I got a question at university which I cannot solve. We are currently working on RSA encryption and I'm not sure what that has to do with the question. Maybe I miss something. Anyway, here is the ...
0
votes
1answer
47 views

A formula that, when plotted, yields its own display

I've just seen a video on Tupper's self-referential formula. When I heard that this formula was not at all self-referential but merely a simple way to generate every possible $17\times 107$ dot matrix ...
1
vote
1answer
28 views

If for any $M' \subseteq M$ there is an embedding of $M'$ into a $Mod(T)$, then there is an embedding of $M$ into $Mod(T)$.

I need to prove that, for $M$ a given $L$-structure and $T$ be a theory in the language $L$. Show that if for any finitely generated substructure $M'$ of $M$ there is an embedding of $M'$ into a model ...
0
votes
1answer
76 views

Disjunctive normal form and shannon normal form

Consider the formula (( true | (a <-> b)) & ((c | b) ^ a ^ b)). transform the formula into disjunctive normal form for the variable ordering a ≤ b ≤ c ≤ d. Also transform to Shannon normal form ...
0
votes
0answers
22 views

Construction of atomically closed tableu from a closed tableu

Suppose we have a closed tableu with at least one branch $\theta$ that contains $X$ and $\neg X$ where X is non-atomic formula. My strategy could be that of exploring the cases of X being an ...
3
votes
1answer
65 views
3
votes
1answer
52 views

What is the set of propositional formulas?

What is the set of propositional formulas? I am not sure if I understand this