All Questions
164
questions
0
votes
1
answer
115
views
Set theory - functions: Given that $|A|=|B|$, how to prove that $|A^C|=|B^C|$?
Given that $|A|=|B|$ (the cardinality of set $A$ is equal to the cardinality of $B$).
How can I prove that $|A^C|=|B^C|$ (the cardinality of the set of all functions from $C \longrightarrow A$ is ...
- 393
-1
votes
1
answer
75
views
Infinite recursion of function defined with respect to "every $n$" [closed]
I have very little formal mathematical training, so I apologize in advance for what may seem like basic issues in this question's phrasing.
I am trying to determine whether I can make a certain ...
- 101
1
vote
2
answers
164
views
How to describe a function that depends on the cardinality of a vector with mathematical notation
I have to describe a code I have written using formal mathematical notation, but I don't know how to define an operation that depends on the number of elements.
Here's an example pseudocode:
...
-1
votes
1
answer
61
views
Given |A\B| = |B\A|, prove |A|=|B| and provide 2 sets (A and B) such that |A| = |B| but |A\B| is not the same as |B\A|
Part A : Given |A\B| = |B\A|, prove |A|=|B|
Part B : Provide 2 sets (A and B) such that |A| = |B| but |A\B| is not the same as |B\A|
Part A:
Let A,B be sets. Given that |A\B| = |B\A| then |A|=|B|
Hint ...
- 147
1
vote
1
answer
94
views
Proving countability and uncountability
I am given two sets:
$$A= \{ (x,y)\in \mathbb{Q}^2 \mid x-y \in \mathbb{Z} \}$$
$$B= \{ (x,y)\in \mathbb{R}^2 \mid x-y \in \mathbb{Q} \}$$
I am told that $A$ is countable and $B$ is not. For a set ...
user1197800
2
votes
4
answers
122
views
Cardinality of the set of all bit strings not containing the bit "0" (i.e. $11$, $111$ ...)
I need to show the cardinality of $S$, the set of all bit strings that don't contain the bit $0$.
I came up with a function that maps $\mathbb{N}$ to $S$ in the following way:
$f(n) = \sum_{i=0}^{n-1} ...
- 623
0
votes
1
answer
57
views
Showing that the set of all finite binary strings is countable via Cantor-Bernstein-Schroder
Suppose that $A$ is the set of all finite binary strings. We need to show an injection $A \rightarrow \mathbb{N}$ and $\mathbb{N} \rightarrow A$.
$\mathbb{N} \rightarrow A$
Each number in the ...
- 187
0
votes
0
answers
104
views
Proof that the set of all functions $f : \mathbb{Z}^{+} \rightarrow \{ 0,1,2,3,4,5,6,7,8,9 \}$ is uncountable
Let
$ A= \{ f \vert f: \mathbb{Z}^{+} \rightarrow \{ 0,1,2,3,4,5,6,7,8,9 \} \}$.
Now, if we want to prove that it is uncountable, we can prove that there doesn't exist a bijection between $\mathbb{N}$ ...
- 187
0
votes
0
answers
49
views
Geometrically finding a function that proves $\vert(0, \infty)\vert = \vert{(0,1)}\vert$
I came across an exercise online that showed the following proof. The exercise stated that for this to be true, we have to find a bijection $(0, \infty) \rightarrow {(0,1)}$
Consider the interval (0, ...
- 893
1
vote
0
answers
71
views
Hilbert's Hotel - why do we sort the rooms?
Suppose we have one variation of Hilbert's hotel problem:
Suppose we have infinitely many hotels, each with infinitely many rooms, and we want to close all other hotels except one, and we need to ...
- 187
4
votes
2
answers
224
views
What is the cardinality of the set of injective functions from $\mathbb{N}$ to $\mathcal P \mathbb{N}$?
Question
What is the cardinality of the set of injective functions from $\mathbb{N}$ to $\mathcal P \mathbb{N}$?
Attempt
If we denote the desired set as $I$, then we can find an upper bound by ...
- 4,331
4
votes
1
answer
203
views
Construct a bijection given two injections
I know that if there exists an injection $f: A \to B$, then $|A| \leq |B|$. Then trivially, $f: A \to B$ and $g: B \to A$ both being injections imply that $|A| = |B|$. However, the definition of $|A| =...
- 985
1
vote
0
answers
47
views
Uncountability of the set of functions from the set of natural numbers to itself
I'm new to this website so forgive me for any formatting mistakes or other errors you encounter. I would appreciate it if you pointed them out. For anyone interested, the problem is from Algebra by ...
- 11
1
vote
1
answer
194
views
Is there a function $f: \mathbb{Q} \rightarrow \mathbb{N}$ that is surjective but not injective?
I would like to know whether or not there exists a function
$$f: \mathbb{Q} \rightarrow \mathbb{N}$$
that is surjective but not injective?
I am rather new to the principle of cardinality. I know that $...
- 189
1
vote
2
answers
968
views
Are most real functions non-linear?
I made an observation that for two finite sets $A$, $B$ that most $R \subseteq A \times B$ where $R$ is a function also 'appear to be' non-linear. It got me wondering if this is true in the highly ...
- 1,876