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)

2
votes
1answer
110 views

Might proof by contradiction be needed for this mundane problem?

This present question is inspired by this earlier question. Consider the problem of proving that if $f\ge 0$ on an interval $I\subseteq\mathbb R$ and $\int_I f=0$, then $f$ is $0$ (almost) everywhere ...
2
votes
3answers
142 views

prove: $\dfrac{2^{n+1}+(-1)^n}{3}$

I am asked to prove this notation with induction for $n\in \mathbb{N}$: real problem is to fill the area with tilings. and for $n\in \mathbb{N}$ there are exactly so many chances to fill the area as ...
2
votes
1answer
133 views

impossible to prove something

(Edited by comments) Let sentence P and Q are under this situation: , in logic of ZFC theory Pvbl( P(X) ) → { if Pvbl(Q) then X(X) } Q≡ ¬pvlb( P(P) ) using fixed point theorem, let's ...
2
votes
2answers
128 views

How to prove that $(A \lor B) \land (\lnot A \lor B) = B$

I know this is fairly basic, and I understand that it becomes $$ \begin{align} (A \land \lnot A) \lor B \\ F \lor B \\ B \end{align} $$ However, I can't work out how to prove that it becomes that ...
2
votes
1answer
1k views

Any functionally complete sets with XOR?

According to wikipedia, the set {^, ¬} is functionally complete. But is there any 2-set functionally complete set with XOR (e.g. (¬A) ⊕ A is always true). I'm looking for a 2-set functionally ...
2
votes
2answers
473 views

What does $\forall x \exists y(x + y = 0)$ mean?

What does $\forall x \exists y(x + y = 0)$ mean? Does it mean "For all x there exists a y for which x + y equals zero"? Thanks.
2
votes
1answer
3k views

Boolean Algebra - Product of Sums

I converted from a truth table to sum of products and simplified that easily. What I am having problems with is simplifying the product of sums for that same truth table. I have: NOTE: $A' = ...
2
votes
4answers
515 views

Proving that for any sets $A,B,C$, and $D$, if $(A\times B)\cap (C\times D)=\emptyset $, then $A \cap C = \emptyset $ or $B \cap D = \emptyset $

I'm trying to prove that for any sets $A$, $B$, $C$, and $D$, if the Cartesian product of $A$ and $B$ is disjoint with the Cartesian product of $C$ and $D$, then either $A$ and $C$ are disjoint or $B$ ...
2
votes
2answers
129 views

How to show the statement is false?

How to do you show the statement is false and prove its negation is true? $$\forall n \in\mathbb Z^+ \exists a \in\mathbb Z^+ \text{ such that } a|n\text{ and }\frac na\text{ is odd}$$
2
votes
1answer
104 views

Models of infinite cardinal and compactness

I'm stuck with this problem: $L$ is first-order language with identity and $L_q$ a language obtained by adding to $L$ the quantifier $Q$. If $P$ is a formula and $x$ a variable, $QxP$ is a formula ...
2
votes
3answers
275 views

Writing Propositions With Propositional Variables

The puzzle I am working on is: "Let $p$, $q$, and $r$ be the propositions $p$: Grizzly bears have been seen in the area. $q$: Hiking is safe on the trail. $r$: Berries are ripe along the trail. ...
2
votes
3answers
136 views

Are these two statement equivalent?

$\forall x \exists y P(x,y)$ $\exists x \forall y P(x,y)$ where P(x,y) means x is smaller than y. I believe that they mean the same thing.
2
votes
1answer
2k views

How to prove the distributive property without using truth tables?

I did it with using truth tables but I am inquisitive about how to proof the distributive property without using truth tables (i.e using the other rules of replacement or inference). $$ (P \land (Q ...
2
votes
2answers
281 views

Why there's difference between $\forall x \in T\ \exists y \in S\ F(x,y)$ and $\exists y \in S\ \forall x \in T\ F(x,y)$

I don't understand why there's difference between $\forall x \in T\ \exists y \in S\ F(x,y)$ and $\exists y \in S\ \forall x \in T\ F(x,y)$. It sems that it's exactly same thing just order is changed ...
2
votes
1answer
224 views

Independence results in first-order PA and second-order PA

There are statements $\varphi$ that are independent of first-order Peano Axioms. Are these statements also independent of second-order Peano Axioms? I'm reading Wikipedia articles around ...
2
votes
4answers
147 views

All naturals are T-finite, all finite sets are T-finite

In Jech's Set Theory, there is defined T-finite, where a set $S$ is T-finite if every non-empty $X\subseteq\mathcal{P}(S)$ has $\subseteq$-maximal element. [ie. there is $u\in X$ s.t. there is no ...
2
votes
1answer
117 views

Induction (over 2 variables)

Suppose, in a group $G$ with $a$ in $G$, that $a^n$ is defined to be the $n$-fold product $a\ast a\dots\ast a$, where $\ast$ is the binary operation on $G$. Suppose that we want to prove $a^{(m+n)} = ...
2
votes
1answer
100 views

Defining Category of Problems

Let $\left\{\Pi_i\right\}_{i \in I}$ be a family of problems. Let problem $\Pi_i$ have solution $u_i$ lying in some solution space $X_i$. I am interested in making this set into a category. Is it ...
2
votes
3answers
6k views

Determining the truth value of a statement

I am stuck with the following question, Determine the truth value of each of the following statments(a statement is a sentence that evaluates to either true or false but you can not be ...
2
votes
1answer
356 views

Formalising real numbers in set theory

If I understand correctly, the real numbers can be formalised in a first-order, like in ZF. However, such a formalisation is not strong enough to ensure that all models of the reals are isomorphic. ...
2
votes
1answer
240 views

How can i prove that the theory of random graph has a vaughtian pair?

I'm searching for theories that have a vaughtian pair. I've been given a hint, that $T_{RG}$ has at least one. I have also found many theorems stating in which cases a theory has no vaughtian pair, ...
2
votes
1answer
359 views

Translation of a mathematical statement formulated in words to one formulated in predicate logic

I want to express the fact that for all $x \in A$ that have the property that for all $y\in x$ $T(x,y)$ is true and there exists an $u \in B$ such that $P(y,u)$ is true AND for all $v\in C$, $Q(y,v)$ ...
2
votes
1answer
248 views

Question about maximally consistent sets in logic

Problem: Σ is "proofwise stronger" than a set Γ if {$\alpha$: Σ ⊢ $\alpha$} $\supseteq$ {$\alpha$ : Γ ⊢ $\alpha$ }. Show that for every maximally consistent set of propositions Σ, for every set Γ, ...
2
votes
1answer
105 views

Language over a finite alphabet is “stable” with resprect to primitive recursiveness ( & etc.) under different enumerations

I'm trying to prove the following proposition: The fact that a language $L$ over a finite alphabet $A$ is primitive recursive, recursive or recursively enumerable does not depend upon the enumeration ...
2
votes
1answer
454 views

Proof by induction that $\Sigma$-formulas are uniquely readable

My question is how to prove that $\Sigma$-formulas are uniquely readable (in our course this was wasn't really proved - in the proof it said just "proof by induction", but I'm confused what was meant ...
2
votes
1answer
179 views

Construction of a sequence of theorems with increasing and unbounded “difficulty”?

Let's define the "difficulty" of a theorem as the logarithm of the size of its shortest proof divided by the logarithm of the size of the theorem itself. For example, if a theorem has difficulty less ...
2
votes
1answer
275 views

How can ZF prove relative consistency for itself?

This is related to my first question. In order to get what I don't get, I ll go with something much more specific here. It is well known that $ZF \vdash Con(ZF) \longrightarrow Con(ZF + AF)$. The way ...
2
votes
1answer
116 views

quantifier translation

how can i translate this sentence to a quantifier formula, when the universe - { o|o is a set } Any master has as elements all and only sets which are not elements of themselves. i know it starts ...
2
votes
1answer
359 views

Unique normal form of formulae of predicate calculus?

Is there a unique normal form for each formula of predicate calculus? I am aware of prenex normal forms of predicate calculus and of disjunctive and conjunctive normal forms of propositional ...
1
vote
1answer
43 views

Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
1
vote
3answers
90 views

Can a statement in FOL be equivalent to two separate independent statements?

This may seem like a dumb question, and it certainly seems dumb to me asking it, but I'm running into a contradiction. I'm looking at the problem of finding a statement $\phi$ such that $\psi$ and ...
1
vote
1answer
48 views

Model-theory : questions regarding partial isomorphism

I'm having problems with the first pages of Bruno Poizat, A Course in Model: Theory An Introduction to Contemporary Mathematical Logic (ed or 1985), specifically with local isomorphism and back- and ...
1
vote
1answer
74 views

How to define multiplication in addition terms in monadic second order logic?

How to define multiplication in addition terms in monadic second order logic? meaning, having natural numbers variables, N sub-groups variables, successor function, negations, "for every", "there ...
1
vote
2answers
96 views

Abstract Objects in Logic

I am confused on the concept of extensionality versus intensionality. When we say 2<3 is True, we say that 2<3 can be demonstrated by a mathematical proof. So, according to mathematical logic, ...
1
vote
3answers
130 views

Invalid Argument vs. Contradiction?

I'm confused about the differences between valid/invalid arguments and contradictions/tautologies. An argument is valid when the statement "all of it's hypothesis are true implies the conclusion" is ...
1
vote
1answer
35 views

Partial order version of elementary equivalence

Elementary equivalence is an important concept in mathematical logic. Two models $\mathfrak{M}$ and $\mathfrak{N}$ of the same signature are elementarily equivalent, written $\mathfrak{M} \equiv ...
1
vote
0answers
93 views

Range/Image of a Non-Decreasing Total Recursive Function is Recursive

How do I show that the range of a non-decreasing, total-recursive function is recursive? I've made reference to this question, but the method used there is not clear to me. My attempt: Let $f$ be ...
1
vote
2answers
75 views

Show that $((\phi → \psi)→((\psi→\chi)→(\phi→\chi)))$ is a Theorem of L.

Show that $((\phi → \psi)→((\psi→\chi)→(\phi→\chi)))$ is a Theorem of L. I a previous part of the Q i am asked to state the deduction theorem so I assume i have to use this and the axioms A1, A2, A3, ...
1
vote
2answers
40 views

Resolving a contradiction in the proof of expected value of Binomial distribution

I've seen this proof in a text. I have an issue with it and wanted to check its validity. Let $X\sim B(n,p)$, we seek the expectation. We let $q=1-p$ \begin{equation} E(X)=\sum_{j=0}^{n} j {n\choose ...
1
vote
1answer
68 views

$(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

Show that $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$ is a tautology. I have the truth tables but cannot algebraically manipulate the language itself to prove it. What I ...
1
vote
1answer
66 views

First order logic tableaux with multiple quantifiers

I find very confusing to understand how combined qualifiers might expand on a tableaux. While for $\exists x\ p(x)$, I would just create a new term, a, and for $\forall x\ p(x)$ I would use an ...
1
vote
1answer
78 views

Sound and Complete

So I am in a introductory formal logic class, and my professor has asked us questions on our homework about "Sound and Complete rules of inference". Unfortunately, I am having a hard time finding out ...
1
vote
1answer
49 views

formal proof - logic

I am trying to prove the following, using natural deduction: $$p\wedge q\Leftrightarrow p \vdash p \Rightarrow q$$ with the following but i seem to get stuck. I know i have to prove $q$, but am not ...
1
vote
2answers
69 views

Meaning of variables and applications in lambda calculus

The wikipedia definition of lambda terms is: The following three rules give an inductive definition that can be applied to build all syntactically valid lambda terms: a variable, $x$, is ...
1
vote
3answers
71 views

Using quantifiers to express this sentence.

These are from a study guide, just checking my work. Let $F(x,y)$ be the statement "$x$ and $y$ are friends." where the domains consists of all people in the class. Use quantifiers to express the ...
1
vote
1answer
37 views

Other than $\models$, is there standardized notation for semantic consequence?

It is common practice to use $\models$ both for the satisfaction relation between models and sentences, and for the corresponding semantic consequence relation. Question. Suppose I don't want to use ...
1
vote
3answers
139 views

What does $\rightarrow$ mean in $p \rightarrow q$

I was looking at an exercise where it asked the following: $$\begin{array}{ccc} p&q&p\rightarrow q \\ T&T&T \\ &\ldots \end{array}$$ So, for the third column, I just put $T$ ...
1
vote
4answers
106 views

Free variables in definitions

Consider the epsilon delta definition of the limit below, as it is usually stated: the limit of f as f approaches a is L if and only if, for all ε > 0, there is a δ > 0 such that for all x, 0 ...
1
vote
2answers
139 views

Model Theory problem

Good afternoon. I need some help with this little problem. I hope somebody could help me. Thanks a lot Assume that $A\equiv B$. Then there exists a $C$ such that $A\prec C$ and $B\prec C$.
1
vote
4answers
102 views

Boolean Algebra simplify minterms

I have this equation $$\bar{A}\cdot\bar{B}\cdot\bar{C} + A\cdot\bar{B}\cdot C + A\cdot B\cdot \bar{C} + A \cdot B\cdot C$$ and need to simplify it. I have got as far as I can and spent a good 2 ...