2
votes
0answers
26 views

Need some help with this Cardinality/sets question.

I've got this problem about sets, and cardinality. I don't really understand it other than cardinality is the number of elements within each set, I don't understand a lot of the signs used within the ...
1
vote
1answer
63 views

Countable Set & Formal Grammar

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary ...
1
vote
2answers
57 views

About well formed formula

Axiom of specification is schema because it talks about definite condition(or wff) which use notion of finite but this again we define from sets. But in logic we defined wff using consept of tuple and ...
1
vote
1answer
61 views

Thinking logically instead of Venn diagrams

I hit upon the following identity while reading the book How to Prove: $$(A \cup B) \backslash B \subseteq A$$ Now if I solve this logically I can reduce this like this: $$ \begin{gather*} x \in (A ...
5
votes
4answers
300 views

Can functions be defined by relations?

So let us say that for whatever reasons, we are not allowed to use function symbols in first-order logic. Then can we define and use a function only by relations?
1
vote
1answer
64 views

set theory, Incompleteness and axiomatic systems

Is the number of theorems that can be proved (decidable) within a certain set of axioms (for instance ZFC) is finite or infinite ? in other words, are we going to fully exhaust that set of axioms ...
1
vote
1answer
99 views

question about Herbert B. Enderton's book : A mathematical introduction to logic

I hope someone can help me. My question arises on page 114 of the second edition of the book. Here the notion of 'prime formula' is introduced to enable one to view a formula as a formula of ...
1
vote
0answers
47 views

Two definitions of functions

In literature on logic and set theory, there seem to be two different definitions of functions, one more general than the other. First of all, a function $f\colon X\to Y$ consists of three element ...
2
votes
7answers
445 views

Are the real numbers really uncountable?

Consider the following statement Every real number must have a definition in order to be discussed. What this statement doesn't specify is how that loose-specific that definition is. Some examples ...
2
votes
4answers
535 views

What is the truth table for demorgan's law?

From Demorgan's law: $(A \cup B)^c = A^c \cap B^c$ I constructed the truth table as follows: $$\begin{array}{cccccc|cc} x\in A & x \in B & x \notin A & x \notin B & x \in A^c ...
0
votes
2answers
31 views

Showing that $A \cap X = A$ for all $A$ if and only if $X = S$.

I have the following task: Let $S$ be a nonempty set. All capital letters will denote subsets of $S$. Show that $A \cap X = A$ for all $A$ if and only if $X = S$. This does not seem to true. ...
2
votes
1answer
59 views

How to prove that $max(\aleph_{0}, card(X)) = max(\aleph_{0}, card(L(X)))$?

I struggle with the following problem. Let $X$ be a set of elementary sentences and $L(X)$ be the smallest elementary language in which we can express all the sentences from $X$. How to prove that ...
1
vote
1answer
48 views

Cantor's diagonal argument: the coherence of the sequence constructed to prove that 2[N] has a higher cardinality than N

I think I have a good understanding of how Cantor's argument for showing larger cardinalities works; but I do have a continuing problem with one part of it, namely the construction of the element ...
0
votes
1answer
41 views

Does intuitionist logic deny diagonal argument?

Let us for example give an example of diagonal proof of uncountability of the set of real numbers $\mathbb{R}$. Would intuitionists accept this, or deny this? If they deny this argument, why would ...
0
votes
1answer
70 views

Extensional versus intensional theories in mathematics

Lambda calculus is often cited as an intensional theory whereas set theory is cited as an extensional theory. What are other examples of extensional and intensional theories of mathematical logic?
3
votes
1answer
84 views

Semantics and Logical structure in Definitons

Continuation of Free and bound variables in "if" statements definitions: A number is even if it is divisible by $2$. The number is even if it is divisible by $2$. Is the usage of the ...
1
vote
1answer
46 views

Logical structure of definitions

Here are some "concepts" that are confusing me: The assertion $x>2$ is true when we replace $x$ by a number greater than $2$($3$ for example) and false if we replace it by $1$. But the assertion ...
3
votes
1answer
45 views

Preimage simple problem

Which one is correct and which one is wrong ? $f^{-1}[Y \cap Y^{'}] \subseteq f^{-1}[Y] \cap f^{-1}[Y^{'}]$ $f^{-1}[Y] \cap f^{-1}[Y^{'}] \subseteq f^{-1}[Y \cap Y^{'}]$ Here is my solution: ...
0
votes
2answers
41 views

Beginner questions about Sets.

I have a quick question in regard to sets. I am a little confused when I see the notation $A\subseteq B$. How is this different than the sets $A$ and $B$ being identical? I guess some of the confusion ...
1
vote
1answer
50 views

Simple fact about class of sets.

I have a simple question which is very trivial for the other people, I guess. However, I never fully understand the argument completely. Take any $X\neq\emptyset$ and let $\mathbf{S}$ be an arbitrary ...
3
votes
3answers
70 views

Truth set of a Universal Quantifier and Family of sets

The definition of an intersection of family($F$) is: $$\cap F=\bigl\{x\mid\forall A(A\in F \implies x\in A)\bigr\} $$ If my understanding serves me correctly this notation means that all the $x$ ...
3
votes
1answer
73 views

Definition of intersection of a family of sets

The definition of an intersection of family($F$) is: $$\cap F=\bigl\{x\mid\forall A: (A\in F \implies x\in A)\bigr\} $$ If my understanding serves me correctly this notation means that all the $x$ ...
1
vote
0answers
96 views

The set of all philosophers is a camel

In Wilder's book "Introduction to the Foundations of Mathematics," a "proof" for the statement: "The set of all philosophers is a camel" is mentioned in passing as something done by Grelling under the ...
1
vote
2answers
54 views

Formalizing the Fallacy of Composition

Is there a well-known formalization of the fallacy of composition? More generally, where in mathematics is it true that if a property holds for all of some elements of a set it holds for the whole ...
1
vote
0answers
27 views

How to show that $\bigcup_{i\in \emptyset} A_i=\emptyset$ and $\bigcap_{i\in \emptyset}A_i=X$? [duplicate]

It was probably asked multiple times before which is about basic logic. But I couldnt find any. let X a set and I is index set. for $i\in I$, $A_i$ is a subset of X. if $I=\emptyset$, how can we show ...
2
votes
1answer
78 views

A proof in naive set theory.

I am trying to use naive set theory to figure out a proof of the following statement: $$(x = u \land y = v) \to 〈x, y〉 = 〈u, v〉$$. What propositions should i use to prove this?
1
vote
1answer
54 views

A* finite or infinite? (Set theory)

I have a question regarding the following: If A is a set, then by A* we mean the set of all finite rows of elements of A. Now suppose A is finite. How big is A*, and how can you see that? I ...
1
vote
3answers
73 views

Prove that $A\subseteq B\Longleftrightarrow A\cap B = A$

In set theory logic mathematics. How would i do the proof for: $A\subseteq B\Longleftrightarrow A\cap B = A$
0
votes
2answers
44 views

prove that $f(A) \backslash f(B) \subseteq f(A\backslash B)$

Let $A,B$ be two subsets of a set $X$,and let $f:X \to Y$ be a function.Prove that $f(A) \backslash f(B) \subseteq f(A\backslash B)$ So I first show what these sets are. The set $f(A) \backslash ...
2
votes
2answers
68 views

Axiom of unrestricted comprehension

I'm doing some research on naive set theory and was a little confused over the statement of the axiom of unrestricted comprehension, $\exists$B$\forall$x(x$\in$B$\iff$$\phi$(x)). I am curious as to ...
2
votes
3answers
106 views

Formal logic and functions (I am struggling with writing my proof)

I wish to show that $f\left(\bigcup_aX_a\right)=\bigcup_af(X_a)$ My attempt: $$y\in f\left(\bigcup_aX_a\right)\implies\exists x\in\bigcup_aX_a:y\in f(\{x\})$$ which I didn't like, so I re-wrote it ...
1
vote
2answers
87 views

Need help with a fundamental theorem of finite arithmetic

An amateur mathematician, I am working with a finite set $N$, elements $0, m\in N$ and partial function $S$ on $N$ such that the following Peano-like relations hold. ($0$ is the first element of $N$. ...
0
votes
1answer
48 views

Formal statement of the well-ordering theorem

Out of interest, how would you write the well-ordering theorem in pure set-theoretic language?
0
votes
2answers
89 views

Suppose $A, B$, and C are sets. Prove that $C\subset A\Delta B \Leftrightarrow C \subset A \cup B$ and $A \cap B \cap C = \emptyset $

The problem statement is in the title. I'm proving a problem in class and I need to show the above containment. I've drawn some Venn diagrams to make sure the containment makes sense, and it does to ...
0
votes
1answer
31 views

Can all cardinal numbers be represented by an ordinal numbers, assuming choice?

Can all cardinal numbers be represented by ordinal numbers, assuming AC? (ZF+AC) If or if not, what would be the proof?
2
votes
1answer
106 views

Is the following set stratified (and why not) in New Foundations?

notation: $Id=\{\langle x,y\rangle : x=y\}$ (identity relation) $X[y]$ (image of an element y under a relation X) the set I am asking for is: $Z=\{\langle x,y\rangle : \neg \exists k\; y \in k ...
2
votes
5answers
116 views

Question about definition of binary relation

Wikipedia says: Set Theory begins with a fundamental binary relation between and object $o$ and a set $A$. If $o$ is a member of $A$, write $o \in A $. I thought that a binary relation is a ...
2
votes
1answer
35 views

choosing elements from the set of sequences in ZFC

In my previous question, I asked about infinite-length formula in ZFC. But I am still confused over following: Suppose you want to build a function from a set of sequences to a set that chooses $n$th ...
4
votes
2answers
185 views

Is infinite-length formula allowed in ZFC?

I am curious whether infinite-length formulas are allowed in ZFC. If it is not, then how does it express the case where infinite number of terms (in ordinary mathematics) are being handled? (Like ...
1
vote
1answer
41 views

Subtraction of elements from $\mathbb Z$

Let $M_n$ be the set of integers which are integer multiples of $n$. If $\mathbb N = {1,2,3...}$ What would $$ \mathbb Z - \bigcup_{n\in\mathbb N}M_{2n+1} $$ be? I know that $M_{2n+1}$ represents ...
0
votes
2answers
33 views

Use of “for all” in definition of reflexive and symmetric relations.

My book says that a relation R on A is reflexive, if $\ (a,a) \in R, \ for\ every \ a \in A$ symmetric, if $\ (a_1,a_2) \in R \implies (a_2,a_1) \in R,\ for\ all\ a_1,a_2 \in A$ Although I ...
0
votes
1answer
31 views

Can an element hood test be converted into an existential statement?

I'm just curious whether it makes sense to convert a statement of the form: $$ y\in \{x\in A : \phi(x) \} \;\; \text{into the form} \;\; \exists x(\,...) $$ It's just that in the book I'm reading the ...
3
votes
2answers
217 views

De Morgan's laws in logic and set theory

In logic De Morgan's law means $\lnot (A \land B) \Leftrightarrow \lnot A \lor \lnot B$ In set theory De Morgan's law means $(A \cap B)^C = A^C \cup B^C$ I'm surprised that the same idea is true in ...
0
votes
1answer
53 views

Analogue of Russell's paradox

Using ZF set theory (without the axiom of foundation), is $$ \{z: \neg(\exists u_1,...,u_n)((z \in u_1)\land (u_1 \in u_2) \land ... \land (u_n \in z))\}$$ A set for any n? This is an analogue of ...
2
votes
4answers
101 views

Convincing proofs, proofs by contradiction and countability

Disclaimer: I have a (modest) background in mathematical physics, not logic, so I know very little of the latter. Although when I understood Cantor's argument for the first time (from one of Martin ...
0
votes
1answer
73 views

Countable and Uncountable sets

Is $\mathbb{N}\cup\{a\}$, for some $a\not\in\mathbb{N}$ countable or uncountable? $\mathbf{Attempt: }$ It is true that a set is countable if there exists an injective function $f : S → N$ from $S$ to ...
0
votes
3answers
64 views

How did I solve this problem?

While writing a SQL query I had to solve a problem I'd never dealt with before. It was trivial, but I cannot explain the solution without drawing lines on paper or making examples with actual numbers ...
-3
votes
1answer
263 views

What's the difference between relations, functions, and operations?

My understanding is vague: operations is a subclass of functions, functions is a subclass of relations. operations and functions can form terms but not formulas, relations can form formulas but not ...
1
vote
2answers
102 views

Sigma hierarchy of logical formulae

In some papers on mathematical logic I've found references to hierarchy like $\Sigma_1^0$-sentence and so on. What does it mean? What is $\Sigma_n^m$, what is $n$ and $m$ here?
1
vote
2answers
73 views

A quick question about a logical negation

I just want to make sure I'm negating the following logical statement correctly (for a contradiction proof): For every set $A$, there exists a well ordered set $V$ such that there exists no ...