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

Clarification on deductive consequence

The Standford Encyclopedia on Philosophy page on Classical Logic has the following theorem: Theorem 12. A set Γ is consistent if and only if there is a formula θ such that it is not the case that Γ ⊢ ...
10
votes
2answers
185 views

A group is not the union of two subgroups, constructively.

Let $G$ be a group, and let $H$ and $K$ be subgroups of $G$. The following is well-known: Proposition 1. If $H \cup K = G$, then $H = G$ or $K = G$. See, for instance, this answer. Question. Is ...
1
vote
3answers
64 views

Syntax of First Order Logic [duplicate]

Give a counter example to show that a sentence of the form $\forall x (F \vee G) \rightarrow (\forall x F) \vee (\forall x G)$ I know that I should use two particular formulas $F$ and $G$ from some ...
1
vote
2answers
76 views

Quantifier Statements

$\exists x\forall y, \exists z \ni xz=y$. $\forall x, \forall y, \exists z \ni z>y \implies z>x+y$. Other than testing lots of values, is there a way to determine if the above two ...
3
votes
4answers
127 views

Proving equivalences

Here I have a proposition: ((¬p ∨ x) ∧ (p ∨ y)) → (x ∨ y) I am proving that it's a tautology but I wanted to know if what I am doing is correct. I'm just learning equivalences, I have tried to type ...
0
votes
1answer
265 views

necessity and sufficiency condition

I'm trying to solve the following excercise (Houston: How to Think Like a Mathematician; Exercise 27.23): Consider the following statements (a) $n$ is divisible by 3, (b) $n$ is divisible by 9, (c) ...
2
votes
3answers
516 views

Predicate Logic Translating “All But One”

I need to translate an English sentence including the phrase "all but one" into predicate logic. The sentence is: "All students but one have an internet connection." I'm not sure how to show "all but ...
1
vote
1answer
117 views

Constructing a parallel composition from a given transition system and automaton

I am looking at an exercise, where it asks me to construct a parallel composition from a given transition system and an automaton. The transition system looks like this: and the automaton (with ...
2
votes
2answers
79 views

Getting weird results

Consider two nonempty sets $ S $ and $ T $, $S\subseteq T$. We can write: $$\forall x (x\in S \Rightarrow x\in T) $$ Knowing, that $ p\Rightarrow q $ is equivalent to $\neg (p \wedge \neg q) $, we ...
1
vote
3answers
84 views

$(\forall x \in D) (P(x)) \Leftrightarrow (\forall x)(x\in D \implies P(x)) $. how are two the same?

Assuming all the variables are naturals, why are those two equal? I don't get how $\implies$ is introduced in the latter equation: $(∀x)(x∈D \implies P(x))$ Thanks.
1
vote
1answer
145 views

How one can prove inadequacy of a set of propositional connectives?

My question is that how can I for example prove that connectives and (^), or (v), and implication (=>) cannot be defined using only negation (~) and equivalence (<=>)? What is the general strategy ...
0
votes
2answers
379 views

For all $y$, there exists an $x$ where $x\geq y$

For all $y$, there exists an $x$ where $x\geq y$ Is this statement true or false? If so why? My note says it's true, but I don't really get why. Thanks!
1
vote
2answers
323 views

Russell's Paradox

Many of you know such paradox... " $\exists y \forall x (x \in y \Longleftrightarrow \Phi(x)$" for any function $\Phi(x)$ substitute $x \notin x$ for $\Phi(x)$ Then by existential instantiation ...
1
vote
1answer
398 views

Neither Even Nor Odd Natural Numbers

I confused myself and the OP when I tried to answer a recent question. Modular arithmetic (MA) has the same axioms as first order PA except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. ...
3
votes
0answers
67 views

Are there some kind of “multialgebras” with terms or equations, where an operation can result with different values in different places?

Many-valued (multivalent, polivalent) operations are studied in multialgebras. Applied to a certain value of its argument, a many-valued operation o(x) can result in different values. But in ...
0
votes
3answers
290 views

If the contrapositive of a statement can be proven directly, can that statement itself necessarily be proven directly?

So to be more formal: Given statements $A$ and $B$ such that a direct proof exists for $\neg B \implies \neg A$, is there necessarily a direct proof for $A \implies B$. By "direct proof," I mean a ...
1
vote
1answer
341 views

What is the order of precedence for a statement containing the universal quantifier and an implication?

In the statement $\forall x:X \bullet p(x) \Rightarrow q(x)$, does the universal quantifier apply over the predicate q? i.e. it is equivalent to $$\forall x:X \bullet (p(x) \Rightarrow q(x))$$ or ...
2
votes
1answer
69 views

Translate a text into a set of inference rules

I'm working on a question from one of my past college test. I have to translate a text into a set of formal rules of inference. The text is: "Ugo is a LP student that also writes software in ...
2
votes
0answers
67 views

How strong is ramified predicative second-order arithmetic?

A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...
3
votes
2answers
87 views

How to say that $f(x,y)$ is true for all x but only some y.

I have to translate an English sentence into logical statements using quantifiers, and I think I'm on the right track but something doesn't feel right about this. I'm not really sure how I should take ...
4
votes
1answer
114 views

What assumptions can be used to prove the equivalence of two subformulae?

Let $\tau$, $\sigma$ and $\sigma'$ denote formulae in some language of interest, and suppose we wish to show that $$\tau \wedge \sigma \iff \tau \wedge \sigma'.$$ Then obviously, it suffices to show ...
2
votes
1answer
65 views

Deciding Consistency

Decide if the following subsets of Form are consistent: $$\{P_{1} \lor P_{2}, P_{2} \lor \neg P_{3},\neg P_{3} \lor \neg P_{4}, P_{3} \lor \neg P_{1}, \neg P_{2} \lor P_{4}\}$$ $$\{ P_{1} \to ...
10
votes
1answer
534 views

Why is CH true if it cannot be proved?

Continuum hypothesis (CH) states that there can be no set whose cardinality is strictly between that of integers and real numbers. Godel, 1940 and Paul Cohen,1963 showed that CH can neither be proved ...
2
votes
1answer
100 views

Where is the least upper bound property used in transcendence proofs?

The second-order theory of real numbers is what you get when you take the axioms for ordered fields and add one more axiom, the least upper bond property, also known as Dedekind completeness: that ...
1
vote
2answers
226 views

What does the negation of set difference give?

I was given the following problem: For sets A, B, C, and D. Prove or disprove that $(A-B)-(C-D) = (A-C)-(B-D)$. My proof by counterexample was: Let $A=\{1,2\}, B=\{2,3\}, C=\{3,5\}, ...
5
votes
3answers
852 views

Prove that transcendental numbers exist: Are there less paniful ways of doing it?

I've found this exercise on Boolos' Logic and Computability: A real number $x$ is called algebraic if it is a solution to some equation of the form: $$c_{\small d}x^{\small ...
2
votes
1answer
99 views

a logical proposition

Here I have a proposition: ((¬p ∨ x) ∧ (p ∨ y)) → (x ∨ y) To prove whether a tautology or contradiction or neither. ≡ ¬[((¬p ∨ x) ∧ (p ∨ y))] ∨ (x ∨ y) implication equivalence ≡ (¬(¬p ∨ x) ∨ ...
2
votes
1answer
91 views

Is open induction as strong as bounded induction without free bounds?

As was established in my question here, one reason that $Q$ + induction on formulas with bounded quantifiers is stronger than $Q$ + induction on quantifier-free formulas is that the variable that ...
6
votes
2answers
176 views

Olympiad inequality: is this reasoning sound?

I am trying to show that for $a,b,c>0,\;abc=1:$ $$\underbrace{\frac{1}{b(a+b)}+\frac{1}{c(b+c)}+\frac{1}{a(c+a)}}_{X}\geq \frac{3}{2}$$ This problem is from the Zhautykov Olympiad of 2008. ...
1
vote
1answer
92 views

Show that α is tautologically equivalent to β iff (α↔β) is a tautology?

α|==|β iff |= (α↔β) Does anyone know how to go about showing that this is true?
1
vote
2answers
115 views

Prove this logical equivalence.

I'm determining whether this logical proposition is a tautology or a contradiction. I'm stuck in the middle of this equation, and cannot move further using only logical equivalences. The proposition ...
2
votes
1answer
83 views

Equality and order in sets

Just started Baby Rudin and got struck in this. While defining order in sets, $<$ was introduced as a relation and for a set to be ordered the condition was: for all $x,y$ belonging to an ordered ...
0
votes
3answers
72 views

Help explaining a logical math statement

All variables are part of $M$ which consists of airports. The predicate $p(x, y)$ means "there's a direct flight from $x$ to $y$). Explain the statements: #1: $\forall x\forall y\exists z ...
0
votes
1answer
194 views

Partial order relation

Define the relation $\leq$ on a boolean algebra $B$ by for all $x,y\in B$, $x\leq y \iff x\lor y=y$, show that $\leq$ is a partial order relation. First of all what exactly does boolean ...
6
votes
1answer
158 views

Why is bounded induction stronger than open induction?

It seems to me that any formula in the language of first-order arithmetic which has only bounded quantifiers can be written as a formula without any quantifiers. For instance, "There exists an n ...
0
votes
2answers
69 views

Is it a tautology?

I have this: $$(p \lor q) \oplus (\lnot p \land \lnot q) $$ Here are the steps I took: First I took the equivalence of $$p \oplus q \equiv (p \land \lnot q) \lor (\lnot p \land q)$$ Let $a= p ...
0
votes
2answers
103 views

Prove that “If $n^2+m^2 = k^2$, then $n$ is uneven or m is even” [closed]

So I've been trying to prove this for like two hours. I think that I should form the antithesis first(to get rid of the OR) which is "If $n^2+m^2 = k^2$, then $n$ is even and $m$ is uneven" $m,n$ ...
2
votes
2answers
206 views

Short symmetric formula for 'at most one of P, Q, and R is true'?

Just now I discovered that $$ \text{at most one of } P, Q, R \text{ is true} $$ is equivalent to $$ ((P \equiv Q) \land (Q \not\equiv R)) \:\:\equiv\:\: R $$ I like this, but I don't like the loss of ...
14
votes
2answers
458 views

What practical proofs work in intuitionistic but not minimal logic?

Intuitionistic logic contains the rule $\bot \rightarrow \phi$ for every $\phi$. In the formulations I have seen this is a separate axiom, and the logic without this axiom(?) is termed "minimal ...
1
vote
1answer
66 views

Help me go from English to Logic

The positive-definiteness axiom used for just about all the definitions of inner-product spaces that I've seen goes like this: $$\langle \mathbf{x},\mathbf{x}\rangle \ge 0 \text{ with equality only ...
2
votes
3answers
662 views

Apply Equivalence Rules To Convert To CNF

I am having trouble seeing how I could apply the equivalence rules mentioned here to the following formula in order to convert it into Conjunctive Normal Form: $$(p \wedge q) \vee (\neg p \wedge ...
1
vote
2answers
55 views

Boolean Algebra - Tautology for (D or Not D or (anything))

Ok so I am working on boolean algebra right now and I've stumbled upon my own lemma here, and want to verify that my thinking is correct. If you have something that end up being in the form: ...
4
votes
1answer
3k views

Translating sentences into propositional logic formulas.

I have some trouble with translating certain sentences into a statement of propositional logic. It is homework, so I will also be happy with some hints. Please keep in mind that I translated these ...
0
votes
2answers
39 views

Product of Sum canonical transformation

This question is related to Logic Gates calculation. Why is: G = ( A + B + C * C' ) = ( A + B + C )*( A + B + C') where + is OR, * is AND, ' is NOT.
3
votes
1answer
125 views

An exercise in stability theory

This is taken from Pillay's highly minimalistic book on stability theory. Let $T$ be stable, $\mathcal{M} \prec \mathcal{N}$ models, and $a$ a tuple in the big model such that its type over $N$ ...
1
vote
1answer
45 views

How to read structural rules

In the wikipedia page on structural rules, we have the following "weakening" rule. $$\frac{\Gamma \vdash \Sigma}{\Gamma \vdash A, \Sigma}$$ This makes no sense to me. It seems to be saying that, if, ...
-1
votes
1answer
60 views

An elementary substructure $(\mathbb{Z};+,0).$ [closed]

show that ($\mathbb{2Z};+,0)$ is not an elementary substructure of $(\mathbb{Z};+,0).$
1
vote
2answers
102 views

Propositional logic problem

Show that [ (p ∨ q) ∧ (p → r) ∧ (q → r) ] → r is a tautology (without a truth table). I am new to this, so I am not quite sure of how some rules can be used. Here is what I have so far: ...
-1
votes
1answer
75 views

Elementry question on elementarily equivalence

Source: SHAWN HEDMAN Definition:Let M and N be V-structures. If M and N models the same V-sentences, then M and N are said to be elementarily equivalent, denoted $M \equiv N.$ Example: the ...
0
votes
3answers
140 views

Is this statement true: 1 = 0.99 [duplicate]

Now this question might sound a bit weird to some people, but the situation is this: Say I have the number $0.999..$ where there is an infinite number of 9's (much like $0.3333..$ with ...