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 ...

learn more… | top users | synonyms (1)

1
vote
1answer
453 views

Finding the atoms and elements of a Lindenbaum–Tarski algebra

Let B be the Lindenbaum–Tarski algebra with three variables $p,q,r$ (1) Find all the atoms of $B$. (2) How many elements of does $B$ have? So I think I know what an atom is, but I'm still not sure ...
1
vote
1answer
79 views

Double check my quantifier logic? $(\exists x~:~P(x) \rightarrow \exists y~:~Q(y)) \equiv (\exists z~:~P(z) \rightarrow Q(z))$

I was looking at some random math problem and needed to resolve $$\bigg( \exists x ~:~ P(x) \bigg) \rightarrow \bigg(\exists y ~:~ Q(y) \bigg) \tag 1$$ by rewriting as an equivalent statement. I ...
2
votes
1answer
90 views

Calculate percentage between two sensorvalues

I've got two distance sensors on the sides of a car, and I'm trying to come up with a formula that will attempt to put the car so that it has an equal distance on both sides. There is an IR sensor on ...
2
votes
2answers
61 views

$a>0$ and $a\geq 0$ - is this a contradiction?

I have a very, very elementar question. If the assumption is that $a>0$ and then in a proof it is shown that $a\geq 0$, is that a contradiction?
1
vote
0answers
19 views

Expressing an equal sized partition in second order logic

I would like to characterize the class of (finite) structures that can be partitioned into two disjoint sets $X,Y$ having the same cardinality, using second order logic (with usual logical connectives ...
3
votes
0answers
84 views

Why is it not possible to combine set theory and category theory?

I know that there are attempts to do category theory in the framework of set theory, but I'm not asking that. I'm asking about the converse. I will explain my thought below. I think my thought makes ...
3
votes
1answer
73 views

Natural Algebraic Structures on the Set of Automorphisms of a Structure

If $M$ is a first order structure (e.g. some algebraic structure) we usually refer to its set of automorphisms, $Aut(M)$, as a group with its natural "function combination" operator.i.e. $\langle ...
1
vote
1answer
87 views

Algorithm to force decidability of statements using an intuitionistic series of new axioms

Say that a set $\Phi$ is a finite set of statements in Peano arithmetic is meekly consistent if it contains no "inner,immediate" contradiction, i.e. for any statements $\alpha,\beta$, it does not ...
1
vote
1answer
63 views

is $P(x) \to \forall x P(x)$ satisfiable

I need to prove that this formula $P(x) \to \forall x P(x)$ is satisfiable. Can I say for example that x is even number ?
-2
votes
2answers
111 views

What is the negation of the statement $f=0$ almost everywhere?

Today in class, we were proving a theorem that relied on negating the statement $f=0$ almost everywhere, for $f$ a function. However, I am not convinced of the right negation. What is it?
12
votes
2answers
1k views

What's an example of a theory that's consistent yet has no model?

By the completeness theorem for first order logic, if a theory is consistent then it has a model. But what's a counterexample to this : what's an example of a logic where some theory is consistent ...
3
votes
2answers
148 views

Is the first-order incompleteness of a theory (like arithmetics, set theory or logic itself) avoidable in a second or higher-order axiomatizations?

Can we avoid the first-order incompleteness of a theory (like arithmetics or set theory) in a second-order theory which contains the previous? How does it depend on the chosen semantics or models? If ...
0
votes
1answer
53 views

Modus ponens proof

I'm trying to prove that $\neg\bullet\varphi$ in system $L(\neg, \to, \bullet)$, $\bullet \varphi \approx (\varphi \to \varphi)$ Axiomas are the followind: A1) $\neg\neg\bullet\bullet\varphi$ A2) ...
0
votes
1answer
92 views

How to decide if propositional function is complete

I have two 3-ary propositional functions given by the table $$ \begin{array}{|c|c|c|c|c|} v(a) & v(b) & v(c) & v(f(a, b, c)) & v(g(a, b, c)) \\ \hline 0 & 0 & 0 & 1 & ...
0
votes
1answer
40 views

Is this quantifier negation correct?

I would like to know, if this negation is correct, and if not, an explanation on what is wrong. Any help would be appreciated :) Original: $$ \forall \epsilon > 0 \exists \delta > 0 \forall ...
1
vote
1answer
279 views

Prove equivalence in predicate logic

I have to prove that these formulas are equivalent: $$\begin{align} \exists x \forall y P(x,y) \equiv \forall y \exists x P(x,y) \\ \end{align}$$ Can I say that $$\begin{align} \forall y \exists x ...
1
vote
0answers
98 views

question in math logic: find the d.n.f. and c.n.f.

The question is as follows: Find the disjunctive and conjunctive normal forms of the following: $$ (A \to (B \to C)) \to ((A \to \neg C) \to (A \to \neg B)) $$ My solution is as follows, but I ...
-1
votes
1answer
57 views

Is $\exists x \forall y \exists z P(x,y,z)$ satisfiable? [closed]

I have this formula: $$\begin{align} \exists x \forall y \exists z P(x,y,z) \\ \end{align}$$ How to check whether it is satisfiable? I know that I have to find a structure in which it is true.
0
votes
1answer
21 views

Predicate formula to propositional formula

I have: $$\begin{align} \exists x \forall y P(x,y) \\ \end{align}$$ where $$\begin{align} M=\{a,b\} \\ \end{align}$$ I need to convert this formula to propositional logic. I know that if ...
2
votes
3answers
625 views

How can this English sentence be translated into a logical expression?

You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old. Let: $P$ stands for "you can ride the roller coaster" $Q$ stands for "you are under 4 ...
1
vote
3answers
79 views

Contrapositive of a Definition

I have a problem (in real analysis class) that states "What is the contrapositive of the definition of "closed"?" The definition in our class of closed is: "a set E is closed iff the set contains all ...
1
vote
0answers
43 views

Undecidebility in Number Theory [duplicate]

Recently one of my teachers says that it is not impossible that we find a problem in number theory that is undecidable in usual system of set theory. This was so wonderful for me. When I say this ...
1
vote
0answers
41 views

Relations between equations in a theory, and the number of independent equations

I have a question on equational reasoning in theories, which is made quite often in mathmeatics, and I am trying to make this more formal. So for my attempt to make this more rigouros, I choosed ...
6
votes
1answer
131 views

Does iterating the consistency of ZFC answer any natural questions?

The following is a natural question that occurred to me, but I'm not sure if it's even well-defined since I haven't read the literature on iterating consistency statements. Let $Con_0(ZFC)=Con(ZFC)$ ...
0
votes
1answer
49 views

Need alternative proof to $ \exists x (k(x) \rightarrow t)$ entails $\forall x (k(x)) \rightarrow t $

I tried to prove $ \exists x (k(x) \rightarrow t)$ entails $\forall x (k(x)) \rightarrow t $ as; $ \exists x (k(x) \rightarrow t)$ $ \exists x (\neg k(x) \lor t)$ $ \exists x (\neg k(x)) \lor ...
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 ...
4
votes
1answer
116 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
3k 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
106 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
103 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
98 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 ...
13
votes
2answers
1k 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
47 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
61 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
234 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
206 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
361 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
76 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
49 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
30 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
94 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
112 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
62 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
47 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 ( ...
22
votes
0answers
478 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
303 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
55 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
570 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
43 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 ...
2
votes
2answers
68 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) ⇒ ...