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)

1
vote
1answer
35 views

How do logicians notate a proposition that posits the instantiation of a property?

In The Oxford Companion to Philosophy, the entry on existence includes this paragraph. It is often held that ‘exist’ is not a firstlevel predicate. What this means is that ‘exist’ does not ...
0
votes
0answers
33 views

How many boolean formulas are there over n variables?

Suppose our alphabet is $x_1, \ldots, x_n$, $\wedge, \vee$. How many legal boolean formulas can we have? I know it's more than $2^n$ since $$(x_1 \vee x_2) \wedge x_3 \ne x_1 \vee (x_2 \wedge x_3),$$ ...
1
vote
1answer
26 views

Prove if $x$ is greatest lower bound of $U$ then $x$ is the least upper bound of $B$

This is one of the problem I have been solving from Velleman's How to prove book; Suppose $R$ is a partial order on $A$ and $B \subseteq A$. Let $U$ be the ...
1
vote
1answer
57 views

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable.

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable. Okay can prove this by contradiction. So we say that a tableau $\tau$ is $\textit{satisfiable}$ iff there exists an ...
0
votes
0answers
27 views

Let $\Phi = \{Rwt, Rzt, Rwt \wedge Rzt \rightarrow Rxt, y\equiv t\}$. Does $\mathcal{J}^{\Phi} \models Rxy$ hold?

Im working on a mathematical logic question but i'm a little stuck here. The question is the fallowing: Let $\Phi = \{Rwt, Rzt, Rwt \wedge Rzt \rightarrow Rxt, y\equiv t\}$. Does $\mathcal{J}^{\Phi} ...
2
votes
1answer
48 views

How to define “is a structure” by a first-order formula of ZFC

So, I've been trying to define a series of notions by first-order formulas in ZFC, and I'd like to know if I'm getting this right. In particular, I'd like to know if my formula for defining a ...
2
votes
1answer
36 views

Why do we tell functions from relations in structures?

A relation is a set of ordered pairs (a,b) A function is a relation (a,b) which satisfies the following conditions: For all a, there is one and only one b Therefore, all functions are relations. ...
0
votes
1answer
291 views

Show that $S=\{\wedge, \Leftrightarrow\}$ are not an adequate set of connectives

How do I show that $\{\wedge, \Leftrightarrow\}$ (i.e. conjunction and biconditional) are not an adequate set of connectives?
0
votes
0answers
16 views

Are there Karnaugh maps over other algebras?

Karnaugh maps are a useful way to minimize or factorize polynomial expressions in Boolean algebra by considering the smallest combinations of logical "subcomponents" of an expression, whose sum is ...
3
votes
2answers
47 views

Particular case of an Implication

Let's take the following propositions : 1 - "If Bill Gates is poor then Bill Gates is rich". 2 - "If Bill Gates is poor then the moon is made of cheese". Both propositions are inevitably true ...
0
votes
3answers
3k views

Prove « If P(A) is a subset of P(B) => A is a subset of B » [duplicate]

I need to prove «If P(A) is a subset of P(B) => A is a subset of B», generally, I understand the main way I should prove it, but the problem is in the formal, pedantic language I have to use to ...
0
votes
2answers
140 views

Compactness Theorem explanation

Compactness Theorem definition: If $T$ is a theory in a first-order language $L$, then $T$ has a model iff every finite subset $S$ of $T$ has a model. A number of questions regarding this ...
2
votes
1answer
35 views

If for every k the interval $[a,ak]$ contains $n$ specials numbers how many special numbers $[az,akz]$ must contain?

The purpose of my question is to determine if a specific kind of reasoning is true or false. Let's say that for every positive natural number $a$, there is a at least $n$ "special numbers" in the ...
2
votes
0answers
27 views

Proving some property of a set of logical expressions that satisfies some properties

I am stuck at this problem. Let $\Sigma$ be a (finite/ infinite) set of logical expression (I.e. strings of the form $(P\land Q)$ or $\lnot(P\lor \lnot (Q\land R))$ etc.). That satisfies the ...
2
votes
0answers
46 views

How does Godel Escher Bach support Artificial Intelligence? [closed]

Typically, Godel's Incompleteness theorems have been used to argue against the possibility that the human mind is essentially equivalent to a formal system. However, in Daniel Dennett's book "Darwin's ...
2
votes
1answer
74 views

What is the _simplest_ way to solve problems of this kind?

Two doors with talking doorknockers - one always tells the truth and one always lies. One door leads to death other to escape. Only one question may be asked to either of the door knockers. What would ...
0
votes
1answer
23 views

Logical Equivalence of Wffs in Sentence, Predicate Logic using Tables, Interpretations Resp.

just curious if there is a formal name for the results that: a) Two wffs in Sentence Logic are equivalent iff their truth tables are equal , as binary functions of {T,F} b) Two wffs A,B in ...
0
votes
1answer
33 views

Build an infinite set of logical expressions that satisfies certain properties

I am stuck at this problem. Build an infinite set $\Sigma$ of logical expression (I.e. strings of the form $(P\land Q)$ or $\lnot(P\lor \lnot (Q\land R))$ etc.). That satisfies the following two ...
4
votes
9answers
200 views

Why is the negation of $A \Rightarrow B$ not $A \Rightarrow \lnot B$?

The book I am reading says that the negation of "$A$ implies $B$" is "$A$ does not necessarily imply $B$" and not "$A$ implies not $B$". I understand the distinction between the two cases but why is ...
2
votes
0answers
47 views

Are Euclid's Axioms Non-Logical or Logical

This question may seem trivial, but I recently became aware of the distinction between the two types of axioms: Logical and non-logical. What category does Euclid's fall under? I would assume they ...
2
votes
3answers
71 views

What is the negation of the statement “Every odd nmber is divisible by 2”.

Intuitively,I think it is "no odd number is divisible by 2" or it could be "every odd number is not divisible by 2". Is this a trivial question or is there more to it? What is the correct answer? BTW ...
0
votes
0answers
28 views

Is every natural recursive relation necessarily holomorphic?

Define the set of algebraic primitive recursive relations as the set of functions defined by: $$ F(n,a,k) = F(n-1,F(n-1,F(n-1,a,a),a)...,a)_{\text{nested to depth k}}$$ $$ F(0,a,k) = a + k $$ Along ...
4
votes
3answers
746 views

Classifying Types of Paradoxes: Liar's Paradox, Et Alia

The well-known Liar's Paradox "This statement is false" leads to a recursive contradiction: If the statement is interpreted to be true then it is actually false, and if it is interpreted to be false ...
0
votes
1answer
75 views

is differ between distributive lattice vs semi-lattice on Turing Degrees

We know a Posed Closed under suprema but not necessarily under infima is an upper semi-lattice. We now r.e set forms a distributive lattice. But my question is why following statement is hold? I ...
0
votes
0answers
36 views

Is this set of numbers correct?

We have $A = \{n \in \mathbb{Z}\mid 2 \leq n \leq 10\}$. For any positive integer $m$ we define the set $A_m$ by $A_m = \{n \in A\mid n \text{ is divisible by }m\}$ If I need the sets ...
1
vote
2answers
52 views

for some or for all

The following text is from Velleman's How to Prove book from the reflexive closure section: According to the definition we gave in the last section, the ...
3
votes
1answer
102 views

What is an example of a proof that explicitly relies on the law of excluded middle?

I was talking with a friend about logic and I realized she might be an intuitionist. I was looking online for a proof that explicitly uses the law of excluded middle to see if she would have an issue ...
1
vote
2answers
49 views

prove P ∧ Q → P ⇔ R ∨ ¬R in natural deduction

I am a beginner in Natural Deduction currently reading the book "Logic in Computer Science" and got stuck at proving: $$ P\land Q\to P\Leftrightarrow R\lor\lnot R$$ The latter formula is clearly a ...
-4
votes
1answer
70 views

9 hens lay 9 eggs in 9 days… [closed]

9 hens lay 9 eggs in 9 days. How many eggs will 3 hens lay in 3 days??? it's a tricky question asked by a friend and can you solve it and explain your answer.
1
vote
2answers
61 views

Set of axioms for finite subset of Natural Numbers

I would like to get a set of Peano like first-order axioms for a finite subset of natural numbers $N'$ such that $0 \leq N' \leq Max$, with $Max$ denoting the upper-bound. (So my signature might be ...
7
votes
0answers
73 views

Infinite palindromes in number of nonisomorphic posets is independent of $\mathsf{ZF}$

The following is an "exercise" in P. Stanley's book "Enumerative Combinatorics": Let $f(n)$ be the number of nonisomorphic $n$-element posets (...) let $\mathcal{P}$ denote the statement that ...
2
votes
1answer
115 views

I need help understanding Frege's definition of number

I have really been trying to understand Frege's definition of a number or at least gain a strong intuition of it. However, my attempts have not been fruitful. If someone could help me it would be much ...
4
votes
3answers
293 views

What is the mistake in this proof?

During a long night without sleep I managed to come up with a proof for a statement I know is false, and for the life of me I cannot figure out what I did wrong. Where is my mistake? Theorem: Let ...
1
vote
1answer
33 views

How to represent a function that says “send least element to least element and next to next” using a first order formula?

Suppose that $A$ is a finite set. $<_1$ and $<_2$ are two well-orderings on $A$. Suppose that I want to find a formula that repesents the function $F$ that says " send least element in ordering ...
0
votes
1answer
13 views

pinpoint the position of devices

My question is I know the distances d1, d2 and d3, thats the only information I have access to, but am build a android app where I need to indicate the positions of where the devices that are ...
2
votes
1answer
25 views

How to correctly draw logic formation trees?

I had an exam on Logic and came across a question which asked me to draw the logic formation tree for the following: $$\exists xP(x,x) \lor Q(x) \land \neg \forall y R(x) \to x = y$$ The formula was ...
0
votes
1answer
23 views

Prove the following logical implications

Prove the following logical implications: (a) $\forall v_1 Qv_1\models Qv_1$ (b)$Qv_1\models \forall v_1 Qv_1$ The two questions are extracted from the book 'A Mathematical Introduction to Logic' ...
1
vote
1answer
33 views

Intuition of the function defined in first order logic

According to first-order logic, $\models_{\mu} \forall x \phi [s]$ if and only if for every $d \in |\mu|$, we have $\models_{\mu} \phi [s(x|d)]$, where $$ s(x|d) = \left\{ \begin{array}{lr} ...
1
vote
2answers
36 views

analytical ability and logical reasoning

There are $6561$ balls out of which $1$ is heavy. Find the minimum number of times the balls have to be weighed for finding out the heavy ball. How can I solve this step by step?
2
votes
1answer
76 views

The definition of the $false$ truth value

In "Topoi: The Categorial Analysis of Logic" by R. Goldblatt the $false: 1 \to \Omega$ truth value is defined as the characteristic arrow of the arrow $0_1: 0 \to 1$. This definition requires that ...
0
votes
2answers
27 views

Truth Value for Quantifier

What would be the truth value for the following two quantifiers if n and m are both integers? I have trouble proving each of these statements. I appreciate any help you can provide! a)   ...
0
votes
1answer
18 views

Predicate Logic - Translations

I'm having a hard time translating logic statements into english because most of the time I don't know how to translate a pattern I have not seen before: There are two relations where $lecturer(x)$ ...
0
votes
1answer
27 views

Let $M,N$ be structures with relation $E$. $E^N$ and $E^M$ are equivalence relations, find sufficient and necessary condition for isomorphism

Let there be signature $S=\{E\}, n_E=2$, and let $M,N$ be S-structures. $E^N$ and $E^M$ are equivalence relations, find a sufficient and necessary condition for $M$ and $N$ being isomorphic. I ...
0
votes
1answer
58 views

Existence only as a result of its presupposition?

Is there an analogy in logic to the paradox that a concept comes into existence only by presupposing it as already existing?
1
vote
3answers
66 views

Are there infinite sequences not reproducible by finite algorithms?

Let me know if this is a repeat question. I was thinking that sequence of integers we deal with (e.g., the digits of $\pi$, the prime numbers, the Fibonacci numbers, pseudorandom numbers) seem to be ...
0
votes
0answers
104 views

Does removing the (1) in $\Phi{(1)}$ affect the proof that $ K_0 \leq_m K$ or not?

The fragment below from Martin Davis' book shows $ K_0 \leq_m K$ and also proves $ K_0 \leq_1 K $. My question is if we remove the $(1)$ of $ \Phi^{(1)}$ in the definition of $Y$ (i.e fifth line in ...
2
votes
0answers
21 views

Structure for first order language

Suppose our first order language has two binary function symbols $f,g$ and a constant symbol $c$. Let the structure $\mu$ be defined as $|\mu|=\{ 0,1,2,3 \}$, $f^{\mu}$ is addition modulo $4$, ...
3
votes
2answers
82 views

Predicate calculus (formal deduction vs resolution) [closed]

I am part of the logic club at my school and the question of the week was; Use formal deduction for predicate calculus to show that the following argument is valid. State each rule you use. Premise ...
0
votes
1answer
43 views

Predicate Calculus - Resolution

A question came up at the our schools logic club this week which involves using resolution to prove an argument in predicate calculus. I am slightly aware of how to find prenex normal forms but to ...
2
votes
2answers
99 views

How to find the minimum expression(s) of a set of fixed-width bit fields?

If we define $x_1 x_2 \cdots x_n$ as a bit field of width $n$, and each element $x_i$ may be $0$, $1$, or wildcard $*$. A set of 4-width bit fields $\{0000, 0001, 0100, 0101\}$ can be aggregated ...