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)

5
votes
5answers
195 views

Is there a simple example of how the law of the excluded middle can be inapplicable?

Why does a logic system not use the law of the excluded middle? I studied non-classical logic (intuitionistic and modal) where double negation can't be removed and the law of excluded middle can't be ...
0
votes
1answer
287 views

Convert expression to NAND only

Endless youtube videos and reading through notes later I am yet again stuck. I have to covert the following to NAND only $$\bar{A}\cdot\bar{B}\cdot\bar{C} + A\cdot\bar{B}\cdot C + A\cdot B\cdot ...
2
votes
2answers
36 views

How to efficiently determine if any two propositional formulas are equivalent

Given any two arbitrary propositional formulas (but only using $\land, \lor, \lnot$), like $\lnot(A \land (B \lor \lnot B) \land C)$ and $\lnot C \lor \lnot A$, how can I (or a computer) efficiently ...
0
votes
2answers
40 views

Expressing boolean operators using logical operators

From my limited understanding of logical operators, it is possible to express the more complex logical operators such as $\operatorname{xnor}$ and $\operatorname{iff}$ as a combination of just a few ...
12
votes
5answers
631 views

Purpose of the Peano Axioms

Wikipedia says the Peano Axioms are a set of axioms for the natural numbers. Is the purpose of the axioms to create a base on which we can build the rest of mathematicas formally? If this is true ...
0
votes
2answers
34 views

To prove $A\rightarrow B, C\rightarrow D \vdash (A\vee C)\rightarrow (B\vee D)$ with natural deduction [closed]

How to prove this statement? $ A\rightarrow B, C\rightarrow D \vdash (A\vee C)\rightarrow (B\vee D)?$ in inference rule? tnx!
2
votes
1answer
56 views

How can a proof by formula induction in a formal language be formalized?

From a set of not-so-rigorous lecture notes on Metalogic: Formulas of $L$: (i) Each sentence letter is a formula. (ii) If $A$ is a formula, then so is $\neg A$. (iii) If $A$ and $B$ ...
0
votes
1answer
31 views

Natural Deduction for sets

I'm a student of logic and I have a question, want to prove The Following sets by natual deduction, but do not know how to proceed. $$\begin{align} a) A \cap (B \cup C) ≡ (A \cap B) \cup (A \cap C) ...
1
vote
3answers
22 views

Discrete Structures : predicate logic (negations)

Could someone please explain why the negation makes "nobody" into "someone" and not "everyone" Which of the following is the correct negation for “Nobody is perfect.” 1. Everyone is imperfect. ...
6
votes
5answers
194 views

Is a proposition about something which doesn't exist true or false?

Let S = {x | x is not an element of x } The set S doesn't exist. Then, would a proposition such as "The cardinality of S is 1," be true or false? Equivalently, I could have made a proposition, "the ...
0
votes
2answers
25 views

Trouble understanding surjective function proof

I'm studying for my discrete math exam and I'm having some trouble understanding this practice problem and solution. I know what surjective functions are, but I can't really understand the way this ...
1
vote
2answers
48 views

$\vdash[(\forall x)P(x)]\rightarrow[(\exists x)P(x)]$

$$\vdash[(\forall x)P(x)]\rightarrow[(\exists x)P(x)]$$ answer:$$\neg P(x)\to\neg P(x)$$$$by QR$$ $$ \neg P(x)\to(\forall x)\neg P(x)$$$$by QR$$ $$(\exists x) \neg P(x)\to(\forall x)\neg P(x)$$ ...
3
votes
0answers
59 views

Consequence in $\mathcal{L}_{\infty\lambda}$

Consider the infinitary first-order language $\mathcal{L}_{\infty\lambda^+}$ whose non-logical vocabulary consists of $\lambda \geq \omega$ individual constants and countably many predicate constants ...
6
votes
2answers
52 views

Ultraproducts and Elementary Embeddings

Let $K= \{A_i: i\in \omega\}$ be a countable collection of $L-$structures. Suppose that for each $A_i, A_j$ in $K$, $\exists A_p \in K$ such that $i,j< p$ and $A_i \prec A_p $ and $A_j \prec ...
0
votes
1answer
18 views

How to negate $(a=1 \text{ and } b=n) \text{ or } (a=n \text{ and } b=1)$ to get $1<a<n \text { and } 1<b<n$?

n>1 is composite if and only if it can be written as a product $n=ab$ of integers $a$ and $b$ such that $1<a<n$ and $1<b<n$. If a prime number $n$ is the product of two positive ...
3
votes
1answer
75 views

If $P$ a probability of a sentence to be true, then $\{P(\phi | T_i)\}_{i \in \mathbb{N}}$ is a martingale over constructed theories $T_i$

I am reading Section 2.1 of Definability of Truth in Probabilistic Logic. For a language $L$, fix a probability distribution $P:L \to [0,1]$. Enumerate sentences $\phi_1, \phi_2, \ldots$ of a ...
2
votes
1answer
76 views

proving $ (A \rightarrow B \vee C )\rightarrow((A\rightarrow B) \vee (A\rightarrow C))$

I'm looking for a way to prow $ (A \rightarrow B \vee C )\rightarrow((A\rightarrow B) \vee (A\rightarrow C))$ from the following axioms and rules $$\vdash A \rightarrow A$$ $$\vdash A \wedge B ...
7
votes
0answers
46 views

References on filter quantifiers

This post is primarily a reference request. In combinatorics and other areas, we use filter quantifiers to simplify the statements of various definitions, theorems and proofs. The general idea is ...
0
votes
0answers
23 views

show that $K_{1}$is not computable?

show that $K_{1}=\{x|W_{x}\ne \emptyset\}$is not computable? answer: i let $K_{1}$is computable. so $K_{1}$is computable enumerable. then $K_{1}$ is $\sum_{1}^0 $ and $z\in K_{1}\iff z\in ...
0
votes
1answer
28 views

Theorems of GL in modal logic

So I've been reading George Boolos' "The Logic of Provability" and he's explaining different systems of modal logic. He's taken as his basic symbols → (implication), □ (necessity), ⊥ (falsehood), a ...
41
votes
9answers
3k views

Does mathematics require axioms?

I just read this whole article: http://web.maths.unsw.edu.au/~norman/papers/SetTheory.pdf which is also discussed over here: Infinite sets don't exist!? However, the paragraph which I found most ...
1
vote
1answer
34 views

Proving a bi-conditional predicate calculus formulae

Prove the following: ∀x(C → D(x)) ↔ (C →∀xD(x)) I am looking at the axioms I can use under hilberts deductive system as well as the Generalization rule but I ...
1
vote
1answer
55 views

Propositional calculus logic question

In my assignment I have the following question: For every proposition $\theta$ let $E(\theta)$ be the set of basic propositions. Prove the following: For every two propositions, $\alpha$ and ...
1
vote
1answer
29 views

How would one prove that satisfaction of closed formulas is valuation-independent? (In FOL)

Consider this proposition in first-order logic: For any interpretation $I$, any closed formula $\phi$ and any two valuations $\rho$, $\sigma$. $I\rho \models \phi \iff I\sigma \models \phi$ This is ...
0
votes
0answers
14 views

Proving that a predicate calc wff with a bi conditional [duplicate]

Prove: ∀x(C → D(x)) ↔ (C →∀xD(x)) resources: axiom 1:∀XA →Axt axiom 2:∀X(A→B) → (∀XA→∀XB) axiom 3:A→∀XA; Hilbert Generalization rule my attempt: ...
1
vote
1answer
20 views

Recurrence Relations: Understanding Homogeneous Reccurences

In an effort to better educate myself on the practices of Discrete Math. I have been attempting several practice problem sets. While most of the concepts up to this point have made sense, I find ...
0
votes
2answers
969 views

Duality discrete math problem

This is the only answer I got wrong on my HW and the prof does not want to give us the correct answers before our midterm The dual of a compound proposition that contains only the logical operators ...
0
votes
1answer
97 views

Trouble with by-contradiction proof

I'm studying for an exam and I'm having trouble with one of these problems. ...
2
votes
1answer
138 views

Knight Knave puzzle with three boxes

Could you please help me with the following puzzle: Consider the following puzzle: Suppose there are two box makers: Knight and Knave. Knight always writes true statements on his box, ...
1
vote
0answers
39 views

Knights and Knaves island [duplicate]

You appear on the Island of Knights and Knaves. Knights always tell truth, knaves always lie. You meat three inhabitants, Carl, Peggy and Zippy, and hear the following conversation: Carl says, "I ...
-2
votes
1answer
52 views

Model Theory - Equivalence of formulas using automorphisms

Let $\mathbf Q$ denote the additive group of rational numbers, i.e. the structure $\mathbf Q = (\mathbb Q;+,0)$. Let $L$ be the language of $\mathbf Q$ and let $T$ be the complete theory of $\mathbf ...
2
votes
1answer
35 views

Countable transitive model of ZFC and $\mathcal{P}(\omega)$

Let $\mathbb{M}$ be a countable transitive model of ZFC. I understand that $\omega^\mathbb{M} = \omega$ but $\mathcal{P}(\omega)^\mathbb{M} \neq \mathcal{P}(\omega)$, for ...
1
vote
1answer
20 views

I'm trying to find the latex symbol for a logical notation… Analogy: the symbol is to “logical and” as $\Sigma$ is to summation [closed]

I'm trying to find the latex symbol for a logical notation... Analogy: the symbol is to "logical and" as $\Sigma$ is to summation. For example if I want to "logical and" over sentences with varying ...
0
votes
0answers
28 views

proving $(A \rightarrow B \vee C) \rightarrow ((A\rightarrow B) \vee (A\rightarrow C))$in hilbert system(HP) [duplicate]

I'm looking for $(A \rightarrow B \vee C) \rightarrow ((A\rightarrow B) \vee (A\rightarrow C))$ in Hilbert system
0
votes
2answers
38 views

Are these negation steps correct?

$\neg(\exists p \exists q \forall x (m(p,x) \to m(q,x)))$ = $\neg(\exists p \exists q \forall x (\neg m(p,x) \lor m(q,x)))$ = $\forall p \neg \exists q \forall x (\neg m(p,x) \lor m(q,x))$ = ...
0
votes
1answer
28 views

Showing logical equivalence of these two formulas

I have the following statement in propositional logic: (¬g v s1 v ¬s2) ^ (¬g v ¬s1 v s2) ^ (¬g v s1 v s2) (1) I want to show equivalence to this statement: ...
1
vote
1answer
19 views

translating a sentence into predicate calculus

I am supposed to translate the following sentence into predicate calculus: No Student likes the classroom. S(x) : x is a student C(x) : x likes the classroom I ...
2
votes
1answer
29 views

translating phrases into propositional logic

translate the following into propositional logic: students attend the annual meetings where s: students A: attend annual meetings my first intuition is: s -> ...
3
votes
2answers
140 views

Unexpressibility of a property in first order logic

We can give a very general notion of what is to iterate a function. Given a set $\mathcal U$ and a function $f:\mathcal U \rightarrow \mathcal U$, then, to iterate the function $f$ will mean to ...
0
votes
2answers
39 views

Do antecedents have to be true for the entire universal quantifier or just 1 case?

Sample: $$∀x ∈ R+,∃y ∈ R+, x < y ⇒ x > y$$ Say I tried y = 5. Do I need to check if the consequent is true for just the x values less than 5? Secondly, ...
0
votes
1answer
64 views

Translate an english sentence to first order logic

Here's an English statement - Politicians can't fool all of the people all of the time. (𝈗x for all things, P(x) x is a person, Q(x) x is a politician, T(x) x is a time and F(x, y, z) x can ...
0
votes
1answer
52 views

Use Resolution to proove a sentence in First Order Logic

I was just wondering if anyone could tell me if I've solved this problem right. If wrong, I would like to know what I did wrong. "Use resolution to prove Green(Linn) given the information below. You ...
0
votes
2answers
44 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 ...
7
votes
1answer
173 views

Are there non-equivalent cardinal arithmetics?

‎Generalizing a concept in mathematics is always a problematic situation. In most cases there are several ways to generalize a notion and it is not easy to decide if a particular generalization is ...
0
votes
0answers
51 views

Is this an accurate description of structures and interpretations.

I read about structures and interpretations today. I've described them below this paragraph. Have I accurately described them? If not, what have I incorrectly described? A structure, $\mathscr{A}$, ...
1
vote
1answer
90 views

Example of relation that is neither transitive nor intransitive?

I have been struggling to think of an example of a relation that is neither transitive nor intransitive, does anyone have any tips? I ended up finding one website that described this as non ...
4
votes
2answers
102 views

Formalize the sentence: “Earth is the only planet inhabited by mathematicians”

I have to formalize the sentence: "Earth is the only planet inhabited by mathematicians" Let: $P(x)$ stands for 'x is a planet' $M(x)$ stands for 'x is a mathematician' $I(x,y)$ stands for 'x ...
2
votes
4answers
3k views

How do I prove the transitivity of a set of implications?

If I have a set of implications, how can I prove the transitivity? In other words: I know the transitivity law, but I need to show on paper for an assignment whether the argument is valid or not. $$ ...
0
votes
0answers
31 views

Proof of Correctness: Recursion inside loop

I am trying to prove the correctness of the algorithm in the research paper. It is at page 17 in the pdf. ...
0
votes
0answers
28 views

Quick question about the relation between elementary classes and pseudo-elementary classes

Let $\mathcal{L}$ be a logic and $\mathscr{K}$ a class of structures in the vocabulary of $\mathcal{L}$. We say that $\mathscr{K}$ is a (basic) elementary class iff there is $\phi \in \mathcal{L}$ ...