Questions about logic and 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
23 views

For every pair of the following formulas, decide whether one follows from the other, or the other way round.

Could someone please please explain this to me? I have the following formulas: (A ∧ B) → C (A → C) ∧ (B → C) (A → C) ∨ (B → C) for the second one, I got (NOT A AND NOT B) OR C) I don't know if ...
0
votes
0answers
21 views

Independent equations and mutually independent events

Given $n$ experiment, that is $n$ decompositions $$ \Omega = A_1^{(i)} \cup A_2^{(i)} \cup \ldots \cup A_{r_i}^{(i)}, \quad i = 1,2,3,\ldots,n $$ of the basic set $\Omega$. It is then possible ...
1
vote
1answer
50 views

Which quantifiers get negated in negation?

So lets say I have an implication that I have a counter example for, so I'm going to negate it and prove that. There are a number of quantifiers. Some universal and some existential. My question is, ...
4
votes
1answer
90 views

What goes wrong when you try to reflect infinitely many formulas?

The reflection principle in ZFC shows that you can construct a set that reflects finitely many formulas. Suppose we wanted to reflect {$\phi_n$} and we construct a set $M_n$ to reflect $\phi_1, ... , ...
0
votes
1answer
59 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
48 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
47 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
36 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 ...
10
votes
2answers
900 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
40 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
39 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
101 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
47 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
122 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
39 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. Are my doing these correctly and if not can someone show me a correct way to represent ...
1
vote
1answer
38 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
21 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
20 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
41 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
52 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
33 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 ( ...
11
votes
0answers
152 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 ...
-1
votes
2answers
59 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
46 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 ...
5
votes
3answers
348 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
29 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
7 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
22 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
29 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
68 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 ...
0
votes
0answers
67 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
30 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
46 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 ...
2
votes
0answers
34 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
219 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
55 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. ...
1
vote
1answer
29 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
59 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 ...
1
vote
3answers
51 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
60 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, ...
3
votes
1answer
25 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
99 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 ...
2
votes
3answers
69 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
50 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
4answers
65 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
55 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
36 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
46 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
22 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
28 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 ...