Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [logic]

Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the following tags as well, if they fit the question: (model-theory), (set-theory), (computability), and (proof-theory). This tag is not for logical puzzles, use (puzzle).

0
votes
0answers
23 views

Gödel's 2nd for a theory of strings over a convenient alphabet?

I am trying to find a proof of Gödel's second incompleteness theorem for an axiomatic theory T of finite strings from some fixed alphabet Γ, where Γ is, or is similar to, the set of symbols required ...
1
vote
1answer
25 views

Countable countable models

I have a proof of the following: [*] Let $A$ be a countable $\omega$-saturated model of a complete, countable theory $T$ (with infinite models). There is a bijection between the orbits under ...
1
vote
0answers
18 views

Formal Logic Reading List

My focus for my undergraduate studies was computer science, but I have been becoming more and more interested in studying formal logic on my own, and am looking for book recommendations to develop a ...
2
votes
1answer
83 views

Is there a mathematical validity of my claims?

I have a question which is not homework. Actually, I have a hard time asking the question. But I will try to express the question as clearly and clearly as I can. In the question, since I cannot use ...
4
votes
2answers
53 views

Are “ replacement rules” and “ inference rules” ( in natural deduction) really two kinds of rules?

I think the distinction, in natural deduction systems, between " inference rules" and " replacement rules" is standard. ( For example, Bergmann, The Logic Book). Is " replacement rule" anything ...
3
votes
1answer
30 views

$\mathbb{Q}^{alg}[[a,b]] $ is not elementary equivalent to $\mathbb{C}[[a,b]]$, and the same for $\mathbb{Q}^{alg}[a]$ and $\mathbb{C}[a]$?

Since ACF is complete, $\mathbb{Q}^{\text{alg}}$ is elementary equivalent to $\mathbb{C}$, and by Ax-Kochen $\mathbb{Q}^{\text{alg}}[[a]]$ is elementary equivalent to $\mathbb{C}[[a]]$. But how should ...
0
votes
1answer
14 views

Need help with relation properties using logical operators

I was wondering how should I proceed to determine what will be in the relation and what will not given these properties. Operating with integers: $R: \{(a, b)|(a= 0∧b= 0)∨ GCD(a, b) = 5\}$
0
votes
1answer
30 views

An incomplete yet decidable theory

I am working on the following exercise from Boolos' Computability and Logic: Problem. Suppose an axiomatizable theory $T$ has only infinite models. Suppose $T$ is not complete, [yet has] two ...
2
votes
1answer
40 views

Enderton's sentential “tautological implication” subsumed by Enderton's first-order “logical implication”?

(My question is clearly marked at the bottom. I don't think I'm asking the same question as this math.stackexchange.com question.) I'm working in the framework of Enderton's A Mathemtical ...
0
votes
2answers
37 views

Proof by contradiction, status of initial assumption after the proof is complete.

First of all I'd like to say that I have looked for the answers to my specific question and have not found it in the existing topics. The question is fairly simple. Say, we need to prove statement P ...
0
votes
0answers
77 views

Hall's Theorem for infinite graphs (Compactness theorem)

To Proof: Let $G = (V,E)$ be an infinite bipartite graph with $V = S \overset{.}{\cup}T$ and finite node degree for each node. G has a matching, that covers a set S iff for all subset $H \subseteq ...
0
votes
0answers
22 views

I have seen the definition of pointwise convergence, i read through logic scripts but still do not know how to read it properly.

it is not only about the definition, i want to know how to read those logicial explanations properly. It says For all epsilons and (?) for all x there exists N for all n>N: ... this does not sound ...
0
votes
0answers
14 views

Convert these statements into propositional logic statements

Can someone please help with this question. i have confusing with the question and im not sure where to start. im new to propositional logic and have no idea about convert to a statements. thanks ...
0
votes
0answers
10 views

finding the most general unifier

i am trying to find the most general unifier of the following: 1)Daughter(Uncle(y),y), Daughter(Uncle(x),emily) 2)Loves(cat(x),x), Loves(y,y) what i think: 1)$\theta = [emily/y, x/y]$ 2)$\theta = ...
1
vote
1answer
33 views

Terminology for tree-like proofs

In a tree-like proof what is the term for the number of steps between any node and the root (the statement proved by the proof)? That is, if numb were this term, then one would have depth of tree = ...
-1
votes
0answers
16 views

Are all the invalid inferences of a system valid in its extension? [on hold]

Take for example S3.5 and S5. Is every invalid inference of S3.5 valid in S5?
1
vote
2answers
50 views

Three fractions with a numerator of 1 and denominators of $a, b$, and $c$ added together equals $\frac{6}{7}$. What is $a+b+c?$

If $a, b$ and $c$ are positive integers such that $\frac{1}{a} + \frac{1}{b} + \frac{1}{c} = \frac{6}{7}$ , then what is $a + b + c?$ I start by adding the LHS together, which results in $\frac{ab+...
15
votes
2answers
204 views

Knights and knaves again on an island

In an island there are 3 inhabitants, one of which is a knight (who always tells the truth) and the other two are Jokers who randomly decide whether to tell truth or lie. The 3 men have the numbers 1, ...
-2
votes
1answer
51 views

simplify using laws and axiom of logic [on hold]

$(¬a∨b)∧(a∨b)∧¬a$ So I have been looking at this question all day and and i have no idea how to start. Can someone please help with me proving this algebra logic and what laws I would need to use? ...
0
votes
1answer
98 views

Why do we not use letters as numbers? [on hold]

To me, it seems like such a waste of energy to teach children a new set of symbols $(0,1,2.....)$ after they have learnt the alphabet. Why do we not replace $a=0$ and $b=2$ until $j=9$ and use the ...
1
vote
0answers
49 views

“Truth set” approach to validity and logical consequence: how does it relate to the standard approach? what are the possible drawbacks?

References : I think the " truth set approach" to validity and logical consequence can be linked to the name of R. Carnap ( who defines L-truth and L-implication in this way in his Introduction to ...
2
votes
0answers
53 views

The automorphism group of the countable atomless Boolean algebra does not have ample generics

I was told that the automorphism group of the countable atomless Boolean algebra does not have ample generics. I assume that one would show this by using the Fraisse-theoretic characterizations of ...
0
votes
1answer
33 views

How could I proceed in proving that a Lindenbaum algebra is atomless?

Given a $P$ infinite set of propositional variables we consider the Lindenbaum algebra generated by $P$. Then is this algebra atomless?
2
votes
1answer
43 views

Attacking proof of a statement with the form: $(\forall x \in X): ( P_1(x) \lor P_2(x) ) \rightarrow Q$

I have a statement of the form $(\forall x \in X): ( P_1(x) \lor P_2(x) ) \rightarrow Q$ but I am not sure how to approach proving it. I feel as though there is some sort of case analysis that can be ...
0
votes
0answers
40 views

Has the “ Logic of relations” chapter disappeared from logic books? ( Looking for modern references on this subject)

In Russell's Principles Of Mathematics and Principia, there was a chapter called " Logic of relations". I cannot find such a chapter in modern logic books. Could a reference having this chapter be ...
1
vote
0answers
35 views

Is the “no dictatorship” condition in Arrow's Impossibility Theorem related to the drinker paradox?

Arrow's Impossibility Theorem states that no rank-order electoral system can be designed that always satisfies these three "fairness" criteria: If every voter prefers alternative X over alternative Y,...
3
votes
1answer
51 views

If every truth assignment satisfies some wff, some finite disjunction is a tautology

Let $X_1,X_2,X_3,...$ be well formed formulas. If for every truth assignment $v$ there exists $n$ with $X_n$ satisfied by $v$, show there exists $n$ with $X_1\lor...\lor X_n$ a tautology. We can ...
5
votes
0answers
40 views

Real exponential field with restricted analytic functions: $\mathbb R_{an,\exp,\log}$ has quantifier elimination, but $\mathbb R_{an,\exp}$ does not.

At a talk sometime ago a result was presented, which I believe originates from: van den Dries, Lou; Miller, Chris, On the real exponential field with restricted analytic functions, Isr. J. Math. 85,...
2
votes
1answer
31 views

Help me with this propositional logic demonstration

This is a simple propositional logic demonstration. I’d appreciate your help. I don’t know if my answer is correct, but the textbook used another demonstration. The question $T \vee R$ $(T \vee R) \...
3
votes
1answer
49 views

Models that realize all types

Let us call a theory $T$ good if it is complete; it is formulated in a countable language $L$; it has infinite models. Suppose $T$ is good and $M \models T$, the exercise is to prove $M$ is $\...
1
vote
1answer
69 views

Propositional Logic: $Τ\vDash\varphi\implies\existsΤ_0\subseteq T$ such that $Τ_0\vDash\varphi$

Suppose $Τ$ is an infinite set of propositional types and $\varphi$ a propositional type. Prove that if $Τ\vDash\varphi$, then a finite set $Τ_0\subseteq T$ exists, such that $Τ_0\vDash\varphi$. I ...
-1
votes
4answers
74 views

Why $\forall$ is not a predicate [closed]

There is a reason why existence can not be a predicate, namely: Let's prove that unicorns exist. It is sufficient to prove that there is an existing unicorn. There are two possibilities: either an ...
0
votes
1answer
36 views

In a truth table, does a row represent technically an interpretation , or a subset of the whole ( infinite?) collection of possible interpretations?

I would like to understand more precisely the relation between the basic truth table method to test validity of formulas (and of reasonings) and the more advanced set theoretic definition of validity ...
-1
votes
0answers
22 views

Decidability, consistency, completeness formal theory help

Being T the formal theory based on the language of L, which has the axiom A → ¬¬A and the following rule of inference: R1: X |- Y -> X Determine if T is correct, complete, consistent and / or ...
0
votes
0answers
41 views

If $M$ is a transitive set and $R$ well orders $A$ in $M$, then $R$ well orders $A$ universally

I am asked to prove the following: Working in ZF - P. If $M$ is (Edit) a transitive model of ZF - P, and $R, A \in M$, then $(R \ well \ orders \ A) ^M \rightarrow (R \ well \ orders \ A)$ I am ...
2
votes
1answer
58 views

Can we prove this proposition without thinking semantics?

Let $A$ be a set of propositional symbols, $\alpha$ ba a WFF on $A$ and $M$ be a subset of $A$. And let $M^+: = M \cup \{(\neg a): a\in (A-M)\}$. Then, only one of $M^+ \vdash \alpha$ or $M^+ \vdash ...
2
votes
0answers
60 views

Relative consistency of $\mathsf{ZFC}-$Ext$+\neg$Ext+“every set has a unique powerset”

Let $T$ be the $\mathcal L_\in$-theory whose axioms are the axioms of $\mathsf{ZFC}$, with extensionality replaced by its negation, and an additional axiom specifying that every set has a unique ...
0
votes
0answers
28 views

Most General unifier in logic

i have a question about most general unifier in logic. i'll begin by saying that in the class we were only given a summary in a few words, without any example, and they just moved on to the next topic ...
0
votes
1answer
28 views

Ambiguous logic in Theorem statements

Whenever I have a proposition to prove such as this: $$f:X\rightarrow Y \text{ continuous, X connected} \implies Y \text{ connected}$$ I get confused whether the following two are equivalent to the ...
3
votes
1answer
63 views

Distributing locks and keys so certain subsets of people can open all locks

A vault can be opened by n number of keys. Five people, A, B, C, D, E are given some of the keys. Each key can be duplicated arbitrary number of times. Find the smallest number n and the distribution ...
2
votes
1answer
54 views

About Logic proof

I solute this question like that and the question need to use the logic to proof that the first part implies the second part is true is my solute right or not , would appreciate any help. \begin{...
0
votes
0answers
11 views

How to finding minterm from 5 var Boolean Expression that having 4 terms

I have this question for my assignment and I am not getting that how can we find the minterms of this expression. It has 4 terms, it is 5 variable expression and it contains NAND. i need the minterms ...
0
votes
1answer
27 views

Circle symbol for true logical statements?

I am reading the book Introduction to Higher-Order Categorical Logic by Lambek and Scott, and have run across this inference rule when they define what they call the "conjunction calculus": $$A \...
1
vote
1answer
49 views

Knights and Knaves problem from Smullyan’s “Logical Labyrinths”

I’d spent a considerable amount of time on this problem before I finally gave up and looked at the solution, where I discovered essentially the deductions identical to mine. In the solution the ...
1
vote
0answers
34 views

Can we use induction on the number of connectives?

Usually when we prove some properties of propositional formulas, we use induction on the complexity of propositional formulas, but instead, we can just use induction on the number of occurrence of ...
0
votes
0answers
40 views

Where does $(A\Delta B)\Delta C = ((A\Delta B)\cup C)\cap ((A\Delta B)^c \cup C^c)$ come from?

I am working with operations and sets, and have been reading about the symmetric difference of AΔB. The textbook has explained some equivalences of this difference, such as: $$(A\setminus B)\cup(B\...
2
votes
1answer
43 views

Decidability of Gödel sentences.

Letting $\text{Pr}(x)$ be a formula that weakly represents the set $\{x:x\text{ is a Gödel code of a provable sentence in PA}\}$, where PA means Peano Arithmetic. Gödel's first incompleteness theorem ...
-5
votes
3answers
38 views

Show that ∀a, b, c ∈ Z, a|b ∨ a|c ⇒ a|bc. [closed]

Show that ∀a, b, c ∈ Z, a|b ∨ a|c ⇒ a|bc. How would I prove the following in discrete math?
-2
votes
0answers
20 views

Rules of Inference with only 1 premise [closed]

I'm having a hard time proving the following: Premise: H Conclusion: B∨¬B Any hints?
3
votes
4answers
104 views

In Peano's Axioms are the uniqueness of the successor and $x^{\prime}=y^{\prime}\implies{x=y}$ redundant?

In Peano's Axioms are the uniqueness of the successor and the property $x^{\prime}=y^{\prime}\implies{x=y}$ redundant? This seems obvious to me, but I may be missing something. In the various forms ...