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
3 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 $\...
0
votes
0answers
14 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
42 views

Why $\forall$ is not a predicate

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

What do technically represent, in terms of “ interpretations/ value assigning functions” the rows of a truth table?

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 ...
-3
votes
0answers
27 views

find all the prime numbers (p, q, r) such that an equation hlds true [on hold]

find all the prime numbers (p, q, r) such that $\frac{p}{q}-$$\frac{4}{r+1}=1$. Guys, the problem above is from a JBMO past exam. I am preparing for it as we speak, however, I got stuck with this ...
-1
votes
0answers
13 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
20 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 ...
1
vote
0answers
20 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 ...
1
vote
0answers
36 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
20 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
27 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 ...
0
votes
0answers
14 views

Approximating a measurable set with rectangles

Let $\mathcal{U}$ be an ultrafilter on $\mathbb{N}$. Let $(S_n)$ be a sequence of finite sets of increasing length. For each $k\in\{1,2\}$, let $E_k$ denote the ultraproduct $[S_n]_{\mathcal{U}}^k$ ...
2
votes
1answer
47 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
50 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
10 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
25 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
37 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
29 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
38 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\...
1
vote
1answer
39 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 ...
-4
votes
3answers
31 views

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

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

Rules of Inference with only 1 premise [on hold]

I'm having a hard time proving the following: Premise: H Conclusion: B∨¬B Any hints?
3
votes
4answers
76 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 ...
1
vote
2answers
46 views

Correspondence between a countably infinite set A and the set of positive integers

I'm currently taking a course on logic & computability and they're using as a manual the famous "Logic and computability" by Boolos, Burgess and Jeffrey. The last week I've been trying to solve ...
0
votes
2answers
36 views

the possible permutations of a number, following a set of rules

We can change a natural number $n$ in the following ways A) If the number $n$ has at least 2 digits, we can delete the last digit and subtract it from the number remaining (for example, if we have ...
0
votes
0answers
20 views

Assumption on the bound of variables

To quote from the book in Lemma 3.3.4, we assume that all variables in the formula are bound at most once. Why is this restriction placed? Clearly the language with such a restriction is a subset of ...
0
votes
0answers
47 views

Does the language of Hilbert-style proofs lies in NTIME(n)? [on hold]

Suppose $T$ is a finite theory. Let $\mathcal{L}$ be a language of all strings that are Hilbert-style proofs in the theory $T$. Is $\mathcal{L}\in \text{NTIME}(n)$? Thank you.
-2
votes
0answers
18 views

prove syllogism is valid

I have a question where I have this syllogism in a set-theory notation: x ∈ p x ∈ h - - - - p ∩ h ≠ θ I translated it into predicate notation ...
2
votes
2answers
49 views

How can I prove that (p→q)∧(p→r) ⇔ p→(q∧r)

How can I prove that (p→q)∧(p→r) compound statements and compound statement p→(q∧r) are logically equivalent? And can I use logical equivalences on this proof?
1
vote
1answer
27 views

In FOL, can we define equality for two predicate symbols?

In FOL, I think equality is always used for two variable or constant symbols. Can we define equality for two predicate symbols? If not, why? (Do we need higher order logic to use such a concept?)
0
votes
0answers
25 views

Predicate logic proof (some a are b, some a are c, therefore there exists some c)

For the syllogism: Some A are B Some A are C ------------ There exists C Something like: My cake is pink, My cake is round, there exist things that are round We ...
4
votes
1answer
59 views

Two friends have $2$ natural written on their forehead. One is $2$ times the other + $1$. They can raise their hands.

The problem: Two friends have $2$ natural written on their forehead. One of them is $2$ times the other + $1$. Let's call them $X$ and $2X + 1$. They have to come up with a strategy to guess their ...
0
votes
0answers
7 views

Method for proving the functional completeness of connective sets [duplicate]

I've read that when dealing with sets of connectives, one approach to proving the functional completeness is taking an already known functionally complete set, i.e {$\land,\lor,\neg$} and try to ...
3
votes
1answer
77 views

In what way is the structure of the Turing degrees “extremely complicated”?

The Wikipedia article on Turing degrees states "One general conclusion that can be drawn from the research is that the structure of the Turing degrees is extremely complicated." They claim this is ...
0
votes
1answer
37 views

Relationship between consistency, strong completeness and soundness

I have trouble understanding the explanation provided in my notes which goes as follows: A set $\Sigma$ of L-formulas being inconsistent means $\Sigma\vdash\bot$. Sound means $\Gamma\vdash\...
3
votes
2answers
242 views

Why constant symbols in a language?

What is the point of constant symbols in a language? For example we take the language of rings $(0,1,+,-,\cdot)$. What is so special about $0,1$ now? What is the difference between 0 and 1 besides ...
1
vote
1answer
82 views

Motivation of the von Neumann definition of ordinals

The von Neumann ordinals are defined in such a way that each ordinal is exactly the set of all smaller ordinals. I am wondering about the origin/motivation for this definition of ordinals (that is, ...
0
votes
1answer
47 views

Does $x \notin A \backslash B $ mean $x \notin A \wedge x \in B$?

Does $x \notin A \backslash B $ mean $x \notin A \wedge x \in B$? I am trying to prove a statement where I need to use $x \notin A \backslash B$. But it does not help me, so I am assuming I am using ...
-3
votes
0answers
29 views

finding all possible combinations of a, b, c, such that a number, is a power of 2016 [on hold]

Find all the possible trios of integers (a, b, c), such that the number $N=\frac{(a-b)(b-c)(c-a)}{2}+2$, is a power of 2016 The question above is from a past JBMO exam. I attempted to solve it, with ...
-2
votes
2answers
57 views

A question, from a past JBMO exam, involving, finding all possible solutions [on hold]

Find all the solutions to the equation $x^2-3xy+p^2y^2=12p$, where x and y are integers and p is a prime number. Guys, I tried solving the question above, however, to no avail. The question is from a ...
1
vote
2answers
23 views

A quest involving modulo and coins [on hold]

A piggy-bank contains exactly 1000 coins (of 2, 5, 10, 20 and 50 cents), of total value $100. Prove that the piggy-bank contains at least one 10 cent coin. I was attempting this question, in ...
0
votes
1answer
26 views

A question invoving combinatorics and many limitations [on hold]

Three kids, Andrew, Basil and George, were listening to four different songs. None of the four songs was appreciated, by all three kids. For each of the three possible pairs of kids (Andrew and Basil ...
0
votes
1answer
22 views

Nonintuitve logical equivalence in the predicate calculus

In the first order predicate calculus as usually constructed the formula $ ((\forall x Ax) \implies B ) $ is logically equivalent to $( \exists x(Ax \implies B))$. It is not clear to me why these ...
0
votes
0answers
24 views

tricky theoretical question about input resolution(logic)

i happen to have a theoretical question about input resolution in logic. so in input resolution we can use the resolution rule/theorem if at least one out of two clauses in the resolution are from ...
0
votes
3answers
37 views

Prove that a sentence is tautology, satisfiable but not tautology or unsatisfiable

I am trying to understand how to determine whether a sentence is a tautology, satisfiable but not tautology or unsatisfiable using the right approach Example: (¬up → ¬down) → ¬up I tried the ...
0
votes
2answers
60 views

How to turn into conditional statements the equations of physics? Looking for basic examples ( at the high school physics, college physics level).

My question is related to philosophy, but I do not ask for a philosophical answer. I would be interested in a technical answer from a logician's / mathematician's point of view In basic philosophy ...
1
vote
2answers
70 views

“For all X, X =A iff X=B, therefore the A = B”. Is this logically correct?

Suppose I want to prove ( in elementary arithmetics, or, maybe, in an abstract additive group) that : the additive inverse of (a+b) = -b + -a May I proceed as follows? Suppose X = - ( a+b). Now,...
4
votes
3answers
55 views

Prove $\vdash (A_1 ↔ A_2) \vee (A_2 ↔ A_3) \vee (A_3 ↔ A_1) $ using natural deduction.

I think this is true. Because by the pigeon hole principle, Two of $A_1, A_2, A_3$ must have the same true value. But I have no idea how to prove it.. Can somebody help me? Of course, we can use ...
1
vote
1answer
39 views

Relation of self-application to non termination in the untyped lambda calculus.

I was reading the following question: Self-application in Church's untyped lambda calculus First, we can have terms which, if applied to themselves, still have normal form. For example, $(\lambda ...
0
votes
1answer
36 views

proving the independance of an equation, from certain variables

The different and unequal to zero real numbers x, y, z satisfy the equation $x^3+y^3+m(x+y)=y^3+z^3+m(y+z)=z^3+x^3+m(z+x)$ prove that $K=(\frac{x-y}{z}$ $+\frac{y-z}{x}$ $+\frac{z-x}{y})$ $(\frac{z}...