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)

2
votes
2answers
138 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 ...
1
vote
2answers
82 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 ...
2
votes
1answer
320 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$ ...
1
vote
3answers
290 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. ...
0
votes
2answers
37 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 ...
3
votes
0answers
74 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 ...
1
vote
2answers
65 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)$$ ...
2
votes
1answer
56 views

Are there non-trival logics that exibit soundness and completeness that are not first order?

In our logic class, we just we just completed the proofs of soundness and completeness. To me, these proofs hinge on models being filtered through first order logic. For instance, I could set up a ...
1
vote
1answer
99 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 ...
1
vote
1answer
53 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 ...
1
vote
1answer
44 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 ...
6
votes
5answers
381 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
1answer
20 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 ...
1
vote
1answer
44 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
1answer
146 views

Proof by-contradiction that $(A \subseteq B) \implies (A \setminus B = \{ \})$

I'm studying for an exam and I'm having trouble with one of these problems. Use proof-by-contradiction to prove the predicate $$(A \subseteq B) \implies (A \setminus B = \{ \})$$ where A and B ...
2
votes
1answer
61 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
100 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 ...
-2
votes
1answer
67 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 ...
0
votes
0answers
31 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
2
votes
1answer
102 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 ...
0
votes
1answer
32 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
43 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 ...
12
votes
0answers
197 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 ...
2
votes
1answer
43 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 -> ...
6
votes
2answers
82 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 ...
-1
votes
1answer
241 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
0answers
61 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}$, ...
0
votes
2answers
42 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, ...
1
vote
0answers
60 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. ...
4
votes
2answers
181 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 ...
0
votes
0answers
62 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}$ ...
3
votes
2answers
212 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
4answers
58 views

Can $(A \lor B) \land (\lnot A \land \lnot C)$ be more simplified?

Can $(A \lor B) \land (\lnot A \land \lnot C)$ be more simplified/expanded? With a kind of distributive property?
3
votes
1answer
79 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 ...
0
votes
1answer
132 views

Big-Omega proof using L'Hopital's Rule?

Prove or disprove: $15n^2$ is in $\Omega(3 \times 2^n)$ So we'd have to prove or disprove this statement: $$ \exists c \in\mathbb{R}^+,\,\exists B\in\mathbb{N}, \forall n \in\mathbb{N}, n ≥ B ...
0
votes
0answers
156 views

Symbol for “Take Highest Number”

As the title states, is there a symbol for taking the highest value? Let's say we have two variables $a=2$ and $b=3$ now I want $aXb$ (where $X$ is the symbol I am looking for) and I want that answer ...
2
votes
2answers
154 views

A question on empty set and Russell's paradox

Suppose $S$ is a well-defined set and $A$ is meant to be a subset of $S$ that is defined as follows: $A = \{x|(x\in S)\wedge(x\not\in S)\}$. Is $A$ the empty set $\varnothing$, since it is based on ...
0
votes
1answer
207 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
4answers
69 views

proof for a problem in propositional logic

I cant find a proof for given problem: $$p \to ( q \to p) ≡ \lnot p \to ( p \to q ) $$ Please give proof to prove above statement.
9
votes
2answers
382 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
1answer
54 views

Did I do this big-Omega proof correctly?

Prove or disprove: 6n^3 – 4n^2 + 3n +2 is in Ω (5n^3 – n^2 + n +1). So I'm not sure if I did this right or not, any pointers or the correct steps would be helpful Ǝc ∈ ℝ+, ƎB ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ ...
2
votes
2answers
59 views

How would you prove in FOL that x is a member of {x} for all x?

How can I formulate and prove the following in first-order logic? $$\forall x (x\in \{x\})$$ I have the following two statements: member(x,$\alpha$) $\neg \exists y(\text{member}(y,\alpha )\land ...
5
votes
2answers
163 views

Formula for perfect squares spectrum.

I have been working on exercises from "A first Course in Logic" by S. Hedman. Exercise 2.3 (d) asks to find a first-order sentence $\varphi$ having the set of perfect squares as a finite spectrum. But ...
3
votes
2answers
63 views

origin of syntax for mathematical equations

Bear with me, I don't have any formal training in mathematics. I wonder if there is something that accounts for the syntax of mathematical equations, some deeper logic or reasons why I know that ...
1
vote
1answer
88 views

Proof of $p\rightarrow (\Box (\Box p \wedge p) \rightarrow (\Box p \wedge p))$

I need to prove: $$p\rightarrow (\Box (\Box p \wedge p) \rightarrow (\Box p \wedge p))$$ The system contains all propostional tautologies and the axiom scheme $\mathbf K$:$ \Box(p \rightarrow q) ...
0
votes
1answer
281 views

King Arthur and knights at the round table puzzle

Can you help me with this math problem : Each of the $K$ knights from the round table needs to choose a card which is marked with a number from $1$ to $N$, $N \ge K$. The cards all have a different ...
0
votes
1answer
338 views

Use mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes.

Use strong mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes. I know the steps of weak mathematical induction... Basis step: $p(n)$ for $n=1$ or any ...
1
vote
1answer
76 views

Given an open statement determine if their quantification is true

The Question My Work/Question My book says for part a, iv is true. I disagree. To show an existential statement is false we have to show that for all x that statement is untrue. There are no ...
1
vote
2answers
103 views

Consider $(\mathbb N, +)$ as a model for the language with one binary function $+$ . Are the following statements true?

Consider $(\mathbb N, +)$ as a model for the language with one symbol $+$ for a binary function. Are the following statements true? $(\mathbb N, +) \vDash \forall x \exists y \forall z\ x + y\neq z$ ...
0
votes
1answer
45 views

A predicate logic question about write down a sentence

Let $\mathcal{L}=\{f\}$ be a first-order language containing a unary function symbol f, and no other non-logical symbols. Write down sentences $φ$ and $ψ$ of $\mathcal{L}$ such that for any ...