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

proof that p implies q entails not p or q [duplicate]

I could easily prove $\neg P \lor Q$ entails $P \rightarrow Q$. It is well known that $P \rightarrow Q$ entails $\neg P \lor Q$ but I couldn't find a way to prove it. Although there is the ...
2
votes
1answer
80 views

Kolmogoroff's Axioms of Probability and Completness

In Kolmogoroff Classic Foundations of the Theory of Probability, right at the beginning he gives the (now well-known axioms) Let $E$ be a collection of elements $\xi,\eta,\zeta,\ldots$ which we ...
0
votes
1answer
61 views

Modus ponens proof in system L(¬,→,∙)

I'm trying to prove $\neg\neg\bullet\varphi$ in system $L(\neg, \to, \bullet)$, where $\bullet$ is constant truth, i.e. $\bullet \varphi \approx (\varphi \to \varphi)$ Using modus ponens with ...
0
votes
1answer
48 views

Notation for rank of weakly ordered elements

I'm looking for a mathematical notation for the following algorithm where $D$ is a diagonal square matrix and $w$ a scalar value. Sort $D$ by the diagonal entries ascending for the first entry ...
11
votes
2answers
989 views

How to find the shortest proof of a provable theorem?

Roughly speaking, there are some fundamental theorems in mathematics which have several proofs (e.g. Fundamental Theorem of Algebra), some short and some long. It is always an interesting question ...
1
vote
1answer
41 views

How to prove that $\forall n\in \mathbb{N}$, $\sum ^{n}_{i=1}i^{3}=\frac {n^{2}(n+1)^{2}}{4}$? [duplicate]

Use mathematical induction to prove that $\forall n\in \mathbb{N}$, $$\sum ^{n}_{i=1}i^{3}=\dfrac {n^{2}(n+1)^{2}}{4}$$ $$\begin{align*} \sum_{k=1}^{n+1} k^3 &= \sum_{k=1}^{n} k^3 + (n+1)^2 ...
0
votes
1answer
53 views

Is there a logical error in the proof of $\sum \vdash \theta \equiv \sum \vdash \forall x\theta$?

Here in "Friendly Introduction to Mathematical Logic", this theorem is mentioned in page $72$: I wonder, Is this lemma true? I find some problems in the proof: First of all, The author used (QR) ...
7
votes
0answers
190 views

Fixed points in computability and logic

I asked this question on CS.SE, too: http://cstheory.stackexchange.com/questions/27322/fixed-points-in-computability-and-logic I would like to understand better the relation between fixed point ...
0
votes
2answers
82 views

Does the negation have to be true to disprove something?

I found a case that shows that the implication is not true, so I'm trying to disprove it. I always see it done by proving the negation of the implication. Does the negation have to be true to ...
4
votes
2answers
240 views

Is it possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem?

I want to ask if it is possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem. I am reading the following AMS-Notice article. The authors claim that: The ...
0
votes
2answers
53 views

English sentences to first order logic

I'm pretty new to first order logic and I'm attempting to translate some english sentences to first order logic. Am I doing these correctly and if not can someone show me a correct way to represent ...
1
vote
1answer
41 views

what is the difference between NOT(C IMPLIES (A AND B)) and (NOT C IMPLIES (A AND B))?

Like for the following example: $ (¬A ∧ (B ∨ C)) ↔ ¬(C → (A → B))$ Is this formula satisfiable? And how do I do it? Please explain as much as you can because I'm trying to understand this subject but ...
1
vote
1answer
29 views

Taking the inverse of a statement and then substituting

I'm taking a junior high/high school geometry course. We were talking about how a square is a rhombus and a rectangle, and therefore a parallelogram, but a parallelogram is not necessarily a rhombus ...
2
votes
1answer
53 views

Three atomic forms expression both in disjunctive and in conjunctive form?

we know that A v B is in both conjunctive and in disjunctive normal form. we also know that A ^ B is in both conjunctive and in disjunctive normal form. Does it follow from this, that A v B v C is ...
1
vote
1answer
73 views

Don't really understand the absorption law

I don't really get the absorption law, specifically in this case: $$ (\lnot p \lor q) \land (\lnot r \lor q) \equiv (\lnot p \land \lnot r) \lor (\lnot p \land q) \lor (q\land \lnot r) \lor (q \land ...
-2
votes
3answers
60 views

Operation with Cartensian product

I need to show the following using logical connectives: $A\times (B\setminus C) =(A\times B)\setminus(A \times C)$
0
votes
3answers
37 views

Logical Expression : Is it same or not?

I have $p\rightarrow \left ( q\wedge r \right )$, If i negate it: It will become like below: $\lnot \left ( p\rightarrow \left ( q\wedge r \right ) \right )$ $\lnot \left ( \lnot p\vee \left ( ...
16
votes
0answers
318 views

How much set theory does the category of sets remember?

Question. Let $M$ be a model of enough set theory. Then we can form a category $\mathbf{Set}_M$ whose objects are the elements of $M$ and whose morphisms are the functions in $M$. To what extent is ...
0
votes
2answers
141 views

How to express other logical operations via Pierce's arrow?

x↑y, x⇒y, and x⇔y. So I have really given my best, but all I could do is express the conjunction, disjunction, negation, and impilcation.
0
votes
1answer
53 views

Is this statement false? if so, how should I disprove it?

We define $\lfloor x\rfloor$ by $$\lfloor x\rfloor \in \mathbb{Z} \land \lfloor x\rfloor \leq x \land( \forall z \in \mathbb{Z}, z\leq x \Rightarrow z\leq\lfloor x\rfloor)$$ Prove or ...
6
votes
3answers
452 views

Good Sources for Lecture Movies in Set Theory, Logic and Philosophy of Maths

Of course as any other researcher I'm not able to attend any scientific event in my research area. But it is always interesting and useful to watch the lecture movies of these events. I will ...
1
vote
1answer
36 views

Formulate a condition that function f(x,y) must hold in order to be considered as “associative”.

Let $f(x,y)\colon\{0,1\}^2\to\{0,1\}$ be a Boolean function. Answer the following "warm-up" questions: Prove or dispute: The function $f$ can be one-to-one. Formulate a condition that function ...
0
votes
0answers
8 views

formulate a condition that function f(x,y) must hold in order to be considered as “associative” [duplicate]

Let f(x,y):{0,1}^2->{0,1} be a Boolean function. Answer the following "warm-up" questions: a. Prove or dispute: The function f can be one-to-one. b. Formulate a condition that function f(x,y) must ...
1
vote
2answers
43 views

How do I prove converse of these two claims?

Prove or disprove the claim, and prove or disprove the converse: Claim 1: ∀n ∈ ℕ, (Ǝk ∈ ℕ, n = 5k + 2) ⇒ (Ǝj ∈ ℕ, n^2 = 5j + 4) Claim 2: ∀m,n ∈ ℕ, (Ǝk ∈ ℕ, m = 7k + 3) ∧ (Ǝj ∈ ℕ, n = 7j + 4) ⇒ ...
1
vote
1answer
54 views

What is the conjunctive normal form of the boolean constant TRUE?

I have the following problem: Is TRUE (or 1) a logically equivalent formel in conjuctive normal form to a tautology? How can I build the conjunctive normal form ...
1
vote
3answers
112 views

Robinson arithmetic and its incompleteness

Wikipedia in Italian has a sketch-of-proof that Robinson arithmetic is not complete, since commutativity of addition is undecidable. The sketch of proof creates a model that adds two elements, $a$ and ...
1
vote
0answers
82 views

Is “to be married” a transitive relation?

If you define a relation on the set of people, given by $R=\{x,y : x\text{ is married with } y\}$. Is this relation transitive? I would say it depends: In the western culture: If $x$ is married with ...
3
votes
1answer
75 views

How to prove that a set of connectives is adequate

I have this Table: $$\begin{array} {|c|} \hline A & B & A*B\\ \hline 1 & 1 & 0\\ \hline 1 & 0 & 1\\ \hline 0 & 1 & 1\\ \hline 0 & 0 & 0\\ \hline \end{array}$$ ...
5
votes
0answers
51 views

Type-definable Forcing or forcing in a non-first order setting

Roughly speaking, in set forcing the forcing notion is a set from ground model's perspective and in class forcing its a definable subset of the ground model given by solutions of some formula with ...
1
vote
0answers
41 views

Is it true that each large cardinal which is not first order expressible has no extender characterization?

It is well-known that Reinhardt cardinal (i.e. The critical point of a non-trivial self-elementary embedding of the universe in $ZF$) is not first order expressible. Does this imply that Reinhardt ...
4
votes
2answers
244 views

Is there any category theoretic proof for independence of Continuum Hypothesis?

Both of set theory and category theory could be a foundation for mathematics. Many set theoretic arguments could be translated to a category theoretic argument and vice versa. Question: Is there ...
2
votes
1answer
115 views

How can universal quantifier manipulation rules be made redundant by the generalization rule (metatheorem)?

On the Wikipedia page for Hilbert style axioms, in the "Logical axioms" section, it gives the axioms to manipulate universal quantifiers : $Q5. \forall x(\phi)\rightarrow \phi[x:=t] $ $Q6. ...
2
votes
1answer
39 views

using the elimination rule in natural deduction

Prove that $$(A ∧ B) \to C ⊢ A \to (B \to C)$$ Am I using the conjuction elimination rule correctly? Or am I assuming too much? $(A ∧ B) \to C$ (Given) $A \to C , B -> C$ (∧E 1) $A ...
2
votes
4answers
63 views

Prove $Q \rightarrow \neg(Q \rightarrow \neg P)$

I have an exercise about proving statements: Suppose that P is true. Prove that Q → ¬(Q → ¬P ) is true Givens: $P$ $Q \rightarrow \neg P$ Goal: $\neg Q$ which I simply prove ...
2
votes
3answers
60 views

If true for the general element, then true for all. What's this?

In mathematics often (always) one proves that a property is true for the general element of a set. From that, one can say that that property is true for all the elements of that set. Is that a ...
1
vote
1answer
112 views

Reference request basic logic/model theory

I'm taking a knowledge representation class and need more perspective on basic model theory. We're currently using Levesque and Brachman. Specifically, a question on the midterm was something like, ...
4
votes
1answer
39 views

Show functionally completeness property for propositional logic

Let $n>0, n\in \mathbb{Z}$ and let t,f denote true and false. For every function $$g:\{t,f \}^n \to \{t,f\} $$ There is a propositional forumala $B$, using only the connectives ...
1
vote
3answers
129 views

Proof of the Principle of mathematical Induction [duplicate]

We always use the Principe of Mathematical induction and we have two versions of it. I myself have been using it for many years. But it just came to my mind that I have never seen a proof of the ...
3
votes
3answers
86 views

How to show that something is not logically entailed?

I was just thinking about entailment and would like to know if you can show that something is NOT entailed by the premises. I know that to show $A, A → B \vdash B$, I could just provide a proof ...
1
vote
3answers
82 views

Where to put the “such that”, given multiple quantifier

Personally, I would put the "such that" (i.e. the symbol $:$ or $|$) behind any quantification. That is given an assertion $A(x,y)$, I'd write $$ \forall x\in X\exists y\in Y:A(x,y)\\ \exists x\in ...
4
votes
5answers
101 views

semantics(truth) vs formal system?

my first question is can we just define semantics in logic and not define a formal system ? why do we need a formal system to prove a proposition when for example we know the proposition is true ? ...
2
votes
3answers
60 views

What does 'any' mean in predicate calculus

I need to translate an English sentence into a well-formed predicate calculus formula. The sentence starts off as: Any tiger who chases every creature also chases itself. Does 'any' translate ...
2
votes
2answers
69 views

The existence of conjunctive/disjunctive normal forms?

I am studying propositional logic/calculus and I am currently learning about normal forms. The algorithm to construct a conjunctive/disjunctive normal form from any given formula is straightforward. I ...
2
votes
2answers
58 views

Syntax of an epsilon delta proof/why is this version incorrect [duplicate]

So we have the regular $\delta$-$\epsilon$ definition of continuity as: (1) For all $\epsilon>0$, there exists a $\delta>0$ such that, if $|x-a|<\delta$, then $|f(x)-f(a)|<\epsilon$. My ...
1
vote
1answer
31 views

proof checking - power set and family set

Decide if it is true that $P(A) \subseteq P(B) \implies \bigcup A \subseteq \bigcup B $ where $P(A), P(B)$ are power set and $A,B$ are family of sets My proof: Let $x \in P(A)$ then we have ...
1
vote
1answer
34 views

Generic in Boolean-Valued-Models

Let $M$ be a transitive $\in$-interpretation of a extension $T$ of $ZF$ in $ZF$,and let $B$ such that $$T\vdash B\in M\wedge B\text{ is a complete Boolean algebra}$$ Then, using the fact that any set ...
3
votes
1answer
74 views

Bases of complex vector spaces and the axiom of choice

In Zermelo-Fraenkel set theory $ZF$ consider the following statement defined for every field $K$: $B_K$ : Every vector space over $K$ has a basis. It is well-known that $AC \Rightarrow \forall K ...
0
votes
3answers
67 views

Recommendation on Quine's text

I'm planning to study logic seriously and I think Quine's style is fine to me so i'm going to read his book. There are two famous books by him. Namely, "Methods of logic" and "Mathematical logic". I ...
0
votes
1answer
69 views

Problem in solving a logical Equivalence

Prove or disprove the following equivalence: $$ ∀x Px \wedge ∀x Qx \Leftrightarrow ∀x ∃y ( Px \vee Qy ) $$ I've tried it, but I do not know how to solve logical equivalences involving quantifiers.
4
votes
1answer
161 views

Propositions logic and problem solving

How can a question of this nature be approached: Two avid game players Alice and Bob play three different games. They are very competitive and so would do anything within the rules of the game to ...